Регулярные разбиения и отсечения в целочисленном программировании тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах, рукописи

КОЛОКОЛОВ Александр Александрович

РЕГУЛЯРНЫЕ РАЗБИЕНИЯ И ОТСЕЧЕНИЯ В ЦЕЛОЧИСЛЕННОМ ПРОГРАММИРОВАНИИ

01.01.09 - Математическая кибернетика

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Иркутск - 1995

Работа выполнена в Институте информационных технологий и прикладной математики СО РАН (г.Омск).

Официальные оппоненты - доктор физико-математических наук.

профессор В.П.Булатов,

Ведущая организация - Институт математики и механики УрО РАН

Защита диссертации состоится И августа 1995 г. в 10.00 часов на заседании Совета Д063.32.04 по защите диссертаций на соискание ученой степени доктора наук в Иркутском государственном университете по адресу: 664000, Иркутск, бульвар Гагарина, 20, 1-й корпус ИГУ.

С диссертацией можно ознакомиться в библиотеке Иркутского государственного университета (бул. Гагарина, 24).

Автореферат разослан \£_ июня 1Э95 г.

доктор физико-математических наук, профессор Э.Х.Гимади, доктор физико-математических наук, профессор В.Н.Шевченко.

Ученый секретарь Совета к.ф.-м.н., доцент

Н.Б.Бельтюков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Современный этап развития дискретной оптимизации характеризуется разнообразием рассматриваемых моделей и методов решения. дальнейшей разработкой таких направлений как структура и сложность решения задач, теория двойственности, устойчивость решений, многокритериальные задачи, полиэдральный подход, методы отсечения, ветвей и границ, декомпозиции, множителей Лаг-ранжа, приближенные и гибридные алгоритмы, программное обеспечение и экспериментальные исследования. Это нашло отражение в многочисленных статьях и в опубликованных в последнее время монографиях [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].

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

Из сказанного выше вытекает актуальность развития специальных подходов к анализу рассматриваемых методов и получения оценок числа итераций (отсечений) для различных классов задач ЦП, в том числе и нелинейных.

Цель работы. Разработка методов исследования и решения задач целочисленного программирования на основе регулярных разбиений релаксационных множеств и лексикографии, их применение к указанным выше классам алгоритмов (отсечения, ветвей и границ, декомпозиции и др.)

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

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

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

Значительная часть результатов получена с помощью Ь-раз-биения. которое в определенном смысле согласовано с лексикографическим порядком. Элементы такого разбиения произвольного множества в й" называются Ь-классами, а 1-разбиение дробного накрытия задачи - ее Ь-накрытием.

Основные результаты диссертации заключаются в следующем.

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

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

- введены классы отсечений, регулярных относительно рассматриваемых разбиений; для Ь-разбиения найдены отсечения (Р-отсечения и др.). глубина которых ограничена сверху числом целочисленных переменных задачи; в классе Р-отсечений выделен подкласс вполне регулярных отсечений и показано, что в нем со-

держится ряд известных отсечений; для задач булева программирования исследован класс вполне регулярных отсечений, получены необходимые и достаточные условия принадлежности линейного неравенства этому классу, выделена "самая сильная" система неравенств в некотором расширении указанного класса, проведено сравнение алгоритмов с такими отсечениями;

- разработаны алгоритмы для решения задач ЦП и измерения мощности их Ь-накрытий, основанные на переборе Ь-классов, в том числе гибридные и декомпозиционные алгоритмы для частично целочисленных производственно-транспортных задач, в которых используются отсечения Гомори и Бендерса, алгоритм отсечения для задачи упаковки;

- предложены методы построения оценок 'числа итераций (отсечений), для указанных алгоритмов; в терминах регулярных разбиений, глубины отсечений и ряда параметров задач ЦП получены верхние (а в ряде случаев и нижние) оценки числа итераций для алгоритмов перебора Ь-классов, двойственных дробных алгоритмов отсечения, включая известные алгоритмы Гомори, и других алгоритмов; исследованы некоторые алгоритмы ветвей и границ (метода Лэнд и Дойг). в частности, показана их регулярность относительно канонического разбиения, получены верхние оценки числа итераций;

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

3. Проведены экспериментальные исследования на ЭВМ алгоритмов отсечения, перебора Ь-классов. ветвей и границ, гибридных алгоритмов, получены данные об Ь-накрытиях задач ЦП.

Методы исследования. При выполнении работы использовались теория и методы математического программирования, ряд разделов выпуклого анализа, последние достижения в области дискретной оптимизации.

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

ния. Ее материалы применяются в процессе подготовки студентов и аспирантов на математическом факультете Омского государственного университета, в частности, в спецкурсе по методам дискретной оптимизации. На их основе опубликовано учебное пособие [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), а также на научно-исследовательских семинарах в Институте кибернетики

АН УССР, Институте математики СО АН РАН. ВЦ СО РАН, Институте математики и механики УрО РАН. Институте информационных технологий и прикладной математики СО РАН, Международном институте прикладного системного анализа (Австрия, Лаксенбург) и др.

Публикации. Основные результаты диссертации опубликованы в работах [38-82].

Структура и объем работы. Диссертация состоит из введения. пяти глав, списка литературы (189 наименований) и приложения. В каждой главе использована своя нумерация параграфов, утверждений, лемм, теорем, примеров и формул. Общий объем диссертации - 284 страницы.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы диссертации, излагаются идеи.'лежащие в основе предлагаемых методов, дается общая характеристика полученных результатов и их краткое изложение.

Глава 1 посвящена описанию предложенных наш методов исследования на основе регулярных разбиений релаксационных множеств и лексикографии. Основные результаты главы опубликозаны В [49-52,60,61,65-67,71-74].

В п.1.1. 1.2 приводятся исходные постановки задач ЦП и ряд свойств лексикографического порядка, "округлений" векторов и множеств. Особое внимание уделяется лексикографическим задачам. которые используются при разработке и исследовании методов решения.

Пусть 2 - непустое замкнутое множество в пространстве И", п>1. - множество всех вещественных п-векторов, у которых

