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

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

КОРБУТ Мария Федоровна

ИССЛЕДОВАНИЕ И РЕШЕНИЕ ЗАДАЧ ОБ УПАКОВКЕ МНОЖЕСТВА НА ОСНОВЕ ¿-РАЗБИЕНИЯ И ЛЕКСИКОГРАФИЧЕСКОЙ ОПТИМИЗАЦИИ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

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

18 !;::■'! 20|3 005531648

Омск - 2013

005531648

Работа выполнена в Омском филиале Федерального государственного бюджетного учреждения науки Института математики им. С.Л. Соболева Сибирского отделения Российской академии наук

Научный руководитель:

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

Официальные оппоненты:

Попков Владимир Константинович,

доктор физико-математических наук, профессор, Федеральное государственное бюджетное учреждение науки Институт вычислительной математики и математической геофизики Сибирского отделения Российской академии наук, главный научный сотрудник

Картак Вадим Михайлович,

доктор физико-математических наук, доцент,

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Уфимский государственный авиационный технический университет»,

профессор кафедры вычислительной математики и кибернетики Ведущая организация:

Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Уральский федеральный университет имени первого Президента России Б.Н. Ельцина»

Защита состоится 8 октября 2013 года в 15 часов на заседании диссертационного совета Д 003.061.02 на базе Федерального государственного бюджетного учреждения науки Института вычислительной математики и математической геофизики Сибирского отделения Российской академии наук (ИВМиМГ СО РАН) по адресу: 630090, г. Новосибирск, проспект Академика Лаврентьева, д. 6, тел. (383)330-71-59.

С диссертацией можно ознакомиться в библиотеке ИВМиМГ СО РАН. Автореферат разослан 9 июля

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

2013 г.

Сорокин Сергей Борисович

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

Актуальность темы. Исследование многих задач оптимизации, разработка и анализ методов их решения осуществляется на основе математического моделирования, в том числе с использованием аппарата целочисленного программирования (ЦП). Особый интерес к задачам ЦП обусловлен их большой теоретической значимостью и широким кругом приложений в экономике, планировании, управлении, теории информации и других отраслях. В настоящее время модели и методы целочисленного программирования применяются для анализа и решения различных задач дискретной оптимизации, например, оптимального размещения, о покрытии, оптимизации на графах, о рюкзаке, задач проектирования, поэтому их построение и изучение являются перспективными [1-5,7-10,12,13].

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

Для исследования задач целочисленного программирования, построения и анализа алгоритмов их решения A.A. Колоколовым предложен метод регулярных разбиений [8], получивший применение и развитие во многих работах [6,11,15]. В соответствии с этим подходом релаксационное множество задачи ЦП разбивается определенным образом на классы эквивалентности. Наиболее изученным является одно из таких разбиений - L-разбиение, элементы которого называются L-классами. На его основе предложен алгоритм перебора L-классов [8], который может использоваться для решения многих задач целочисленного линейного программирования (ЦЛП), в том числе в сочетании с лексикографической оптимизацией [5].

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

3

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

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

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

Для достижения поставленной цели решались следующие задачи:

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

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

3) построить и исследовать алгоритмы, основанные на переборе ¿-классов и лексикографической оптимизации для решения рассматриваемых задач;

4) разработать научно-исследовательский вариант комплекса программ для задач об упаковке множества, в том числе с учетом ограничений блочного вида;

5) выполнить экспериментальные исследования предложенных алгоритмов.

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

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

4

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

Практическая значимость. Полученные в диссертации результаты имеют важное значение в области развития методов целочисленного программирования. Они нашли применение в лаборатории дискретной оптимизации Омского филиала ФГБУН Института математики им. C.J1. Соболева СО РАН в научных исследованиях, в частности для изучения структуры и сложности задач ЦП, при анализе, построении и тестировании алгоритмов, решении задач об упаковке множества на базе разработанного научно-исследовательского варианта комплекса программ. Кроме того, указанные результаты используются в учебном процессе на кафедре прикладной и вычислительной математики в Омском государственном университете им. Ф.М. Достоевского при подготовке специалистов по методам оптимизации и исследованию операций.

Апробация работы. Результаты диссертации докладывались и обсуждались на следующих конференциях: XXXIII научно-практической студенческой конференции «Молодежь III тысячелетия», (г. Омск, 2009), IV, V Всероссийских конференциях «Проблемы оптимизации и экономические приложения», (г. Омск, 2009, 2012), VII Международной научно-технической конференции «Динамика систем, механизмов и машин», (г. Омск, 2009), Российской конференции «Дискретная оптимизация и исследование операций», (Республика Алтай, 2010), XIV Всероссийской конференции «Математическое программирование и приложения», (г. Екатеринбург, 2011), XV Байкальской международной школе-семинаре «Методы оптимизации и их приложения», (г. Иркутск, 2011), Международной конференции «Optimization and Applications OPTIMA-2011», (г. Петровац, Черногория, 2011), Международной конференции «Алгебра и линейная оптимизация», посвященной 100-летию С.Н.Черникова (г. Екатеринбург, 2012), на заседании научного семинара лаборатории прикладных систем ФГБУН Института вычислительной математики и математической геофизики СО РАН (г. Новосибирск, 2013), а также на заседаниях научного семинара «Математическое моделирование и дискретная оптимизация» Омского филиала ФГБУН Института математики им. C.JI. Соболева СО РАН и Института математики и информационных технологий ОмГУ им. Ф.М. Достоевского (г. Омск, 2009-2013).

