МОНЕТА-ИЛИ

МОНЕТА-ИЛИ

Веб-сайт	www .coin-или .org

Вычислительная инфраструктура для исследования операций ( COIN-OR ) — это проект, цель которого «создать для математического программного обеспечения то же, что открытая литература для математической теории ». Открытая литература (например, исследовательский журнал) предоставляет сообществу исследователей операций (OR) процесс рецензирования и архив. Статьи в журналах по исследованию операций по математической теории часто содержат подтверждающие численные результаты вычислительных исследований. Реализации программного обеспечения, модели и данные, используемые для получения численных результатов, обычно не публикуются. Статус-кво не позволял исследователям воспроизводить результаты вычислений, проводить объективные сравнения и расширять современный уровень техники.

Успех Linux , Apache и других проектов популяризировал открытым исходным кодом модель разработки и распространения программного обеспечения с . Группа из IBM Research предложила открытый исходный код в качестве аналогичного, но жизнеспособного средства публикации программного обеспечения, моделей и данных. COIN-OR был задуман как инициатива по продвижению открытого исходного кода в сообществе исследователей вычислительных операций и предоставлению онлайн-ресурсов и услуг хостинга, необходимых для того, чтобы другие могли запускать свои собственные проекты программного обеспечения с открытым исходным кодом .

Веб-сайт COIN-OR был запущен в качестве эксперимента в 2000 году одновременно с 17-м Международным симпозиумом по математическому программированию в Атланте, штат Джорджия. В 2007 году у COIN-OR было 25 прикладных проектов. включая инструменты для линейного программирования (например, COIN-OR CLP ), нелинейного программирования (например, IPOPT ), целочисленного программирования (например, CBC, Bcp и COIN-OR SYMPHONY ), языков алгебраического моделирования (например, Coopr ) и многого другого. К 2011 году это число выросло до 48 проектов. COIN-OR проводится Институтом исследований операций и наук управления INFORMS и управляется образовательным некоммерческим фондом COIN-OR.

Проекты

CLP

с открытым исходным кодом, линейного программирования COIN-OR LP (CLP или Clp) — это решатель написанный на C++ . Он опубликован под лицензией Common Public License , поэтому его можно использовать в проприетарном программном обеспечении без каких-либо ограничений Стандартной общественной лицензии GNU . CLP в первую очередь предназначен для использования в качестве вызываемой библиотеки, хотя можно создать и автономную исполняемую версию. Он разработан так, чтобы быть таким же надежным, как любой коммерческий решатель, хотя и в несколько раз медленнее. и уметь решать очень большие проблемы.

CLP предназначен для решения таких задач линейного программирования, как:

минимизировать $c_{1}x_{1}+c_{2}x_{2}\,$

• с учетом проблемных ограничений следующего вида

$a_{11}x_{1}+a_{12}x_{2}\leq b_{1}$

$a_{21}x_{1}+a_{22}x_{2}\leq b_{2}$

$a_{31}x_{1}+a_{32}x_{2}\leq b_{3}$

• и неотрицательные переменные

$x_{1}\geq 0$

$x_{2}\geq 0$

с миллионами переменных и/или ограничений. Его основным алгоритмом является симплексный алгоритм .

CLP используется в других проектах COIN-OR, таких как SYMPHONY , Branch Cut and Price (BCP), COIN-OR Branch and Cut ( CBC ) и других.

Си-Би-Си

COIN-OR ветвления и разреза с открытым исходным кодом, (CBC или Cbc) — это программа смешанного целочисленного программирования написанная на C++ . Его можно использовать как автономный исполняемый файл, так и как вызываемую библиотеку (через A Mathematical Programming Language ( AMPL ) [исходно], General Algebraic Modeling System (GAMS) [с использованием ссылок, предоставляемых COIN-OR Optimization Services (OS) ) и проекты GAMSlinks ], MPL [через проект CoinMP ], AIMMS [через проект AIMMSlinks ], PuLP , CMPL, OpenSolver для Excel, ЮМП, или МиниЦинк ). Хотя он уже много лет является популярным решением MIP с открытым исходным кодом, его производительность сейчас значительно уступает HiGHS.

