Введение к работе
Актуальность темы. Многие задачи исследования операций, возникающие в экономике, управлении, планировании и других областях, сводятся к моделям оптимизации, в которых все или часть переменных должны принимать целочисленные значения. Условие целочисленности позволяет учесть такие факторы, как неделимость объектов, наличие альтернатив, дискретность процессов, фиксированные доплаты и т.п. Указанные модели, методы их исследования и решения относятся к области целочисленного программирования (ЦП), одного из активно развивающихся направлений дискретной оптимизации (ДО). Целочисленное программирование можно также рассматривать как достаточно универсальный подход к изучению и решению различных классов задач ДО.
Современный этап развития дискретной оптимизации характеризуется разнообразием рассматриваемых моделей и методов решения, дальнейшей разработкой таких направлений как структура и сложность решения задач, теория двойственности, устойчивость решений, многокритериальные задачи, полиэдральный подход, методы отсечения, ветвей и границ, декомпозиции, множителей Лаг-ранжа, приближенные и гибридные алгоритмы, программное обеспечение и экспериментальные исследования. Это нашло отражение в многочисленных статьях и в опубликованных в последнее время монографиях [1,9-11,13,26,34,36].
Сложность решения задач ЦП определяется свойствами целевой функции задачи и допустимой области. Наиболее изученными являются задачи целочисленного линейного программирования (ЦЛП). у которых целевая функция представляет собой линейный функционал, а допустимые решения лежат в выпуклом многогранном множестве конечномерного евклидова пространства. Несмотря на эту специфику, известные задачи ЦЛП, как правило, относятся к числу МР-трудных [4].
Значительная часть методов решения задач ЦП может быть объединена з две большие группы, связанные с развитием следующих основных идей:
сведение исходной задачи ЦП к последовательности более "легких" задач непрерывной оптимизации,
построение различных схем направленного перебора точек, удовлетворяющих условию целочисленности.
- г -
Кроме того, разрабатываются гибридные методы [7,10,34,45, 70.71], в которых эти и другие идеи комбинируются с целью повышения эффективности алгоритмов.
Диссертация посвящена главным образом исследованию и развитию методов первой группы, включающей методы отсечения, ветвей и границ (типа метода Лэнд и Дойг [30]). декомпозиции (с отсечениями Бендерса [18]) и некоторые другие. Характерными особенностями этих методов являются использование релаксационных множеств, дополнительных линейных ограничений (отсечений) и аппарата непрерывной оптимизации. Кроме того, в работе рассматривается ряд гибридных алгоритмов.
Релаксационное множество задачи ЦП определяется системой ограничений, получающейся из исходной путем исключения условия целочисленности и, возможно, некоторых других ограничений. В дальнейшем в процессе решения задачи оно последовательно изменяется с помощью вводимых дополнительных линейных ограничений до получения оптимального решения или другого требуемого результата. Например, в случае ЦЛП решение исходной задачи таким методом сводится к анализу и решению последовательности задач линейного -программирования.
Значительное внимание в диссертации уделяется методу отсечения, который продолжает оставаться идейной основой многих исследований. Важную роль в разработке метода сыграл предложенный и обоснованный Р.Гомори алгоритм для решения общей задачи ЦЛП [23]. В дальнейшем эта проблематика получила развитие в работах Р.Гомори. Э.Балаша, А.Бен-Израэля и А.Чарнса. В.П.Булатова. А.А.Вотякова, Ф.Гловера. М.Гретшеля. Р.Джерос-лоу. М.Падберга, И.Пилера, А.Схрейвера, Ю. Ю. Финкельштейна. В.Хватала, Ю.Ю.Червака, В.Н.Шевченко, Д.Эдмондса, Р.Юнга и многих других авторов.
Весьма плодотворным оказалось использование в качестве отсечений фасетных неравенств, порождающих грани максимальной размерности многогранника задачи ДО (выпуклой оболочки допустимых целочисленных решений задачи) [5,25,26,34]. С их помощью удалось решить задачи коммивояжера большой размерности (рекордная задача имела более 2 тыс. "городов"). Дополнительные линейные ограничения нашли применение в исследовании вопросов сложности решения задач [11,20]. Появились обобщающие работы, направленные на создание теории отсечений [11.29]. В гибридных
- З -методах отсечения комбинируются с методом ветвей и границ и другими подходами [7,10,34.71]. Следует также отметить широкое использование отсечений в методах непрерывной оптимизации [3]. Исследования, связанные с этими подходами, включают разработку способов построения дополнительных линейных ограничений, анализ классов отсечений, области допустимых решений и релаксационных множеств задач, нахождение оценок числа итераций (отсечений) и контрпримеров, сравнение эффективности алгоритмов и отсечений, построение приближенных алгоритмов и др.
В целом, несмотря на значительную развитость рассматриваемого направления, многие теоретические вопросы здесь до последнего времени оставались нерешенными или слабо разработанными. В частности, далеко не исчерпаны возможности использования релаксационных множеств для исследования задач, построения и анализа алгоритмов их решения. Особенно это относится к структуре и сложности решения задач ЦП. проблемам конечности и получения оценок числа итераций (отсечений) алгоритмов. Имеющиеся результаты представляются весьма неполными.
По верхним оценкам числа итераций (отсечений) наиболее заметное продвижение было сделано для двойственных дробных алгоритмов Гомори [23]: сначала оценки были получены автором диссертации [49-52]. а затем в работе [32]. Пока не найдены верхние оценки числа отсечений для прямых алгоритмов отсечения (в общем случае), не известны "явные" (не алгоритмические) верхние оценки числа итераций для двойственных полностью целочисленных алгоритмов отсечения.
Результаты по нижним оценкам в основном связаны с построением семейств "трудных" задач, показывающих возможность экспоненциального роста числа итераций (с увеличением размерности задачи), а также как угодно большого их числа или бесконечности процесса решения. К ним относятся нижние оценки максимального числа итераций для полностью целочисленного алгоритма Гомори [12], прямьк алгоритмов отсечения [48,53.60] и метода ветвей и границ [28], контрпримеры для рудиментарного прямого алгоритма [31,53,60] и ряд других. Показана возможность получения любого числа итераций первого алгоритма Гомори (для задачи малой размерности) [27]. Следует отметить, что рассматриваемые работы (и данная диссертация) посвящены исследованию поведения алгоритмов в наихудшем случае.
.- .. .., - 4' -Указанные оценки получены в основном для задач ЦЛП. Они выражены, как правило, в,терминах размерности задачи (числа переменных и ограничений), а также некоторых специальных параметров, зависящих от ее исходных данных. Например, с этой целью часто используется максимум абсолютной величины коэффициентов, входящих в эти данные. Применение таких общих параметров позволяет охватить широкий класс задач ЦП и в этом достоинство подхода. Они используются и при оценке эффективности других алгоритмов [10.11.16.17].
Вместе с тем, естественно, что в подобных оценках слабо учитывается специфика конкретной задачи, в частности, строение ее релаксационного множества, которое существенно используется в методах и влияет на процесс решения. В результате для многих задач указанные оценки могут сильно отличаться от числа реально выполненных итераций. Поэтому, на наш взгляд, весьма перспективным представляется нахождение оценок числа итераций (отсечений) , в которых учитывается структура релаксационных множеств задач, ЦП. Такие "структурные" оценки позволят лучше понять особенности и возможности рассматриваемых методов, объяснить различные эффекты, которые- наблюдались в вычислительном эксперименте, (трудности решения некоторых задач малой размерности, успехи в решении достаточно больших задач, проблемы ускорения алгоритмов и пр.), наметить пути улучшения известных и разработки новых алгоритмов. На их основе можно получать оценки числа итераций через исходные параметры задач, выделять семейства задач с различными свойствами.
Из сказанного выше вытекает актуальность развития специальных подходов к анализу рассматриваемых методов и получения оценок числа итераций (отсечений) для различных классов задач ЦП, в том числе и нелинейных.
Цель работы. Разработка методов исследования и решения задач целочисленного программирования на основе регулярных разбиений релаксационных множеств и лексикографии, их применение к указанным выше классам алгоритмов (отсечения, ветвей и границ, декомпозиции и др.)
Научная новизна. В диссертации проведено исследование ряда задач и методов целочисленного программирования, предложены алгоритмы их решения с использованием введенных автором регулярных разбиений релаксационных' множеств. Важную роль в этом
- 5 -подходе играют лексикография и дробные накрытия задач ЦП. Дробное накрытие представляет собой множество всех точек релаксационного множества, лежащих между лексикографически опта-, мальными решениями задачи ЦП и соответствующей ей "непрерывной" задачи. Оно должно быть "снято" (исключено) в процессе решения.,
С помощью регулярных разбиений исследуется сложность решения задач ЦП. в частности, измеряется "объем" дробного накрытия, изучается строение релаксационных множеств, вводятся и исследуются классы отсечений, определяется их глубина, разрабатываются и сравниваются алгоритмы, анализируются последовательности приближений, находятся оценки числа итераций (отсечений), проводятся экспериментальные исследования алгоритмов и тестовых задач.
Значительная часть результатов получена с помощью L-разбиения. которое в определенном смысле согласовано с лексикографическим порядком. Элементы такого разбиения произвольного множества в Rn называются L-классами, а L-разбиение дробного накрытия задачи - ее L-накрытием.
Основные результаты диссертации заключаются в следующем.
1. Предложен и развит подход к исследованию и решению задач целочисленного программирования, основанный на применении регулярных разбиений релаксационных множеств. С помощью этого подхода
описан класс регулярных разбиений и некоторые его подклассы, найден и исследован ряд таких разбиений (L-разбиение. каноническое, кубические и др.); изучена структура L-разбиения * многогранников некоторых известных задач дискретной оптимизации (о рюкзаке, покрытии, упаковки и др.). в частности, оценена сверху мощность их L-накрытий; показано, что некоторые из многогранников обладают в определенном смысле наилучшей (альтернирующей) L-структурой; для задач линейного булева программирования установлена связь между L-разбиением и множеством вершин релаксационного многогранника;
введены классы отсечений, регулярных относительно рассматриваемых разбиений; для L-разбиения найдены отсечения (Р-отсечения и др.). глубина которых ограничена сверху числом целочисленных переменных задачи; в классе Р-отсечений выделен подкласс вполне регулярных отсечений и показано, что в нем со-
держится ряд известных отсечений: для задач булева программирования исследован класс вполне регулярных отсечений, получены необходимые и достаточные условия принадлежности линейного неравенства этому классу, выделена "самая сильная" система неравенств в некотором расширении указанного класса, проведено сравнение алгоритмов с такими отсечениями;
разработаны алгоритмы для решения задач ЦП и измерения мощности их L-накрытий, основанные на переборе L-классов, в том числе гибридные и декомпозиционные алгоритмы для частично целочисленных производственно-транспортных задач, в которых используются отсечения Гомори и Бендерса, алгоритм отсечения для задачи упаковки;
предложены методы построения оценок 'числа итераций (отсечений), для указанных алгоритмов; в терминах регулярных разбиений, глубины отсечений и ряда параметров задач ЦП получены верхние (а в ряде случаев и нижние) оценки числа итераций для алгоритмов перебора L-классов, двойственных дробных алгоритмов отсечения, включая известные алгоритмы Гомори, и других алгоритмов; исследованы некоторые алгоритмы ветвей и границ (метода Лэнд и Дойг). в частности, показана их регулярность относительно канонического разбиения, получены верхние оценки числа итераций;
-
Построены семейства задач, приводящие к бесконечному процессу для любого варианта рудиментарного прямого алгоритма отсечения, верхние оценки числа итераций (в случае задачи ЦП на плоскости) и нижние оценки максимального числа итераций для конечных прямых алгоритмов отсечения, найдены некоторые верхние оценки числа итераций для двойственного полностью целочисленного алгоритма отсечения.
-
Проведены экспериментальные исследования на ЭВМ алгоритмов отсечения, перебора L-классов. ветвей и границ, гибридных алгоритмов, получены данные об L-накрытиях задач ЦП.
Методы исследования. При выполнении работы использовались теория и методы математического программирования, ряд разделов выпуклого анализа, последние достижения в области дискретной оптимизации.
Практическая значимость. Развитые в диссертации методы могут быть рекомендованы для построения и исследования новых алгоритмов решения задач ЦП. разработки программного обеспече-
- 7 -ния. Ее материалы применяются в процессе подготовки студентов и аспирантов на математическом факультете Омского государственного университета, в частности, в спецкурсе по методам дискретной оптимизации. На их основе опубликовано учебное пособие [60].
Под руководством автора создан комплекс программ для ПК типа IBM PC/AT. в котором реализованы предложенные в работе алгоритмы перебора L-классов и гибридные алгоритмы, а также ряд известных алгоритмов отсечения ЦП. проведены экспериментальные исследования, решен ряд задач оптимального планирования. Комплекс программ используется в научно-исследовательской работе и учебном процессе в ОмГУ.
Апробация работы. Результаты диссертации докладывались на III. IV, V ( Новосибирск, 1974. 1977, 1980) и VII] (Горький. 1988) Всесоюзных конференциях по проблемам теоретической кибернетики. Всесоюзной конференции по исследованию операций (Шушенское, 1979), Международных и сибирских школах-семинарах по методам оптимизации (Иркутск, 1980, 1986 ,1989, 1992), конференциях по математическому программированию и приложениям (Свердловск, 1981. 1984. 1S87, 1989. 1991. Екатеринбург. 1993.1995). Всесоюзных семинарах по дискретной математике и ее приложениям (Москва. 1981. 1984). Всесоюзных симпозиумах по программному обеспечению (Усть-Нарва. 1976, 1982, 1988, Минск, 1986), II Всесоюзной школе-семинаре "Дискретная оптимизация и приложения" (Кишинев, 1983), Межреспубликанских семинарах по дискретной оптимизации (Крым, 1984, 1987.1989-1991), Ш и IV Всесоюзных совещаниях "Оптимизация на сетях и графах" (Ташкент, 1984, Новосибирск, 1989). Республиканских семинарах по дискретной оптимизации (Ужгород. 1985. 1989). III Всесоюзной школе-семинаре "Дискретная оптимизация и компьютеры" (Таш-тагол, 1987), Одесском семинаре по дискретной математике и смежным вопросам (1990, 1991.1993.1994). I и II Всесоюзных семинарах по дискретной оптимизации и исследованию операций (Новосибирск. 1990, 1992), 16-й Международной конференции IFIP по моделированию систем и оптимизации (Франция, 1993), международной конференции IFIP по моделированию и проектированию на базе оптимизации и компьютеров (Чехия. 1994), международном симпозиуме по транспортным проблемам (Италия. 1994), а также на научно-исследовательских семинарах в Институте кибернетики
- 8 -АН УССР. Институте математики СО АН РАН. ВЦ СО РАН, Институте математики и механики УрО РАН. Институте информационных технологий и прикладной математики СО РАН, Международном институте прикладного системного анализа (Австрия, Лаксенбург) и др.
Публикации. Основные результаты диссертации опубликованы в работах [38-82].
Структура и объем работы. Диссертация состоит из введения, пяти глав, списка литературы (189 наименований) и приложения. В каждой главе использована своя нумерация параграфов. , утверждений, лемм, теорем, примеров и формул. Общий объем диссертации - 284 страницы.