Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.
Un programa lineal de enteros mixtos (MILP) es un problema con
Función objetiva lineal,fT, 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 resolverflbubAAeqbbeqintcon
x
utiliza esta estrategia básica para resolver programas lineales de enteros mixtos. puede resolver el problema en cualquiera de las etapas.intlinprog
intlinprog
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.
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
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]
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 LlamarxLP la solución al problema relajado y la solución al problema original con restricciones de enteros.x Claramente
fTxLP ≤fT,x
porquexLP 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.
Durante el preprocesamiento de programas enteros mixtos, analiza las desigualdades lineales junto con las restricciones de integralidad para determinar si:intlinprog
A*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.IntegerPreprocess
intlinprog
Si incluye un argumento, utiliza ese valor en el preprocesamiento.x0
intlinprog
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]
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.intlinprog
CutGeneration
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.CutMaxIterations
intlinprog
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]
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. |
'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. |
'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. |
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. |
o el equivalente'rss' 'rss-diving' | aplica un procedimiento híbrido que combina ideas y ramificaciones locales para buscar soluciones de enteros factibles. |
'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. |
'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. |
'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.
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. |
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.x0
intlinprog
'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'
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 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 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 factiblexfeas Satisface
fTxfeas ≥fT,x
porque fTx 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 enxLP, correspondiente a un entero especificado en INTCON, no es un entero. AquíxLP 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 afTxLP, 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
— 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.k
k
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'
k2
k2
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
Pi–
Y
Pi+Dónde
Pi–
= () – ⌊ () ⌋xixi
Pi+
= 1 –
Pi–.
: Elija el nodo con el.'simplebestproj'
mejor proyección
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.AbsoluteGapTolerance
RelativeGapTolerance
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]
[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.