Algoritmos de programación lineal de enteros mixtos

Definición de programación lineal de enteros mixtos

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

Función objetiva lineal,f^T, donde es un vector de columna de constantes, y es el vector de columna de desconocidosxfx
Límites y restricciones lineales, pero sin restricciones no lineales (para las definiciones, consulte)Escribir restricciones
Las restricciones en algunos componentes de tener valores enterosx

En términos matemáticos, dados vectores, y, matrices y, vectores correspondientes y, y un conjunto de índices, encontrar un vector para resolverflbubAAeqbbeqintconx

$\min_{x} f^{T} x subject to {\begin{array}{l} x (intcon) are integers \\ A \cdot x \leq b \\ A e q \cdot x = b e q \\ l b \leq x \leq u b . \end{array}$

Algoritmo intlinprog

Información general del algoritmo
El preprocesamiento lineal del programa
Programación lineal
El preprocesamiento de programa entero mixto
Generación de corte
Heurística para encontrar soluciones factibles
Rama y encuadernado

Información general del algoritmo

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

Reduzca el tamaño del problema utilizando.El preprocesamiento lineal del programa
Resuelva un problema inicial relajado (no entero) usando.Programación lineal
Realizar para apretar la relajación LP del problema entero mixto.El preprocesamiento de programa entero mixto
Intente ajustar aún más la relajación de LP del problema de enteros mixtos.Generación de corte
Intente encontrar soluciones de enteros factibles usando.Heurística
Utilice un algoritmo para buscar sistemáticamente la solución óptima.Rama y encuadernado Este algoritmo resuelve relajaciones LP con rangos restringidos de valores posibles de las variables enteras. Intenta generar una secuencia de límites actualizados en el valor de la función de objetivo óptimo.

El preprocesamiento lineal del programa

Según el, hay matrices y vectores correspondientes y que codifican un conjunto de desigualdades lineales y ecualidades linealesDefinición de programación lineal de enteros mixtosAAeqbbeq

$\begin{matrix} A \cdot x \leq b \\ A e q \cdot x = b e q . \end{matrix}$

Estas restricciones lineales restringen la solución.x

Por lo general, es posible reducir el número de variables en el problema (el número de componentes de), y reducir el número de restricciones lineales.x Mientras que la realización de estas reducciones puede tomar tiempo para el solucionador, por lo general reducen el tiempo total a la solución, y pueden hacer problemas más grandes solucionables. Los algoritmos pueden hacer que la solución sea más estable numéricamente. Además, estos algoritmos a veces pueden detectar un problema infactible.

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

Para más detalles, véase Andersen y Andersen y Mészáros y Suhl.[2][7]

Programación lineal

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

f^Tx_LP ≤f^T,x

porquex_LP minimiza la misma función pero con menos restricciones.

Este LP relajado inicial (nodo raíz LP) y todas las relajaciones LP generadas durante el algoritmo de bifurcación y encuadernado se resuelven utilizando técnicas de solución de programación lineal.

El preprocesamiento de programa entero mixto

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

El problema es inviable.
Algunos límites se pueden apretar.
Algunas desigualdades son redundantes, por lo que se pueden ignorar o eliminar.
Algunas desigualdades pueden fortalecerse.
Algunas variables enteras pueden ser fijas.

La opción le permite elegir si toma varios pasos, toma todos ellos, o no toma casi ninguno de ellos.IntegerPreprocessintlinprog Si incluye un argumento, utiliza ese valor en el preprocesamiento.x0intlinprog

El objetivo principal del preprocesamiento de programas enteros mixtos es simplificar los cálculos de bifurcación y encuadernado subsiguientes. El preprocesamiento implica rápidamente el preexamen y la eliminación de algunos de los candidatos a subproblemas inútiles que de otro modo analizarían.

Para obtener más información sobre el preprocesamiento de enteros, consulte Savelsbergh.[9]

Generación de corte

Los cortes son restricciones de desigualdad lineal adicionales que se suman al problema.intlinprog Estas desigualdades intentan restringir la región factible de las relajaciones LP para que sus soluciones estén más cerca de los enteros. Puede controlar el tipo de cortes que utiliza con la opción.intlinprogCutGeneration

cortes incluyen:'basic'

Los cortes de redondeo de enteros mixtos
Gomory corta
Clique corta
Los cortes de cubierta
La cubierta de flujo corta

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

Strong Chvatal-Gomory corta
Cero-medias cortes

cortes incluyen todos los cortes, más:'intermediate''basic'

Cortes simples de levantamiento y proyecto
Los cortes simples de pivote y reducción
Reduzca y divida los cortes

cortes incluyen todos los cortes excepto los cortes de reducción y división, además de:'advanced''intermediate'

Strong Chvatal-Gomory corta
Cero-medias cortes

Para los problemas puramente enteros, utiliza los tipos de corte más, ya que utiliza cortes de reducción y división, mientras que no.'intermediate''advanced'

Otra opción, especifica un límite superior en el número de veces que se recorre en iteración para generar cortes.CutMaxIterationsintlinprog

Para obtener más información sobre los algoritmos de generación de cortes (también denominados métodos de plano de corte), véase cornuéjols y, para camarilla Cuts, atamtürk, nemhauser y savelsbergh.[5][3]

Heurística para encontrar soluciones factibles

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

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

Opción	Descripción
predeterminado`'basic'`	El solucionador ejecuta la heurística de redondeo dos veces con diferentes parámetros, ejecuta la heurística de buceo dos veces con parámetros diferentes y, a continuación, se ejecuta.`'rss'` El solucionador no ejecuta la heurística posterior cuando la heurística anterior conduce a una solución lo suficientemente buena como un entero factible.
`'intermediate'`	El solucionador ejecuta la heurística de redondeo dos veces con parámetros diferentes y, a continuación, ejecuta la heurística de buceo dos veces con parámetros diferentes. Si hay una solución de entero factible, el solucionador se ejecuta seguido de.`'rins''rss'` Si encuentra una nueva solución, el solucionador se ejecutará de nuevo.`'rss''rins'` El solucionador no ejecuta la heurística posterior cuando la heurística anterior conduce a una solución lo suficientemente buena como un entero factible.
`'advanced'`	El solucionador ejecuta la heurística de redondeo dos veces con parámetros diferentes y, a continuación, ejecuta la heurística de buceo dos veces con parámetros diferentes. Si hay una solución de entero factible, el solucionador se ejecuta seguido de.`'rins''rss'` Si encuentra una nueva solución, el solucionador se ejecutará de nuevo.`'rss''rins'` El solucionador no ejecuta la heurística posterior cuando la heurística anterior conduce a una solución lo suficientemente buena como un entero factible.
o el equivalente`'rins''rins-diving'`	busca en la vecindad de la actual, mejor punto de solución de enteros factible (si está disponible) para encontrar una nueva y mejor solución.`intlinprog` Véase Danna, Rothberg y le Pape.[6] Cuando se selecciona, el solucionador ejecuta la heurística de redondeo dos veces con parámetros diferentes, ejecuta la heurística de buceo dos veces con parámetros diferentes y, a continuación, se ejecuta.`'rins''rins'`
o el equivalente`'rss''rss-diving'`	aplica un procedimiento híbrido que combina ideas y ramificaciones locales para buscar soluciones de enteros factibles.`intlinprog'rins'` Cuando se selecciona, el solucionador ejecuta la heurística de redondeo dos veces con parámetros diferentes, ejecuta la heurística de buceo dos veces con parámetros diferentes y, a continuación, se ejecuta.`'rss''rss'` El solucionador no ejecuta la heurística posterior cuando la heurística anterior conduce a una solución lo suficientemente buena como un entero factible. Estos ajustes realizan la misma heurística que.`'basic'`
`'round'`	toma la solución LP para el problema relajado en un nodo, y redondea los componentes enteros de una manera que intenta mantener la viabilidad.`intlinprog` Cuando se selecciona, el solucionador, en el nodo raíz, ejecuta la heurística de redondeo dos veces con parámetros diferentes y, a continuación, ejecuta la heurística de buceo dos veces con parámetros diferentes.`'round'` A partir de entonces, el solucionador solo ejecuta la heurística de redondeo en algunos nodos ramifican y enlazados.
`'round-diving'`	El solucionador funciona de forma similar a, pero también ejecuta la heurística de buceo (además de la heurística de redondeo) en algunos nodos de bifurcación y enlazado, no solo el nodo raíz.`'round'`
`'diving'`	utiliza la heurística que es similar a los pasos de bifurcación y enlazado, pero sigue solo una rama del árbol hacia abajo, sin crear las otras ramas.`intlinprog` Esta sola rama conduce a una rápida "inmersión" por el fragmento del árbol, por lo tanto el nombre "buceo." Actualmente, utiliza seis heurísticas de buceo en este orden:`intlinprog` El buceo de longitud vectorial El buceo con coeficiente El buceo fraccional Pseudo costo de buceo Línea de buceo de búsqueda Buceo guiado (se aplica cuando el solucionador ya encontró al menos un punto entero factible) La heurística de buceo generalmente selecciona una variable que debe ser de valor entero, para la cual la solución actual es fraccionada. A continuación, la heurística introduce un límite que obliga a que la variable sea de valores enteros y resuelve de nuevo el LP relajado asociado. El método de elegir la variable a enlazar es la principal diferencia entre la heurística de buceo. Véase Berthold, sección 3,1.[4]
`'none'`	no busca un punto factible.`intlinprog` El solucionador simplemente toma cualquier punto factible que encuentra en su búsqueda ramificación y enlazada.

La principal diferencia entre y es que se ejecuta heurística con más frecuencia durante las iteraciones ramifican y enlazadas.'intermediate''advanced''advanced'

Después de cada heurística completa con una solución factible, llama a funciones de salida y funciones de trazado.intlinprog Ver.Función de salida y sintaxis de función de trazadointlinprog

Si incluye un argumento, utiliza ese valor en la heurística de buceo guiada hasta que encuentre un mejor punto de entero factible.x0intlinprog'rins' Así que cuando usted proporciona, usted puede obtener buenos resultados estableciendo la opción a u otra configuración que utiliza.x0'Heuristics''rins-diving''rins'

Rama y encuadernado

El método de bifurcación y enlazado construye una secuencia de subproblemas que intentan converger a una solución de la MILP. Los subproblemas dan una secuencia de límites superior e inferior en la solución f^Tx. El primer límite superior es cualquier solución factible, y el primer límite inferior es la solución al problema relajado. Para una discusión del límite superior, vea.Heurística para encontrar soluciones factibles

Como se explica en, cualquier solución al problema de programación lineal relajado tiene un valor de función objetivo inferior que la solución a la MILP.Programación lineal Además, cualquier punto factiblex_feas Satisface

f^Tx_feas ≥f^T,x

porque f^Tx es el mínimo entre todos los puntos factibles.

En este contexto, a es un LP con la misma función objetiva, límites y restricciones lineales que el problema original, pero sin restricciones de enteros y con cambios concretos en las restricciones o límites lineales.Nodo Es el problema original sin restricciones de enteros y sin cambios en las restricciones o límites lineales, lo que significa que el nodo raíz es el LP relajado inicial.nodo raíz

Desde los límites iniciales, el método de bifurcación y enlazado construye nuevos subproblemas ramificando desde el nodo raíz. El paso de ramificación se toma heurísticamente, 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 que un entero J, o mayor o igual que J + 1. Estos dos subproblemas surgen cuando una entrada enx_LP, correspondiente a un entero especificado en INTCON, no es un entero. Aquíx_LP es la solución a un problema relajado. Tome J como el suelo de la variable (redondeado hacia abajo), y J + 1 como el techo (redondeado hacia arriba). Los dos problemas resultantes tienen soluciones que son mayores o iguales af^Tx_LP, porque tienen más restricciones. Por lo tanto, este procedimiento potencialmente eleva el límite inferior.

El rendimiento del método de bifurcación y enlazado depende de la regla para elegir qué variable se dividirá (la regla de bifurcación). El algoritmo utiliza estas reglas, que puede establecer en la opción:BranchRule

: Permite elegir la variable fraccionaria con un máximo.'maxpscost'pseudocost
Pseudocost
El pseudocoste de una variable se basa en estimaciones empíricas del cambio en el límite inferior cuando se ha elegido como variable de ramificación, combinada con la parte fraccionaria del componente del punto actual.iiix La parte fraccionaria se encuentra en dos piezas, la parte inferior y la parte superior:p
P_i^– = () – ⌊ () ⌋xixi
P_i⁺ = 1 – P_i^–.
Dejar X_i^– ser la solución del programa lineal restringido a tener x(i) ≤ ⌊x(i)⌋, y dejar que el cambio en la función objetiva sea denotado
Δ_i^– =f^TX_i^– –f^T.x
Semejantemente Δ_i⁺ es el cambio en la función objetiva cuando el problema está restringido a tener x(i) ≥ ⌈x(i)⌉.
La ganancia objetiva por cambio de unidad en la variable X_i Es
$d_{i}^{-} = \frac{Δ_{i}^{-}}{p_{i}^{-}} or d_{i}^{+} = \frac{Δ_{i}^{+}}{p_{i}^{+}} .$
Dejar s_i^– Y s_i⁺ ser los promedios empíricos de D_i^– Y D_i⁺ durante el algoritmo de bifurcación y enlazado hasta este punto. Los valores empíricos se inicializan en el valor absoluto del coeficiente objetivo () para los términos antes de que haya observaciones.fi A continuación, la regla es bifurcar en un nodo que maximiza, para algunos pesos positivos'maxpscost'i W⁺ Y W^–, la cantidad
W^– * P_i^– * s_i^– + W⁺ * P_i⁺ * s_i⁺.
En términos generales, esta regla elige un coeficiente que es probable que aumente el límite inferior máximo.
— Similar a, pero en lugar del pseudocosto que se inicializa para cada variable, el solucionador intenta ramificar en una variable sólo después de que el pseudocosto tiene una estimación más confiable.'strongpscost''maxpscost'1 Para obtener una estimación más fiable, el solucionador hace lo siguiente (véase Achterberg, Koch y Martin).[1]
- Ordene todas las posibles variables de ramificación (las que actualmente son fraccionarias pero deben ser enteros) por sus puntuaciones actuales basadas en pseudocostos.
- Ejecute los dos programas lineales relajados basados en la variable de ramificación actual, comenzando desde la variable con la puntuación más alta (si la variable aún no se ha utilizado para un cálculo de bifurcación). El solucionador utiliza estas dos soluciones para actualizar los pseudocostos de la variable de ramificación actual. El solucionador puede detener este proceso temprano para ahorrar tiempo en la elección de la rama.
- Continúe eligiendo variables en la lista hasta que la puntuación más alta actual basada en pseudocostos no cambie para las variables consecutivas, donde es un valor elegido internamente, normalmente entre 5 y 10.kk
- Ramificar en la variable con la puntuación más alta basada en pseudocosto. Es posible que el solucionador ya haya calculado los programas lineales relajados basados en esta variable durante un procedimiento de estimación de pseudocostos anterior.
Debido a las soluciones de programas lineales adicionales, cada iteración de bifurcación tarda más que el valor predeterminado.'strongpscost''maxpscost' Sin embargo, el número de iteraciones ramifican y enlazadas normalmente disminuye, por lo que el método puede ahorrar tiempo en general.'strongpscost'
— Similar a, pero en lugar de ejecutar los programas lineales relajados sólo para ramas pseudocost sin inicializar, ejecuta los programas hasta el momento para cada variable, donde es un número entero pequeño como 4 u 8.'reliability''strongpscost''reliability'k2k2 Por lo tanto, tiene ramificación incluso más lenta, pero potencialmente menos iteraciones ramificadas y enlazadas, en comparación con.'reliability''strongpscost'
: Permite elegir la variable con la parte fraccionaria más cercana.'mostfractional'1/2
— Elija la variable con el valor absoluto máximo correspondiente en el vector objetivo.'maxfun'f

Después de las ramas del algoritmo, hay dos nuevos nodos para explorar. El algoritmo elige qué nodo explorar entre todos los que están disponibles usando una de estas reglas:

: Elija el nodo que tiene el valor de función objetivo más bajo.'minobj'
: Elija el nodo con la suma mínima de inbilidades de enteros.'mininfeas' Esto significa que para cada entero-componente infactible () en el nodo, agregue el más pequeño dexi P_i^– Y P_i⁺Dónde
P_i^– = () – ⌊ () ⌋xixi
P_i⁺ = 1 – P_i^–.
: Elija el nodo con el.'simplebestproj'mejor proyección
Mejor proyección
Dejar X_B denotan el mejor punto entero-factible encontrado hasta ahora, X_R degradar la solución de LP relajado en el nodo raíz, y denotan el nodo que examinamos.x Let () denota la suma de las inbilidades de enteros en el nodo (ver).inxx'mininfeas' La mejor regla de proyección es minimizar
$f^{T} x + \frac{f^{T} x_{B} - f^{T} x_{R}}{i n (x_{R})} i n (x) .$
Si no hay un punto entero factible encontrado hasta el momento, fije f^Tx_B = 0.

omite el análisis de algunos subproblemas al considerar la información del problema original, como el mayor divisor común de la función objetiva (GCD).intlinprog

El procedimiento de bifurcación y encuadernación continúa, generando sistemáticamente subproblemas para analizar y descartar aquellos que no mejorarán un límite superior o inferior del objetivo, hasta que se cumpla uno de estos criterios de detención:

El algoritmo excede la opción.MaxTime
La diferencia entre los límites inferior y superior de la función objetiva es menor que la o tolerancias.AbsoluteGapToleranceRelativeGapTolerance
El número de nodos explorados supera la opción.MaxNodes
El número de puntos factibles enteros excede la opción.MaxFeasiblePoints

Para obtener más información sobre el procedimiento de sucursal y encuadernado, véase Nemhauser y Wolsey y Wolsey.[8][10]

Referencias

[1] Achterberg, T., T. Koch and A. Martin. Branching rules revisited. Operations Research Letters 33, 2005, pp. 42–54. Available at https://www-m9.ma.tum.de/downloads/felix-klein/20B/AchterbergKochMartin-BranchingRulesRevisited.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://www.zib.de/groetschel/students/Diplom-Berthold.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] Mészáros C., and Suhl, U. H. Advanced preprocessing techniques for linear and quadratic programming. OR Spectrum, 25(4), pp. 575–595, 2003.

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

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

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