Современные программные системы, реализующие метод ветвей и границ
Хотя задачи ДО в общем трудны для решения, в последнее время наблюдается существенный количественный и качественный рост числа разработок в области программного обеспечения (ПО) ‑ как коммерческого, так и некоммерческого ‑ решения задач ДО. Хороший обзор основных алгоритмических компонентов коммерческих решателей, таких как 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; просмотров: 1514;