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

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

ЗАОЗЕРСКАЯ Лидия Анатольевна

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

05.13.16 - применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

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

Омск - 1998

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

Научный руководитель: доктор физико-математических наук

A.A. Колоколов

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

профессор Э.Х. Гимади кандидат физико-математических наук, доцент O.A. Заблоцкая

Ведущая организация: Институт математики и механики

Уральского отделения РАН

Защита состоится " 21" ноября 1998г. в 10 часов на заседании диссертационного совета К 200.63.01 по защите диссертаций на соискание ученой степени кандидата наук в Институте информационных технологий и прикладной математики СО РАН по адресу: 644099, Омск, ул. Певцова, 13.

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

Автореферат разослан 'jfe>" Е 1998г.

Ученый секретарь

диссертационного совета

к.ф.-м.н.

№

аА"

в.п. Ильев

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

Актуальность темы. Целочисленное программирование (ЦП) представляет собой одно из активно развивающихся направлений дискретной оптимизации. К моделям ЦП сводятся многие прикладные задачи, возникающие в экономике, управлении, проектировании и других областях. Значительная часть методов решения задач ЦП основана на сведении исходной задачи ЦП к последовательности задач непрерывной оптимизации. К таким- методам относятся методы отсечения, ветвей и границ (типа метода Лэнд и Дойг), декомпозиции (с отсечениями Бендерса), алгоритмы перебора ¿-классов и некоторые другие [3,4,7]. Характерными особенностями этих методов являются исполь-' зование релаксационных множеств, дополнительных линейных ограничений (отсечений) и аппарата непрерывной оптимизации.

Для исследования задач ЦП, построения и анализа алгоритмов рассматриваемого типа А.А.Колоколовым был предложен метод регулярных разбиений, получивший развитие в [1-4,6] и других работах.

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

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

шения, основанных на методе перебора ¿-классов н отсечениях, исследование свойств кубических разбиений, изучение возможностей их применения.

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

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

1. Проведен анализ задач о покрытии и упаковке множества:

- получены нижние оценки и точное значение мощности ¿-накрытий для семейства задач о покрытии, предложенных Э.Балашем;

- построены и исследованы задачи о покрытии и упаковке блочно-диагонального вида с ¿-накрытиями, мощность которых растет экспоненциально с увеличением числа переменных задачи;

- получены оценки числа итераций при решении этих задач некоторыми алгоритмами отсечения и методом Лэнд и Дойг.

2. Разработаны и исследованы алгоритмы перебора ¿-классов для точного и приближенного решения задач о покрытии множества. Создано программное обеспечение, проведены экспериментальные исследования.

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

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

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

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

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

Апробация работы. Результаты работы докладывались на III Всесоюзной школе "Дискретная оптимизация и компьютеры" (Ташта-гол, 1987), 10 Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования" (Усть-Нарва, 1988), 6 Всесоюзной конференции "Методы математического программирования и программное обеспечение" (Свердловск, 1989), IV Всесоюзном совещании "Методы и программы решения оптимизационных задач на графах и сетях" (Новосибирск, 1989), III Всесоюзном семинаре "Дискретная математика и ее приложения" (Москва, 1990), 7 Всесоюзной конференции "Математическое программирование и приложения" (Свердловск, 1991), XI международной Байкальской школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 1998), а также на семинарах в Институте математики им. С.Л.Соболева СО РАН, в Институте информационных технологий и прикладной математики СО РАН.

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

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

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

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

В первой главе исследуется ¿-структура задач о покрытии и упаковке множества, проводится анализ решения этих задач некоторыми алгоритмами отсечения и методом Лэнд и Дойг.

В п. 1.1 приводится краткий обзор результатов, полученных на основе метода регулярных разбиений. Пусть ÎÎ - замкнутое множество из Rn, имеющее лексикографически максимальный элемент х. Рассмотрим следующую задачу ЦП:

