Main Content

Algoritmos de programación lineal de enteros mixtos (MILP)

Definición de programación lineal de enteros mixtos

Un programa lineal de enteros mixtos (MILP) es un problema con:

  • Una función objetivo lineal, fTx, donde f es un vector columna de constantes y x es el vector columna de

  • límites y restricciones lineales, pero no restricciones no lineales (para ver las definiciones, consulte Escribir restricciones)

  • Restricciones en algunos componentes de x para que tengan valores enteros

en términos matemáticos, dados los vectores f, lb y ub, las matrices A y Aeq, los vectores b y beq correspondientes y un conjunto de índices intcon, encuentre un vector x para resolver

minxfTx subject to {x(intcon) are integersAxbAeqx=beqlbxub.

Algoritmo intlinprog

Visión general del algoritmo

intlinprog utiliza esta estrategia básica para resolver programas lineales de enteros mixtos. intlinprog puede resolver el problema en cualquiera de las fases. Si resuelve el problema en una fase, intlinprog no ejecuta las fases posteriores.

  1. Reduzca el tamaño del problema mediante Preprocesamiento de la programación lineal.

  2. Resuelva un problema relajado inicial (no entero) mediante Programación lineal.

  3. Realice Preprocesamiento de programas de enteros mixtos para ajustar la relajación de la LP del problema de enteros mixtos.

  4. Pruebe Generación de cortes para ajustar aún más la relajación de la LP del problema de enteros mixtos.

  5. Intente encontrar soluciones de enteros factibles mediante heurística.

  6. Utilice un algoritmo Ramificación y acotación para buscar sistemáticamente la solución óptima. Este algoritmo resuelve relajaciones de la LP con rangos restringidos de posibles valores de las variables de enteros. Intenta generar una secuencia de límites actualizados en el valor óptimo de la función objetivo.

Preprocesamiento de la programación lineal

Según la Definición de programación lineal de enteros mixtos, existen las matrices A y Aeq y los vectores b y beq correspondientes que codifican un conjunto de desigualdades lineales e igualdades lineales.

A·xbAeq·x=beq.

Estas restricciones lineales limitan la solución x.

Por lo general, es posible reducir el número de variables del problema (el número de componentes de x) y el número de restricciones lineales. Aunque el solver puede tardar en realizar estas reducciones, con ello se suele reducir el tiempo total para encontrar la solución y se pueden resolver problemas más grandes. Los algoritmos pueden hacer que la solución sea más estable numéricamente. Además, estos algoritmos pueden detectar a veces un problema no factible.

Los pasos del preprocesamiento tienen como objetivo eliminar variables y restricciones redundantes, mejorar la escala del modelo y la dispersión de la matriz de restricciones, fortalecer los límites de las variables y detectar la infactibilidad primal y dual del modelo.

Para obtener detalles, consulte Andersen and Andersen [2] y Mészáros and Suhl [8].

Programación lineal

El problema relajado inicial es el problema de programación lineal con el mismo objetivo y restricciones que Definición de programación lineal de enteros mixtos, pero sin restricciones de enteros. Llame xLP a la solución al problema relajado y x a la solución al problema con restricciones de enteros. Claramente,

fTxLPfTx,

porque xLP minimiza la misma función, pero con menos restricciones.

Esta LP relajada inicial (LP de nodo raíz) y todas las relajaciones de la LP generadas durante el algoritmo de ramificación y acotación se resuelven utilizando técnicas de solución de programación lineal.

Preprocesamiento de programas de enteros mixtos

Durante el preprocesamiento de programas de enteros mixtos, intlinprog analiza las desigualdades lineales A*x ≤ b junto con las restricciones de integralidad para determinar si:

  • El problema no es factible.

  • Algunos límites pueden reforzarse.

  • Algunas desigualdades son redundantes, por lo que se pueden ignorar o eliminar.

  • Algunas desigualdades pueden reforzarse.

  • Algunas variables de enteros pueden corregirse.

La opción IntegerPreprocess permite elegir si intlinprog realiza varios pasos, los realiza todos o no realiza casi ninguno. Si incluye un argumento x0, intlinprog utiliza este valor en el preprocesamiento.

El objetivo principal del preprocesamiento del programa de enteros mixtos es simplificar los cálculos del algoritmo de ramificación y acotación. El preprocesamiento implica preexaminar rápidamente y eliminar algunos de los posibles subproblemas innecesarios que la ramificación y acotación analizaría de otra manera.

Para obtener detalles sobre el preprocesamiento de enteros, consulte Savelsbergh [10].

Generación de cortes

Los cortes son restricciones lineales adicionales de desigualdad que intlinprog añade al problema. Estas desigualdades intentan restringir la región factible de las relajaciones de la LP para que sus soluciones estén más cerca de los enteros. Con la opción CutGeneration puede controlar el tipo de cortes que intlinprog utiliza.

Entre los cortes 'basic' encontramos los siguientes:

  • Cortes de redondeo de enteros mixtos

  • Cortes de Gomory

  • Cortes de clique

  • Cortes de cobertura

  • Cortes de cobertura de flujo

Además, si el problema es puramente de enteros (todas las variables tienen valores enteros), entonces intlinprog también utiliza los cortes siguientes:

  • Cortes fuertes de Chvatal-Gomory

  • Cortes cero-medio

Los cortes 'intermediate' incluyen todos los cortes 'basic' y:

  • Cortes de elevación y proyección simples

  • Cortes de reducción y pivoteo simples

  • Cortes de reducción y fracción

Los cortes 'advanced' incluyen todos los cortes 'intermediate' salvo los cortes de reducción y fracción, y también:

  • Cortes fuertes de Chvatal-Gomory

  • Cortes cero-medio

Para problemas puramente de enteros, 'intermediate' utiliza la mayoría de los tipos de cortes, ya que utiliza cortes de reducción y fracción, mientras que 'advanced' no lo hace.

Otra opción, CutMaxIterations, especifica un límite superior en el número de veces que intlinprog itera para generar cortes.

Para obtener más detalles sobre los algoritmos de generación de cortes (también denominados métodos de planos de corte), consulte Cornuéjols [5], y para cortes de clique, Atamtürk, Nemhauser y Savelsbergh [3].

Heurística para encontrar soluciones factibles

Para obtener un límite superior de la función objetivo, el procedimiento de ramificación y acotación debe encontrar puntos factibles. Una solución a una relajación de la LP durante la ramificación y acotación puede ser factible para enteros, lo que puede proporcionar un límite superior mejorado a la MILP original. Ciertas técnicas encuentran puntos factibles más rápido antes o durante la ramificación y la acotación. intlinprog utiliza estas técnicas en el nodo raíz y durante algunas iteraciones de ramificación y acotación. Estas técnicas son heurísticas, lo que significa que son algoritmos que pueden tener éxito, pero que también pueden fallar.

La heurística puede ser heurística de inicio, que ayuda al solver a encontrar una solución inicial o nueva de enteros factibles. O la heurística puede ser heurística de mejora, que empieza en un punto entero factible e intenta encontrar un punto entero factible mejor, es decir, uno con un valor de función objetivo más bajo. Las heurísticas de mejora intlinprog son 'rins', 'rss', 1-opt, 2-opt e inmersión guiada.

Establezca la heurística intlinprog utilizando la opción 'Heuristics'. Las opciones son:

OpciónDescripción
'basic' (valor predeterminado)

El solver ejecuta heurística de redondeo dos veces con diferentes parámetros, ejecuta heurística de inmersión dos veces con diferentes parámetros y, a continuación, ejecuta 'rss'. El solver no ejecuta heurística posterior si la heurística anterior conduce a una solución de enteros factibles suficientemente buena.

'intermediate'

El solver ejecuta heurística de redondeo dos veces con diferentes parámetros y, a continuación, ejecuta heurística de inmersión dos veces con diferentes parámetros. Si hay una solución de enteros factibles, el solver ejecuta 'rins' seguido de 'rss'. Si 'rss' encuentra una nueva solución, el solver vuelve a ejecutar 'rins'. El solver no ejecuta heurística posterior si la heurística anterior conduce a una solución de enteros factibles suficientemente buena.

'advanced'

El solver ejecuta heurística de redondeo dos veces con diferentes parámetros y, a continuación, ejecuta heurística de inmersión dos veces con diferentes parámetros. Si hay una solución de enteros factibles, el solver ejecuta 'rins' seguido de 'rss'. Si 'rss' encuentra una nueva solución, el solver vuelve a ejecutar 'rins'. El solver no ejecuta heurística posterior si la heurística anterior conduce a una solución de enteros factibles suficientemente buena.

'rins' o el equivalente 'rins-diving'

intlinprog realiza una búsqueda en el entorno del mejor punto de solución de enteros factibles actual (si está disponible) para encontrar una solución nueva y mejor. Consulte Danna, Rothberg y Le Pape [6]. Cuando selecciona 'rins', el solver ejecuta heurística de redondeo dos veces con diferentes parámetros, ejecuta heurística de inmersión dos veces con diferentes parámetros y, a continuación, ejecuta 'rins'.

'rss' o el equivalente 'rss-diving'

intlinprog aplica un procedimiento híbrido combinando ideas de 'rins' y de ramificación local para buscar soluciones de enteros factibles. Cuando selecciona 'rss', el solver ejecuta heurística de redondeo dos veces con diferentes parámetros, ejecuta heurística de inmersión dos veces con diferentes parámetros y, a continuación, ejecuta 'rss'. El solver no ejecuta heurística posterior si la heurística anterior conduce a una solución de enteros factibles suficientemente buena. Estos ajustes realizan la misma heurística que 'basic'.

'round'

intlinprog toma la solución LP del problema relajado en un nodo y redondea las componentes de los enteros para intentar mantener la factibilidad. Cuando selecciona 'round', el solver, en el nodo raíz, ejecuta heurística de redondeo dos veces con diferentes parámetros y, a continuación, ejecuta heurística de inmersión dos veces con diferentes parámetros. A partir de entonces, el solver solo ejecuta heurísticas de redondeo en algunos nodos de ramificación y acotación.

'round-diving'

El solver funciona de un modo similar a 'round', pero también ejecuta heurística de inmersión (además de heurística de redondeo) en algunos nodos del árbol de ramificación y acotación, no solo en el nodo raíz.

'diving'

intlinprog utiliza heurística similar a los pasos de ramificación y acotación, pero sigue solo una ramificación del árbol sin crear otras ramificaciones. Esta ramificación única conduce a una rápida "inmersión" (dive) en el fragmento del árbol, de ahí el nombre "diving". Actualmente, intlinprog usa seis heurísticas de inmersión en el orden siguiente:

  • Inmersión por longitud del vector

  • Inmersión de coeficientes

  • Inmersión fraccionaria

  • Inmersión de pseudocoste

  • Inmersión de búsqueda de recta

  • Inmersión guiada (se aplica cuando el solver ya ha encontrado al menos un punto entero factible)

La heurística de inmersión generalmente selecciona una variable que debería tener valor entero, para la cual la solución actual es fraccionaria. A continuación, la heurística introduce un límite que fuerza a la variable a tener un valor entero y vuelve a resolver la LP relajada asociada. El método de elegir la variable que se va a restringir es la principal diferencia entre las heurísticas de inmersión. Consulte Berthold [4], sección 3.1.

'none'

intlinprog no busca un punto factible. El solver simplemente toma cualquier punto factible que encuentre en su búsqueda de ramificación y acotación.

La principal diferencia entre 'intermediate' y 'advanced' es que 'advanced' ejecuta heurística con más frecuencia durante las iteraciones de ramificación y acotación.

Además de la tabla anterior, la heurística siguiente se ejecuta cuando la opción Heuristics es 'basic', 'intermediate' o 'advanced'.

  • ZI round: esta heurística se ejecuta siempre que un algoritmo resuelve una LP relajada. La heurística revisa todas las variables de enteros fraccionarios para intentar desplazarlas a un entero próximo sin afectar la factibilidad con respecto a otras restricciones. Para obtener más detalles, consulte Hendel [7].

  • 1-opt: esta heurística se ejecuta siempre que un algoritmo encuentre una nueva solución de enteros factibles. La heurística revisa todas las variables de enteros para intentar desplazarlas a un entero próximo sin afectar la factibilidad con respecto a otras restricciones, al mismo tiempo que se disminuye el valor de la función objetivo.

  • 2-opt: esta heurística se ejecuta siempre que un algoritmo encuentre una nueva solución de enteros factibles. 2-opt encuentra todos los pares de variables de enteros que afectan a la misma restricción, lo que significa que tienen entradas distintas de cero en la misma fila de una matriz de restricción A o Aeq. Para cada par, 2-opt toma una solución de enteros factibles y mueve los valores de los pares de variables hacia arriba o hacia abajo utilizando los cuatro movimientos posibles (arriba-arriba, arriba-abajo, abajo-arriba y abajo-abajo), buscando una solución próxima factible que tenga un valor de función objetivo mejor. El algoritmo prueba cada par de variables de enteros calculando el mayor tamaño (misma magnitud) de desplazamientos para cada variable del par que cumpla con las restricciones y también mejore el valor de la función objetivo.

Al principio de la fase de heurística, intlinprog ejecuta la heurística trivial a menos que Heuristics sea 'none' o proporcione un punto inicial de enteros factibles en el argumento x0. La heurística trivial comprueba la factibilidad de los puntos siguientes:

  • Todo ceros

  • Límite superior

  • Límite inferior (distinto de cero)

  • Punto de "bloqueo"

El punto de "bloqueo" se define solo para problemas con límites superiores e inferiores finitos en todas las variables. El punto de "bloqueo" de cada variable es su límite superior o inferior, elegido como se explica a continuación. Para cada variable j, cuente el número de entradas positivas correspondientes en la matriz de restricciones lineales A(:,j) y reste el número de entradas negativas correspondientes. Si el resultado es positivo, use el límite inferior para esa variable, lb(j). De lo contrario, use el límite superior para esa variable, ub(j). El punto de "bloqueo" intenta satisfacer la mayor cantidad de restricciones de desigualdad lineales para cada variable, pero no es necesariamente factible.

Después de que cada heurística termina con una solución factible, intlinprog llama a funciones de salida y funciones de gráfica. Consulte intlinprog Output Function and Plot Function Syntax.

Si incluye un argumento x0, intlinprog utiliza este valor en la heurística 'rins' y en la heurística de inmersión guiada hasta que encuentra un punto factible entero mejor. Así, cuando proporciona x0, puede obtener buenos resultados estableciendo la opción 'Heuristics' en 'rins-diving' u otro ajuste que utiliza 'rins'.

Ramificación y acotación

El método de ramificación y acotación genera una secuencia de subproblemas que intentan converger en una solución de la MILP. Los subproblemas proporcionan una secuencia de límites superiores e inferiores en la solución fTx. El primer límite superior es cualquier solución factible y el primer límite inferior es la solución al problema relajado. Para ver una discusión sobre el límite superior, consulte Heurística para encontrar soluciones factibles.

Tal como se explica en Programación lineal, cualquier solución al problema relajado de programación lineal tiene un valor de función objetivo menor que la solución a la MILP. Además, cualquier punto factible xfeas satisface

fTxfeasfTx,

porque fTx es el mínimo entre todos los puntos factibles.

En este contexto, un nodo es una LP con la misma función objetivo, límites y restricciones lineales que el problema original, pero sin restricciones de enteros ni cambios concretos en las restricciones lineales o límites. El nodo raíz es el problema original sin restricciones de enteros y sin cambios en las restricciones lineales ni en los límites, lo que significa que el nodo raíz es la LP relajada inicial.

A partir de los límites iniciales, el método de ramificación y acotación construye nuevos subproblemas ramificándose desde el nodo raíz. El paso de ramificación se toma de forma heurística, de acuerdo con una de varias reglas. Cada regla se basa en la idea de dividir un problema restringiendo una variable para que sea menor o igual a un entero J, o mayor o igual a J+1. Estos dos subproblemas surgen cuando una entrada en xLP, correspondiente a un entero especificado en intcon, no es un valor entero. Aquí, xLP es la solución a un problema relajado. Tome J como la parte más baja de la variable (redondeado hacia abajo) y J+1 como la parte más alta (redondeado hacia arriba). Los dos problemas resultantes tienen soluciones que son mayores que o iguales a fTxLP, porque tienen más restricciones. Por lo tanto, este procedimiento aumenta potencialmente el límite inferior.

El rendimiento del método de ramificación y acotación depende de la regla para elegir qué variable dividir (la regla de ramificación). El algoritmo usa estas reglas, que se pueden establecer en la opción BranchRule:

  • 'maxpscost': elige la variable fraccionaria con el pseudocoste máximo.

     Pseudocoste

  • 'strongpscost': similar a 'maxpscost', pero en lugar de que el pseudocoste se inicialice en 1 para cada variable, el solver intenta ramificar en una variable solo después de que el pseudocoste tenga una estimación más fiable. Para obtener una estimación más fiable, el solver lleva a cabo lo siguiente (consulte Achterberg, Koch y Martin [1]).

    • Ordena todas las posibles variables de ramificación (aquellas que actualmente son fraccionarias, pero que deberían ser enteros) por sus puntuaciones actuales basadas en pseudocostes.

    • Ejecuta los dos programas lineales relajados basados en la variable de ramificación actual, empezando desde la variable con la puntuación más alta (si la variable aún no se ha utilizado para un cálculo de ramificación). El solver utiliza estas dos soluciones para actualizar los pseudocostes para la variable de ramificación actual. El solver puede detener este proceso temprano para ahorrar tiempo en la elección de la ramificación.

    • Continúa eligiendo variables en la lista hasta que la puntuación actual más alta basada en el pseudocoste no cambie para k variables consecutivas, donde k es un valor elegido internamente, generalmente entre 5 y 10.

    • Realiza una ramificación en la variable con la puntuación más alta basada en el pseudocoste. El solver podría haber calculado previamente los programas lineales relajados basados en esta variable durante un procedimiento anterior de estimación de pseudocostes.

    Debido a las soluciones adicionales del programa lineal, cada iteración de la ramificación 'strongpscost' toma más tiempo que el valor predeterminado 'maxpscost'. Sin embargo, el número de iteraciones de ramificación y acotación generalmente disminuye, por lo que el método 'strongpscost' puede ahorrar tiempo en general.

  • 'reliability': parecido a 'strongpscost', pero en lugar de ejecutar los programas lineales relajados solo para ramificaciones de pseudocoste no inicializadas, 'reliability' ejecuta los programas hasta k2 veces para cada variable, donde k2 es un número pequeño como 4 u 8. Por lo tanto, 'reliability' tiene una ramificación aún más lenta, pero potencialmente menos iteraciones de ramificación y acotación, en comparación con el método de 'strongpscost'.

  • 'mostfractional': permite elegir la variable con la parte fraccionaria más cerca de 1/2.

  • 'maxfun': permite elegir la variable con el valor absoluto máximo correspondiente en el vector objetivo f.

Después de que el algoritmo se ramifique, quedan dos nuevos nodos por explorar. El algoritmo elige el nodo que desea explorar de entre todos los disponibles empleando una de las reglas siguientes:

  • 'minobj': permite elegir el nodo que tiene el valor de función objetivo inferior.

  • 'mininfeas': permite elegir el nodo con la suma mínima de infactibilidades de enteros. Esto significa que para cada componente de entero no factible x(i) del nodo, se suma el inferior de pi y pi+, donde

    pi = x(i) – ⌊x(i)⌋
    pi+ = 1 – pi.

  • 'simplebestproj': permite elegir el nodo con la mejor proyección.

     Mejor proyección

intlinprog omite el análisis de algunos subproblemas considerando información del problema original, como el máximo común divisor (GCD) de la función objetivo.

El procedimiento de ramificación y acotación continúa, con lo que se generan sistemáticamente subproblemas para analizar y se descartan los que no mejorarán un límite superior o inferior en el objetivo, hasta que se cumpla uno de estos criterios de parada:

  • El algoritmo supera la opción MaxTime.

  • La diferencia entre los límites inferior y superior de la función objetivo es menor que las tolerancias AbsoluteGapTolerance o RelativeGapTolerance.

  • El número de nodos explorados supera la opción MaxNodes.

  • El número de puntos factibles enteros encontrados supera la opción MaxFeasiblePoints.

Para obtener detalles sobre el procedimiento de ramificación y acotación, consulte Nemhauser y Wolsey [9] y Wolsey [11].

Referencias

[1] Achterberg, T., T. Koch and A. Martin. Branching rules revisited. Operations Research Letters 33, 2005, pp. 42–54. Available at https://opus4.kobv.de/opus4-zib/files/788/ZR-04-13.pdf.

[2] Andersen, E. D., and Andersen, K. D. Presolving in linear programming. Mathematical Programming 71, pp. 221–245, 1995.

[3] Atamtürk, A., G. L. Nemhauser, M. W. P. Savelsbergh. Conflict graphs in solving integer programming problems. European Journal of Operational Research 121, 2000, pp. 40–55.

[4] Berthold, T. Primal Heuristics for Mixed Integer Programs. Technischen Universität Berlin, September 2006. Available at https://opus4.kobv.de/opus4-zib/files/1029/Berthold_Primal_Heuristics_For_Mixed_Integer_Programs.pdf.

[5] Cornuéjols, G. Valid inequalities for mixed integer linear programs. Mathematical Programming B, Vol. 112, pp. 3–44, 2008.

[6] Danna, E., Rothberg, E., Le Pape, C. Exploring relaxation induced neighborhoods to improve MIP solutions. Mathematical Programming, Vol. 102, issue 1, pp. 71–90, 2005.

[7] Hendel, G. New Rounding and Propagation Heuristics for Mixed Integer Programming. Bachelor's thesis at Technische Universität Berlin, 2011. PDF available at https://opus4.kobv.de/opus4-zib/files/1332/bachelor_thesis_main.pdf.

[8] Mészáros C., and Suhl, U. H. Advanced preprocessing techniques for linear and quadratic programming. OR Spectrum, 25(4), pp. 575–595, 2003.

[9] Nemhauser, G. L. and Wolsey, L. A. Integer and Combinatorial Optimization. Wiley-Interscience, New York, 1999.

[10] Savelsbergh, M. W. P. Preprocessing and Probing Techniques for Mixed Integer Programming Problems. ORSA J. Computing, Vol. 6, No. 4, pp. 445–454, 1994.

[11] Wolsey, L. A. Integer Programming. Wiley-Interscience, New York, 1998.