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
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.
Reduzca el tamaño del problema mediante Preprocesamiento de la programación lineal.
Resuelva un problema relajado inicial (no entero) mediante Programación lineal.
Realice Preprocesamiento de programas de enteros mixtos para ajustar la relajación de la LP del problema de enteros mixtos.
Pruebe Generación de cortes para ajustar aún más la relajación de la LP del problema de enteros mixtos.
Intente encontrar soluciones de enteros factibles mediante heurística.
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.
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,
fTxLP ≤ fTx,
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ón | Descripció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 |
'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 |
'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' o el equivalente 'rins-diving' |
|
'rss' o el equivalente 'rss-diving' |
|
'round' |
|
'round-diving' | El solver funciona de un modo similar a |
'diving' |
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' |
|
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
oAeq
. 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
fTxfeas ≥ fTx,
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.'strongpscost'
: similar a'maxpscost'
, pero en lugar de que el pseudocoste se inicialice en1
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, dondek
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 hastak2
veces para cada variable, dondek2
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 de1/2
.'maxfun'
: permite elegir la variable con el valor absoluto máximo correspondiente en el vector objetivof
.
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+, dondepi– = x(i) – ⌊x(i)⌋
pi+ = 1 – pi–.'simplebestproj'
: permite elegir el nodo con la 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
oRelativeGapTolerance
.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.