найти z* — lexmax(Q П Z"). (1)

При решении этой задачи различными методами, основанными на аппарате непрерывной оптимизации, требуется исключить множество Îλ = {ж G ÎÎ | х >- 2 для всех 2 6 Q П Z"}, называемое дробным накрытием. Если Û П Zn = 0, то Q совпадает с flt.

В соответствии с рассматриваемым методом в пространстве Rn вводится класс регулярных разбиений [4]. Каждая точка z G Zn образует отдельный класс разбиения, остальные классы состоят только из нецелочисленных точек. Пусть F - некоторое регулярное разбиение. Порождаемое F фактор-множество для S Ç R" обозначается S/F, а его мощность - через |S/.F|. Элементы S/F называются F-классами, а множество Q*/F - F-накрытием задачи (1).

Пусть х g Zn и Wx(Q) - элемент F-накрытпя, содержащий точку х. Линейное неравенство ^х < Jq с вещественными коэффициентами

3 = 0, п, называется регулярным отсечением для разбиения ^ (или .Р-регулярным), если

1) ух' > 7о для любого х' £ И'^П);

2) 72 < То Для любого 2 £ 57 П

Наиболее изученным регулярным разбиением является ¿-разбиение, которое определяется следующим образом: точки х,у из Я" (х >- у) эквивалентны, если не существует г £ 2п такой, что х У г У у. Элементы данного разбиения называются ¿-классами. Для двойственного дробного процесса отсечения О [3], использующего только ¿-регулярные отсечения, и задачи (1) с конечным ¿-накрытием имеют место оценки

< /д(П) < \Я./Ц,

где - число отсечений процесса Б, а Н(0.) - верхняя оценка глу-

бины применяемых в нем отсечений. Глубина определяется как число полностью исключаемых данным отсечением элементов ¿-накрытия. Для вполне регулярных отсечений Н(П) = п.

В работе изучаются и другие регулярные разбиения. Пусть Вп -множество всех п-мерных булевых векторов и <5 £ Бп. Определим 6-округление вектора х £ Яп следующим образом: ¿¿(х) = [ж,-], если 6] = О и 6{(х) — [ж,], если <5; = 1, г = 1,п. Нецелочисленные точки х, у £ Я" являются ¿-эквивалентными, если ¿(х) — 8(у). Порождаемое этим отношением эквивалентности разбиение называется кубическим. С помощью таких разбиений получены верхние оценки числа итераций для дробных алгоритмов отсечения и метода Лэнд и Дойг [3,4].

Аналогичные определения и результаты естественным образом переносятся на задачу: найти г* — 1ехтгп($1 П Zn).

В этом же параграфе приводится формулировка задачи о покрытии множества [5,9] и рассматриваются некоторые ее свойства. Модель ЦП для этой задачи имеет вид:

найти xq = cixi ~"* (-)

при условиях J=1

n _

52 ClijXj > 1, i = 1,771, (3)

3=1

0<^<1, j = (4)

xj ez, j = T7n, (5)

где A =|| aij || - булева m x п-матрица, cj > 0 - целые, j = 1, n.

В и. 1.2 исследуется ¿-структура невзвешенных задач о покрытии Т(п,р) из семейства, предложенного Э.Балашем [8]. Здесь р - оптимальное значение целевой функции задачи. Эти задачи характеризуются значительной разностью оптимальных значений целевых функций задачи ЦП и ее линейной релаксации. Обозначим через К(п,р) лексикографическую задачу, соответствующую Т(п,р). Нами выделены задачи, у которых мощность L-накрытий Kt(n,p)/L растет экспоненциально с увеличением числа переменных.

Теорема 1.6. Для задачи К'(п, р^]) (п > i) имеет место оценка \Kt(n, \n-f\)IL\) > g.

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

Получено также точное выражение мощности ¿-накрытия произвольной задачи из рассматриваего семейства.

Теорема 1.7. Для задачи К(п,р) имеет место соотношение

IfttMMI- £ а+ЕЁЧ^ + Ь

m=[-_2_] щ=0по=0 ГО, иначе,

где I — I i)-n+ii\.

