Estoy escribiendo un código en C++, y resulta que necesito resolver un problema de optimización que puede formularse usando mvariables y nrestricciones lineales (es decir, la restricción itiene la forma \sum_j a_{i,j} x_j >= b_i; aunque si no sabe qué es la programación lineal, puede probablemente no responda esta pregunta).
Sucede que el número de variables es bastante pequeño, por ejemplo, menos de 10 típicamente; pero el número de restricciones es mucho mayor.
Necesito que la solución sea rápida, al menos en la expectativa (con suerte, no más de una pasada sobre la mayoría de las restricciones), y estoy dispuesto a pagar en distancia desde el óptimo para eso.
¿Existe una biblioteca para este 'nicho' de programación lineal? Si no, ¿cuáles serían las bibliotecas de programación lineal generalmente rápidas?
Requisitos:
Características deseadas:
Estoy investigando el CLP de COIN-OR . Es un solucionador C++ FOSS LP; más allá de eso no puedo decir mucho por ahora.
Hay dos aspectos a discutir aquí:
El algoritmo es lo que determina el tiempo de ejecución y la precisión del método. Si está dispuesto a sacrificar la precisión, elegiría un método como IP sobre Simplex (este es un ejemplo con fines ilustrativos).
En cuanto a la implementación , al ver cómo este tipo de problemas generalmente se resuelven mediante operaciones matriciales, puede usar la biblioteca clásica para estas cosas: BLAS . Otra posibilidad es el paquete GLPK . Si quieres una demostración de cómo usar este último, echa un vistazo al código fuente de Octave . Quizás la documentación de Octave sobre el tema también podría ser útil.
Por cierto, otra forma de compensar, independientemente de la técnica específica, es realizar el cálculo en un tipo de datos de precisión reducida, por ejemplo, float32y no float64.
Geoffrey De Smet