СИМФОНИЯ

Одно- или многопроцессная оптимизация в сетях (SYMPHONY) — это инфраструктура с открытым исходным кодом для решения смешанных целочисленных программ (MIP) в гетерогенных сетях. Он может использовать CLP , CPLEX , XPRESS или другие решатели линейного программирования для решения базовых линейных программ.

SYMPHONY — это вызываемая библиотека, которая реализует как последовательные, так и параллельные версии ветвей, разрезов и цен для решения задач MILP. Алгоритм ветвей, разрезов и цен аналогичен алгоритму ветвей и границ , но дополнительно включает методы секущей плоскости и алгоритмы ценообразования. Пользователь библиотеки может настраивать алгоритм любым количеством способов, предоставляя подпрограммы для конкретного приложения для чтения пользовательских файлов данных, генерируя плоскости сечения для конкретного приложения или применяя собственные правила ветвления, что приводит к созданию индивидуального алгоритма ветвления и разреза. Большинство компонентов алгоритма, например, управление деревом поиска, управление решением линейного программирования, управление пулом вырезов и управление связью, являются внутренними по отношению к библиотеке и не требуют вмешательства пользователя. Исполняемые файлы могут быть построены в любом количестве конфигураций, от полностью последовательных до полностью параллельных, с независимо функционирующими генераторами разрезов, пулами вырезов и решателями LP. Распределенная версия в настоящее время работает в любой среде, поддерживаемой PVM Протокол передачи сообщений . Тот же исходный код можно скомпилировать для архитектур с общей памятью с помощью любого компилятора, совместимого с OpenMP .

SYMPHONY читает файлы MPS (через программу чтения COIN-OR MPS) и файлы GNU MathProg . SYMPHONY не имеет собственного LP-Solver, но может использоваться с такими решателями, как Clp, Cplex, Xpress, через интерфейс Osi. Вырезы генерируются с использованием библиотеки создания вырезов COIN: CGL. SYMPHONY также имеет специфичные для структуры реализации для таких задач, как задача коммивояжера , задача маршрутизации транспортных средств , проблема разделения наборов , смешанная задача почтальона и т. д. SYMPHONY также имеет интерактивную оболочку, в которой пользователь может вводить команды для выполнения программы и управления ею.

ПуЛП

PuLP — это средство моделирования LP/IP, написанное на Python . Он может генерировать файлы MPS или LP и вызывать GLPK , CLP / CBC и CPLEX для решения линейных задач. PuLP — это инструмент оптимизации по умолчанию в SolverStudio для Excel .

SMI

SMI — это средство моделирования и решения стохастического программирования , написанное на C++. Он может читать Stochastic MPS и предлагает прямые интерфейсы для построения стохастических программ. Он генерирует детерминированную эквивалентную линейную программу, решает ее и предоставляет интерфейсы для доступа к решениям сценария.

См. также

• Решатели COIN-OR доступны в системах моделирования JuMP , AIMMS , AMPL , GAMS и FortSP . Их также можно использовать из Excel через OpenSolver и SolverStudio . надстройки

Дальнейшее чтение

• Дж. Т. Линдерот и Т. К. Ральфс: Некоммерческое программное обеспечение для смешанно-целочисленного линейного программирования . В: Целочисленное программирование: теория и практика , Джон Карлоф (ред.), Серия исследований операций CRC Press, 2005, 253–303. (Версия рабочего документа)
• Т. Ральфс: Введение в пакет оптимизации COIN-OR: инструменты с открытым исходным кодом для построения и решения моделей оптимизации . Дни оптимизации, Монреаль, 7 мая 2013 г. (слайды презентации)

Внешние ссылки

• Официальный сайт COIN-OR, Вычислительная инфраструктура для исследования операций