Как выбрать решатель целочисленного линейного программирования?

Я новичок в целочисленном линейном программировании. Я планирую использовать решатель целочисленного линейного программирования для решения моей задачи комбинаторной оптимизации. Я больше знаком с C++/объектно-ориентированным программированием в среде IDE. Теперь я использую NetBeans с Cygwin для написания своих приложений большую часть времени.

Могу я спросить, есть ли для меня простой в использовании решатель ILP? Или это зависит от проблемы, которую я хочу решить? Я пытаюсь сделать некоторую оптимизацию сопоставления ресурсов. Пожалуйста, дайте мне знать, если потребуется дополнительная информация.

Большое спасибо, Кэсси.


c++ algorithm graph-algorithm linear-programming genetic-algorithm
person Cassie    schedule 07.05.2010    source источник

Ответы (5)


arrow_upward
8
arrow_downward

Если вам нужно линейное смешанное целочисленное программирование, я бы указал на Coin-OR (и, в частности, на модуль CBC). Это бесплатное программное обеспечение (как речь). Вы можете использовать его с определенным языком или использовать C++.

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

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

Но в тегах вы упоминаете генетические алгоритмы и алгоритмы графов. Может быть, вам следует начать с лучшего определения вашей проблемы... Для графиков мне очень нравится Boost::Graph

person Tristram Gräbener    schedule 07.05.2010
comment
Большое Вам спасибо. Моя проблема в основном заключается в сопоставлении заданий с машинами на графе задач для планирования. Предположим, у меня есть граф задач. Каждый узел представляет задание, которое необходимо выполнять на машине. Различное сопоставление заданий с машинами приводит к различному общему времени планирования на критическом пути. Моя цель - найти минимальное время планирования некоторых заданий для машин. Итак, кто-нибудь знает какой-нибудь простой в использовании решатель, который не требует для меня сильного программирования? Большое Вам спасибо. Кэсси - person Cassie; 10.05.2010
comment
Что ж, такого рода планирование само по себе является полноценной исследовательской областью. Некоторые проблемы можно решить с помощью алгоритма кратчайшего пути (если у вас нет ограничений на одновременные задачи). Если ваши машины вытесняемые, то есть простые полиномиальные алгоритмы. В противном случае велика вероятность, что у вас есть трудная проблема. Попробуйте использовать CBC в качестве черного ящика (но вам нужно будет научиться моделировать эти проблемы в линейной модели) или попробуйте написать свой собственный код ветвления :) - person Tristram Gräbener; 11.05.2010

arrow_upward
8
arrow_downward

Я использовал lp_solve ( http://lpsolve.sourceforge.net/5.5/ ) на нескольких случаи с успехом. Он зрелый, многофункциональный и очень хорошо документирован с множеством полезных советов, если ваши навыки линейного программирования заржавели. Целочисленное линейное программирование — это не просто дополнение, в этом пакете ему уделяется особое внимание.

Только что заметил, что вы говорите, что вы «новичок» в этом. Что ж, тогда я настоятельно рекомендую этот пакет, так как документация полна примеров и несложных руководств. Другие пакеты, которые я пробовал, предполагают много пользователей.

person ravenspoint    schedule 29.10.2010

arrow_upward
4
arrow_downward

В случае больших проблем вы можете обратиться к AMPL, который представляет собой интерпретатор оптимизации со многими серверные решатели. Он работает как отдельный процесс; C++ будет использоваться для записи входных данных.

Затем вы можете попробовать различные современные решатели.

person Potatoswatter    schedule 07.05.2010

arrow_upward
2
arrow_downward

Посмотрите GLPK. Поставляется с несколькими примерами и работает с подмножеством AMPL, хотя IMHO работает лучше всего, когда вы придерживаетесь C/C++ для настройки модели. Справляется и с довольно большими моделями.

person Pete    schedule 27.02.2011

arrow_upward
1
arrow_downward

Линейное программирование из Википедии охватывает несколько различных алгоритмов, в которых вы могли бы покопаться, чтобы увидеть, какие из них могут работать лучше всего для вас. Это помогает или вы хотели что-то более конкретное?

person JB King    schedule 07.05.2010