Комплект линейного программирования GNU

GNU Linear Programming Kit ( GLPK ) — это программный пакет, предназначенный для решения крупномасштабного линейного программирования (LP), смешанного целочисленного программирования (MIP) и других связанных задач. Это набор процедур, написанных на ANSI C и организованных в виде вызываемой библиотеки . Пакет является частью проекта GNU и выпускается под лицензией GNU General Public License .

GLPK использует пересмотренный симплексный метод и метод прямоугольных и двойственных внутренних точек для нецелочисленных задач, а также алгоритм ветвей и границ вместе со смешанными целочисленными сечениями Гомори для (смешанных) целочисленных задач.

ГЛПК разработан Махориным Андреем Олеговичем (Андрей Олегович Махорин) из Московского авиационного института . Первый публичный релиз состоялся в октябре 2000 года.

• Версия 1.1.1 содержала библиотеку для переработанного прямого и двойного симплексного алгоритма.
• В версии 2.0 представлена ​​реализация метода прямоугольно-двойственной внутренней точки.
• В версии 2.2 добавлено решение задач методом ветвей и границ для смешанных целочисленных задач.
• В версии 2.4 добавлена ​​первая реализация языка моделирования GLPK/L.
• В версии 4.0 GLPK/L был заменен языком моделирования GNU MathProg, который является подмножеством языка моделирования AMPL .

Начиная с версии 4.0, проблемы GLPK можно моделировать с помощью GNU MathProg (GMPL), подмножества языка моделирования AMPL, используемого только GLPK. Однако GLPK чаще всего вызывается из других языков программирования. Существуют оболочки для:

• Julia ^[2] и пакет моделирования JuMP ^[3]
• Java (используя OptimJ ) ^[4]

В Wikibooks есть книга по теме: GLPK

• Эйдзи Оки (2012). Линейное программирование и алгоритмы для сетей связи: практическое руководство по проектированию, контролю и управлению сетями . CRC Press. ISBN 978-1-4665-5264-7.В книге используется исключительно GLPK и содержится множество примеров.

• Официальный сайт ГЛПК
• Вики-книга GLPK