mathematical optimization - Mejor solucionador de optimización de enteros mixtos de código abierto
mathematical-optimization linear-programming (13)
Personalmente, encontré que GLPK es mejor (es decir, más rápido) que LP_SOLVE. Es compatible con varios formatos de archivo, y una ventaja adicional es su interfaz de biblioteca, que permite una integración fluida con su aplicación.
Estoy usando CPLEX para resolver grandes 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 enteros mixtos (MILP) y CPLEX funciona bien, pero es muy costoso si Quiero escalar, así que realmente necesito encontrar una alternativa o comenzar a escribir nuestra propia biblioteca de optimización ad-hoc (lo cual será doloroso)
Cualquier sugerencia / idea sería muy apreciada
Recomiendo ver el proyecto COIN. MONEDA O
Muchos buenos solucionadores aquí, incluyendo ipOPT para problemas no lineales y un par de solucionadores de enteros mixtos también.
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.
Otro endoso para COIN-OR . Encontramos que el componente optimizador lineal (Clp) era muy fuerte y el componente entero mixto (Cbc) podía sintonizarse bastante bien con algunos análisis. Comparamos con LP-Solve y GLPK.
Para problemas realmente difíciles, un solucionador comercial es el camino a seguir.
Scip no está mal!
Pruebe el solucionador de SCIP. Lo he usado para problemas de MILP con más de 300K variables con buen rendimiento. Su rendimiento de MILP es mucho mejor que GLPK. Gurobi también tiene un excelente rendimiento para los problemas de MILP (y generalmente mejor que SCIP (mayo de 2011)), pero puede ser costoso si no eres un usuario académico. Gurobi usará múltiples núcleos para acelerar el solucionador.
No es de código abierto, pero si tiene una licencia de Microsoft Academic Alliance, se incluye la edición empresarial de Microsoft Solver Foundation (MSF). Gurobi también es gratuito con fines académicos, lo he usado en mi investigación de tesis.
Aunque es posible que esto no sea lo que quiere 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.
Sin embargo, puede tener suerte y su modelo funciona bien con GLPK, Coin o similar, 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 difíciles para los solucionadores de código abierto. Créame...
No es tanto una cuestión de tamaño, sino de dificultad numérica.
He usado DICOPT usando el servidor NEOS ( http://www.neos-server.org/neos/solvers/minco:DICOPT/GAMS.html ) para resolver grandes (aproximadamente 1k variables y 1k restricciones) programas enteros mixtos no lineales y lo encontré excelente.
Para mi problema, DICOPT lo hizo mucho mejor que los otros solucionadores de MINLP que figuran en el servidor de 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.
Si yo fuera usted, trataría de usar una interfaz multisolución 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 vas a resolver son enormes, recomendaría Python sobre C ++, porque tu código se verá más limpio y el 99% del tiempo se gastará en el solucionador.
Si, por el contrario, los problemas son pequeños, entonces ya no se debe pasar por alto el momento de copiar los problemas de la memoria de Python al solucionador (ida y vuelta): en ese caso puede experimentar algunas mejoras de rendimiento notables usando un lenguaje compilado .
Pero si los problemas son abrumadoramente enormes, los lenguajes compilados volverán a ganar, porque la huella de memoria se dividirá aproximadamente por 2 (ninguna copia del problema en python).
Agregaré lo siguiente a las respuestas ya excelentes.
Si bien, como han señalado otros, los solucionadores comerciales son mucho más rápidos y más capaces que las alternativas gratuitas, es importante tener en cuenta la brecha de optimalidad 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 optimalidad del 1% o incluso mayor (los valores predeterminados tienden a ser de alrededor del 0,01% o menos).
Por supuesto, si está resolviendo un problema en el que el 1% se traduce en millones de dólares, esto no es aceptable, de ahí el mercado de solucionadores de primera categoría. (Algunas comparaciones de Gurobi a solucionadores libres aquí )
Estoy de acuerdo con otros en que el uso de una plataforma que genera archivos problemáticos independientes del solucionador (como * .mps, * .lp) vale la pena ya que puede probar con otros solucionadores. Estoy usando PuLP y lo estoy encontrando, y el solucionador COIN_CBC gratuito, excelente. Aunque limitado por problemas con muchas variables enteras.
¿Has probado lp_solve ? También hubo algunas otras sugerencias en las siguientes preguntas, para Java:
Me sorprende que nadie haya mencionado MIPCL ( http://www.mipcl-cpp.appspot.com/index.html ). Es de código abierto bajo licencia LGPL (fuente: http://www.mipcl-cpp.appspot.com/licence.html ), por lo tanto, también es adecuado para ser utilizado en aplicaciones de código abierto.
Hans Mittelmann hace muy poco (10 de septiembre de 2017) hizo el Índice de programación lineal mixta de enteros: http://plato.asu.edu/ftp/milpc.html (también podría estar interesado en consultar la página de información general http: //plato.asu .edu / bench.html o las diapositivas de su charla: http://plato.asu.edu/talks/informs2017.pdf ).
En el Índice de programación lineal de enteros mixtos con 12 subprocesos 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 o 87 instancias, respectivamente).
También en términos de la métrica de rendimiento elegida (una vez más usando 12 subprocesos) MIPCL es más rápido que los derivados de SCIP comparados (FSCIPC, FSCIPS) - recuérdese que SCIP no es un solucionador de código abierto - y el solucionador de código abierto CBC. De nuevo, solo los solucionadores comerciales CPLEX, Gurobi y XPRESS superan ampliamente a MIPCL en términos de rendimiento.