§ 2. Результаты вычислительных экспериментов

В этом параграфе кратко излагаются некоторые результаты вычислительных экспериментов. Авторы не старались сделать свой обзор исчерпывающим, но лишь достаточно полным, чтобы дать основу для обобщающего § 3. Материал расположен в основном в хронологическом порядке. Особо следует отметить обзор Балинского [50], содержащий интересный материал по эффективности алгоритмов метода отсечения.

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

Переходим теперь к обзору отдельных работ.

Гомори [89], 1960 г. Машинный эксперимент по первому алгоритму Гомори привел к успешному решению задач с числом переменных, не превышающим 15.

Миллер, Таккер, Землин [117], 1960 г. Предложена модель ЦЛП для задачи коммивояжера (и некоторого ее обобщения, см. § 3 гл. 2). По этой модели проделано пять вычислительных экспериментов (с числом городов, равным 4 и 10). Использовался первый алгоритм Гомори. Удачными оказались лишь два эксперимента.

Гасс [78], 1961 г.. Сообщаются сведения о трех программах для решения полностью целочисленных задач ЛП по третьему алгоритму Гомори.

Карп [102], 1961 г.. Сообщается об успешном практическом использовании алгоритма Гомори для решения одной задачи оптимального кодирования.

Ояхиа [118], 1962 г. Проводились машинные эксперименты по третьему алгоритму Гомори. Принималось не только лексикографическое право выбора порождающей строки (см. п. 2.4 гл. 7), но и некоторые другие правила. Для одной и той же задачи (20 неравенств, 29 переменных) один из вариантов алгоритма дал решение за 70 итераций, а другой — не привел к решению после 30 000 итераций.

Женюи [79], 1963 г. Рассматривалась некоторая задача раскроя, при решении которой возникает вспомогательная задача ЦЛП. Проведен машинный эксперимент по решению вспомогательных задач сравнительно небольшого размера по алгоритму Гомори. Значительная часть задач не была решена после нескольких десятков тысяч итераций.

Стори, Вагнер [123], 1963. Решались задачи теории расписаний с тремя машинами и различным количеством деталей. Использовалась модель ЦЛП, предложенная ранее одним из авторов (см. Вагнер [126]). Эта модель содержит переменных и уравнений (здесь количество деталей). По третьему алгоритму Гомори решались задачи с числом деталей от 4 до 9. В частности, для задачи с 7 деталями (число перестановок равно 5040) три задачи были решены (за 85, 105 и 78 симплексных итераций соответственно), а три задачи не были решены после 1000 симплексных итераций.

Для задачи с 4 деталями проводилось решение по различным модификациям первого и второго алгоритмов Гомори, отличающимся друг от друга правилом выбора порождающей строки. Оказалось, что изменение

правила выбора может сильно влиять на продолжительность вычислений.

Джильо, Вагнер [81], 1964 г. Рассматривалась целочисленная линейная модель для задачи теории расписаний с тремя машинами и шестью деталями (число перестановок равно 720). Решение проводилось по третьему алгоритму Гомори. Некоторые из решавшихся задач были решены за сравнительно небольшое число итераций, другие — более чем за 720 итераций. Отдельные задачи не были решены за 10 000 итераций.

Мартин [116], 1963 г. Предложен новый алгоритм, являющийся модификацией первого алгоритма Гомори. Решены некоторые задачи, не решавшиеся другими алгоритмами метода отсечения, в частности одна задача с 54 неравенствами и 442 переменными.

Как сообщают Балинский и Куондт [51] (1964 г.) по алгоритму Мартина были успешно решены девять обобщенных задач покрытия (возникших из практических задач развозки, см. п. 1.5 гл. 3). В этих задачах число неравенств число переменных Одна задача не была решена после 200 симплексных итераций.

В обзоре Балинского [50] (1965 г.) сообщается о решении по алгоритму Мартина серии комбинаторных задач (возникающих из задач планирования) при следующих размерах:

Эти задачи имеют матрицы ограничений, на 85% состоящие из нулей, причем из ненулевых элементов — около 85% единиц. Решены были также задачи размером и (215,2600). Все эти задачи решались с введением сравнительно небольшого количества правильных отсечений. Балинский считает, что этот успех достигнут не только за счет преимуществ алгоритма Мартина, но и за счет некоторых удачных свойств данного класса задач.

ДЭзоп о, Лефковиц [71], 1964 г. Рассматривается задача распределения грузов по транспортным

судам при минимизации общего количества используемого транспорта. Строится модель ЦЛП. Ряд задач решен по третьему алгоритму Гомори (число типов судов число неравенств число переменных Число итераций колебалось от 94 до 447.

Сринивасан [122], 1965 г. Исследовались различные модификации первого алгоритма Гомори, в которых понятия угла и расстояния в -мерном евклидовом пространстве использованы для выбора порождающей строки. Во всех экспериментах количество переменных , количество ограничений В качестве тестовых были выбраны несколько моделей ЦЛП, являющихся формализациями известных прикладных задач. Задача размером была решена по 4 модификациям из 5, а по пятой не была решена после 300 симплексных итераций. Другая задача размером не была решена ни по одной из модификаций после 600 симплексных итераций.

Хэлди, Айзексон [98], 1965 г. Авторы поставили перед собой задачу показать, что первый алгоритм Гомори является не менее эффективным, чем некоторые другие алгоритмы метода отсечения (отвечая тем самым на скептическое отношение ряда исследователей к практической значимости первого алгоритма Гомори). На ряде тестовых задач небольшого размера была подтверждена эффективность первого алгоритма Гомори. При расчетах использовался лексикографический критерий выбора порождающей строки (сам Гомори пользовался этим критерием для доказательства конечности алгоритма, но не предлагал его для практического использования).

Дэй [69], 1965 г. Задача оптимального извлечения информации из параллельных систем запоминания сводится к модели ЦЛП и решается по алгоритму Гомори. Опыт показал возможность успешного решения практических задач.

Балинский [50], 1965 г. В этом обзоре много места уделено эффективности алгоритмов метода отсечения. Остановимся лишь на некоторых, наиболее интересных фактах, основанных на личном опыте автора и на публикациях, практически недоступных для советского читателя.

В Сиднейском университете были успешно решены (на практическом материале) по второму алгоритму Гомори шесть задач размером

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

В ряде вычислительных экспериментов замечено, что число итераций сильно зависит от

а) выбора порождающей строки,