Публикации. Основные результаты диссертации опубликованы в 11 научных работах, три из них - в журналах из списка ВАК.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы (144 наименования). Объем диссертации -129 страниц.

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

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

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

В разд. 1.1. рассматриваются постановки задач об упаковке множества и их приложения.

Пусть дано конечное множество I = {1, ...,тп} и семейство его подмножеств Т = {5i,..., £■„}. Упаковкой множества I называется совокупность попарно непересекающихся подмножеств из Т. Задача состоит в нахождении упаковки множества I максимальной мощности. Если для каждого подмножества Sj е Т задан его вес cj > 0, j = 1, п, то задача называется взвешенной, в ней требуется найти упаковку множества I наибольшего веса.

Модель целочисленного линейного программирования для этой задачи имеет вид:

max{cz : Ах < е, х S {0,1}"}. (1)

Здесь А = (a¿j)mxn, (Mj € {0,1}, причем a¿j = 1, если i € Sj, иначе aij — 0, i = l,m, j = 1,п, с = (ci,..., Сп), е = (1,..., 1)т; переменные задачи: х = (reí,..., хп)Т, где Xj = 1, если Sj включается в упаковку, и i¿ = 0 в противном случае, j — 1, п.

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

Для матрицы А можно построить граф пересечений специального вида [4], и рассматривать задачу об упаковке множества как проблему отыскания наибольшего независимого множества вершин в данном графе (см. разд. 1.2.). В разд. 1.3. дается описание классов графов, для которых указанные задачи полиномиально разрешимы.

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

Пусть Я - выпуклое замкнутое ограниченное сверху множество из Rn, т.е. существует вектор d 6 R" такой, что х ^ d для всех х 6 П. Рассмотрим задачу целочисленного программирования, в которой требуется:

найти z* = lexmax (Í2 П Z"). (2)

При решении данной задачи различными методами, основанными на аппара-

6

те непрерывной оптимизации (алгоритмы отсечения, ветвей и границ и т.д.), требуется исключить множество = {х е О, : х у г для Мг € П П Ъп), которое называется дробным накрытием задачи (2).

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

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

2) если множество X С К" ограничено, то его разбиение состоит из конечного числа элементов;

3) для произвольного X и любого гег" имеет место (X + г) ¡Е — Х/Е+г.

Разбиение, удовлетворяющее условиям 1)-3), называется регулярным. Множество Х/Е называется F-структурой, а его элементы - Е-классами.

В данной работе для анализа задачи об упаковке множества и построения алгоритмов ее решения применяется ¿-разбиение пространства Мп, в котором каждая точка г £ 2™ образует отдельный класс, нецелочисленные точки х,у £Шп (х >- у) принадлежат одному классу, если Е Ъп: х >- г >- у. Будем называть ¿-класс V существенным, если найдется лексикографически максимальный элемент ж ё V. Множество С1„/Ь называется Ь-накрытием.

На рис. 1 изображено разбиение множества П С К2 на ¿-классы, ¿-структура имеет вид П/Ь = {Уь ..., У5}. Здесь И = {ж 6 П : Х\ > 1}, У2 = {х € П : XI = 1, х2> 1}, У3 - точка (1,1), У4 = {х € О : хг = 1, х2 < 1}, У5 = {ж € Г2: XI < 1}.

Х2

2

1

О 1 2 " X,

Рис. 1. Разбиение множества П на ¿-классы

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

найти г* = 1ехтах (£/Л2П+1), 7

п

где II = {х € Еп+1 : х0 - ^ с^х^ =0, Ах < е, х ^ 0}. В этом случае

¿=1

дробное накрытие имеет вид £/« = {ж' е ?7 : ж' г, для Уг £ (/П 2П+1}, здесь г = (го, 21,..., гп) - допустимое решение задачи (3).

В разд. 1.5. описывается алгоритм перебора Ь-классов (ЬСЕ) [8] для отыскания оптимального вектора х 6 {0,1}", доставляющего максимум целевой функции /(х) = (с, а;) на множестве М = {х £ [0,1]" : Ах < Ь,х ^ 0}, А 6 Ктхп, Ь 6 Мт. Основной шаг процесса решения задачи состоит в переходе от одного ¿-класса релаксационного множества М к следующему за ним в порядке лексикографического убывания с учетом рекордного значения целевой функции. В результате порождается последовательность 5 точек х^ € М. Процесс начинается с лексикографически максимальной точки а^1' е М. Текущие точки х® строятся посредством решения задач линейного программирования (ЛП) с помощью лексикографического двойственного симплекс-метода или метода лексикографической (последовательной) оптимизации. Процесс завершается, когда не удается найти представителя очередного //-класса. В случае, если задача разрешима, лучшее из найденных булевых решений является оптимальным. Анализ алгоритма ЬСЕ и разработка на его основе гибридных схем решения представлены в главе 3.

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

