¿Cómo elegir un solucionador de programación lineal entero?

Question

Soy un novato para la programación lineal entera. Planeo usar un solucionador de programación lineal entero para resolver mi problema de optimización combinatoria. Estoy más familiarizado con C++/programación orientada a objetos en un IDE. Ahora estoy usando NetBeans con Cygwin para escribir mis aplicaciones la mayor parte del tiempo.

¿Puedo preguntar si hay un solucionador de ILP de uso fácil para mí? O depende del problema que quiero resolver? Estoy tratando de hacer algunos recursos de optimización de mapeo. Por favor, avíseme si se requiere más información.

Muchas gracias, Cassie.

Answer 1

Linear Programming de Wikipedia cubre algunos algoritmos diferentes que podría investigar para ver cuál puede funcionar mejor para usted. ¿Eso ayuda o querías algo más específico?

Answer 2

Para problemas grandes, puede consultar AMPL, que es un intérprete de optimización con muchos backend solvers disponibles. Funciona como a separate process; C++ se usaría para escribir los datos de entrada.

Luego puede probar varios solucionadores de última generación.

Answer 3

Si lo que quieres es una programación lineal de enteros mixtos, apuntaré a Coin-OR (y específicamente al módulo CBC). Es software gratuito (como voz) Puede usarlo con un idioma específico o usar C++.

Use C++ si sus datos requieren mucho preprocesamiento, o si quiere poner sus manos en el solucionador (elegir puntos de pivote, generación de columnas, agregar cortes, etc.).

Utilice el lenguaje integrado si desea utilizar el solucionador como una caja negra (simplemente está interesado en el resultado y el problema es fácil o lo suficientemente clásico para ser resuelto sin ajustar).

Pero en las etiquetas mencionas algoritmos genéticos y algoritmos de gráficos. Tal vez debería empezar por una APP mejor su problema ... Para gráficos me gusta un montón Boost :: Gráfico

Answer 4

he utilizado lp_solve (http://lpsolve.sourceforge.net/5.5/) en un par de ocasiones con éxito. Es maduro, tiene muchas funciones y está muy bien documentado con muchos buenos consejos si tus habilidades de programación lineal están oxidadas. La programación lineal entera no es solo un complemento, sino que se enfatiza fuertemente con este paquete.

Acabo de notar que dices que eres un "novato" en esto. Bueno, entonces recomiendo este paquete ya que la documentación está llena de ejemplos y tutoriales amables. Otros paquetes que he probado tienden a suponer mucho del usuario.

Answer 5

Busque en GLPK. Viene con algunos ejemplos y funciona con un subconjunto de AMPL, aunque en mi humilde opinión funciona mejor cuando se apega a C/C++ para la configuración del modelo. Se las arregla con modelos bastante grandes también.