Kit de programación lineal GNU

El Kit de Programación Lineal GNU ( GLPK ) es un paquete de software diseñado para resolver problemas de programación lineal (PL) a gran escala, programación entera mixta (MIP) y otros problemas relacionados. Es un conjunto de rutinas escritas en ANSI C y organizadas en forma de biblioteca invocable . El paquete es parte del Proyecto GNU y se publica bajo la Licencia Pública General 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 contenía una biblioteca para un algoritmo simplex primario 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 agregó resolución de ramas y límites para problemas de números enteros mixtos.
• La versión 2.4 agregó 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 GLPK se pueden modelar utilizando GNU MathProg (GMPL), un subconjunto del lenguaje de modelado AMPL utilizado únicamente por GLPK. Sin embargo, GLPK se invoca más comúnmente desde otros lenguajes de programación. Existen contenedores 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 oficial de GLPK
• Wikilibro de GLPK