В разд. 2.1. рассматривается задача, возникающая при проектировании системы радиосвязи. Пусть имеется множество пар источник-получатель Р = {р!,..., Рп-в}, между которыми устанавливаются сеансы связи. Сформированы К групп пар абонентов Р\,..., Рк, Рк С Р, к = 1, К и столько же объединений каналов связи 7?1,..., Як из множества Я = {1,..., ш}, где Як = {1,..., тк}, причем пара абонентов из Рк может применять для передачи данных только каналы из множества Як, к = 1, К. Здесь в качестве каналов связи используются радиочастоты, деление на группы определяется диапазонами применяемых частот при передаче сообщений. В систему также входят выделенные абоненты - «центры» связи И = {<¿1,..., с^}, которые работают во всех К частотных диапазонах. Между центром € Б, ^ = в и каждой группой абонентов Рк, к = 1, К закреплены каналы для обмена данными. Для каждого канала задана его производительность /,-, г = 1 , т, которая определяет число возможных одновременных соединений между абонентами по данному каналу. Требуется найти максимальное количество абонентов, которые могут устанавливать сеансы связи в указанной системе.

Построим математическую модель задачи. Составим матрицы Ак = (^)ткхпк, А' = (а'ц)тхз, где = 1, если пара абонентов р, € Р

8

(центр 6 й) использует канал г для передачи сообщений, 0 - иначе. Введем переменные х^ ] = ..., х'г 3 = ^ • • • > в> положим х^ = 1,

если пара абонентов р^ выбрана для передачи данных в системе связи, х^ = 1, если центр включается в рассматриваемую систему, х^ = 0 (х^ = 0) в противном случае. Тогда модель ЦЛП имеет следующий вид:

К Пк 8

к=1

Пк а