первые Ю1 координат являются целыми. Если К=п, то гп,к совпадает с множеством всех целочисленных векторов и обозначается 1п. Предположим, • что 2 имеет лексикографически максимальный элемент х*. Рассмотрим лексикографическую задачу ЦП следующего вида: найти лексикографически максимальную точку 2. множества (ЙГЕп'к), т.е. требуется найти

г, = 1ехтах (О П 2п-к). (1)

Любой вектор из (О П гп-к) называется допустимым решением. а г. - оптимальным. Нами также изучается задача ЦП для к=п: найти

- 9 -

г. = 1ехшах (Й П 2п). (2)

Множествой называется релаксационным.

Важную роль в исследовании задачи (1). и методов решения играет ее дробное накрытие

й. = (х е й: х > 2 для любого 2 € (О П гп ■к)). Здесь и в дальнейшем >, >. - символы лексикографического сравнения. В случае й П гп-к = 0 получаем Й. = Й. Выделение этой части релаксационного множества задачи связано с тем, что в рассматриваемых нами методах ЦП происходит последовательное исключение точек из й.. т.е. эти методы можно рассматривать как определенные способы "снятия" дробного накрытия.

Для обеспечения существования г, (при й П 1п * * а) нами в основном используется требование ограниченности -й сверху: найдется й еИп такой, что х < сЗ для всех х ей. Класс замкнутых ограниченных сверху множеств обозначим Кв.

В п.1.3 излагается идея подхода в ЦП, основанного на применении регулярных разбиений, описывается класс таких разбиений, приводятся примеры разбиений.

Пусть х. у еИ™ и х > у. Будем говорить, что векторы х и-у отделит, если найдется г е 2°, для которого выполняется х > г > у. Точку г назовем отделяющей. Имеется тесная связь между отделимостью и "округлениями" векторов.

Пусть Вп={х: 0 < х1< 1. 1=1.....п). Каждой вершине 5 еВ"

поставим в соответствие обозначаемое тем же символом (для простоты) отображение б: ¡?п— >Еп, называемое округлением, по правилу х —> г=5(х), где [х} ], если б^О. и г^Х! [. если

=1. 1=1.....п. Таким образом, рассматривается 2П различных

округлений. Зафиксируем некоторое округление 5 . Множество целочисленных векторов, получающихся с помощью округления б всех элементов данного множества X £ И" обозначим через 5(Х).

В вопросах отделимости важную роль играют специальные пары округлений. Округления 5 и б* называются взашлньили, если для соответствующих им векторов выполняется 5 +5* = еп, где

е„=(1.....1)т. Если х и у отделимы, то одна из отделяющих их

точек содержится в множестве (5(х).б(у),б* (х).б" (уН. Лексикографическая отделимость тесно связана с рассматриваемыми ниже разбиениями множеств.

В соответствии с нашим подходом в пространстве И" вводится разбиение Р. которое индуцирует разбиение релаксационного

множества и обладает следующими свойствами (в случае к=п):

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

b) если 'X - ограниченное множество, то фактор-множество ЬТ - конечное;

c) для любого X с И" и любого г ег" имеет место (Х+г)/Г -(Х/Г) + г.

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

Элементы из Х/Т называются Е -классами, а множество Й./Е - ¥-жкршием. задачи (1).

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

Пусть X,У - некоторые непустые множества из И". Будем говорить, что X лексикографически больше У и писать X > У, если х > у для любых х е X, у € у. Запись X > У означает, что либо X >У. либо X = У.

Важную роль в изучении задач и методов ЦП играет свойство согласованности разбиения с лексикографическим порядком. Будем считать, что регулярное разбиение Г обладает указанным свойством, если введенное выше отношение лексикографического сравнения множеств является линейным порядком в Яп/е.

Точки х.у е йп (х*у) называются I-эквивалентными, если не существует отделяющей их точки 2 егп. Данное отношение эквивалентности порождает разбиение пространства Нп. называемое Ь-разбиением. Показано, что это разбиение является регулярным, согласовано с лексикографическим порядком и существенно зависит от упорядочения координат в

Для задачи (1) предложено I*-разбиение, совпадающее с Ь-разбиением в случае к=п. Оно определяется следующим образом: точки х, у из Еп принадлежат различным классам разбиения <=> найдется номер б < к такой, что хЕ * у8 и эти точки отделимы.

Рассмотрим примеры других регулярных разбиений. Кубическое разбиение, отвечающее округлению 5. определяется условия-

- и -

ми: каждая точка z е Z" образует отдельный класс разбиения, а нецелочисленные точки х и у принадлежат одному классу, если они 5-эквиваленты, т.е. 5(х) = 5(у).

С помощью взаимных округлений вводится более мелкое каноническое разбиение К. Пусть 5 и 5* - взаимные округления. Точки х и у являются К-эквивалентными, если одновременно выполняются соотношения: 5(х) = б(у). 5*(х) = 5* Су)-

В этом же параграфе рассмотрены некоторые другие разбиения и связь введенных разбиений с разбиениями, порождаемыми совокупностями гиперплоскостей и полупространств.

Кубические и каноническое разбиения в общем случае не обладают свойством согласованности с лексикографическим порядком. Если исключить требование лексикографической сравнимости дробных классов разбиения, то мы приходим к следующему определению. Будем говорить, что разбиение F частично согласовано с лексикографическим порядком, если для любого дробного класса VeRn/F и любого z eZn имеет место либо V > z, либо г >4.

Теорема 1.5. Пусть F - разбиение пространства Rn , удовлетворяющее условию "а" в определении регулярного разбиения. Разбиение F частично согласовано с лексикографическим порядком тогда и только тогда, когда оно либо совпадает„ с L-разбиением. либо является его измельчением.

Разбиение К является измельчением L-разбиения, а любое кубическое для п ) 2 не обладает этим свойством.

Теорема 1.в.. Пусть X я Rn и 5 - некоторое кубическое разбиение. Любой, дробный класс множества Х/5 состоит не более чем из п L-классов.

Оценка является точной, из нее вытекает, что |X/L|<n|X/5| [60]. В частично целочисленном случае п заменяется на к.

В п. 1.4 исследуются последовательности векторов на основе лексикографии и разбиений пространства.

Пусть F - регулярное разбиение, S={x(t)}.teT - последовательность точек из Rn. Последовательность S называется F-регулярной, если любой класс из R"/F содержит не более одного ее члена. С помощью округлений получены верхние оценки числа элементов L-регулярной последовательности, которые были использованы при выводе верхних оценок числа отсечений для первого алгоритма Гомори [49-52]. Для Xs Rn положим Х0= Xnzn. X, =Х\Х0.

- 12 -

Теорема 1.8. Пусть X - ограниченное множество в Rn, причем Хг*0. и б, 6* - взаимные округленш. Для любой L-регуляр-ной последовательности S точек из Xf имеет место оценка |S| < |6(Xt)U5*(Xf)| -1.

Отсюда, например, следует, что длина любой L-регулярной последовательности векторов из Bnf не превышает 2п-1.

В п.1.5 излагается метод получения верхних сценок длины лексикографически монотонных последовательностей, с помощью которого нами впервые были получены верхние оценки числа итераций (отсечений) для двойственных алгоритмов Гомори [49].

Глава 2 посвящена более глубокому изучению структуры L-разбиения (L-структуры) множеств. Излагаемые здесь результаты используются в дальнейшем для нахождения оценок числа итераций и построения алгоритмов. Основные результаты главы опубликованы В [54,55,59-61.63.65.70-72,74-78].

В п.2.1 даются необходимые определения и изучается L-структура релаксационных множеств некоторых задач ЦП.

Подмножество Q дробнЫх классов из X/L называется L-комплексом, "если для любых V. V' е q, (V > V') не найдется г еХ0 такой, что V >-z > V'. L-комплекс. который не является собственным подмножеством некоторого другого L-комплекса, называется полным. Через С(X) обозначим совокупность всех L-комплек-сов, порождаемых X.

