Современные программные системы, реализующие метод ветвей и границ


Хотя задачи ДО в общем трудны для решения, в последнее время наблюдается существенный количественный и качественный рост числа раз­рабо­ток в области программного обеспечения (ПО) ‑ как коммерческого, так и неком­мерческого ‑ решения задач ДО. Хороший обзор основных алгорит­мических компонентов коммерческих решателей, таких как CPLEX, LINGO, XPRESS, дан в работе Atamtürk & Savelsbergh[7]. В работе[8] анализи­руются возможности некоммерческого и открытого ПО для решения задач ДО. Почти без исключений, эти новые пакеты ПО реализуют различные версии метода ветвей и границ. Метод ветвления и отсечения (branch-and-cut)[9] является обобщением метода ветвей и границ и чистого метода отсечений Гомори, при этом после решения линейной релаксации и невозможности успешного зондирования на основе реше­ния соответствующей задачи ЛП, делается попытка нахождения нарушаю­щегося отсечения. Если найдены нару­шаю­щиеся отсечения, они добав­ляются к форму­лировке релаксационной задачи и полученная задача ЛП решается вновь. Если же нарушающегося отсечения не было найдено, производится ветвле­ние. Метод отсече­ний и ветвлений объединяет вычис­ли­тельные возможности алгоритмов ветвей и границ с теоретическими резуль­татами комбинаторики многогранников[10]. В 1998 г. Applegate et al. использовали этот метод для решения задачи о коммивояжере с 13509 городами, что на порядок больше размера задач, которые решались ранее[11]. Этот результат становится более впечатляющим, если учесть, что число перемен­ных в стандартной формулировке этой задачи примерно равно квадрату числа городов. Таким образом, здесь решалась задача с примерно 100 млн. переменных.

Пакеты ПО можно разделить на две группы: решатели, использующие алгоритмы общего назначения для решения задач СЦЛП, не использующие особенности структуры задач) и решатели, позволяющие пользователю использовать преимущества специальной структуры задачи. Наиболее часто предлагаются решатели СЦП. Среди последних следует упомянуть MINTO[12], MIPO[13], а также bc-opt[14].

Общие схемы – SYMPHONY, COIN/BCP и ABACUS[15] наиболее полно отражают возможности решателей первого вида. Другие пакеты, такие как MINTO, могут использовать подпрограммы, учитывающие специфику задачи. CONCORDE[16] ‑ один из наиболее совершенных в настоящее время программных пакетов для решения задачи о коммивояжере. Среди коммерческих пакетов следует также выделить CPLEX (ILOG), OSL (IBM), XPRESS (Dash).

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

Теоретические основы для ускорения процесса решения сложных задач ДО предложены в [15], где описана РЕСТАРТ-технология, основанная на использовании РЕСТАРТ-распределения и РЕСТАРТ-критерия останова алгоритма.

 


[1] Метод поиска с возвратами более подробно разбирается в главе 10 настоящего пособия.

[2] Land A.H., Doig A.G. An automatic method of solving discrete programming problems // Econometrica. — 1960. — V. 28, № 3. — P. 497-520.

 

[3] Эвристический алгоритм (эвристика) — алгоритм решения задачи, не имеющий строгого обоснования, но, тем не менее, дающий приемлемое решение задачи в большинстве практически значимых случаев.

[4] Для задачи минимизации выбирается задача с наименьшей нижней оценкой.

[5] Geoffrion A.M., Marsten R.E. Integer programming algorithms: a framework and state-of-the-art survey // Management Science. ‑ 1972. ‑ V. 18, N 9. ‑ P. 465-491.

[6] Geoffrion A.M., Marsten R.E. Integer programming algorithms: a framework and state-of-the-art survey // Management Science. ‑ 1972. ‑ V. 18, N 9. ‑ P. 465-491.

[7] Atamtürk A., Savelsbergh M. W. P. Integer-programming software systems // Annals of Operations Research. ‑ 2005. ‑ V. 140. ‑ P. 67-124.

[8] Linderoth J. T., Ralphs T. K. Noncommercial software for mixed-integer linear programming // Integer Programming: Theory and Practice / J. Karlof (ed). CRC Press Operations Research Series, ‑ 2005. ‑ P. 253-303.

[9] Ladányi L., Ralphs T.K., and Trotter L.E. Branch, cut, and price: Sequential and parallel // Computational Combinatorial Optimization / D. Naddef, M. Jünger (eds.). ‑ Berlin: Springer, 2001. ‑ P. 223-260.

[10] Conforti M., Cornuéjols G., and Zambelli G. Polyhedral Approaches to Mixed Integer Linear Programming // Jünger M. et al. (eds). 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art. ‑ Berlin, Heidelberg: Springer Verlag, 2010. ‑ 804 p. ‑ P. 343-386.

[11] Applegate D, Bixby R., Chvatal V., and Cook W. On the solution of traveling salesman problems // Documenta Mathematica, Journal der Deutschen Mathematiker-Vereinigung, International Congress of Mathematicians. ‑ 1998.

[12] Nemhauser G. L., Savelsbergh M. W. P., and Sigismondi G. S. MINTO, a Mixed INTeger Optimizer // Operations Research Letters. ‑ 1994. ‑ V. 15. ‑ P. 47-58.

[13] Balas E., Ceria S., and Cornuejols G. (1996) Mixed 0-1 programming by lift-and-project in a branch-and-cut framework // Management Science. ‑ 1996. ‑ V. 42. ‑ P. 1229-1246.

[14] bc-opt: A branch-and-cut code for mixed integer programs / C. Cordier [et al.] // Mathematical Programming. ‑ 1999. ‑ V. 86. ‑ P. 335-353.

[15] Jünger M., Thienel S. The ABACUS system for branch and cut and price algorithms in integer programming and combinatorial optimization // Software Practice and Experience. ‑ 2000. ‑ V. 30. ‑ P. 1325-1352.

[16] http://www.tsp.gatech.edu/concorde.html



Дата добавления: 2016-06-05; просмотров: 1504;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.008 сек.