X°%зхз + Xа'чх'з < /*>1 = 1>т>" к = 1>К>

3=1 3=1

^ € {0,1},^ = 1,п-я;х) е {0,1},^ = М.

Данная модель представляет собой задачу об упаковке множества блочной структуры со связующими столбцами, в разд. 2.2. исследуются семейства задач указанного типа, а в разд. 3.3. построен алгоритм ВЗРСХ, который может быть применен для ее решения.

В разд. 2.2. рассматривается задача об упаковке множества (3) с матрицей £>£, к, г € М, состоящей из к блоков и г столбцов в связующем блоке,

(В

т =

V

грЪк+1

грЗк+\ л2

о тЦк+г

гр2к+г \ грЗк+т

Т3к+г у

где В =

( 0 1 1\ 1 0 1

V1 1

Т/ = (ТД, 1*з)т, е {0,1}, г = 1,3, з = 1, /с, Н = 1, г. Далее ТЬ будем называть тройкой. Эти задачи представляют собой обобщение блочных-диагональных задач с матрицей Д исследование которых проведено в [11]. Доказана следующая

Теорема 2.3. Если в каждом столбце с номерами э = З/г+1,..., 3к+г имеется хотя бы одна тройка, в которой не менее двух единиц, то для мощности Ь-накрытий невзвешанных задач вида (3) с матрицами Огк, г, справедлива оценка

\и.(Щ)/Ц >

зк-з

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

Полученные оценки указывают на то, что наличие связующих столбцов может заметно уменьшить мощность /^накрытия.

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

При построении указанных семейств применялись следующие графы: порожденный простой цикл, его дополнение, колесо и клика. Обозначим через Н(с[), А(д), И^д), С(д) соответственно матрицы инциденций «ребра-вершины» данных графов на д вершинах, а через XVе (о) - матрицу максимальных клик для колеса, также содержащего q вершин.

Метод построения семейств трудных задач заключается в объединении к одинаковых матриц С?((7) из множества {#(<?), А(д), \¥(д), С(д), IVе(д)}, к, д е N в одну путем создания блочно-диагональной системы ограничений без пересечения блоков. В общем виде получаем семейства невзвешенных задач (3) с матрицами Ос(ч),к- Доказаны теоремы 2.5. - 2.12., в которых получены нижние оценки мощности ¿-накрытий задач из рассматриваемых семейств. Было установлено, что \и,(Пс(ч),к)/Ц > а, где а принимает значения из табл. 1.

Таблица 1.

_Значение параметра а___

Семейство/<7 9 = 3 | 9 = 5 1 9 ^ 7, д - нечет. 9 = 4 | 9 = 6 | 9^8, ? - чет.

9»-1

Д4(,),к - 6"-1 9 — 1

<!(<!'-' -11 9(9^-1)

- 2*-2 („-1Г-1 0-2

- (9-1) -(9-1) (4-2)9

°С(я),к з"-з 3 о'-оГ^т 9(9^-1) 4'-2 3 9(9^-1)

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

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

Теорема 2.13. Пусть имеются две невзвешенные задачи об упаковке

множества вида (3) с МСППриЦОЛШ .Агщхщ; -^7712x712 «Я = ^ ^, тогда

справедливо неравенство \и„(Н)/Ь\

ю

Рассмотрим невзвешенную задачу вида (3) с произвольной матрицей ограничений А. При помощи объединения матриц А и ¿>с(?),ь к, с/ <Е N в одну блочно-диагональную систему ограничений получим подклассы ИР-трудных задач об упаковке множества, для которых остаются справедливыми оценки мощности ¿-накрытий из табл. 1. Решение этих задач требует экспоненциального числа итераций алгоритмов, основанных на вполне регулярных отсечениях, методе перебора ¿-классов и его вариантов с использованием лексикографической оптимизации. Указанные задачи могут применяться при тестировании и других алгоритмов ЦП.

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

В разд. 3.1. проведен анализ алгоритма перебора ¿^классов и найдена нижняя оценка числа его итераций. При изучении алгоритма ЬСЕ важную роль играет связь построенной им последовательности приближений 5 с множествами нецелочисленных вершин многогранников задач. Было установлено, что в алгоритмах перебора ¿-классов выполняется лексикографический перебор существенных ¿-классов. На основе отмеченного свойства в работе доказана следующая

Теорема 3.2. Для последовательности приближений алгоритмов, основанных на методе перебора Ь-классов, при решении задачи (1) справедлива оценка

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

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

Рассмотрим задачу поиска лексикографически максимальной точки х* = (х^,..., х*) многогранника М, определенного системой линейных уравнений и неравенств. Идея метода лексикографической (последовательной) оптимизации [5] состоит в формировании оптимального решения данной задачи из соответствующих значений целевых функций последовательности подзадач линейного программирования к = 1, ...,п следующего вида:

/(х) = Хк —> тах

х=(хи...,хп)еМк, Мк = МП и^!1^- = х}}.

Разработан алгоритм перебора Ь-классов ЬСЕсх, в котором при отыскании представителя очередного ¿-класса для решения лексикографических задач линейного программирования применяется метод последовательной оптимизации, и каждая задача ЛП без учета лексикографии, полученная в соответствии с этим подходом, решается при помощи пакета программ СРЬЕХ.

Заметим, что для алгоритма ЬСЕСХ остается справедливой оценка числа итераций, полученная в теореме 3.2.

Для задачи об упаковке множества построены модификации БРСХ, дрсх_^£рсх алгоритма ЬСЕсх за счет внесения в исходные процедуры следующих изменений: исключение переменных, значения которых в оптимальном решении заведомо равны 0; учет информации, содержащейся в текущих симплексных таблицах; использование эвристик для получения начального рекорда; добавление правильных неравенств к матрице ограничений и удаление доминируемых строк; применение переупорядочения переменных, как одного из унимодулярных преобразований задачи.

Рассмотрим задачу об упаковке множества вида (1) с матрицей Щ, в которой вь € {о, 1>™, г = 1Л в = (5у) € {о, 1}гхт,

Н1

( 5п

521

V 9т1

9\Т вг \

92т в2 о

9тг

вк

С целью решения таких задач был разработан алгоритм перебора ¿-классов ВЗРСХ с использованием декомпозиции по блокам. В процедуре ЬСЕсх при решении задач ЛП, часть переменных исходной задачи принимает фиксированные значения. Идея алгоритма ВБРСХ заключается в следующем. В случае, когда зафиксированы переменные х\,...,хр, соответствующие связующим столбцам (р > г), то задача отыскания оптимальных значений переменных (жр+х,..., хп) разбивается на несколько подзадач ЦЛП, каждая из которых соответствует отдельному блоку или его части. Все подзадачи решаются отдельно при помощи алгоритма БРах.

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

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

pax перебора L-классов при решении задач вида (1).

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

В разд. 4.1. представлено описание разработанного научно-исследовательского варианта комплекса программ «MIS and MSP» для решения задач об упаковке множества. Программное обеспечение написано на языке С++, для создания интерфейса применялись библиотеки MFC. Данное приложение позволяет генерировать, просматривать, загружать, сохранять в файлы, решать задачи об упаковке множества в общей постановке, с системами ограничений блочной структуры и задачи о наибольшем независимом множестве. Решение рассматриваемых задач может быть найдено при помощи алгоритмов перебора L-классов, их модификаций с учетом специфики и структуры задач, в том числе с использованием лексикографической оптимизации, жадного и вероятностных алгоритмов, пакета программ IBM ILOG CPLEX 12.1.

На базе созданного программного обеспечения «MIS and MSP» проведены экспериментальные исследования. Расчеты были выполнены на задачах со случайными исходными данными с использованием ПК Intel Core Î5-2410M 2,3 Гц/RAM 4Гб.

Пусть элементы матрицы А задачи (1) являются случайными величинами, при этом P{a,ij = 1} = р, P{aij = 0} = 1 — р. В разд. 4.2. изучалась зависимость среднего числа итераций алгоритма LCE от р. Экспериментально было показано, что наиболее сложными для LCE оказываются задачи, у которых р « где pkz - значение вероятности, которая вместе с параметрами задачи удовлетворяет условию rnpfz ^ Inn. Если P{(iij = 1} = Pkz, то теоретически обосновано (см. [6]), что среднее число итераций алгоритма LCE не превосходит Зп + 1 при решении задач вида (1).

В разд. 4.3. проводится анализ гибридных алгоритмов, основанных на сочетании методов перебора L-классов и лексикографической оптимизации для задач об упаковке множества. Были определены особенности каждой модификации SPfx + SPfx. Сравнение времени решения задач вида (1) с применением процедуры SPCX и пакета CPLEX показало, что алгоритм gpCX 0бладает преимуществом перед модулем CP LEX на задачах достаточно большой размерности, полученных с использованием значений р из интервала (^р,

Разд. 4.4. посвящен экспериментальному исследованию алгоритмов для задач об упаковке множества блочной структуры. Каждая серия тестовых примеров была решена алгоритмами SPCX и BSPCX. По результатам вычислений задачи можно разделить на две группы: для одних алгоритм SPCX

находил решение за небольшое время, быстрее чем BSPCX, а для других алгоритмом SPCX были найдены только приближенные решения после 60 минут счета, в то время как BSPCX решал задачи второго типа за время, не превосходящее 5 минут. Из этого можно сделать вывод, что алгоритм BSPCX является более «устойчивым» к значениям мощности ¿-накрытия задач и, следовательно, предпочтительнее для решения задач блочного типа.

В заключении сформулированы основные результаты и выводы диссертационной работы.

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

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

2. Разработаны гибридные алгоритмы, основанные на переборе ¿-классов и методе лексикографической оптимизации, для решения задач об упаковке множества в общей постановке и с системами ограничений блочной структуры.

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

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

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

Автор благодарит научного руководителя Колоколова A.A. за внимание и поддержку при подготовке данной работы.

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

[1] Авербах И.Л., Цурков В.И. Целочисленные оптимизационные модели блочного типа // Математическое моделирование. - 1990. - Т. 2, № 2. -С. 39-57.

[2] Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. - Ижевск: НИЦ «Регулярная и хаотичная динамика», 2001. - 288 с.

[3] Евтушенко Ю.Г., Посыпкин М.А. Варианты метода неравномерных покрытий для глобальной оптимизации частично-целочисленных нелинейных задач // Доклады Академии наук. - Т. 437, № 2. - С. 168-172.

[4] Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы,

оптимизация. - М.: Наука, 1981. - 344 с.

14

[5] Еремин И.И., Мазуров Вл.Д., Скарин В.Д., Хачай М.Ю. Математические методы в экономике. - Екатеринбург: УрГУ - Центр «Фактория Пресс», 2000. - 303 с.

[6] Заозерская JI.A., Колоколов A.A. О среднем числе итераций некоторых алгоритмов для решения задачи об упаковке множества // Труды XIV Байкальской международной школы-семинара «Методы оптимизации и их приложения». - Иркутск, 2008. - Т. 1. - С. 388-395.

[7] Картак В.М. Метод группировки для решения непрерывной задачи линейного раскроя // Дискретный анализ и исследование операций. -2009. - Т. 3, № 16. - С. 47-62.

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

[9] Леонтьев В.К. Устойчивость в линейных дискретных задачах // Проблемы кибернетики. - 1979. - Вып. 35. - С. 169-184.

[10] Попков В.К. Математические модели связности // 2-е изд., испр. и доп. - Новосибирск: Изд. ИВМиМГ СО РАН. - 2006. - 490 с.

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

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

[13] Шевченко В.Н. Качественные вопросы целочисленного программирования. - М.: Физматлит, 1995. - 190 с.

[14] Borndörfer R. Aspects of Set Packing, Partitioning, and Covering. PhD thesis, Technische Universität Berlin, 1998.

[15] Kolokolov A.A. On the ¿^structure of integer linear programming problems // System Modelling and Optimization: Proceedings of the 16th IFIP conference on the modelling and optimization. - Springer Verlag. 1993. - P. 756-760.

Опубликованные работы по теме диссертации

В рецензируемых журналах из списка ВАК

1. Колоколов A.A., Орловская Т.Г., Рыбалка М.Ф. Исследование алгоритмов целочисленного программирования с использованием регулярных разбиений и унимодулярных преобразований // Автоматика и телемеханика. - 2012. - № 2. - С. 178-190.

2. Колоколов A.A., Корбут М.Ф. Исследование одного класса задач об упаковке множества // Вестник Омского университета. - 2012. 4. -С. 21-26.

3. Колоколов A.A., Корбут М.Ф. Решение задачи об упаковке множества с ограничениями блочной структуры // Омский научный вестник. -2013.1(117).-С. 29-33.

В других изданиях

4. Рыбалка М.Ф. Решение некоторых задач об упаковке множества // Труды научно - практической студенческой конференции «Молодежь III тысячелетия». - Омск, 2009. - С. 260-261.

5. Колоколов A.A., Рыбалка М.Ф. Разработка и анализ алгоритмов решения задачи об упаковке множества с использованием ¿-разбиения // Труды Всероссийской конференции «Проблемы оптимизации и экономические приложения». - Омск: Полиграфический центр КАН, 2009. -С. 138.

6. Колоколов A.A., Рыбалка М.Ф. Исследование и решение задачи об упаковке множества блочной структуры // Материалы VII Международной научно-технической конференции «Динамика систем, механизмов и машин». - Омск: ОмГТУ, 2009. - Кн. 3. - С. 55-59.

7. Колоколов A.A., Рыбалка М.Ф. Анализ и решение одного класса задач об упаковке множества // Материалы Российской конференции «Дискретная оптимизация и исследование операций» - Новосибирск: Изд-во Института математики, 2010. - С. 95.

8. Колоколов A.A., Рыбалка М.Ф. Анализ алгоритмов перебора ¿-классов для решения задачи об упаковке множества // XIV Всероссийская конференция «Математическое программирование и приложения»: Информационный бюллетень № 12. - Екатеринбург, 2011. - С. 187.

9. Рыбалка М.Ф. Анализ некоторых алгоритмов для задачи об упаковке множества с матрицей блочной структуры // Труды XV Байкальской международной школы-семинара «Методы оптимизации и их приложения». - Иркутск, 2011. - Т. 4. - С. 197-202.

10. Kolokolov A.A., Orlovskaya T.G., Rybalka M.F. Analysis of some integer programming algorithms based on the method of regular partitions // Abstracts of II International conference «Optimization and applications» (OPTIMA-2011). - М.:ВЦ PAH, 2011. - P. 133-136.

И. Корбут М.Ф. Решение задач об упаковке множества с использованием последовательной оптимизации и перебора ^классов. Препринт. - Омск: ОмГУ, 2013. - 24 с.

Подписано в печать 04.07.2013. Формат 60x84/16. Бумага писчая. Оперативный способ печати. Усл. печ. л. 1,0. Тираж 140 экз. Заказ №511.

Отпечатано в «Полиграфическом центре КАН» тел. (3812) 24-70-79, 8-904-585-98-84.

E-mail: pc_kan@mail.ru 644050, г. Омск, ул. Красный Путь, 30 Лицензия ПЛД № 58-47 от 21.04.97

Омский филиал

Федерального государственного бюджетного учреждения науки Института математики им. С.Л. Соболева Сибирского отделения Российской академии наук

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

04201 361 594

КО РВУТ Мария Федоровна

ИССЛЕДОВАНИЕ И РЕШЕНИЕ ЗАДАЧ ОБ УПАКОВКЕ МНОЖЕСТВА НА ОСНОВЕ Ь-РАЗБИЕНИЯ И ЛЕКСИКОГРАФИЧЕСКОЙ ОПТИМИЗАЦИИ

05.13.18 - Математическое моделирование, численные методы и комплексы

программ

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

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

Омск - 2013

Оглавление

Введение ..................................................................4

Глава 1. Математические модели и методы для задач об упаковке множества......................................................11

1.1. Постановки задач и приложения..................................11

1.2. Задача о наибольшем независимом множестве..................14

1.3. Полиномиально разрешимые случаи..............................21

1.4. Метод регулярных разбиений......................................24

1.5. Алгоритм перебора ¿-классов......................................32

Глава 2. Исследование задач об упаковке множества с системами ограничений блочной структуры............................37

2.1. Проектирование одной системы радиосвязи......................37

2.2. Анализ ¿-накрытий задач со связующими столбцами..........40

2.3. Оценки мощности ¿-накрытий для некоторых семейств задач 48

2.4. Подклассы ^тР-трудных задач ....................................60

Глава 3. Разработка и анализ алгоритмов........................64

3.1. Исследование процесса перебора ¿-классов......................64

3.2. Алгоритмы перебора ¿-классов и лексикографической оптимизации для задач об упаковке множества......................69

3.3. Алгоритмы решения задач блочной структуры..................76

3.4. О приближенном решении задач..................................80

Глава 4. Результаты вычислительного эксперимента..........84

4.1. Описание разработанного комплекса программ..................84

4.2. О среднем числе итераций метода перебора L-классов..........89

4.3. Исследование алгоритмов для задач об упаковке множества . 92

4.4. Решение задач об упаковке множества, блочной структуры . . 104

Заключение................................111

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

Введение

Актуальность темы. Исследование различных задач оптимизации, разработка и анализ методов их решения осуществляется на основе математического моделирования, в том числе с использованием аппарата целочисленного программирования (ЦП) [9.20,29.74.81,90.92]. Особый интерес к задачам ЦП вызван тем. что во многих случаях необходимо находить оптимальные решения, удовлетворяющие условию целочисленности. Указанные задачи имеют большое теоретическое и практическое значение.

Модели и методы целочисленного программирования [8,21.25,27.3739,69.78,85,91,93] применяются для анализа и решения задач дискретной оптимизации [4,39,64.67.73,85], например, оптимального размещения [57. 11. 32. 33. 52. 53, 77], о покрытии [26. 84]. максимальной выполнимости логической формулы [2, 3, 43, 44], о рюкзаке [49, 56, 129, 133], задач проектирования с логическими ограничениями [14. 54, 63]. оптимизации на графах [79.80], поэтому данной проблематике посвящено значительное число публикаций.

Задачи об упаковке множества занимают важное место в дискретной оптимизации и имеют широкий круг приложений в экономике, планировании, управлении, теории информации и других областях [24.68,96-98.121.131,140.142]. Для указанных задач изучается их структура и сложность, выделяются полиномиально разрешимые случаи и семейства трудных задач, устанавливаются новые свойства многогранников, разрабатываются и исследуются алгоритмы точного и приближенного решения [66, 96, 100, 106, 107. 111. 114, 116, 124, 132, 138].

Многие результаты получены с применением целочисленного линейного программирования и отражены в работах [34,47.71,115,134.136.137]. В связи с этим исследование задач об упаковке множества и разработка алгоритмов их решения является актуальным направлением.

При моделировании сложных экономических и технических систем часто возникают оптимизационные задачи большой размерности, которые относятся к задачам целочисленного программирования блочного типа [1, 94]. При этом блоки обычно представляют в моделях отдельные объекты, подразделения фирмы, части одного устройства, различные временные отрезки и т.п. Они могут быть соединены между собой ограничениями, в которых выражена необходимость использования общих ресурсов, обеспечения взаимосвязи решений для всего предприятия, технологического процесса или периода планирования. Некоторые постановки предстваляют собой задачи об упаковке множества блочной структуры. Перспективным направлением анализа и решения таких задач является применение декомпозиционных методов, в которых учитывается блочная структура модели. Так. в работе [94] исследуются дискретные задачи квазиблочного типа, в [72, 99] предлагаются различные методы приведения систем ограничений задач ЦП к блочному виду, в [76] строится алгоритм для решения задачи прямоугольной упаковки на базе использования блочных структур.

Для решения задач об упаковке множества можно применять алгоритмы, разработанные на основе известных методов целочисленного программирования, в частности схемы ветвей и границ [130. 138], различных процедур неявного перебора допустимых решений (см., например, [95]). метода лексикографической оптимизации [28], алгоритмов отсечений [10,31,40,87,88,118,135]. Среди процедур приближенного решения рассматриваемых задач наиболее известны генетические алгоритмы, методы локальной оптимизации, алгоритмы муравьиных колоний, схемы жадного типа [106,107,111,114] и другие.

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

и анализа алгоритмов их решения A.A. Колоколовым был предложен метод регулярных разбиений [40—42. 47]. получивший применение и развитие во многих работах. В соответствии с этим подходом релаксационное множество задачи ЦП разбивается определенным образом на классы эквивалентности. Наиболее изученным является одно из таких разбиений - L-разбиепие, элементы которого называются L-классами. На его основе построены алгоритмы перебора L-классов, используемые для решения различных задач ЦП [3,43-45,47].

С помощью регулярных разбиений изучена структура и сложность ряда задач ЦП. разработаны и исследованы новые алгоритмы и классы правильных отсечений, построены оценки числа итераций для известных алгоритмов целочисленного линейного программирования, выполнены исследования устойчивости некоторых задач и процессов их решения, проведена серия вычислительных экспериментов [16-18,26,30,35,42,47.49, 55,84]. Значительное число результатов получено на основе L-разбиения [2, 3,19,35,42-45.47.50,51,57-С1,65.82.83,109.110.127].

В последнее время рассматриваются вопросы применения метода регулярных разбиений в сочетании с унимодулярными преобразованиями [46.89]. которые позволяют улучшить структуру задач и повысить эффективность алгоритмов их решения [18,129]. Выполнен анализ z-алгоритма решения задач ЦЛП [12], в частности исследована его регулярность относительно кубических и других разбиений [55].

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

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

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

Для достижения поставленной цели решались следующие задачи:

1) исследовать математические модели ряда проблем, возникающих при проектировании сложных систем, в частности систем связи с использованием задач об упаковке множества:

2) провести анализ структуры и сложности задач об упаковке множества, включая постановки блочного типа на основе Ь-разбиения, выделить и изучить семейства задач с Ь-накрытиями экспоненциальной мощности:

3) построить и исследовать алгоритмы, основанные на переборе ¿-классов и лексикографической оптимизации для решения рассматриваемых задач:

4) разработать научно-исследовательский вариант комплекса программ для задач об упаковке множества, в том числе с учетом ограничений блочного вида;

5) выполнить экспериментальные исследования предложенных алгоритмов.

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

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

Практическая ценность. Полученные в диссертации результаты представляют ценность в области развития методов целочисленного программирования. Они нашли применение в лаборатории дискретной оптимизации Омского филиала ФГБУН Института математики им. С.Л. Соболева СО РАН в научных исследованиях, в частности для изучения структуры и сложности задач ЦП, при анализе, разработке и тестировании алгоритмов, решении задач об упаковке множества на базе разработанного научно-исследовательского варианта комплекса программ. Кроме того, указанные результаты используются в учебном процессе на кафедре прикладной и вычислительной математики в Омском государственном университете им. Ф.М. Достоевского при подготовке специалистов по методам оптимизации и исследованию операций.

Апробация работы. Результаты диссертации докладывались и обсуждались на следующих конференциях: XXXIII научно-практической студенческой конференции «Молодежь III тысячелетия», (г. Омск. 2009), IV. V Всероссийских конференциях «Проблемы оптимизации и экономические приложения», (г. Омск, 2009, 2012), VII Международной научно-технической конференции «Динамика систем, механизмов и машин», (г. Омск. 2009), Российской конференции «Дискретная оптимизация и исследование операций», (Республика Алтай, 2010),

XIV Всероссийской конференции «Математическое программирование и приложения», (г. Екатеринбург. 2011). XV Байкальской международной школе-семинаре «Методы оптимизации и их приложения», (г. Иркутск, 2011). Международной конференции «Optimization and Applications ОРТ1МА-2011». (г. Петровац, Черногория. 2011). Международной конференции «Алгебра и линейная оптимизация», посвященной 100-летию С.Н.Черникова (г. Екатеринбург, 2012), па заседании научного семинара лаборатории прикладных систем ФГБУН Института вычислительной математики и математической геофизики СО РАН (Новосибирск, 2013). а также на заседаниях научного семинара «Математическое моделирование и дискретная оптимизация» Омского филиала ФГБУН Института математики им. С.Л. Соболева СО РАН и Института математики и информационных технологий ОмГУ им. Ф.М. Достоевского (Омск, 2009-2013).

Публикации. Основные результаты диссертации опубликованы в 11 научных работах [50.51.57-61.65.82,83,128]. три из них - в журналах из списка ВАК [50,51,57].

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы (144 наименования). Объем диссертации - 129 страниц.

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

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

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

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

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

В заключении сформулированы основные результаты и выводы диссертационной работы.

Автор благодарит научного руководителя Колоколова A.A. за внимание и поддержку при подготовке настоящей работы.

Глава 1

Математические модели и методы для задач об упаковке множества

Настоящая глава посвящена математическим моделям и методам для задач об упаковке множества. В разд. 1.1. приводятся постановки указанных задач и иформация об их приложениях. В разд. 1.2. представлена известная задача о наибольшем независимом множестве вершин графа. Разд. 1.3. содержит описание классов графов, для которых рассматриваемые задачи полиномиально разрешимы, там же перечисляются условия целочисленное™ многогранников задач. В разд. 1.4. даются основные сведения о методе регулярных разбиений, Ь-разбиении и о результатах исследований Ь-структуры. В разд. 1.5. излагается алгоритм перебора Ь-классов.

1.1. Постановки задач и приложения

Пусть дано конечное множество I = {1 ,...,т} и семейство его подмножеств Т = {б1!,..., 5П}. Упаковкой множества I называется совокупность попарно непересекающихся подмножеств из Т. Задача состоит в нахождении упаковки множества / максимальной мощности. Если для каждого подмножества € Т задан его вес с^ > 0, ] = 1,п, то задача называется взвешенной, и в ней требуется найти упаковку множества /

наибольшего веса.

Для анализа и решения задачи об упаковке множества в данной работе используется модель целочисленного линейного программирования. Обозначим через А = (агз) - матрицу инциденций элементов множества I и подмножеств где

{1, если г 6 5, _ _

, г = 1,771, 3 = 1,71.

О, иначе

Введем переменные

{1, если включается в упаковку -

, 3 =

О, иначе

Получаем следующую модель ЦЛП:

п

—>• тах (1.1)

при условиях

п

г = 1,т; (1.2)

3=^

.7 = Т^п. (1.3)

Здесь максимизируется суммарный вес множеств, входящих в упаковку, ограничение (1.2) гарантирует выполнение условия попарного непересечения множеств.

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