[ т—пх — 1 J

В п. 1.3 построены задачи о покрытии блочно-диагонально го вида, обладающие экспоненциальными по мощности ¿-накрытиями, но в от-

личие от задач Балаша у них число ограничений равно числу переменных. Рассмотрен вопрос о решении этих задач 1-м алгоритмом Гомори, показано, что число отсечений этого алгоритма не превосходит п.

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

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

В п. 2.1 описывается алгоритм для задачи о покрытии, в основе которого лежит алгоритм перебора ¿-классов для общей задачи ЦП [4], предлагаются две его модификации и приводятся некоторые свойства данного алгоритма и задачи о покрытии.

Опишем общую схему предложенного нами алгоритма перебора Ь-классов для задачи о покрытии. Через М обозначим множество, определяемое условиями (3),(4). В порядке лексикографического возрастания просматриваются ¿-классы, на которые разбивается множество М = {х £ М | (с, х) < р — 1}. Здесь р - начальный рекорд целевой функции. Очередной Ь-класс находится путем решения последовательности задач линейного программирования (ЛП). Пусть х - начальное допустимое целочисленное решение, х - наилучшее текущее целочисленное решение, а е - целочисленный параметр (е > 1). Если е = 1, то алгоритм находит оптимальное решение задачи (2)-(5). Для е > 1 отклонение от оптимального значения целевой функции не будет превышать £ — 1.

Алгоритм Р. Шаг 0. Положить х = х, х' = х, р = тах{) | х^ = 1,3 < п — 1}. Вычислить рекорд р = (с, г). Переход на шаг 1.

Шаг 1. Найти номер <р = тах{з | х'^ — 0,3 < р — 1}. Если такого у нет, то переход на шаг 4, иначе переход на шаг 2.

Шаг 2. Найти х' — 1ехтгп

где М£_£ = {х € М | (с, ж) < р - е, х? = 1, х, = а;',-,У = 1,9 - 1}. Возможны следующие варианты:

1) получено решение этой задачи ;

если х' € %п. тогда х = х',р = (с,х),р = тах0 | х^ = 1,< п — 1} и переход на шаг 1; иначе переход на шаг 3;

2) задача неразрешима; если при этом <р > 1, то р = р и переход на шаг!, иначе переход на шаг 4;

Шаг 3. Найти 9 = тт{] | х'^ ф < п}. Переход на шаг 2.

Шах 4. Алгоритм завершает работу : х - оптимальное решение исходной задачи.

Очевидно, что число просматриваемых алгоритмом ¿-классов не превосходит \М¡Ь\. Из свойства альтернируемости ¿-структуры многогранника М следует, что в качестве начального целочисленного решения может быть использован элемент V = 1ехтт М.

Отметим, что для задачи о покрытии при определении М условие (4) можно заменить на х^ > 0, 3 = 1, п. Хотя множества оптимальных решений для обоих вариантов совпадают, мощность множества М/Ь во втором случае будет больше. Это не приведет к просмотру лишних ¿-классов, так как условия < 1, — 1 ,п, учитываются алгоритмически и, кроме того, доказано

Утверждение 2.1. Для непустого множества Мр_£ компоненты вектора х' = 1ехтЫ Мр-С удовлетворяют условиям х< I,] — 1 ,п. Проведенный вычислительный эксперимент для задач о покрытии

показал, что при переходе к очередному ¿-классу часто встречаются задачи ЛП, не имеющие допустимых решений.

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

Во второй модификации предлагается анализировать не один Ь-клас.с, а сразу некоторую их совокупность. Здесь также возможно применение тестов из первой модификации.

В п. 2.2 приводятся основные сведения о прямых алгоритмах отсечения. Рассматривается задача ЦП следующего вида:

п

,Т0 = ХЗ С1Х} тах (6)

при условиях

п

£ йцХ; < Ь;, г - 1, т, (7)

X; > 0, -целые, j = 1, п, (8)

где все исходные данные с,-, аг;-, Ь,- - целые числа, Ь,- >0, г = 1,тп.

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

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

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

