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 чаще всего называют из других языков программирования. Обертки существуют для:
- Юлия [2] и пакет моделирования JuMP [3]
- Java (с использованием OptimJ ) [4]
дальнейшее чтение
В Wikibooks есть книга на тему: ГЛПК.
- Эйдзи Оки (2012). Линейное программирование и алгоритмы для сетей связи: Практическое руководство по проектированию, контролю и управлению сетями . ЦРК Пресс. ISBN 978-1-4665-5264-7.В книге используется исключительно GLPK и содержатся многочисленные примеры.
Рекомендации
- ↑ Андрей Махорин (16 декабря 2020 г.). «Информация о выпуске glpk 5.0» . Проверено 16 декабря 2020 г.
- ^ GLPK.jl, JuMP-dev, 16 января 2023 г. , получено 4 февраля 2023 г.
- ^ jump-dev/JuMP.jl, JuMP-dev, 04 февраля 2023 г. , получено 4 февраля 2023 г.
- ^ «GLPK для Java – О программе» .
Внешние ссылки
- Официальный сайт ГЛПК
- Викибук ГЛПК