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.

Ajuste de programación lineal de enteros

Cambiar opciones para mejorar el proceso de solución

Nota

A menudo, puede cambiar la formulación de un MILP para que sea más fácilmente soluble. Para obtener sugerencias sobre cómo cambiar su formulación, consulte Williams.[1]

Después de ejecutar una vez, es posible que desee cambiar algunas opciones y volver a ejecutarla.intlinprog Los cambios que podría desear ver incluyen:

  • Menor tiempo de ejecución

  • Valor de la función objetivo final inferior (una mejor solución)

  • Menor brecha final

  • Más o diferentes puntos factibles

Aquí hay recomendaciones generales para los cambios de opción que tienen más probabilidades de ayudar al proceso de solución. Pruebe las sugerencias en este orden:

  1. Para obtener una solución más rápida y precisa, aumente la opción de su valor predeterminado a un número mayor, como.CutMaxIterations1025 Esto puede acelerar la solución, pero también puede ralentizarse.

  2. Para una solución más rápida y precisa, cambie la opción a o.CutGeneration'intermediate''advanced' Esto puede acelerar la solución, pero puede usar mucha más memoria y puede ralentizar la solución.

  3. Para una solución más rápida y precisa, cambie la opción a.IntegerPreprocess'advanced' Esto puede tener un gran efecto en el proceso de solución, ya sea beneficioso o no.

  4. Para una solución más rápida y precisa, cambie la opción a.RootLPAlgorithm'primal-simplex' Usualmente este cambio no es beneficioso, pero ocasionalmente puede serlo.

  5. Para tratar de encontrar más o mejores puntos factibles, aumente la opción de su valor predeterminado a un número más alto como.HeuristicsMaxNodes50100

  6. Para tratar de encontrar más o mejores puntos factibles, cambie la opción a cualquiera o.Heuristics'intermediate''advanced'

  7. Para intentar encontrar más o mejores puntos factibles, cambie la opción a o, si esa opción no mejora la solución,.BranchRule'strongpscost''maxpscost'

  8. Para obtener una solución más rápida, aumente la opción de su valor predeterminado de cero a una positiva como.ObjectiveImprovementThreshold1e-4 Sin embargo, este cambio puede provocar que se encuentren menos puntos enteros factibles o una solución menos precisa.intlinprog

  9. Para intentar detener el solucionador más rápidamente, cambie la opción a un valor mayor que el predeterminado.RelativeGapTolerance1e-4 Del mismo modo, para intentar obtener una respuesta más precisa, cambie la opción a un valor inferior.RelativeGapTolerance Estos cambios no siempre mejoran los resultados.

Algunas soluciones "integer" no son números enteros

A menudo, algunos componentes supuestamente con valores enteros de la solución no son exactamente enteros. considera enteros todos los valores de la solución dentro de un entero.x(intcon)intlinprogIntegerTolerance

Para redondear todos los números enteros supuestos para que sean enteros, utilice la función.round

x(intcon) = round(x(intcon));

Precaución

El redondeo puede hacer que las soluciones se vuelvan inviables. Compruebe la viabilidad después del redondeo:

max(A*x - b) % see if entries are not too positive, so have small infeasibility max(abs(Aeq*x - beq)) % see if entries are near enough to zero max(x - ub) % positive entries are violated bounds max(lb - x) % positive entries are violated bounds

Componentes grandes no valores enteros

no exige que los componentes de la solución sean enteros valorados cuando superan sus valores absolutos.intlinprog2.1e9 Cuando la solución tiene estos componentes, le advierte.intlinprog Si recibe esta advertencia, Compruebe la solución para ver si los componentes con valores enteros supuestamente de la solución están cerca de enteros.

Grandes coeficientes no permitidos

no permite que los componentes del problema, como los coeficientes en, o, excedan en valor absoluto.intlinprogfAub1e15 Si intenta ejecutar con este tipo de problema, emite un error.intlinprogintlinprog

Si recibe este error, a veces puede escalar el problema para tener coeficientes más pequeños:

  • Para los coeficientes que son demasiado grandes, intente multiplicarse por un pequeño factor de escala positiva.ff

  • Para los coeficientes de restricción que son demasiado grandes, intente multiplicar todos los límites y matrices de restricciones por el mismo factor de escala positivo pequeño.

Referencias

[1] Williams, H. Paul. Model Building in Mathematical Programming. Wiley, 2013.