Obtención de cortes Fenchel para problemas de programación entera mixta

Resumen

El objetivo de programación entera es la optimización de una función en presencia de retricciones con la condición añadida de que alguna o todas sus variables han de ser enteras, El algoritmo principal para la resolución de este tipo de problemas es el algoritmo de branch and bound. Con el fin de mejorar los resultados computancionales obtenidos las investigaciones se han centrado en los últimos años, en la reducción del árbol de ramificación, ya sea obteniendo buenas cotas o la descripción lineal, completa o parcial, de la envolvente convexa de las soluciones factibles, objetivo este último que persiguen las tecnicas poliédricas en programación entera. La mayor parte de las familias de desigualdades validas conocidas parten de un conocimiento teórico del poliedro subyacente. En cuanto a la obtención de buenas cotas, una de las técnicas más utilizadas en la actualidad es la relajación lagrangeana. Los planos de corte Fenchel que dan la descripción lineal del poliedro subyacente en unproblema de programación entera, resuelven el problema convexificado asociado a cualquier relajación lagrangeana integrando de esta forma, las técnicas poliédricas con la relajación lagrangeana. Hasta este momento, solo se habían estudiado las desigualdades Fenchel para algunos problemas de programación entera mixta. En primer lugar se estudian las propiedades del problema separador para la familia de desigualdades Fenchel en modelos generales de programación entera mixta. Dichas propiedades dependen tanto de la solución fraccional que se desea separar como el soporte y características especiales de la estructura subyacente. Todo ello se traduce en una reducción de la dimensión del problema separador, lo que facilita enormemente la resolución de la relajación Fenchel asociada a la estructura. A continuación se proponen para el problema de localización capacitado, una relajación lagrangeana y una relajación Fenchel equiv