Положим ¥(Х)= max{|Q|: 0. еС(Х)}. Так как Q./L является L-комплексом. то |Q./L|< ViQ). Если X содержится -в параллелепипеде Р={х: ad < Xj < а'л> J=1____n), причем все a.,, а'ае Z,

то ¥(Х) < |P0|-1. Пусть M(A.b) = (x: Ax < b, x > 0). где А -(mxn)-матрица, b - m-вектор. Имеет место

Теорема 2.1. Если А > 0 и b ) 0, то имеет место оценка ЧЧМ(А.Ь)) < п.

Данная оценка достигается, например, на симплексе, определяемом неравенствами 2(en.x) < 1, х > 0. Аналогичный результат справедлив и для системы Ах > b, х ) 0 с неотрицательными исходными данными. Условие неотрицательности коэффициентов матрицы А можно несколько ослабить [61].

В этом же параграфе даны примеры многогранников, имеющих "мощные" комплексы дробных L-классов. В частности, показано, что в контрпримере Джерослоу [28] мощность L-комплекса может расти экспоненциально с увеличением п.

- 13 -

В п.2.2 выделяются и изучаются множества, обладающие в определенном смысле наилучшей (альтернирующей) Ь-структурой. Будем говорить, что множество X имеет альтернирующую Ь-струк-туру. если выполняются условия:

1) Ч»(Х) <1;

2) лексикографически максимальный и минимальный элементы множества Х/Ь являются целочисленными (если они существуют);

3) для любых г. г' е Х0 {г > г') найдется V е х/Ь такой, что г > V > 2'.

Для выпуклых множеств условие "3" всегда выполняется. Установлено, что альтернирующую Ь-структуру имеют параллелепипед Р. симплекс Б и слой С

п 11

Б={х: I X! <р. X! > ^,1=1.....п>, С={х: а < I хг < 0} ,

1=1 1=1

если а, р и все принадлежат 2. а также их пересечения.

Альтернирующая Ь-структура используется для построения оценок мощности Ь-накрытий и числа итераций алгоритмов отсечения. при разработке алгоритмов. Нами получен критерий альтернируемое™ для выпуклых множеств .[63] и показано, что альтернирующей Ь-структурой обладают многогранники задач упаковки и покрытии множеств, ряда других задач.

Целочисленные многогранные множества в общем случае не обладают такой структурой. Однако для задач БП справедлива

Теорема 2.6. Любое целочисленное многогранное множество, лежащее в В" , имеет альтернирующую Ь-структуру.

Эта теорема является следствием более общего результата, приводимого в п. 2.4., который связан с распределением нецелочисленных вершин многогранников задач БП по дробным Ь-классам [72,77.78].

В п. 2.3 находятся верхние оценки мощности Ь-накрытий через исходные параметры задач ЦП, на основе которых в следующих главах получаются верхние оценки числа итераций и отсечений.

Общим методом построения верхних оценок для через

исходные параметры задач является погружение О, в различные множества с последующим оцениванием числа целочисленных точек в них. Предположим, что дробное накрытие задачи (2) содержится в ограниченном множестве X. Тогда:

- 14 -

1) |Q./L| <Y(X)(|X0|+1K

2) если X имеет альтернирующую L-структуру и Хо*0, то IQ./LKIXJ-1:

3) если А > О. Ь > О и X = М(А.Ь). то |Q,/L| ( п|Х0|.

Мы применяли погружения дробных накрытий задач ЦП в выпуклые многогранники (параллелепипеды, симплексы, слои и' другие), для которых относительно легко строятся верхние оценки числа целочисленных точек. Например, в случае Х=Р получаем

п

|fi./L| <-1 + П (a'j - а3 + 1).

Следовательно, для Q. из куба В" выполняется |Q./L| < 2n-l. Имеются примеры, для которых указанные оценки достигаются.

Перейдем к построению верхних оценок мощности L-накрытия задачи ЦЛП:

х0 = (с,х) —> max (3)

при условиях

А х < Ь, х >0, (4)

X е zn. (5)

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

X' = (Х0 . Xj____Хп)т И М' = {х' cRn + 1 : х0 - (с, X) =0, X е М).

Тогда соответствующая ей задача (2) имеет вид: найти z. = lexmax (М' П Zn+1).

Введем множество

М. если М0 =0,

и М2, если М0 - и.

где М4 = {х еМ: (с,х)>(с,2:")}_ М2 = {х е М: (с.хЖс.г"), х > г").

Предположим, что М" ограничено и х" - оптимальное решение задачи (1)-(3). Найдем ¿Ис.х"), г=ти (с,х): х е М"}. Нами показано, что мощности множеств М'./Ь и М"/Ь связаны неравенством:

|м*./ь| < 1+([д]-],у[+1) (|м"/ь|+1).

Рассмотрим пример погружения М" в параллелепипед.

- 15 -

Теорема 2.8. Предположим, что в задаче ЦЛП (3)-(5) все исходные данные целочисленные и соответствующее ей множество М" лежит в параллелепипеде Р. Тогда

п

|М'./Ь| < 1+ (ДО-М+1) П (а'л - а} + 1).

Если задача ЦЛП имеет оптимальное решение, то эту оценку можно уменьшить на 1. Существуют задачи БП, у которых мощность М'./Ь больше 2Л [61].

Отметим, что величина Ср.] —1V С легко оценивается сверху с помощью коэффициентов с3, а3, а'}, 3=1.....п. В частности, если |с3| < с', 3=1,..,п, с' >1, то она не превышает п с'шах{ : ¿=1.....п).

Приведем пример погружения в симплекс для многомерной задачи о рюкзаке (задачи (3)-(5) с неотрицательными целочисленными исходными данными ) [71.72]. Предполагается также, что все столбцы матрицы А и" вектор Ь ненулевые. Релаксационный многогранник этой задачи содержится в симплексе

п га

- Б' = {х: I х3 С Ь\ х3 О, 3=1.....п). Ь' = 2 Ь1.

1=1

Он имеет альтернирующую Ь-структуру, поэтому |М"/Ь|<IБ*01-1.

Теорема 2.9. Для Ь-накрытия многомерной задачи о рюкзаке (с целочисленными исходньш данными) справедлива оценка |М'./Ь| < ([до] -1/+1) (п+1 )ь'.

В п.2.4 рассматриваются задачи линейного БП. устанавливается связь между комплексами дробных Ь-классов и множеством нецелочисленных вершин релаксационных многогранников таких задач, приводящая к другим верхним оценкам мощности Ь-накрытий [77]. Рассматривается лексикографическая задача БП вида (2) для многогранника М из В". Ь-класс из М/Ь называется вершинным. если он содержит вершину многогранника М. Обозначим через у(М.) число вершинных классов в М./Ь.

Теорема 2.11. В любом полном комплексе мощности р из С(М) содержится не менее [р/2] вершинных Ь-классов. На основе этой теоремы доказана

Теорема 2.12. Для мощности Ь-накрытия задачи БП имеет место оценка

|М,/Ь| < 2У(М,).

- 16 -

Нами построены примеры задач в И" , для которых полученные оценки достигаются и мощность Ц-накрытия растет экспоненциально с увеличением п.

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

Предположим, что для указанной задачи о рюкзака выполняется С! /г.х > с2 /а2 > ... ) сп /а,,. Имеет место [70]

Теорема 2.18. Если в задаче о рюкзаке ci ¿[О, С], с' >1, а3 е[1,а']. з=1.:..,п, то для ее Ь-накрытия справедлива оценка

|М.(Ь)/Ь| < 1+(с'-1)(п+1)р,

где р=а'(с'а'+1)-1.

'Глава 3 посвящена исследованию двойственных алгоритмов отсечения с использованием регулярных разбиений и лексикографии. Ее основные результаты опубликованы в [42-44,47-52,55-61, 65-68,70-72,74.82].

В п.3.1. рассматриваются классы правильных отсечений и правильно отсекающих систем неравенств, вводится класс более "сильных" (Г-регулярных) отсечений и систем неравенств, изучаются возможности их построения. ;

Рассмотрим задачу (3)-(5). Пусть х* - оптимальное решение задачи (3),(4), причем х* « 2п. Линейное неравенство

•■•(Т.-х) < Ц0 (6)

называется правильным отсечением, если

а) (К.х*) > Ко.

б) (К,2) < К0 для всех допустимых решений г задачи ЦП.