б) перенумерации переменных.

Зондерман [121], 1967 г. Предложенный автором новый вариант симплекс-метода был «вложен» во второй алгоритм Гомори. Некоторые задачи не были решены после значительного количества итераций (например, одна из задач — после 1500 итераций). Размеры задач не названы.

Теплицкий, Финкельштейн [27], 1968 г. Проводилось сравнительное исследование -алгоритма Финкельштейна (см. § 4 гл. 6) и двух алгоритмов Гомори: первого и второго. Решались так называемые «канонические» задачи (см. [30]) следующего вида.

Максимизировать

при условиях

При наборе статистики условия задач формировались при помощи датчика псевдослучайных чисел — отдельно и независимо выбиралась каждая из величин по приведенным ниже правилам.

Коэффициенты и целые числа, равномерно распределенные на отрезке [0, 9]. Коэффициенты целые числа, равномерно распределенные в Решение канонических задач проводилось на ЭВМ типа

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

I. Полностью целочисленные задачи Матрица имела для разных групп задач размеры .

II. Частично целочисленные задачи Матрица А имела для разных групп задач размеры .

Для каждой из групп задач приведены следующие данные: число решавшихся задач; число задач, не решенных по -алгоритму; число задач не решенных по алгоритму Гомори; общее количество правильных отсечений, введенных в процессе решения задачи (отдельно для каждого из двух алгоритмов); 5 — суммарное количество итераций метода последовательного уточнения оценок, затраченных на приведение симплексной таблицы к допустимой и нормальной форме (отдельно для каждого из двух алгоритмов); суммарное количество итераций метода последовательного уточнения оценок, затраченных на приведение симплексной таблицы к -нормальной форме, количество итераций метода последовательного уточнения оценок, при котором задача считалась нерешенной.

Для величин приведены границы изменения, математическое ожидание и среднеквадратическое отклонение а.

В статистику были включены все решавшиеся задачи, в том числе задачи, решение которых: а) доведено до конца, причем получен правильный ответ; б) не доведено до конца; в) доведено до конца, причем получен неправильный ответ.

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

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

Представляет интерес тот факт, что для всех групп задач имеются задачи, решаемые очень быстро по В-ал-горитму и достаточно долго по алгоритму Гомори. Для других задач явление обратное. Это, по-видимому, объясняется тем, что формирование правильных отсечений у алгоритмов Гомори и -алгоритма основано на разных принципах.

Результаты эксперимента позволяют предполагать, что -алгоритм лучше работает на задачах, у которых много целочисленных планов.

В двух группах задач 1-й серии ((2, 8) и (10, 8)) были выявлены задачи, для которых при решении по алгоритму Гомори количество правильных отсечений превысило объем полного перебора

Следует отметить, что в составленной программе при проверке целочисленности элементов симплексной таблицы проверялось условие

Здесь расстояние от до ближайшего целого числа.

В случае выполнения неравенства (2.1) а считалось целым числом, однако в симплексной таблице а на ближайшее целое не заменялось. Этот прием позволил успешно бороться с влиянием ошибок округления. Для использовались значения

В докладе Хохлюка [36] (1967 г.) исследовалась эффективность первого и третьего алгоритмов Гомори, а также алгоритма Мартина. Рассматривались задачи трех типов:

1. Задача о ранце с многими ограничениями.

2. Целочисленная распределительная задача.

3. Задача специального вида с коэффициентами при переменных, равными и неравенствами. Здесь количество переменных. Все переменные булевы.

Приведем некоторые результаты эксперимента.

Задача 1. а) Первый алгоритм Гомори дал плохие результаты при больших (двух- и трехзначных) коэффициентах. Известная задача Лэнд и Дойг [109] не была решена.

б) Алгоритм Мартина не дал решения задачи Лэнд и Дойг, так как возникшие в процессе решения большие числа оказались вне разрядной сетки машины.

в) Третий алгоритм Гомори дал хорошие результаты при числе переменных .

Задача 2 решалась по первому алгоритму Гомори. Получены хорошие результаты (при целых коэффициентах, по модулю не превышающих 10).

Задача 3. Условия задачи были подобраны таким образом, что вершин -мерного единичного куба (из общего числа были ее планами.

Задача решалась по третьему алгоритму Гомори, . Во всех случаях количество итераций

Пусть X — оптимальный план задачи 3, а псевдоплан, полученный на итерации третьего алгоритма Гомори. Оказалось, что в условиях задачи 3 расстояние монотонно не убывает до последней итерации и лишь последняя итерация обращает в нуль.