¿Cuál es el software más rápido (código abierto) para resolver problemas de programación de enteros mixtos

14

Tengo un problema de programación de enteros mixtos. Y estoy actual usando GLPK como mi solucionador. Pero descubrí que GLPK es bueno para el problema de programación lineal, pero para la programación de enteros mixtos, requiere mucho más tiempo, por lo tanto, no cumple con nuestros requisitos. Estoy buscando otro software. ¿Hay alguna otra buena herramienta de código abierto para resolver problemas de programación de enteros mixtos con alta velocidad? ¡Gracias!

Yu Hao
fuente
¿Has visto las comparaciones con SCIP ?
Ali

Respuestas:

14

Si quiere algo de código abierto, probablemente quiera probar el código CBC de COIN (también tienen un par de otros solucionadores MILP, como un marco de sucursal y precio, o SYMPHONY).

Gurobi y CPLEX serán considerablemente más rápidos, y a partir de la reunión INFORMS 2011 o 2012, Gurobi fue más rápido que CPLEX (aunque las métricas de rendimiento dependen, por supuesto, de los problemas). En los MILP resueltos en mi tesis, Gurobi fue aproximadamente 15-100 veces más rápido que CBC, y CPLEX fue casi tan rápido como Gurobi, pero muy ligeramente más lento (como 12-80 veces más rápido).

Aunque el rendimiento en el peor de los casos es exponencial, el tiempo de ejecución dependerá en gran medida de la estructura del problema. Es poco probable que pueda resolver un MILP con millones de variables a menos que explote una estructura especial (tal vez si es un programa estocástico que puede descomponerse en muchos problemas mucho más pequeños), pero es completamente posible resolver MILP no triviales con miles de variables en menos de un minuto. (Por supuesto, también es posible que estos problemas tarden una hora o más en resolverse).

Como señala Brian Borchers, CPLEX y Gurobi tienen licencias gratuitas disponibles para algunos investigadores, uno de estos dos paquetes de software sería realmente el mejor para usar como un solucionador MILP de propósito general.

Geoff Oxberry
fuente
6

Los problemas de programación lineal de enteros mixtos son mucho más difíciles de resolver que los problemas de programación lineal. En términos de complejidad computacional, los LP se pueden resolver en tiempo polinómico mientras que resolver MILP es un problema NP-Hard. Los algoritmos conocidos para resolver MILP tienen una complejidad exponencial en el peor de los casos.

Hay otros paquetes de software para la programación lineal de enteros mixtos que puede ver, incluidos SCIP (gratuito para uso académico), CPLEX (comercial pero tiene una opción de licencia académica) y GUROBI (también comercial con una opción de licencia académica). Uno o más de estos paquetes puede ser sustancialmente más rápido que GLPK en sus problemas, pero no espere que ninguno de ellos sea tan rápido para resolver MILP como lo son para resolver LP de tamaño similar.

Brian Borchers
fuente
4

Si desea probar varios solucionadores diferentes, pruebe el marco de modelado JuMP de Julia . Le permite escribir su modelo como un modelo JuMP y luego cambiar los solucionadores con una línea de código. Por ejemplo, para problemas MILP, puede elegir entre los solucionadores Bonmin, Cbc, Couenne, CPLEX, GLPK, Gurobi y MOSEK. Debido a esto, si lo escribe en JuMP, puede probar todos los solucionadores que mencionó Geoff y ver qué funciona sin tener que escribir un montón de código. Sus propias pruebas personales serán la mejor fuente de conocimiento sobre cuáles son los algoritmos más rápidos para sus problemas.

Chris Rackauckas
fuente
¿El marco JuMP agrega mucha sobrecarga?
naught101
1
No, JuMP se realiza a través de macros, por lo que está en tiempo de compilación. De hecho, lo que hace JuMP usa macros para reescribir el código y usar la autodiferenciación para calcular funciones eficientes para gradientes, jacobianos y hessianos, por lo que será más rápido en casos en los que de otro modo no habría proporcionado una forma analítica para el gradiente / Jacobian / Hessian. En realidad, puede verificar a través @code_llvmdel código de ensamblaje resultante para ver que el código de pegamento no es esencialmente nada (esto también se debe a que Julia usa ingenuamente punteros de función y las mismas matrices de bits que C / Fortran).
Chris Rackauckas
@ChrisRackauckas ¿Qué solucionador funciona mejor para problemas no lineales con restricciones no lineales?
skan
Esa es una pregunta completamente diferente si probablemente no debería hacerse en un comentario, pero tiendo a usar JuMP con NLopt o IPOPT dependiendo de las restricciones requeridas y si necesito una optimización global o local.
Chris Rackauckas
3

Siguiendo las sugerencias de otros, he usado (el comercial) GAMS para muchos proyectos. Es muy sencillo; todo lo que tiene que hacer es poner la formulación matemática de su problema. Recoge las variables, restricciones, funciones objetivo y todos los datos de entrada. Luego, proporciona una gama de solucionadores (optimizadores) para cualquier caso. Dependiendo de su caso, agrega solucionadores más sofisticados.

Ciertamente, FÁCIL vale la pena echarle un vistazo. Marco de código abierto.

¡El término "rápido" es muy vago! Tienes que ser más específico; ¿Rápido en términos de número de iteraciones? cantidad de evaluaciones? ¿tiempo transcurrido? combinación de estos?

Sin embargo, si no está buscando un software y solo desea resolver el problema, podría sugerirle que utilice el optimizador global NSGA-II, que es un optimizador de código abierto de muy alta reputación y rendimiento.

Si proporcionara más información, podría guiarlo con precisión.

T3rmInAt0r
fuente
1
¡Debe considerar seriamente [openMDAO] [1], que está desarrollado / respaldado por la NASA y es bastante flexible!
T3rmInAt0r