Для лексикографической задачи (1) определение правильного

отсечения отличается лишь тем, что в нем вместо оптимального решения задачи (3},(4) используется х* = 1ехшах 2. Предложены различные способы построения таких отсечений [3,8,10,14.15,16, 29,42,61,68]. Широко известны отсечения Гомори [23,24].

Процесс решения задачи, основанный на правильных отсечениях, может оказаться бесконечным. Это связано с тем. что среди правильных отсечений могут появляться весьма "слабые", исключающие лишь малую часть дробного накрытия. Наш подход состоит в выделении отсечений, которые гарантируют исключение х*

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

Рассматривается задача (1) и регулярное разбиение F. Пусть х* « Zn•* и VFX,(Q.) - элемент из Q./F, содержащий х' . Линейное неравенство (6) называется регулярным отсечением для F (или F-регулярным), если

а) (t.x) > Ко для всех xeVFx.(Q.);

б) су. 2) < Yo Для всех 2 е й n Z"'k. ■

Для любого x«Zn определим ф(х) =min{i: х^ [xt ], 1=1, .., п}.

Теорема 3.1. Предположим, что для задачи (1) выполнены условия: х* «Zn-k и найдется d е zn-r такой, что х <d для всех х eQ. Тогда для любого а > 1+ max {{d1 - х']): г=1.....к} линейное неравенство

ф ( X •) - 1

I а5,(х,)"1(х1 - x*i) + Хф(х<) < [х*ф(х.)] П)

1 = 1

является Lk-регулярным отсечением.

Для ограниченного множества аналогичные отсечения получены с использованием его диаметра [61]. На основе этих теорем показано, что существует система цз s<k-отсечений вида (7). которая исключает все точки дробного накрытия задачи (1).

Нами установлено, что свойство L-регулярности имеется у ряда отсечений, предложенных Гомори и другими авторами. При этом важную роль играют правила выбора производящей строки и формулы построения отсечений. Отсечение Данцига [8] для многих задач не является L-регулярным, что отрицательно сказывается на сходимости алгоритмов.

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

Gx <g (8)

называется правильно отсекающей, если х* ей не удовлетворяет и Gz<g для всех zeQ0. Будем говорить, что правильно отсекающая система является F-регулярной, если ей не удовлетворяет- ни одна точка из VFX,(Q.). Вызывает интерес вопрос о минимальной

мощности Р-регулярной системы для заданного класса множеств и разбиения Г. Для класса Кв и любого регулярного разбиения она не превышает■величины к. а'в "случае Ьк-разбиения и канонического разбиения равна 1."Для кубических разбиений она может быть больше 1 [66].

В п.3.2. рассматриваются вопросы эффективности и сравнения отсечений. В исследованиях по методу отсечения этой тематике уделяется значительное внимание (см., например, [3,8,10]).

"Объем" отрезаемой части дробного накрытия мы предлагаем измерять с помощью разбиений. Пусть Р - некоторое регулярное разбиение. Глубиной системы линейных неравенств (8) относительно разбиения Г назовем число полностью' исключаемых ею элементов из 0,/¥. Очевидно, что глубина Р-регулярной системы не меньше 1.

Более детально эти вопросы изучались для Ь-разбиения. Глубина известных отсечений может колебаться на различных задачах от 0 до +о . Систематическое применение отсечений глубины 0, как правило, давало плохую сходимость. Нами найдены классы отсечений (Р-отсечения и др.), глубина которых ограничена сверху числом целочисленных - переменных задачи (см. п. 3.3). Получены экспериментальные данные о глубине отсечений для Ь-разбиения [45]. Установлено, что при решении известных тестовых задач их глубина часто не превышает нескольких единиц, а во многих примерах близка к 1.

Сравнение отсечений можно производить на основе дробного накрытия задачи (1). Будем говорить, что правильное отсечение (У'.х ) < К'0 не сильнее (К,х ) < у0, если из Су,х") < у0 следует ("К'.х") < К'о Для любого х" € 0.' . Аналогичное определение используется для сравнения систем неравенств.

В алгоритмах представляется полезным использовать не только Р-регулярные, но и правильные отсечения, имеющие "большую" глубину, например, фасетные неравенства [215,34].

При анализе классов отсечений естественно возникает вопрос о существовании и возможности построения "самой сильной" системы неравенств. В классе Р-регулярных отсечений таким свойством обладает некоторая система неравенств типа (7). однако для ее построения нужна информация,'' получение которой не проще, чем решение задачи ЦП. Для задач БП нами' указан способ

получения системы неравенств, которая не слабее, чем любая другая из рассматриваемых там систем [42].

В п.3.3. вводится и изучается класс Р-отсечений, анализируется его подкласс вполне регулярных отсечений, отмечается их связь с отсечениями Финкельштейна [8] и Червака [15]. Рассматривается задача (1). Пусть

Р' ={ х: < Х-, < а'^, ¿=1.....п }.

где ау г, а3 е г 1Л-со}. о=1.....п. Предполагается, что с Р'.

Линейное неравенство (6) называется Р-отсечением, если а) (у. х') > К0 для всех х' е ух. (2.). б*) а,г) с 10 для всех г е Р' Л гп-к . г < х*. По сравнению с определением Ьк-регулярного отсечения здесь усилено условие сохранения допустимых частично целочисленных точек.

Теорема 3.4. Глубина любого Р-отсечения не превышает числа целочисленных переменных задачи (1).

Вполне регулярным отсечением называется линейное неравенство (1), удовлетворяющее условию б*) из определения Р-от-сечения и,требованию

а*) ПГ.х) > Ко Для всех х е УХ,(Р'). где Ух. (Р')-элемент из Р'/Ьк, содержащий х*. Таким образом, любое вполне регулярное отсечение является Р-отсечением и, следовательно, его глубина не превышает величины к.