В пп. 2.3-2.4 исследуются вопросы конечности и построения оценок числа итераций для прямых алгоритмов отсечения.

Пусть Л - класс прямых алгоритмов отсечения, включающий РПА и алгоритмы, получающиеся из него путем конкретизации выбора ведущего столбца и производящей строки (без управляющего ограничения), Ah -.расширение класса Л, включающее алгоритмы, в которых допускается использование управляющего ограничения. Через 1а(Р) обозначим число итераций, выполняемых алгоритмом а £ Л при решении задачи Р, Iß(P) - аналогичное обозначение для ß 6 Лъ- Рассмотрим семейство Ks,r,v,w задач ЦП:

XQ = xi — £3 —* raax

при условиях

s^i + (г — s)x2 — rx3 < v, rx 1 4- (s - г).1*2 - SX3 < w, xj > 0 — целые, j = 1,2,3.

Теорема 2.3. Для любых натуральных s,r,v,w таких, что г < v < s и г < w < s, и для любого алгоритма а £ Л имеет место соотношение Ia(Ks,r,v,w) = +00.

Рассмотрим семейство задач К^^шс получающееся из при-

соединением неравенства х-3 < с.

Теорема 2.4. Для любых натуральных {,з.г, и,ги тпаких, что г < у<зиг<т<з найдется целое число с(2) > 0 такое, что 1;,ш,с(г)) ^ * для любого алгоритма ¡3 € Ль-

Эти теоремы обобщают результаты из [3]. Приводится семейство, зависящее от б параметров, обладающее теми же свойствами. В п. 2.4 исследуется Ь- и ¿-структуры части задач из семейства

В п. 2.5 приводятся результаты вычислительного эксперимента для рассматриваемых в п. 2.1, 2.3 алгоритмов. Оказалось, что предложенные алгоритмы перебора ¿-классов решают задачи существенно быстрее, чем базовый алгоритм.

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

В п. 3.1 вводятся в рассмотрение регулярные системы неравенств. Обозначим через Кп класс замкнутых множеств из А", для которых существует х = \exrnaxQ.. Пусть Р - некоторое регулярное разбиение, 17 6 А'" и х 0 Систему линейных неравенств ^'х < 7о, г = 1,т, назовем Г-регулярной для П, если

1) для любого х' £Е ^¿(П) сзтцествует номер г такой, что 7!х' > 7ц;

2) 7'г < 7д для любого г £ 17 П Zn, г = 1, т.

Для фиксированного множества через обозначим сово-

купность всех систем, регулярных относительно разбиения Г. Пусть П) - минимальная размерность для систем из Индексом ре-

гулярного разбиения А относительно класса К" назовем величину 1(Г) = тахпед-» Например, для класса КЦ - класса ограничен-

ных сверху множеств [4] 1(Ь) — 1. Показано, что 1(Г) < п для любого регулярного разбиения А" и класса множеств А'д.

В пп. 3.2-3.3 изучаются кубические разбиения и их связь с Ь-

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

Теорема 3.2. Для класса множеств ä'q индекс произвольного кубического разбиения равен д + 1, где q - число пар компонент, соответствующего разбиению вектора 6, удовлетворяющих условиям 6{ = 0 и Si+1 =1,(1 < г < п-2).

Отсюда вытекают следующие результаты:

1. Для произвольного кубического разбиения выполнено соотношение 1 < 1(6) <f + l.

2. Для кубического разбиения индекса 1 соответствующий булев вектор имеет вид: 6 = (1,..., 1,0,..., 0,6„), где 0 < т < п - 1, 6 € {0,1}.

m

3. Для любого целого к такого, что 1 < к < ^у^ существует кубическое разбиение индекса к.

В п. 3.4 рассматривается регулярность известных классов отсечений (отсечений Гомори, вполне регулярных отсечений булева программирования [1] и некоторых других) относительно кубических разбиений. Показана регулярность ¿-алгоритма, предложенного А.А.Вотяковым, для специального класса множеств.

Список литературы

