Mejor solucionador de optimización de entero mixto de código abierto [cerrado]

Question

Estoy usando CPLEX para resolver enormes modelos de optimización (más de 100k variables) ahora me gustaría ver si puedo encontrar una alternativa de código abierto, resuelvo problemas de enteros mixtos (MILP) y CPLEX funciona muy bien, pero es muy caro si queremos escalar, así que realmente necesito encontrar una alternativa o comenzar a escribir nuestra propia biblioteca de optimización ad-hoc (que será doloroso)

Cualquier sugerencia / idea sería muy apreciada

Answer 1

Personalmente encontré GLPK mejor (es decir, más rápido) que LP_SOLVE. Admite varios formatos de archivo, y una ventaja adicional es su interfaz de biblioteca, que permite una integración fluida con su aplicación.

Answer 2

Otro respaldo para COIN-OR . Descubrimos que el componente optimizador lineal (Clp) era muy fuerte, y el componente entero mixto (Cbc) podía ajustarse bastante bien con algún análisis. Comparamos con LP-Solve y GLPK.

Para problemas realmente difíciles, un solucionador comercial es el camino a seguir.

Answer 3

Pruebe el solucionador SCIP. Lo he usado para problemas MILP con más de 300K variables con buen rendimiento. Su rendimiento MILP es mucho mejor que GLPK. Gurobi también tiene un excelente rendimiento para problemas MILP (y generalmente mejor que SCIP (mayo de 2011)), pero podría ser costoso si no es un usuario académico. Gurobi usará multinúcleos para acelerar el solucionador.

Answer 4

¿Has probado lp_solve ? También hubo algunas sugerencias en las siguientes preguntas, para Java:

• biblioteca de optimización matemática para Java & # 8212; - ¿recomendaciones gratuitas o de código abierto?
• Herramienta de programación lineal / Bibliotecas para Java

Answer 5

Si yo fuera usted, trataría de usar una interfaz multi-solucionador como Osi (C ++) o PuLP (python) para que pueda escribir su código una vez y probarlo con muchos solucionadores.

Si los programas enteros que va a resolver son enormes, recomendaría Python sobre C ++, porque su código se verá más limpio y el 99% del tiempo lo dedicará al solucionador.

• https://projects.coin-or.org/Osi
• http://code.google.com/p/pulp-or/

Si, por el contrario, los problemas son pequeños, entonces el tiempo para copiar los problemas de la memoria de Python al solucionador (de ida y vuelta) ya no se debe descuidar: en ese caso, puede experimentar algunas mejoras de rendimiento notables utilizando un lenguaje compilado.

Pero si los problemas son abrumadoramente enormes, los lenguajes compilados volverán a ganar, porque la huella de la memoria se dividirá aproximadamente entre 2 (sin copia del problema en Python).

Answer 6

Recomiendo revisar el proyecto COIN. COIN OR

Muchos buenos solucionadores aquí, incluido ipOPT para problemas no lineales y una pareja solucionadores enteros mixtos también.

Answer 7

Scip no está mal.

Answer 8

Aunque esto quizás no sea lo que desea escuchar, pero hay años luz entre los solucionadores comerciales CPLEX y Gurobi, por un lado, y los solucionadores de código abierto, por otro lado.

Sin embargo, puede tener suerte y su modelo funciona bien con GLPK, Coin o similares, pero en general las soluciones de código abierto están muy por detrás de los solucionadores comerciales. Si fuera diferente, nadie pagaría 12,000 $ por una licencia de Gurobi y aún más por una licencia de CPLEX.

En los últimos años he visto muchos, muchos modelos que fueron demasiado difíciles para los solucionadores de código abierto. Créeme ...

No es tanto una cuestión de tamaño, sino de dificultad numérica.

Answer 9

100k variables es un gran problema. Muchas de las bibliotecas de código abierto no funcionan bien con tantas variables. Por lo que he leído, lp_solve solo se ha probado para alrededor de 30k variables. Usar el sistema comercial puede ser su única opción.

Answer 10

He usado DICOPT usando el servidor NEOS ( http: / /www.neos-server.org/neos/solvers/minco:DICOPT/GAMS.html ) para resolver programas no lineales enteros mixtos grandes (aproximadamente 1k variables y 1k restricciones) y lo encontraron excelente.

Para mi problema, DICOPT funcionó mucho mejor que los otros solucionadores MINLP enumerados en el servidor neos BARON / KNITRO / LINDO / SBB, etc.

Existen ciertas limitaciones para enviar trabajos a NEOS y es un poco engorroso, pero el libre acceso a un poderoso solucionador comercial lo compensa con creces.

Answer 11

Agregaré lo siguiente a las respuestas ya excelentes.

Si bien, como otros han señalado, los solucionadores comerciales son mucho más rápidos y más capaces que las alternativas gratuitas, es importante considerar qué tan grande es la brecha de optimización que puede aceptar. Para problemas grandes con muchas variables enteras, puede obtener tiempos de resolución mucho más rápidos si puede aceptar una brecha de optimización del 1% o incluso mayor (los valores predeterminados tienden a estar alrededor del 0.01% o menos).

Por supuesto, si está resolviendo un problema donde el 1% se traduce en millones de dólares, esto no es aceptable, de ahí el mercado de solucionadores de primer nivel. (Algunas comparaciones de Gurobi con solucionadores gratuitos aquí )

Estoy de acuerdo con otros en que vale la pena usar una plataforma que genere archivos de problemas independientes del solucionador (como archivos * .mps, * .lp), ya que puede probar otros solucionadores. Estoy usando PuLP y lo estoy encontrando y el solucionador gratuito COIN_CBC, excelente. Aunque limitado para problemas con muchas variables enteras.

Answer 12

Me sorprende que nadie haya mencionado MIPCL ( http: //www.mipcl- cpp.appspot.com/index.html ). Este solucionador afirma ser de código abierto bajo licencia LGPL (fuente: http: //www.mipcl -cpp.appspot.com/licence.html ), por lo que también es adecuado para su uso en aplicaciones que no sean de código abierto. Pero lo que falta para ser realmente de código abierto es el código fuente del solucionador mismo.

Hans Mittelmann hace muy poco (10 de septiembre de 2017) realizó un benchmark de programación lineal de enteros mixtos: http: / /plato.asu.edu/ftp/milpc.html (también puede estar interesado en consultar la página de resumen http://plato.asu.edu/bench.html o las diapositivas de su charla: http://plato.asu.edu/talks/informs2017.pdf ).

En el Benchmark de programación lineal de enteros mixtos con 12 hilos y un límite de tiempo de 2 horas, MIPCL logró resolver 79 instancias. Solo los solucionadores comerciales CPLEX, Gurobi y XPRESS lograron resolver más bajo las restricciones dadas (86 u 87 instancias, respectivamente).

También en términos de la métrica de rendimiento elegida (nuevamente utilizando 12 hilos) MIPCL es más rápido que los derivados SCIP de referencia (FSCIPC, FSCIPS) y el solucionador de código abierto CBC. Nuevamente, solo los solucionadores comerciales CPLEX, Gurobi y XPRESS superan significativamente a MIPCL en términos de rendimiento.

Answer 13

No es de código abierto, pero si tiene una licencia de Microsoft Academic Alliance, la Microsoft Solver Foundation Se incluye la edición empresarial (MSF). Gurobi también es gratuito para fines académicos, lo he usado en mi investigación de tesis.