Теоретические основы методов отсечения

По-видимому, успех в  решении задач покрытия связан с  тем, что удалось напасть на класс  задач, практически важных и в  то же время успешно решаемых. Было бы весьма интересно точно охарактеризовать класс задач покрытия, хорошо решаемых по методу отсечения. Это тем более интересно, что построены примеры обобщенных задач покрытия, для которых возникают значительные вычислительные трудности.

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

Наиболее перспективными для дальнейших исследований по методу отсечения представляются следующие  направления:

1) Исследование строения  множеств £^ц и V(£^ц).

2) Исследование свойств  правильных отсечений.

3) Указание новых способов  построения правильных отсечений.

4) Развитие новых классов  алгоритмов метода отсечения  (например, прямых алгоритмов).

5) Выделение отдельных  классов эффективно решаемых  задач.

Список используемых источников

1. И. Х. Сигал, А. П. Иванова Введение в прикладное дискретное программирование, М. Физматлит, - 2007

2. Ковалев Михаил Михайлович Дискретная оптимизация (целочисленное программирование). Изд. 2-е, стереотипное. - М.: Едиториал УРСС, - 2003

3. Карманов В. Г. Математическое программирование: Учеб. пособие. — 5-е изд., М.: Физматлит, - 2004.

4. Ширяев Владимир  Исследование операций и численные  методы оптимизации: Учебное пособие - 3-е изд М.: Едиториал УРСС, КомКнига, - 2007

5. Р. Хаггарти  Дискретная математика для программистов, М.: Техносфера - 2005