[1] Заблоцкая O.A. О сравнении вполне регулярных алгоритмов отсечения // Управляемые системы. - Новосибирск, 1984. - Вып. 25. -С.68-74.

[2] Забудский Г.Г. Некоторые свойства многогранника задачи о р-медиане// Вестник Омского университета. - Омск: Изд-во ОмГУ, 1996. -N1. - С.1-4.

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

[4] Колоколов A.A. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журн. исследования операций - 1994. -N2. - С.18-39.

[5] Кристофидес Н. Теория графов. - М.: Мир, 1978. - 432 с.

[6] Симанчев Р.Ю. О вполне регулярных отсечениях для задач целочисленной оптимизацпи // Управляемые системы. - Новосибирск: ИМ СО АН СССР, 1990. - Вып.ЗО. - С.61-71.

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

[8] Balas Е. A sharp bound on the ration between optimal integer and fractional covers// Math.. Oper. Res. - 1984. - Vol.9, N1. - P.l-5.

[9] Hochbaum D.S. Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems// Approximation Algorithms for NP-Hard Problems. Ed. by S.D.Hochbaum, PWS Publishing Company, 1995. - P.94-143.

Работы автора по теме диссертации

[10] Заозерская JI.A. Некоторые гибридные алгоритмы для задачи о покрытии // Информ. бюлл. АМП. N 7. - Екатеринбург: УрО РАН, 1997. - С.100.

[11] Заозерская JI.A. Об одном алгоритме перебора L-классов для решения задачи о покрытии множества // Труды XI междунар. Байкальской школы-семинара "Методы оптимизации и их приложения", Иркутск, Байкал, 5-12 июля 1998. - Иркутск, 1998. - Том 1. - С.139-142.

[12] Колоколов A.A., Заикина Г.М., Сайко JI.A., Цепкова Е.В. Экспериментальный анализ L-накрытий задач целочисленного программирования и алгоритмов отсечения // III Всесоюзная школа "Дискретная оптимизация и компьютеры", Таштагол, 2-9 декабря 1987. Тез. докл. - Москва, 1987. - С.117.

[13] Колоколов A.A., Сайко JI.A. Некоторые лексикографические алгоритмы решения задачи о покрытии // Математическое программирование и приложения. Тез. докл. конф. - Свердловск: УрО АН СССР, 1991.- С. 87.

[14] Колоколов A.A., Сайко Л.А. О некоторых оценочных разбиениях в целочисленном программировании // Системы программного обеспечения решения задач оптимального планирования. Материалы 10 Всесоюзного симпозиума, г.Нарва-Йыэсуу, 20-27 марта 1988. Тез. докл. - Москва, 1988. - С. 134.

[15] Сайко JI.A. Анализ ¿-сруктуры некоторых задач о покрытии// Методы и программы решения оптимизационных задач на графах и сетях. Тез. докл. IV Всесоюзного совещания, 17-19 окт. 1989г. -Новосибирск: ВЦ СО АН СССР, 1989. - Ч. 2 - С. 94.

[16] Сайко JI.A. Исследование мощности L-накрытий некоторых задач о покрытии // Дискретная оптимизация и анализ сложных систем. - Новосибирск: ВЦ СО АН СССР, 1989. - С. 76-97.

[17] Сайко JI.A. Исследование одного класса разбиений в целочисленном программировании // Управляемые системы.- Новосибирск: ИМ СО АН СССР, 1989. - Вып. 29.- С. 72-82.

[18] Сайко JI.A. О числе итераций прямых алгоритмов отсечения // Дискретная оптимизация и численные методы решения прикладных задач. - Новосибирск: ВЦ СО АН СССР, 1986. - С. 86-88.

[19] Сайко Л.А. Регулярные системы неравенств для одного класса оценочных разбиений // Методы математического программирования и программного обеспечения. Тез.докл. конф.- Свердловск: УрО АН СССР, 1989. - С. 185.

Подписано в печать 01.10.98. Формат 60x84 1/16.

Печ.л. 1,0. Уч-изд. л. 1,0. Тираж 100 экз. Заказ/// ,