Нами получены необходимые и достаточные условия принадлежности линейного неравенства классу вполне регулярных отсечений для задач БП [42]. Достоинством таких отсечений является относительная простота способов их построения и применимость в случаях, когда й не является выпуклым. Вычислительный эксперимент показал, что в ряде случаев по глубине они близки к Ь-ре-гулярным отсечениям Гомори [45].

По аналогии можно перейти к рассмотрению вполне регулярных систем неравенств. Глубина такой системы также не превышает величины к.

Пусть далее в этом разделе Р' ='В" . Совокупность всех вполне регулярных отсечений, построенных по точке х* , обозначим через Т(х*). Введем обозначения

Л0(х*) = { о: х'з = 0. 3 <ф(х')}. ,1+Б(х') = { о: ^ (х*). 3 < э}. з=1.....к.

- 20 -

Теорема 3.6. Класс отсечений-Т(х') совпадает с множеством всех неотрицательных линейных комбинаций следующих неравенств:

Xj < 1. JeJ+ (х* ),

-Xj < 0, jej0 (х* ),

I xs + Xj < и.3(х')|, JeJ0 (X* ), seJj (x*)

£ + Хф(х., <|J+ (x*) | . (9)

SeJ.(X')

причем последнее из них входит в эти комбинации с положительным коэффициентом.

Другой вариант описания класса Т(х*) получен в виде условий для коэффициентов отсечения.

Рассмотрим вопрос о существовании в Т(х') "самой сильной" системы неравенств. Введем класс Т'(х'), который получается из Т(х*) путем допущения, что коэффициент при неравенстве (9) может быть равен 0. Через G(x') обозначим систему линейных неравенств из условия теоремы 3.6.

Теорема 3.7. Любое линейное неравенство из Т'(х*) не сильнее системы порождающих линейных неравенств G(x').

В классе вполне регулярных отсечений нами выделены отсечения единичной глубины [61,68]. Кроме теоретического интереса, они представляются также полезными для измерения мощности L-накрытий задач ЦП.

'В п.3.4. исследуются вопросы конечности и получения оценок числа итераций (отсечений), для двойственного дробного процесса отсечения D. представляющего собой естественное обобщение известных алгоритмов (Гомори и др.). Найдены верхние и нижние оценки числа итераций в терминах мощности F-накрытий задач ЦП и глубины отсечений [55.60.61,67,71,72,74].

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

Конечность процесса О обеспечивается Р-регулярными системами, которые отрезают от дробного накрытия задачи "существенную" часть. Процесс Б, в котором используются только Р-регу-лярные системы неравенств, называется Р-регулярным. Если же порождение таких систем гарантируется в нем'через конечное ите.раций. то - слабо Р-регулярнш.

Теорема 3.12. Процесс Б решает задачу (1) с конечнт Ьк-накрытием тогда и только тогда, когда он является слабо Ьк-регулярным.

В случае произвольного разбиения слабо Р-регулярный процесс- Б может оказаться бесконечным (для конечного Р-накрытия). Это связано с проблемой исключения, дополнительных ограничений. Например, аналогичная теорема имеет место для любого регулярного разбиения и процесса 0'. который отличается от Б тем, что в не.м сохраняются все порождаемые ограничения.

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

Теорема 3.14. Для задачи (1) и ^-регулярного процесса О справедливо неравенство

< |0./Ьк|

В случае произвольного разбиения такая оценка имеет место для процесса Б'. При построении нижних оценок числа итераций вопрос о сохранении дополнительных ограничений и Р-регуляр-ность становятся менее существенными.

Теорема 3.15. Для любого регулярного разбиения Р и задачи (1) выполняется

>10 (О) > Ц/Нп(О.П) 10./П.

Объединение оценок из теорем 3.13 и 3.15 для Ьк-регулярного процесса приводит к важному соотношению.

(1/Нп(0. Ьк))|0,/Ьк| < л0(0) < Ю./Ьк|.

Для процесса Б с Р-отсечениями можно положить Нс(ОЬк)=к. Это означает, что мощность 10,/1к\ существенно определяет сложность решения задачи (1).' Например, в случае 10,/ЬК| =+» процесс не может решить (1). Если же |0./Ьк| экспоненциально растет вместе с п, то и число итераций будет иметь аналогичную зависимость от п.

- 22 -

Еще один класс оценок получается для лексикографических задач БП на основе исследования связи.L-структуры с множеством вершин релаксационного многогранника [78] (см.п.2.4).

Теорема 3.16. Для задачи БП вида (2) и L-регулярного про' цесса D имеет место неравенство

J„(M) .< 2v(M, ) _ Поскольку |M«/L| ) v(M,). то для процесса D с вполне регулярными отсечениями имеет место и нижняя оценка JD(M) > (l/n)v(M.). В п.3.5. на основе оценок предыдущего параграфа и результатов гл. 2 получаются оценки числа итераций для задач ЦЛП с использованием ряда параметров задач. Приведем примеры таких оценок. С помощью погружения в параллелепипед доказана

Теорема 3.17. Пусть в задаче (1) дробное накрытие непусто и содержится в параллелепипеде Р, а процесс D является Lk-регулярным. Тогда

к

JD (Q) С -1+ П (a'j - а3 +1).

Пусть JD(А.Ь„с) - число полных итераций процесса D. выполняемых при решении задачи (3)-(5) с исходными данными A.b.с.

Теорема 3.18. Предположим, что в задаче ЦЛП (3)-(5) все исходные данные целочисленные, к=п и множество М" лежит в параллелепипеде Р. Тогда для L-регулярного процесса D имеет место оценка

п

JD (А,Ь.с) < 1+ ÜJ1] - ]v [ + 1) П (а'., - а-) +1).

j = I

Погружение дробного накрытия в симплекс дает другие оценки. Например, имеет место

Теорема 3.20. Предположим, что в задаче ЦЛП (3)-(5) все исходные данные целочисленные, к=п и М" содержится в симплексе S'. Тогда для L-регулярного процесса D справедлива оценка JD (А.Ь,с) < 1+ ([/il - ]v [ + 1) (1 + п)ь . В п.3.6. проводится сравнение алгоритмов булева программирования с вполне регулярными отсечениями. В частности, выделяется наискорейший по числу итераций алгоритм для одного подкласса рассматриваемых отсечений.

- 23 -

В п.3.7. приводятся необходимые сведения для анализа отсечений и алгоритмов ЦЛП. В п.3.8. изучаются двойственные алгоритмы Гомори с помощью разбиений и Ь-процесса из гл.1. При определенных условиях доказывается Ь-регулярность отсечений первого алгоритма Гомори, что позволяет сделать вывод о справедливости для него ряда оценок числа итераций из п.3.5.

В главе 4 рассматриваются предложенные нами алгоритмы перебора Ь-классов. алгоритмы отсечения и гибридные алгоритмы, излагаются результаты исследования некоторых алгоритмов ветвей и границ (метода Лэнд и Дойг) на основе регулярных разбиений, приводится ряд оценок числа итераций для прямых алгоритмов отсечения. Основные результаты главы опубликованы в [38-41,45,71, 73,77-81].

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

Первый из них опробован для задач БП. В случае целочисленной решетки его возможности ограничены из-за быстрого роста коэффициентов отсечений при увеличении числа переменных. Второй подход применим для достаточно' общих задач и реализован для задач ЦЛП. Основным шагом метода является переход от одного элемента Ь-накрытия к следующему за ним в порядке лексикографического убывания. Он порождает последовательность Б={х(''}, геГ, точек из О., обладающую свойствами:

а) хи) > х(1 + 1), 1=1,2.....'

б) все хс" принадлежат различным Ь-классам,

В) |Б| = ¡0./Ц.

