§ 3. Некоторые выводы

В этом параграфе сделана попытка на основе результатов вычислительных экспериментов охарактеризовать поведение алгоритмов метода отсечения при решении задач целочисленного линейного программирования. В качестве меры продолжительности вычислений могут рассматриваться количество симплексных итераций и количество правильных отсечений (дополнительных линейных ограничений) Для третьего алгоритма Гомори

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

Переходим к изложению отдельных свойств алгоритмов метода отсечения.

3.1. Числа имеют (в среднем) тенденцию к возрастанию с увеличением числа переменных и ограничений, ростом порядка коэффициентов задачи и увеличением заполненности матрицы

Это явление кажется естественным, но опыт показывает, что в дискретном программировании «естественное» и «правдоподобное» не всегда оказывается правильным. Точнее говоря, опыт, накопленный на

задачах ЛП, нельзя механически переносить на задачи ЦЛП.

3.2. Прежде всего обращает на себя внимание «нерегулярность», «непредсказуемость» поведения алгоритмов метода отсечения. Для ряда задач оптимальное решение не удавалось получить после многих тысяч итераций, в то время как другие задачи решались за несколько десятков итераций.

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

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

«Нерегулярность» сказывается и в следующем факте, подмеченном рядом исследователей: иногда удается существенно сократить число итераций за счет перенумерации переменных.

Наконец, имеет место немонотонность приближения псевдоплана к оптимальному плану X — с ростом расстояние не обязательно уменьшается и лишь на последней итерации обязательно становится равным нулю.

3.3. Большое влияние на число итераций оказывает правило выбора порождающей строки. Здесь также имеет место «нерегулярность» — в то время как одно

правило приводит к успеху за десятки итераций, другое не дает решения после тысяч итераций.

Сринивасан ([122], см. выше § 2) пытался исследовать это явление, используя понятия угла и расстояния в -мерном евклидовом пространстве. Однако, по-видимому, эти понятия так же плохо подходят для описания задач ЦЛП, как и число ограничений (см. выше).

3.4. При решении задач ЦЛП по методу отсечения имеются как успехи, так и неудачи. Ряд примеров был приведен в § 2.

К наиболее успешным работам следует отнести:

1) Задачи покрытия, в том числе задачи, связанные с минимизацией булевых функций (см. Балинский [50]).

2) Применение к задачам оптимального кодирования (Карп [102]).

3) Применение к задаче оптимального извлечения информации из параллельных систем памяти (Дэй [69]).

Наиболее характерными задачами, для которых имела место неудача, являются:

1) Задачи коммивояжера (Миллер, Таккер, Землин [117]).

2) Задача теории расписаний (Джильо, Вагнер [81]).

3) Некоторые из обобщенных задач покрытия (Балинский [50], Лаулер и Белл [110]).

3.5. В настоящий момент отсутствует исчерпывающее объяснение удач или неудач различных вычислительных экспериментов. Все же для задачи коммивояжера и задачи теории расписаний является правдоподобным следующее соображение.

Формулировка этих задач на языке ЦЛП является «неестественной». Для задачи сравнительно небольшой в «естественной» формулировке, в модели ЦЛП фигурирует большое количество ограничений и переменных. Возможно, что для этих задач более перспективными являются комбинаторные методы (например, метод ветвей и границ для задачи коммивояжера — см. § 3 гл. 10). Впрочем, последнее утверждение является спорным, так как комбинаторные методы очень чувствительны к специфике задач, введению дополнительных условий и т. п.

3.6. По-видимому, успех в решении задач покрытия связан не только с преимуществами алгоритма Мартина,

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

И вообще, выделение отдельных классов эффективно решаемых задач — важная и интересная проблема.

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

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

1) Исследование строения множеств и (см. Гомори [86а]).

2) Исследование свойств правильных отсечений (см. Гомори [84], [87], Бен-Израэль и Чарнс [55], Гловер [82]).

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

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

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