Издательско-полиграфический отдел ОмГУ 644074, Омск-77, пр. Мира, 55а, госуниверситет

РОССИЙСКАЯ АКАДЕМИЯ НАУК

СИБИРСКОЕ ОТДЕЛЕНИЕ

ИНСТИТУТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И ПРИКЛАДНОЙ МАТЕМАТИКИ

ЗАОЗЕРСКАЯ Лидия Анатольевна

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

05.13.16 - применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

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

Научный руководитель д.ф.-м.н. Колоколов A.A.

Омск - 1998

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ......................................................................................................................................................4

ГЛАВА 1. АНАЛИЗ ¿-СТРУКТУРЫ ЗАДАЧ О ПОКРЫТИИ

И УПАКОВКЕ МНОЖЕСТВА......................................................................................................11

1.1. Метод регулярных разбиений и алгоритмы отсечения..........11

1.1.1. Предварительные сведения..............................................................................................11

1.1.2. Задача о покрытии......................................................................................................................17

1.2. Семейство задач о покрытии Балаша................................................................20

1.3. Блочно-диагональные задачи о покрытии....................................................28

1.4. Задача об упаковке ..............................................................................................................................43

ГЛАВА 2. АЛГОРИТМЫ ПЕРЕБОРА ¿-КЛАССОВ И

ОТСЕЧЕНИЯ....................................................................................................................................................49

2.1. Алгоритм перебора ¿-классов для решения задачи

о покрытии....................................................................................................................................................................49

2.1.1. Базовый алгоритм..........................................................................................................................49

2.1.2. Алгоритм перебора ¿-классов с тестированием............................53

2.1.3. Алгоритм перебора ¿-классов с групповым анализом задач........................................................................................................................................................................................54

2.1.4. Некоторые свойства алгоритма перебора ¿-классов

и задачи о покрытии....................................................................................................................................56

2.2. Прямые алгоритмы отсечения..........................................................57

2.3. Оценки числа итераций и контрпримеры

для прямых алгоритмов отсечения......................................................................................62

2.4. Об ¿-структуре задач из многопараметрического семейства.........................................................................................................67

2.5. Программное обеспечение и вычислительный эксперимент................................................................................................................................................................72

2.5.1. Результаты эксперимента для алгоритма перебора

L-классов ............................................................................................................................................................................72

2.5.2. Экспериментальное исследование прямых

алгоритмов отсечения..................................................................................................................................75

ГЛАВА 3. РЕГУЛЯРНЫЕ СИСТЕМЫ НЕРАВЕНСТВ........................84

3.1. Индекс регулярного разбиения........................................................................................84

3.2. Кубические разбиения и их связь с L-разбиениями........................87

3.3. Классификация кубических разбиений................................................................93

3.4. О регулярности некоторых классов отсечений......................................100

3.4.1. Отсечения 1-го алгоритма Гомори......................................................................100

3.4.2. Вполне регулярные отсечения....................................................................................107

3.4.3. Отсечения конечного прямого алгоритма................................................110

3.4.4. Отсечения z-алгоритма..........................................................................................................111

ЗАКЛЮЧЕНИЕ........................................................................................................................................................113

СПИСОК ЛИТЕРАТУРЫ........................................................................................................................114

Введение

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

В настоящее время целочисленное программирование представляет собой одно из активно развивающихся направлений дискретной оптимизации. Современная проблематика ЦП охватывает такие вопросы как структура и сложность решения задач, теория двойственности, устойчивость решений, многокритериальные задачи, полиэдральный подход, методы отсечения, ветвей и границ, декомпозиции, множителей Лагранжа, приближенные и гибридные алгоритмы, программное обеспечение, экспериментальные исследования и др. [1,5,7,9,12,17,32,3947,53-55,57,58,60,62,63,68,69,77,78,80,84,92].