В случае ЦЛП анализ Ь-накрытия этим методом сводится к решению последовательности задач ЛП. Описание одного из алгоритмов и результаты эксперимента приведены в [45].

В п.4.2. предлагаются прямо-двойственные алгоритмы перебора Ь-классов для решения задач ЦЛП. Эти алгоритмы строятся на основе указанного выше алгоритма измерения мощности Ь-нак-рытия. однако в них вместо исходной задачи рассматривается подходящее семейство задач ЦП. Просмотр Ь-накрытия очередной задачи начинается с элемента, который лексикографически меньше

¡.просмотренных ранее L-классов. ;На базе такого подхода нами разработаны гибридные варианты алгоритмов, в которых перебор L-классов комбинируется, с отсечениями, а также приближенные алгоритмы с оценкой точности получаемых решений [71].

П. 4. 3., посвящен декомпозиционному методу решения линейных частично целочисленных задач производственно-транспортного типа, основанному на применении, отсечений Бендерса.

Ранее в разработанном нами декомпозиционном методе [38-41! для отыскания допустимых решений целочисленных подзадач применялся метод направленного перебора булевых векторов. Оказалось, что с этой целью удобно использовать алгоритмы перебора L-miac-сов. При решении очередной подзадачи ЦП можно возобновлять процесс с последнего просмотренного L-класса, все остальные будут лексикографически больше (для задачи на минимум).

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

Рассмотрим полностью целочисленную задачу (3)-(5) и алгоритм W из указанного класса. Пусть F - регулярное разбиение и Sw - последовательность приближений, порождаемая алгоритмом W при решении этой задачи. Доказано, что в общем случае S„ не является регулярной относительно L-разбиения, регулярна относительно канонического разбиения, для произвольного кубического разбиения 5 любой дробный класс из М/5 содержит не более п ' ее членов. На основе этих утверждений построен ряд верхних оценок числа итераций, в частности, |SJ < |М/К|. Для задач БП также получены оценки в терминах вершин многогранника М.

В п. 4.5.-4.8. рассматриваются алгоритмы отсечения. В п.4.5. описывается прямо-двойственный алгоритм отсечения для задачи упаковки, релаксационный многогранник которой имеет альтернирующую L-структуру. В п.4.6. дается описание прямых алгоритмов, отсечения, доказывается конечность некоторых из них при простом правиле выбора производящей строки. В п. 4.7'. приводятся найденные нами контрпримеры для рудиментарного прямого алгоритма, верхние (в частном случае) и нижние оценки максимального числа итераций для конечных прямых алгоритмов.

В пятой главе излагаются результаты экспериментальных исследований, проведенных с использованием регулярных разбиений. Ее основные результаты опубликованы в [45,46,62,71,72].

- 25 -

В п.5.1. дается общая характеристика реализованных алгоритмов и краткая информация о тестовых задачах. В разработанном нами комплексе программ реализовано несколько двойственных дробных алгоритмов отсечения, алгоритмов перебора L-классов и гибридных алгоритмов. Программы написаны на языках Фортран и Паскаль. Расчеты проводились на ЭВМ ЕС-1033 и IBM PC/AT. В экспериментальных исследованиях были использованы известные тестовые задачи Хальди [35], Петерсена [33], Кивистика [45], задачи со случайными данными, специально построенные нами примеры и прикладные задачи [62].

В п. 5. 2 и п. 1 5.3 описываются результаты вычислительного эксперимента для алгоритмов отсечения, перебора L-классов и гибридных алгоритмов. Эксперимент проводился с целью получения сведений об L-накрытиях задач, изучения известных алгоритмов ЦДЛ и апробации новых алгоритмов. Для сравнения использовался известный пакет MILP88.

Расчеты показали, что прямо-двойственные алгоритмы перебора L-классов и гибридные алгоритмы достаточно перспективны. У них оказались неплохие показатели как по времени счета, так и по надежности получения результата. Использование L-регуляр-ных отсечений в этих алгоритмах во многих случаях приводило к заметному ускорению процесса решения. Для двойственных дробных алгоритмов отсечения важную роль в повышения надежности играли L-регулярные отсечения. Алгоритмы с нерегулярными отсечениями вели себя существенно более непредсказуемо.

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

Во многих случаях заметного уменьшения мощности L-накрытий. числа отсечений и времени счета удавалось достичь путем подходящего упорядочения переменных задачи.

В приложении приводятся исходные данные и оптимальные решения тестовых задач.

ЛИТЕРАТУРА

1. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. - М.: Наука, 1987.- 248 с.

2. Береснев В.Л.. Гимади Э.Х.. Дементьев В.Т. Экстремальные задачи стандартизации. - Новосибирск: Наука, 1978,- 335 с.

3. Булатов В.П. Методы погружения в задачах оптимизации. - Новосибирск: Наука, 1977.- 161 с.

4. Гэри М., Джонсон Д. Вычислительные машины и трудноре-шаемые задачи.-М.: Мир, 1982,- 416 с.

5. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники. графы, оптимизация - М: Наука, 1981. - 344 с.

6. Еремин И.И. .Мазуров В.Д.. Астафьев H.H. Несобственные задачи линейного и выпуклого программирования.- М.: Наука, 1983. - 336 с.

7. Корбут А.А., Сигал И.X., Фйнкельштейн Ю.Ю. Гибридные методы в дискретной оптимизации // Изв. АН СССР. Техн. кибернетика,- 1988.-N1.- С.65-77. -

8. Корбут А.А.. Фйнкельштейн Ю.Ю. Дискретное программирование. - М.: Наука, 1969. - 368 с.

9. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность: Пер. с англ.- М.: Мир, 1985.-512 с.

10. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации, - Киев: Наук, думка, 1988.- 471 с.

11. Схрейвер А. Теория линейного и целочисленного программирования: Пер. с англ. В 2-х т. - М.: Мир, 1991,- 702 с.

12. Фйнкельштейн Ю.Ю. Оценки числа итераций для полностью целочисленного алгоритма Гомори. - ДАН СССР.-1970.-193, N 3.-С.543-546.

13. Хачатуров В.Р. Математические методы регионального программирования, - М.: Наука,1989.- 304 с.

14. Ху Т. Целочисленное программирование и потоки'в сетях: Пер.' с англ. - М.: Мир. 1974,- 520 с.

15. Червак Ю.Ю. Поиск лексикографически максимальной дискретно определенной точки выпуклого множества // Мат. методы решения экономических задач.-М.: Наука.1979.- С.68-75.

16. Шевченко В.Н. Выпуклые многогранные конусы, системы сравнений и правильные отсечения в целочисленном программиро-

вании // Комбинаторно-алгоритмические методы в прикладной математике. - Горький: ГГУ. 1979. - С.109-119.

17. Шевченко В.Н. Алгебраический подход в целочисленном программировании// Кибернетика.-1984.-4. - С.36-41.

18. Benders J. F. Partitioning Procedures'for Solving of Mixed-variables Programming Problems// Numer. Math..-1962.- 4, N3,- P. 238-252.

19. Ben-Israel A., Charnes A. On Some Problems of Diophantine Programming// Cahiers Centre d'Etudes de Rech. Opérât.- 1962,- 4. N4,- P.215-288.

20. Chvatal V. Cutting planes in combinatorics // European J. of Combinatorics.- 1985,- N6,- P.217-226.

21. Dantzig G.B., Fulkerson D.R., Johnson S.M. Solution of a Large Scale Travelling Salesman Problem// Oper. Res.-1954.-2, N3,- P.393-410.

22. Glover F. A new foundation for a simplified Primal Integer Programming Algorithm// Oper. Res.-1968.-16.N6.-P.727 -740.

23. Gomory R.E. Outline of an Algorithm for Integer Solution to Linear Programs // Bull. Amer. Math. Soc.-1958. -64.N5.- P. 275-278.

24. Gomory R.E. All-Integer Integer Programming Algorithm// Industrial Scheduling. Ed. Muth J.F.. " Thompson G.L. Prentice-Hall, Englewoods Cliffs. -1963. - P.193-206.

25. Grotschel M.. Holland 0. Solution of large-scale simmetric travelling salesman promlem // Math. Program.-1991,- N51.- P.141-202.

26 Grotschel M.. Lovasz L.. Schrijver A. Geometric algorithms and combinatorial optimization.- Berlin a.o.:'Springer Verlag. 1988. - XII.- 362 p.

27. Jeroslow R.G., Kortanek K. On an algorithm of Gomory// SIAM J. Appl. Math.-1971.-21. N1. - P.55-60.

28. Jeroslow R.G. Trivial integer programs unsolvable by branch-and-bound (short communication)// Programming.-1974.- 6, N1. - P. 105-109.

29. Jeroslow R.G. Cutting-plane theory: algebraic methods// Diskrete Math. -1978. -23, N2. - P.121-151.

- 28 -

30. Land A.H., Doig A. G. An automatic Method for Solving Discrete Programming Problems//Econometrica. -1960.-28.-P.497-520.

■ 31. Mathis S. A contrexample to the rudimentary Primal Integer Programming Algorithm// Oper. Res.- 1971.-19, N6,- P. 1518-1522.

32. 'Nourie F.J.. Venta E.R. An upper bound on the number of cuts needed in Gomory's method of integer forms// Oper. Res Letters. -1981.-2.- P.129r133.

33. Petersen C.C. Computational experience with variants of the Balas algorithm - applied to the Selection of R&D Projects// Manag. Sci.- 1967'. - 13, N9,- P.736 -750.

34. The Travelling Salesman Problem. Ed. by E.L.Lawler, J.K. Lenstra, A. N.G.Rinnooy Kan, D.B.Shmoys.- John Wiley L Sons Ltd.. 1985,- 465 p.

35. TrauthC.A., ^Woolsey R.E.. Integer programming: a study in computational efficiency // Manag. Sci. -1969. -15,-P.481-493.

36. Walukiewicz S.Integer Programmlng//Warszawa: PWN-Po-lish Scientific Publishers, Dordrecht, Boston, London: Klumer Academic Publishers, 1991.- 182 p.

37. Young R.D. A simplified Primal (All-Integer) Integer Programming Algorithm// Oper. Res.-1968.- 16. N6,- P.750-782.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

38. Бахтин А.Е., Колоколов А.А.. Коробкова З.В. Дискретнь задачи производственно-транспортного типа. - Новосибирск: Наука, 1978.- 167 с.

39. Бахтин А.;Е., Колоколов А. А. Некоторые методы решет производственно-транспортных задач// Планирование отраслевьи систем.- М.: Экономика. 1974.- С. 200-237.

40. Бахтин А.Е.. Колоколов А.Д. Декомпозиционный метод ре шения целочисленных производственно-транспортных задач// Вопросы анализа сложных систем.-Новосибирск: Наука, 1974.-С.196-206.

41. Бахтин А.Е., Колоколов А.А. К вопросу о решении uej численных производственно-транспортных задач//Многоуровневыс

системы отраслевой оптимизации. - Новосибирск: Наука, 1975. - С.196-206. ■ . -

42. Заблоцкая O.A.. Колоколов A.A. Вполне регулярные отсечения в булевом программировании /У Управляемые системы. Новосибирск: ИМ СО АН СССР, 1983,- Вып. 23,- С. 55-63.

43. Заблоцкая O.A., Колоколов A.A. Об одном классе двойственных дробных процессов отсечения булевого программирования // Принятие оптимальных решений в экономических системах. -Горький: ГГУ, 1986,- С.34-41.

44. Заблоцкая O.A., Колоколов A.A. Исследование одного класса отсечений на основе регулярных разбиений // Информ. бюллетень АМП. N4, тез докл. конф."Математическое программирование и приложения". - Екатеринбург, 1993,- С.47.

45. Заикина Г.М., Колоколов A.A. Экспериментальные исследования в целочисленном программировании с применением ¡/-разбиения // Дискретная оптимизация и анализ сложных систем. -Новосибирск: ВЦ СО АН СССР, 1989.- С.26-56.

46. Заикина Г.М.. Колоколов А.А., ЛевановаТ.В. Экспериментальное сравнение некоторых методов целочисленного программирования // Методы решения и анализа задач дискретной оптимизации. - Омск: ОмГУ. 1992.- С.25-41.

47. Колоколов A.A. К оценке числа, итераций для прямых алгоритмов отсечения в целочисленном программировании// Математический анализ экономических моделей. Ч.1,- Новосибирск: ИЭиОПП СО АН СССР, 1971,- С.137-164.

48. Колоколов A.A. Некоторые оценки для прямых алгоритмов отсечения в целочисленном программировании// Математический анализ экономических моделей. Ч.III.- Новосибирск: ИЭиОПП СО АН СССР. 1972.- С.154-161.

49. Колоколов A.A. О длине лексикографически монотонных последовательностей//Оптимизация территориальных и отраслевых систем, методы решения экономических задач.Ч.III.-Новосибирск: ИЭиОПП СО АН СССР, 1973,- С.93-99.

50. Колоколов A.A. Верхняя оценка числа отсечений для первого алгоритма Гомори //Тез. докл. III Всесоюз.. конф. по проблемам теоретической кибернетики.-Новосибирск. 1974.-С.87-88.

:51. Колоколов A.A. О числе отсекающих плоскостей в первом алгоритме Гомори// Проблемы анализа дискретной информации.-Новосибирск: ИЭиОПП СО АН СССР. 1975.- С.84-96.

- 30 -

52. Колоколов А. А. . Верхние оценки числа отсекающих плоскостей для циклического алгоритма Гомори// Методы моделирования и обработки информации. - Новосибирск: Наука, 1976.-С.106-116.

53. Колоколов A.A.,.: Некоторые оценки и крнтрпримеры дл5 прямых алгоритмов отсечения// Тез. докл. IV Всесоюз. конф. пс проблемам теоретической кибернетики.-Новосибирск. 1977.-С.109.

54. Колоколов А.А. О лексикографической структуре некоторых выпуклых многогранных множеств // Тез. докл. Y Всесоюз. конф. по проблемам теоретической кибернетики.- Новосибирск. 1980,- С.77-79.

55. Колоколов A.A. Регулярные отсечения при решении зада1 целочисленной оптимизации // Управляемые системы. - Новосибирск: ИМ СО АН СССР. 1981,- Вып. 21. - С.18-25.

56. Колоколов А. А. Нижняя оценка числа итераций для 'одного класса алгоритмов отсечения// Управляемые системы.- Новосибирск: ИМ СО АН СССР.-1983,- Вып.23.- С.64-69.

■ 57. Колоколов A.A. Нижняя оценка числа регулярных Р-отсе-чений для- задач .целочисленного программирования// Методы математического .программирования и их программное обеспечение. Тез. докл. науч.-тех. конф, - Свердловск.1984.- С.68.

. 58. Колоколов A.A. О наискорейшем алгоритме в одном классе . регулярных процессов отсечения // Методы и программы решения оптимизационных задач на графах и сетях. 4.2. - Тез. докл. III Всесоюз. совещ., Ташкент - Новосибирск: ВЦ СО АН СССР, 1984. - С. 70.

59. Колоколов A.A.. Цепкова Е.В. Верхняя оценка числа регулярных отсечений для одного семейства задач на конусе // Управляемые системы. - Новосибирск: ИМ СО АН СССР, 1984. - Вып. 25. - С. 75-79.

60. Колоколов А. А. Методы дискретной оптимизации // Учебное пособие. - Омск: ОмГУ. 1984.- 75 с.

61. Колоколов A.A. Алгоритмы отсечения и некоторые разбиения множеств // Дискретная оптимизация и численные методы решения прикладных задач. - Новосибирск: ВЦ СО АН СССР, 1986. -С.50-67.

62. Колоколов A.A., Финько В.И., Цепкова Е.В. Оптимизация загрузки кассетного оборудования на предприятиях крупнопанель-

-юго домостроения // Дискретная оптимизация и численные методы зешения прикладных задач. - Новосибирск: ВЦ СО АН СССР. 1986. -С. 48-53.

63. Колоколов A.A. Выпуклые множества., с . альтернирующим L-разбиением // Моделирование и оптимизация систем сложной структуры, - Омск: ОмГУ. 1987. - С. 144-150.

64. Колоколов A.A. Построение оценок числа итераций для «которых методов целочисленного программирования//Тез докл. [II Всесоюзной школы "Дискретная оптимизация и компьютеры". -М., 1987,- С. 38.

65. Колоколов A.A. Исследование задач и методов целочис-1енного программирования на основе L-pa36Hemw//Wiss. Koll.-[lmenau: ТН. 1988. - S.53-55.

66. Колоколов А.А., Сайко Л.А. О некоторых оценочных раз-5иениях в целочисленном программировании // Тез. докл. десятого Всесоюз. симпозиума " Системы програм. обесп. решения задач ттимального планирования". - М., 1988. - С.134.

67. Колоколов A.A. Метод оценочных разбиений в целочис-юнном программировании // Теория и программная реализация ме-'одоз дискретной оптимизации,- Киев: ИК АН УССР. 1989.44-47.

68. Колоколов A.A. Об одном применении вполне регулярных тсечений в булевом программировании// Комбинаторно-алгебраи-еские методы в дискретной оптимизации.- Нижний Новгород: ГУ, 1991.- С.36-45.

69. Колоколов А. А. Построение алгоритмов целочисленного рограммирования на основе Lk-разбиений// Конф. "Матем. програм-ирование и приложения". Тез. докл.- Свердловск, 1991,- С.86.

70. Колоколов А.А., Цепкова Е.В. Исследование задачи о юкзаке на основе L-разбиения//Кибернетика. - 1991. N2,-

.38-43.

71. Колоколов A.A. Регулярные разбиения в целочисленном эограммировании// Методы решения и анализа задач дискретной тгимизации.- Омск: ОмГУ. 1992.- С.67-93.

72. Колоколов A.A. Применение регулярных разбиений в це-эчисленном программировании // Изв. ВУЗов. Математика.-1993.-12,- С. 11-30.

- 32 -

73. Колоколов А.А. Регулярные разбиения и метод ветвей1 границ// Информ. бюллетень АМП, N4. Тез. докл. конф."Математ: ческое программирование и приложения". - Екатеринбург. 1993 С.61.

74. Колоколов А.А. Регулярные разбиения и отсечения в ц лочисленном программировании//Сиб. журн. исследования опер; ЦИЙ. -1994. -N2.- С.18-39.

75. Колоколов А.А. Анализ L-структуры задач булева про: раммирования // Информ. бюллетень АМП, N5. Тез. докл. кош "Математическое программирование и приложения". - Екатерга бург, 1995,- С.122.

76. Kolokolov A.A. Upper bound of L-covering power li the boolean programming problems// III International semlni on global optimization.-Irkutsk, 1992,- P.108.

77. Kolokolov A.A. On the L-structure of integer lineai programming problems// Abstracts of 16th IFIP conference с system modelling and' optimization. - Compiegne. France.

1993,- P.183-184.

78. Kolokolov A.A. On the L-structure of integer lines programming problems// System Modelling and Optimizatior Proceedings of the 16th IFIP conference on the modelling ar optimization.- Springer Verlag, 1993. - P.756-760.

79. Kolokolov A.A. Decomposition Algorithms for Solvin of some Production-Transportation Problems// Triennal'Symposi on Transportation Analysis II. Preprints. Vol.1.- Capri. Ital

1994.- P.179-183.

80. Kolokolov A.A. Some L-class enumeration algorithm for Integer Programming. Problems// Abstracts of 3rd IFI WG-7.6 Working Conference on Optimization-Based Computer-Aide Modelling and Design.-Prague, Czech Republic. 1994.- P.98-99

81. Kolokolov A.A., Levanova T.V. ..Some L-class Enumera tion Algorithms for Simple Plant Location Problem// Abstract of International Conference on Operations Research. ^Berlin 1994. -P. 75.82. Kolokolov A.A. Regular partitions and cuts in intege

programming// Abstracts of International Conference o: Operations Research. - Berlin. 1994.- P. 84.