Estoy interesado en implementar SM para la tarea LP, sin embargo, he oído hablar de posibles dificultades: el libro de Cormen dice que es posible tener datos de entrada que harán que la implementación ingenua se comporte en un tiempo exponencial. También he oído que la implementación ingenua puede repetirse para algún tipo de datos.
¿Existe un libro / documento / fuente que explique los matices de la implementación práctica de SM?
Gracias por adelantado.
Respuestas:
Recomiendo encarecidamente el artículo de Bixby, el "padre" de CPLEX, que analiza no solo la implementación de aspectos del algoritmo simplex (revisado): Robert E. Bixby , Resolviendo programas lineales del mundo real: una década y más progreso , operaciones Research (50) 2002, 3-15 .
fuente
El algoritmo simplex no está en P. CLRS, por lo tanto, afirma que, aunque en la práctica funciona "bien", hay algunas entradas que hacen que el algoritmo se ejecute en tiempo exponencial. Esto está estrictamente relacionado con el algoritmo, no con su implementación: lo enfrentará independientemente de cómo implemente exactamente el algoritmo. Sin embargo, LP está en P. Esto fue probado por Khachian en 1979, sin embargo, su algoritmo elipsoide no es práctico. Hoy en día, los métodos de puntos interiores son ampliamente utilizados. El primero fue descubierto por Karmarkar en 1984.
Si está interesado en implementaciones prácticas, eche un vistazo a:
GUROBI, gratuito para uso académico, es en este momento el mejor optimizador disponible (versiones paralelas secuenciales y de memoria compartida):
http://www.gurobi.com
la biblioteca GLPK:
http://www.gnu.org/software/glpk/
Este es un proyecto de código abierto, que proporciona implementaciones para:
fuente
El libro de Programación Lineal de Vanderbei revisa muchos de los detalles de bajo nivel ... Pero como sugieren las otras respuestas / comentarios, implementar el solucionador de LP es una tarea difícil e ingrata. El solucionador estándar es probablemente el camino a seguir ... (También hay algunos solucionadores LP de código abierto ...)
fuente
No son solo las implementaciones ingenuas las que a veces se comportan en tiempo exponencial. De hecho, creo que todas las reglas deterministas y aleatorias conocidas tienen entradas superpolinomiales en el peor de los casos. La mayoría de las entradas conocidas que producen este comportamiento en el peor de los casos están altamente estructuradas, una pregunta relacionada:
La estructura de instancias patológicas para algoritmos simplex
Sin embargo, en la práctica SM funciona bien. Esto se ha formalizado mediante la introducción del análisis suavizado, que es básicamente el análisis del peor de los casos con entradas ligeramente perturbadas. Bajo este análisis, SM es polytime, en otras palabras, para cada entrada (incluso las patológicas) hay una ligera perturbación que permite que el algoritmo funcione bien. Esta información se ha transformado en un algoritmo aleatorio que funciona en polytime. Sin embargo, hasta donde yo entiendo, todavía hay un debate sobre si este algoritmo califica como un algoritmo simplex 'verdadero'. Tampoco sé si los paquetes estándar implementan algo similar a esto, pero debería poder encontrar alguna implementación si busca, debido a que el resultado tiene más de 5 años.
fuente
Puede consultar Luenberger, Ye, Programación lineal y no lineal, 3ª ed. Eso parece bastante completo, pero aún no he llegado lo suficientemente lejos como para decir si responde completamente a su pregunta.
fuente