Значительная часть методов решения задач ЦП основана на сведении исходной задачи ЦП к последовательности более "легких" задач непрерывной оптимизации. К таким методам относятся методы отсечения, ветвей и границ (типа метода Лэнд и Дойг [40,46]), декомпозиции (с отсечениями Бендерса [35,75,86]), алгоритмы перебора Ь-классов [32] и некоторые другие. Характерными особенностями этих методов являются использование релаксационных множеств, дополнительных линейных ограничений (отсечений) и аппарата непрерывной оптимизации.

Метод отсечения, один из общих подходов к решению задач как непрерывной, так и дискретной оптимизации, получил свое развитие в работах многих авторов, в том числе в [2,21,40,59,60,66,77,80-82,85, 94]. Отличительной чертой метода является генерация и использова-

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

Для исследования задач ЦП, построения и анализа алгоритмов их решения, основанных на использовании релаксационных множеств, А.А.Колоколовым был предложен метод регулярных разбиений [27,33], получивший дальнейшее развитие, в частности, в работах [6,1014,18,19,21,24,25,28-32,34,35,38,56,86-88].

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

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

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

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

Диссертация состоит из трех глав. В первой главе изучается ¿-структура задач о покрытии и упаковке множества. Задачи о покрытии имеют широкое практическое применение. Например, они возникают при составлении расписаний экипажей на авиалиниях, в задачах информационного поиска, политического районирования, упрощении булевых выражений [41,74]. Кроме того, другие известные задачи оптимизации могут быть сведены к задаче о покрытии [41].

Э.Балашем предложено и исследовано семейство задач о покрытии [65], которое характеризуется значительной разностью оптимальных значений целевых функций целочисленной задачи и ее линейной релаксации. В этом семействе нами выделены задачи, для которых мощность ¿-накрытий растет экспоненциально с увеличением числа переменных. Число ограничений в них также экспоненциально зависит от числа переменных. Из проведенного нами вычислительного эксперимента следует, что эти задачи являются трудными для 1-го алгоритма Гомори, так как глубина его отсечений при их решении близка к 1. Получе-

но точное выражение мощности ¿-накрытия произвольной задачи из рассматриваемого семейства.

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

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

Вторая глава посвящена построению алгоритмов решения задачи о покрытии и исследованию прямых алгоритмов отсечения в целочисленном линейном программировании (ЦЛП). В литературе описаны точные алгоритмы решения задачи о покрытии, основанные на методе ветвей и границ, отсечениях, субградиентной технике и других подходах [41,67,70,74,79,90], а также различные приближенные алгоритмы и эвристики [8,71,73,76,78,84].

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

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

Далее в этой главе исследуются вопросы конечности и построения оценок числа итераций для прямых алгоритмов отсечения. Анализу указанных алгоритмов посвящены работы [21,60,64,81,83,89,94,95]. Известно, что простые реализации прямых алгоритмов отсечения (например, рудиментарный алгоритм - РИА) не являются конечными. Первые контпримеры для РПА были опубликованы в [91]. Эти задачи, построенные в Я3, не решаются за конечное число шагов при некоторых "плохих" стратегиях решения. А.А.Колоколовым [23] построены одно-параметрическое и двухпараметрическое семейства задач ЦЛП (также в трехмерном случае), при решении которых получается бесконечный процесс для любого из вариантов РПА и других более сложных прямых алгоритмов отсечения с управляющими ограничениями. Отметим, что на плоскости для РПА получена верхняя оценка числа итераций [20] и нижняя экспоненциальная оценка для общего случая [22].

Во второй главе на основе результатов из [23] получены новые более широкие семейства задач ЦЛП, также дающие бесконечный процесс для любого из вариантов РПА и более сложных алгоритмов. С использованием указанных семейств строятся задачи ЦЛП в Л3, которые как угодно долго решаются конечным прямым алгоритмом (КПА). Это также обобщает результаты из [23]. На основе изучения ¿-структуры дробных накрытий строится верхняя оценка числа регулярных отсечений, появляющихся при решении двойственными алгоритмами части задач из построенных семейств. Исследуется структура дробных накрытий этих же задач для кубических разбиений.

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

покрытии.

