Kit de programación lineal GNU

El Kit de Programación Lineal de GNU ( GLPK ) es un paquete de software diseñado para resolver problemas de programación lineal (PL) y programación entera mixta (PEM) a gran escala , entre otros problemas relacionados. Se trata de un conjunto de rutinas escritas en ANSI C y organizadas en forma de biblioteca invocable . El paquete forma parte del Proyecto GNU y se distribuye bajo la Licencia Pública General de GNU .

GLPK utiliza el método simplex revisado y el método de punto interior primal-dual para problemas no enteros , y el algoritmo de ramificación y acotación junto con los cortes de enteros mixtos de Gomory para problemas de enteros (mixtos).

GLPK fue desarrollado por Andrew O. Makhorin (Андрей Олегович Махорин) del Instituto de Aviación de Moscú . El primer lanzamiento público fue en octubre de 2000.

• La versión 1.1.1 incluía una biblioteca para un algoritmo simplex primal y dual revisado.
• La versión 2.0 introdujo una implementación del método de punto interior primal-dual.
• La versión 2.2 añadió la resolución de problemas de enteros mixtos mediante el método de ramificación y acotación.
• La versión 2.4 añadió una primera implementación del lenguaje de modelado GLPK/L.
• La versión 4.0 reemplazó GLPK/L por el lenguaje de modelado GNU MathProg, que es un subconjunto del lenguaje de modelado AMPL .

Desde la versión 4.0, los problemas de GLPK se pueden modelar utilizando GNU MathProg (GMPL), un subconjunto del lenguaje de modelado AMPL utilizado exclusivamente por GLPK. Sin embargo, lo más común es llamar a GLPK desde otros lenguajes de programación. Existen adaptadores para:

• Julia ^{[ 2 ]} y el paquete de modelado JuMP ^{[ 3 ]}
• Java (usando OptimJ ) ^{[ 4 ]}

• Eiji Oki (2012). Programación lineal y algoritmos para redes de comunicación: una guía práctica para el diseño, control y gestión de redes . CRC Press. ISBN 978-1-4665-5264-7.El libro utiliza exclusivamente GLPK y contiene numerosos ejemplos.

• Sitio web oficial de GLPK
• Wikilibro GLPK