Третья глава посвящена кубическим разбиениям, которые порождаются различными округлениями векторов. В ней исследуется связь этих разбиений с ¿-разбиением и существование регулярных систем неравенств относительно кубических разбиений. Регулярные системы неравенств являются обобщением регулярных отсечений. Они вводятся как системы правильных неравенств, исключающие элемент ¿"-накрытия множества, содержащий точку непрерывного оптимума. Ставится вопрос о минимальной размерности регулярной системы для разбиения называемой индексом этого разбиения, относительно фиксированного класса множеств.

Данный вопрос изучается для кубических разбиений и класса ограниченных сверху множеств [21]. В этом случае получено значение индекса, зависящее от структуры булева вектора, порождающего кубическое разбиение.

Рассматривается регулярность известных классов отсечений (отсечений Гомори [21,40,60,82], вполне регулярных отсечений булева программирования [11] и некоторых других) относительно кубических разбиений. Показана регулярность ¿-алгоритма, предложенного А.А.Вотяковым [3], для специального класса множеств.

Основные результаты диссертации опубликованы в работах [15,16, 34,36,37,48-52] и докладывались на III Всесоюзной школе "Дискретная оптимизация и компьютеры" (Таштагол, 1987), Омской областной математической конференции (1987), 10 Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования" (Усть-Нарва, 1988), 6 Всесоюзной конференции "Методы математического программирования и программное обеспечение" (Свердловск, 1989), IV Всесоюзном совещании "Методы и программы решения оптимизационных задач на графах и сетях" (Новосибирск, 1989),

III Всесоюзном семинаре "Дискретная математика и ее приложения" (Москва, 1990), 7 Всесоюзной конференции "Математическое программирование и приложения" (Свердловск, 1991), XI международной Байкальской школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 1998), а также на семинарах в Институте математики им. С.Л.Соболева СО РАН, в Омском комплексном отделе ВЦ СО АН СССР, в Институте информационных технологий и прикладной математики СО РАН.

Глава 1

АНАЛИЗ Ь-СТРУКТУРЫ ЗАДАЧ О ПОКРЫТИИ И УПАКОВКЕ МНОЖЕСТВА

В данной главе в соответствии с методом регулярных разбиений исследуется ¿-структура задач о покрытии и упаковке множества. В п. 1.1 приведены основные понятия и результаты, полученные на основе указанного метода. В п.1.2 анализируется семейство задач о покрытии, предложенное Э.Балашем, которое характеризуется значительной разностью оптимальных значений целевых функций целочисленной задачи и ее линейной релаксации. Получена экспоненциальная нижняя оценка мощности их ¿-накрытий, а также ее точное выражение. В пп. 1.2-1.3 изучаются задачи о покрытии и упаковке блочно-диагонального вида с числом ограничений, равных числу переменных. Для них также получена экспоненциальная оценка мощности ¿-накрытий. Анализируется процесс их решения алгоритмами отсечения.

1.1 Метод регулярных разбиений и алгоритмы отсечения 1.1.1 Предварительные сведения

Приведенные здесь результаты излагаются на основе работ [31,32]. Через 2п обозначим множество всех целочисленных п-векторов. Определим отношение лексикографического порядка в Вп. Вектор х лексикографически больше вектора у, х >- у, если х ф у и хр > ур для р = тт\% | Х{ ф у^ 1 < г < п}. Запись х У у означает, что либо х у у, либо х = у.

Рассмотрим разбиение пространства Яп на классы эквивалентности, которое определяется следующими условиями:

1) каждая целочисленная точка 2 образует отдельный класс; остальные классы состоят только из дробных точек и называются дробными;

2) если 5 ограничено (5 С Я71), то его разбиение состоит из конечного числа элементов;

3) для любого 5 и любого г £ Zn имеет место равенство

(S + z)/F = S/F + z.

Разбиения такого типа называются регулярными. Здесь через обозначено порождаемое разбиением Р фактор-множество. Его элементы называются Г-классами.

Пусть О - замкнутое множество из Яп, имеющее лексикографически максимальный элемент х. Рассмотрим следующую задачу ЦП: