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

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

005010331

ЛАГЗДИН Артем Юрьевич

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

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

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

9 0ЕЗ 20"е2

Омск - 2012

005010331

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

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

профессор Забудский Геннадий Григорьевич

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

Защита состоится 01 марта 2012 г. в 1645 часов на заседании диссертационного совета ДМ 212.179.07 при Омском государственном университете им. Ф.М. Достоевского по адресу: 644099 г. Омск, ул. Певцова, д. 13.

С диссертацией можно ознакомиться в библиотеке Омского государственного университета им. Ф.М. Достоевского по адресу: 644077 г. Омск, проспект Мира, д. 55-А.

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

Ведущая организация: Иркутский государственный университет

Автореферат разослан "2н " _____ 2012 г.

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

Семенов А.М.

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

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

По признаку наличия фиксированных связей между объектами в задачах размещения можно выделить два класса - размещение взаимосвязанных объектов и размещение-распределение. В задачах первого класса требуется найти позиции для расположения объектов с заранее заданными связями между ними. Наиболее известные представители этого класса - это квадратичная задача о назначениях и задача Вебера. Они рассматривались в работах Ахмедова И.С., Демиденко В.М., Забудского Г.Г., Иорданского М.А., Метельского H.H., Панюкова A.B., Сергеева С.И., Сигала И.Х., Трубина В.А., Burkard R.E., £ela E., Finke G. и других. Во втором классе задач связи между объектами изначально не фиксированы, а устанавливаются в процессе их решения. К ним относятся, в частности, простейшая задача размещения, задача о р-медиане, задача о р-центре, задача размещения с предпочтениями клиентов. Значительный вклад в развитие этого направления внесли Береснев B.JL, Гимади Э.Х., Колоколов A.A., Кочетов Ю.А., Кристофидсс Н. и другие.

Актуальными в настоящее время является исследование задач оптимизации на сетях и различных дискретных структурах. Данному направлению, в частности, посвящены работы Ерзина А.И., Кристофидеса H., Кузьмина О.В., Попкова В.К. В диссертации изучается дискретная задача размещения взаимосвязанных объектов - квадратичная задача о назначениях (КЗН), сформулированная в терминах теории графов. Она ДГР-трудна в общей постановке.

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

Точные методы решения КЗН (например, алгоритмы ветвей и границ) слабо применимы на практике. В задачах с числом объектов более 20

не гарантировано нахождение точного решения за приемлемое время. Для

3

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

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

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

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

• сформулировать задачу оптимального размещения взаимосвязанного технологического оборудования нефтехимического предприятия в виде модели КЗН;

• разработать полиномиальные алгоритмы решения КЗН для специальных структур связей между объектами и сетей, на которых производится размещение;

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

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

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

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

4

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

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

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

2. Разработан полиномиальный алгоритм решения КЗН с минимаксным критерием для размещения объектов со структурой связей в виде цени на древовидной сети в случае ребер одинакового веса.

3. Предложен параллельный алгоритм динамического программирования решения КЗН с минисуммным критерием для графа связей общей структуры с произвольными весами ребер па древовидной сети с равными весами.

4. Разработан алгоритм поиска приближенного решения КЗН с минисуммным критерием для графа связей и сети общего вида с произвольными весами ребер.

5. Создан программный комплекс с реализацией предложенных параллельного алгоритма динамического программирования и алгоритма поиска приближенного решения. Проведено экспериментальное исследование эффективности параллельного алгоритма в зависимости от характеристик сети и конфигурации ЭВМ. Выполнено сравнение его работы с результатами решения задачи программным пакетом 1ВМ 1ЬОС СРЬЕХ. Проведен вычислительный эксперимент по анализу работы алгоритма поиска приближенного решения.

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

5

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

Апробация работы. Результаты диссертации докладывались на IV Всероссийской конференции "Проблемы оптимизации и экономические приложения" (г. Омск, 2009), VII Международной научно-технической конференции "Динамика систем, механизмов и машин" (г. Омск, 2009), Российской конференции "Дискретная оптимизация и исследование операций" (Республика Алтай, 2010), Международной конференции "Operations Research 2010" (г. Мюнхен, Германия, 2010), 8 Международной конференции "Интеллектуализация обработки информации ИОИ-2010" (г. Пафос, Республика Кипр, 2010), XIV Всероссийской конференции "Математическое программирование и приложения" (г. Екатеринбург, 2011), XXXV Региональной научно-практической студенческой конференции "Молодежь третьего тысячелетия" (г. Омск, 2011), Международной конференции "Operations Research 2011" (г. Цюрих, Швейцария, 2011), Международной конференции "Optimization and Applications OPTIMA-2011" (г. Петровац, Черногория, 2011), а также на научных семинарах в Омском филиале Учреждения Российской академии наук Института математики им. C.JI. Соболева Сибирского отделения РАН (2009-2011).

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

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

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

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

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

В п. 1.1 рассматриваются различные постановки КЗН. Впервые данная задача была сформулирована Купмансом Т. и Бекманном М. в 1957 году как математическая модель для дискретной задачи размещения предприятий. Необходимо разместить п предприятий (объектов) в п позиций по одному в каждую таким образом, чтобы минимизировать суммарную стоимость связей, которая пропорциональна удельным стоимостям связей между предпри-

б

ятиями умноженным на расстояния между позициями. В некоторых случаях дополнительно учитывается стоимость размещения предприятий в указанные позиции. Задачу можно сформулировать с помощью трех матриц: А = (оц¡), где щи - стоимость связи между объектами г и fc; В — (Ъц), Ъц - расстояние между позициями j и I; С = (Су), Су - стоимость размещения объекта г в позицию j, где i,j,k = l,...,n. Пусть тг - это подстановка на множестве

{1, ...,га}, тогда целевая функция КЗН в постановке Купманса-Бекманна

имеет вид

П Т1 п

<ЕЕ ^¿fc^7r(i)7r(fc) ^17г(г)) ^TTtzSn тШ,

i=l fc=l ¿=1

где Sn - множество всех подстановок на множестве {1,... ,п}.

Заметим, что в каждой позиции должен быть размещен только один объект. Задача с заданными матрицами А, В, С обозначается как QAP(A, В, С). Если линейное слагаемое (матрица С) отсутствует, задача обозначается QAP(A, В). На практике элементы матрицы В часто удовлетворяют неравенству треугольника bji + bjr > bjr для различных j,l,r = 1,..., n. В этом случае задача называется метрической КЗН.

Если минимизируется максимальная стоимость связей, то задача называется КЗН с минимаксным критерием (минимаксная КЗН) и обозначается QBAP(A, В) при отсутствии матрицы С. Ее целевая функция имеет вид

ШаХ &г/с^7г(г)тг(к) ^7Г€Sn min •

i,k=l,...,n

Постановки КЗН в терминах теории графов формулируются следующим образом1. Дан граф связей G = (V^, Еf) и граф расстояний М = (’Vd, Ed). Множество Vs = {vi : i - 1,..., п} соответствует объектам, а множество Vd = {vi : i — 1,..., n} - позициям, в которые объекты размещаются. Ребро {vi,vj} £ Ef, если существует связь между объектами и* и Vj, w(vi,vj) - это вес ребра {vi,vj} € Ef. Через p(n{vi),Tr(vj)) обозначим кратчайшее расстояние между позициями 7Г(vi) и n(vj). Целевая функция КЗН в терминах теории графов имеет вид

F(n) = w(vi,vj)p(n(vi),ir(vj)) -hres„ min.

{vi,vj }eEf

Целевая функция задачи с минимаксным критерием записывается следующим образом

Fmaxbг) = max w(Vi, Vj)p(ir(Vi), 7Г(г/,-)) min.

{vi,Vj}eEf

^arahani R.Z., Hekmatfar M. Facility location: Concepts, models, algorithms and ease studies. - Heidelberg: Physica-Verlag, 2009. - 543 p.

Для Удобства изложения обозначим граф связей между объектами через ¿7 = (ТУ, Е), где N = {1,..., п} - множество пронумерованных некоторым образом вершин У* и Е = Е*, а М = (V, £/), где V - {1,...,п} = {уь • • • > ^п} I и = £^. Далее граф расстояний Л/ с весами на ребрах будем называть сетью, его вершины - узлами. Не уменьшая общности можно считать, что если в графе веса всех ребер равны, он является невзвешенным (полагаем все веса равными 1). Задача размещения графа (3 на сети М с критериями р или Ртах в дальнейшем обозначается тройкой ((?, М, Р) или (С, М, Ртах) соответственно.

В п. 1.2 описываются некоторые практические задачи, математической моделью которых является КЗН. Приводятся известные задачи оптимизации, являющиеся частными случаями КЗН, в том числе, задача коммивояжера.

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

В п. 1.3 приводится обзор известных методов решения КЗН в различных постановках.

Основные методы нахождения точного решения NР-трудных задач применялись и для решения КЗН. Это алгоритмы ветвей и границ (основная используемая граница - граница Гилмора-Лоулера), отсечений, декомпозиции. Данные подходы оказались слабо применимыми на практике. Оптимальное решение тестовых примеров КЗН за приемлемое время было найдено только для числа объектов не более 20. В середине 1990-х годов разработка параллельных алгоритмов на суперкомпьютерах позволила увеличить размерность решаемых задач до 25. В дальнейшем, применение распределенных вычислений увеличило размерность до 30.

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

Основное внимание в исследованиях КЗН в терминах теории графов уделяется разработке эффективных алгоритмов для специальных структур связей между объектами и сетей. Известны полиномиальные алгоритмы размещения изоморфных графов специальной структуры, эффективные алгоритмы размещения деревьев на цепи, алгоритм локальной оптимизации и другие (Забудский Г.Г., Иорданский М.А., Кристофидес H., Метельский H.H., Rendí F.). Предложен алгоритм динамического программирования решения задачи размещения произвольного взвешенного графа на невзвешенном дереве для мшшеуммного критерия (Забудский Г.Г.). Для решения специальных случаев КЗН на сетях известны приближенные алгоритмы с оценками (Сви-риденко М.И., Hassin R.).

Вторая глава посвящена полиномиальным алгоритмам решения КЗН на древовидных сетях для специальных структур связей между объектами.

В п. 2.1 изучаются задачи с минисуммным критерием размещения невзвешенных цепи и цикла на взвешенной древовидной сети. Даны произвольная древовидная сеть Т = (V, U) с заданными весами ребер и невзвешенная цепь Ch = (N, Е). Рассматривается задача размещения (Ch,T, F). Идея алгоритма Ams решения данной задачи состоит в построении маршрута, проходящего по всем узлам сети Т как минимум один раз, и минимального по суммарному весу входящих в него ребер. Для этого в сети выделяется главная цепь (цепь, соединяющая висячие узлы) максимальной длины, и применяется разработанный алгоритм размещения вершин Ch в узлы Т.

Сформулирована и доказана

Теорема 2.1. Алгоритм Ams находит оптимальное решение задачи (Ch,T,F).

Трудоемкость алгоритма Ams не превосходит 0(п3) операций.

Аналогично задаче (Ch,T,F), рассматривается задача размещения невзвешенного цикла Су на взвешенном дереве Т - задача (Cy,T,F). Для построения оптимального решения указанной задачи цикл "разрезается" по произвольному ребру, и полученная цепь размещается в соответствии с приведенным ранее алгоритмом с выбором произвольной главной цепи в сети Т. Трудоемкость решения задачи (Су, Т, F) не превосходит 0(п) операций.

В п. 2.2 приводится разработанный полиномиальный алгоритм Атт решения задачи с минимаксным критерием размещения невзвешенной цепи на невзвешенной древовидной сети. Даны невзвешенная цепь Ch = (N, Е) и невзвешенная древовидная сеть Т = (V, U). Рассматривается задача (Ch,T, Fmax).

В сети Т выделяется цепь Со = (Vo,Uo), Vo = (h,... ,кр), соединяющая некоторые узлы ki и кр, которая называется главной. Каждому узлу ki £ Vо сопоставляется поддерево Ti = (V*, Ui). Множество Ц состоит из ki и всех тех узлов дерева Т, которые соединены с ki цепями, не содержащими ребер из Uq. Множество Ui образовано ребрами таких цепей.

В алгоритме Amm рассматриваются все возможные представления сети Т с выделенными главными цепями и осуществляется поиск в поддеревьях Ti сетей вида Gi и G2, которые имеют структуру, представленную на рис. 1.

О V,

Рис. 1: Сети вида G, и G'2.

Если алгоритмом Атт найдено представление дерева Т, не являющегося цепью, без сетей вида и С 2, то с его помощью будет получено оптимальное решение 7Г* исходной задачи со значением целевой функции Етах{ъ*) — 2. Если во всех рассмотренных представлениях дерева Т имеется сеть вида С?! или 62, то оптимальное значение Етах(7Г*) = 3. Если Т -это цепь, то Етах(7Г*) = 1.

В диссертации доказана

Теорема 2.2. Алгоритм Атт находит оптимальное решение задачи (С^Т^Етах).

Трудоемкость алгоритма Лтт не превосходит 0(n4logn).

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

10

видных сетей и конфигураций ЭВМ. Приводятся результаты сравнения эффективности предложенного алгоритма с решением задачи с использованием программного пакета 1ВМ П.ОС СРЬЕХ. Сделаны выводы о целесообразности и перспективности применения указанного алгоритма. Предложен алгоритм поиска приближенного решения КЗН размещения графа общей структуры на произвольной сети. Алгоритм реализован на ЭВМ, проведен вычислительный эксперимент по оценке его эффективности.

В п. 3.1 рассматривается задача (С, М, где С = (¿V, Е) - взвешенный граф произвольной структуры, а М — (V, II) - невзвешенная древовидная сеть. Представлен параллельный алгоритм динамического программирования (ДП) решения данной задачи.

Идея алгоритма заключается в следующем. В древовидной сети М в качестве корня выбирается центр (если их два, то произвольный). Предполагается, что нумерация вершин сети М является сплошной и в любом поддереве номер корня больше номера любого узла этого поддерева. Для удобства обозначений вводится подстановка ф — тт Ч Через «¿(й) обозначается степень узла я € V.

Состояние в процессе ДП определяется как подмножество вершин Т = {¿1,... ,га} графа б, размещенных в первые я узлов сети М. Начальное состояние Т — 0 — ни одна вершина не размещена. Конечное состояние Т = - размещены все вершины. Переход из одного состо-

яния в другое рассматривается как последовательный перебор узлов дерева М в соответствии с их нумерацией. Обозначим через Ф(5) множество вершин графа С?, размещенных в множество узлов 5 сети М. Пусть Т = Ф(5Х) и Ф(52) и ... и Ф(5Р), где 5Ь..., 5Р - множества узлов дерева М, которые индуцируют В М несвязные поддеревья, = 5.

Определяются уравнения Веллмана для динамического процесса. Краевые условия:

/(0) = /({*})= 0,/М = Дтг*)

для всех я £ V, где тг* - оптимальная подстановка. Пусть на очередном шаге процесса ДП рассматривается узел я € V.

Для случая ¿(в) = 1 выполнено

/(иС115<иМ) = /№150- (!)

При ¿(в) = 2 справедливо

Пусть при объединении ветвей (d(s) > 3) узел s является корнем поддерева с ветвями, множества узлов которых - это Sj, Sj+1,..., Sp. После размещения вершины I графа G в узел s указанные ветви объединяются, и получаем поддерево с корнем s и множеством узлов H — Sj USj+1 U... USp U {s}. Имеет место равенство

/ШБ{иН)= i(Sj,min){i}; {/(Ц?=15;) + ^^(Ф(50,ФЩ)} (3)

и^.Ф(50и{г}=Ф(Я) i=i

На прямом ходе параллельного алгоритма ДП главный поток определяет множество узлов сети М, смежных с корнем, и передает данные узлы и соответствующие им поддеревья подчиненным потокам. Каждый подчиненный поток применяет прямой ход алгоритма ДП к "своему" поддереву и вычисляет значения функции Веллмана по формулам (1)-(3). После завершения работы подчиненных потоков главный поток вычисляет значение функции f(V), которое является оптимальным значением целевой функции F(n>).

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

Для вычисления значений функции / на очередном шаге алгоритма (размещение в узел s G К) необходимо хранить все возможные в данном случае блоки из узлов дерева М. Это или сочетания без повторений (в случае d(s) < 2), или наборы сочетаний, которые назовем сочетаниями по блокам (при d(s) > 3). Пусть в узле s объединяются р ветвей (блоков), пронумерованных 1,2,... ,р, количество узлов в ветвях равно к\, к2,...,кр соответственно. Тогда сочетанием из п элементов по блокам 1,...,р назовем набор из различных элементов вида (а\,а\,..., alh; а?,..., а\2\ ...; ари..., а?к ; ОР+1), где a\,...,a\i,a\,...,al2,...,a\,...,apkp,oP+l £ {1, ..., п}, причем а\ < а\ < ... < < ... < а|2;... ;а? < ... < а?кр.

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

12

без повторений для вычисления значений функции /. Для ускорения этой операции был разработан алгоритм поиска индекса сочетания.

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

Пусть р - максимальная степень узлов сети М. Сформулирована и доказана

Теорема 3.2. Трудоемкость решения задачи (G,M,F) алгоритмом ДП не превосходит 0{п3(р+ 1)2п). Требуемое количество памяти -0(п(р+1П

В п. 3.2 приводятся результаты численного эксперимента по оценке эффективности параллельного алгоритма ДП. Варьируется структура древовидной сети - рассматриваются деревья различного диаметра при равном количестве узлов, от дерева с наибольшим диаметром - цепи, до дерева минимального диаметра — звезды. Алгоритм ДП реализован на языке C++ с использованием библиотеки ОрепМР, предназначенной для программирования многопоточных приложений на многопроцессорных системах с общей памятью. Для оценки его эффективности использовался программный пакет IBM ILOG CPLEX Optimization Studio 12.2 (решение КЗН алгоритмом ветвей и границ с ограничением по времени работы).

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

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

По результатам сравнения с работой программного пакета IBM ILOG CPLEX сделан вывод, что предложенный параллельный алгоритм ДП эффективно использовать при решении задач на древовидных сетях большого

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

В п. 3.3 излагается алгоритм поиска приближенного решения КЗН на произвольных сетях. Рассматривается задача (С, М, Р), где С? = (ТУ, Е) -взвешенный граф, М — (V, [/) - взвешенная сеть. Идея алгоритма состоит в построении д сетей Мг = (Ц, Щ таких, что Ц С V, 1^1 < к для некоторого к £ {2,..., п} и всех г = 1,..., 5, множества Ц и Ц+1, г = 1,..., д - 1, пересекаются и КЗН размерности к разрешима за приемлемое время. В экспериментах варьируется начальное размещение графа на сети. Последовательно решаются КЗН на сетях М,¡, г = 1,..., д, с учетом линейного слагаемого, представляющего собой сумму стоимостей связей вершин, размещенных в 1^, с вершинами, размещенными в V \ V*. В итоге получаем приближенное решение исходной задачи. Проведен вычислительный эксперимент по оценке эффективности работы предложенного алгоритма. Выполнено сравнение с результатами решения КЗН известными эвристическими алгоритмами: муравьиной колонии и имитации отжига.

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

Опубликованные работы по теме диссертации В рецензируемых журналах из списка ВАК

[1] Забудский Г.Г., Лагздин А.Ю. Полиномиальные алгоритмы решения квадратичной задачи о назначениях на сетях // Журнал вычислительной математики и математической физики. - 2010. - Т. 50, № 11. -С. 2052-2059.

[2] Забудский Г.Г., Лагздин А.Ю. Полиномиальные алгоритмы решения минимаксной квадратичной задачи о назначениях на сетях // Дискретный анализ и исследование операций. - 2011. - Т. 18, № 4. - С. 48-64.

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

[3] Забудский Г.Г., Лагздин А.Ю. Алгоритм решения квадратичной задачи о назначениях с минимаксным критерием на дереве // Материалы VII Международной научно-технической конференции "Динамика систем, механизмов и машин". - Омск: ОмГТУ, 2009. - Т. 3. - С. 23-27.

[4] Забудский Г.Г., Лагздин А.Ю. Анализ эффективности параллельного алгоритма динамического программирования для квадратичной задачи о назначениях на дереве // Тезисы докладов XIV Всероссийской конференции "Математическое программирование и приложения". Информационный бюллетень Ассоциации математического программирования. -Екатеринбург, 2011. - № 12. - С. 176.

14

[5] Забудский Г.Г., Лагздин А.Ю. Параллельный алгоритм динамического программирования решения квадратичной задачи о назначениях на дереве // Материалы Российской конференции "Дискретная оптимизация и исследование операций". - Новосибирск, 2010. - С. 161.

[6] Забудский Г.Г., Лагздин А.Ю. Полиномиальные алгоритмы решения квадратичных задач о назначениях на деревьях // Материалы IV Всероссийской конференции "Проблемы оптимизации и экономические приложения". - Омск, 2009. - С. 126.

[7] Забудский Г.Г., Лагздин А.Ю. Эффективные алгоритмы решения специальных случаев квадратичной задачи о назначениях на сетях// Доклады 8 Международной конференции "Интеллектуализация обработки информации ИОИ-2010". — М: МАКС Пресс, 2010. - С. 255-257.

[8] Лагздин А. Экспериментальное сравнение алгоритмов динамического программирования решения квадратичной задачи о назначениях на дереве II Молодежь третьего тысячелетия: XXXV Региональная научно-практическая студенческая конференция: сборник статей секции "Физико-математические науки". - Омск: Изд-во ОмГУ, 2011. -С. 20-23.

[9] Lagzdin A., Zabudsky G. Polynomial algorithms for some cases of quadratic assignment problem // Abstracts of International conference "Operations Research 2010". - Munich, 2010. - P. 118-119.

[10] Lagzdin A., Zabudsky G. Some algorithms for the quadratic assignment problems on networks 11 Abstracts of International conference "Operations Research 2011". - Zurich: IFOR, 2011. - P. 26.

[11] Zabudsky G., Lagzdin A. Polynomial algorithms for some quadratic assignment problems in terms of graphs // Abstracts of II International conference "Optimization and Applications" (OPTIMA-2011). - М.: ВЦ РАН, 2011. - P. 220-223.

Подписано в печать 17.01.2012 Формат 60x84/16. Бумага писчая. Оперативный способ печати.

Уел. печ. л. 1,00. Тираж 150 экз. Заказ № 24

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

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

61 72-1/602

Омский филиал Учреждения Российской академии наук Института математики им. С.Л. Соболева Сибирского отделения РАН

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

ЛАГЗДИН Артем Юрьевич

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

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

комплексы программ

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

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

Омск - 2012

Оглавление

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

1 Задачи оптимального размещения взаимосвязанных объектов на сетях и методы их решения...... 14

1.1 Математические модели........... 15

1.2 Моделирование прикладных проблем и связь с известными задачами оптимизации............ 21

1.3 Алгоритмы решения ............ 28

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

2.1 Минисуммный критерий...............33

2.2 Минимаксный критерий........... 42

3 Алгоритмы и их экспериментальное исследование для произвольных структур связей.......... 55

3.1 Параллельный алгоритм динамического программирования на невзвешенной древовидной сети...... 55

3.2 Экспериментальное исследование параллельного алгоритма 68

3.3 Алгоритм поиска приближенного решения для произвольных сетей................ 72

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

Приложение 1................. 92

Приложение 2................. 97

Введение

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

Первые попытки анализа задач оптимального размещения относятся к XVII веку, когда Ферма сформулировал следующую задачу: найти точку на плоскости, сумма евклидовых расстояний от которой до трех фиксированных минимальна. В начале XX века ее обобщил Вебер, рассматривая произвольное число точек, которым приписаны веса. Более детальные исследования задач размещения связаны с появлением и развитием исследования операций.

По признаку наличия фиксированных связей между объектами задачи оптимального размещения можно разбить на два класса - размещение взаимосвязанных объектов и размещение-распределение [30]. В задачах первого класса требуется найти позиции для размещения объектов с заранее заданной структурой связей между ними. Наиболее известные представители этого класса - это квадратичная задача о назначениях и задача Вебера [4,12,14-16,25-27,42-44,47,48,50,51,54,57-59,61,63-77,79, 81,83,84,87-89,91,93,94]. Во втором классе задач связи между объектами изначально не фиксированы, а устанавливаются в процессе их решения. К ним относятся, в частности, простейшая задача размещения, задача

0 р-медиане, задача о р-центре, задача размещения с предпочтениями клиентов [2,6,8,9,33,36,37,41,82].

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

В данной работе исследуется задача оптимального размещения взаимосвязанных объектов в дискретной постановке - квадратичная задача о назначениях (КЗН). Ее формулировка в постановке Купманса-Бекманна выглядит следующим образом [83]. Задано п объектов, которые необходимо разместить в п позиций по одному в каждую таким образом, чтобы суммарная стоимость связей между объектами была минимальной. Даны матрица А = (а^), где а^ - удельная стоимость связи между объектами

1 и А;, В = (bji), bß - расстояние между позициями j и I, С = (с^), с^ -стоимость размещения объекта i в позицию j. Пусть ж - это подстановка на множестве {1,..., п}. Целевая функция сформулированной задачи имеет вид

п п п

{YJ Y; <kkh(i)iT(k) + min'

г=1 fc= 1 i—1

где Sn - множество всех подстановок на множестве {1,..., п}.

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

С заданными матрицами А, В, С квадратичная задача о назначениях обозначается как QAP(A, В, С). В случае, если линейное слагаемое (т.е. матрица С) отсутствует. КЗН обозначается QAP(A, В). На практике элементы матрицы В часто удовлетворяют неравенству треугольника

bji + Ъ\г > bjr для всех различных j,l,r = 1,.... п. В этом случае задача называется метрической. Если минимизируется максимальная стоимость связей, то задача называется КЗН с минимаксным критерием (минимаксная КЗН). Часто она рассматривается в постановке без матрицы С и обозначается QBAP(A, В). Целевая функция в этом случае имеет вид

max o^b^wM ~^n€sn min.

i,k=l,...,n

Многие задачи комбинаторной оптимизации являются частными случаями КЗН - в частности, задача коммивояжера и задача о максимальной клике. Например, задачу коммивояжера можно сформулировать как QAP(A,B)j где матрица В задает циклическую подстановку.

Наиболее интенсивно КЗН исследуется в приведенной выше (матричной) постановке [12,62-65,70,73,74]. Выделены матрицы специальной структуры, для которых задача является полиномиально разрешимой. При выполнении некоторых условий на матрицы решение КЗН - это заранее заданная подстановка. Данные свойства называются условиями сильной разрешимости задачи. Впервые такие условия были получены в [78], далее исследования продолжились в [12,63-65,70,74].

Для точного решения задачи в общем виде применяются методы комбинаторного анализа и целочисленного программирования [47,62,65,73]. В комбинаторной постановке в алгоритмах ветвей и границ часто используется граница Гилмора-Лоулера, которая хорошо себя зарекомендовала в вычислительных экспериментах [62,73,75,84]. Для решения задачи с применением аппарата целочисленной оптимизации используются алгоритмы отсечений, декомпозиции. Известно несколько моделей целочисленного программирования для КЗН. Например, исходную нелинейную целевую функцию можно свести к линейной путем введения новых ограничений и переменных. Полученная задача решается известными методами целочисленного линейного программирования [7,10,35,38,49,

52.53,60], в частности, методом регулярных разбиений, предложенным A.A. Колоколовым [31,32]. Указанные выше подходы к решению КЗН описаны, например, в [47,48,62,73].

Точные методы решения малоэффективны на практике, поскольку для задач с числом объектов более 20 не гарантировано нахождение такого решения за приемлемое время. Применение параллельных алгоритмов на суперкомпьютерах позволило увеличить размерность решаемых задач до 25 объектов [61,68], а в последние годы использование распределенных вычислений - до 30 объектов [54,57]. Наряду с точными подходами, разрабатываются алгоритмы поиска приближенных решений для задач большой размерности, в частности, эвристические: муравьиной колонии, имитации отжига, генетические и другие [62,69,73.87,94]. В качестве тестовых примеров используются известные задачи, описанные в работе [88] и дополненные в дальнейшем [62,73].

Недостаточно внимания уделяется исследованию КЗН, сформулированной в терминах теории графов (в теоретико-графовой постановке), которая состоит в следующем [73]. Даны неориентированные граф связей G = (W, и граф расстояний М = (Vd,Ed). Множество вершин V? = {Vi : i — 1 ,...,п} соответствует объектам, а множество yd = ^ : i — 1 ,...,n} - позициям, в которые объекты размещаются. Ребро {vi,Vj} G Е?, если имеется связь между объектами v,L и vj. Вес w(vi,vj) ребра {vi,Vj] е Е? - это удельная стоимость связи. Обозначим через 7г подстановку на множестве {vi : г = 1,... ,п}. Величина p(^(vi),7r(vj)) ~ это кратчайшее расстояние между вершинами ir(vi) и 7r(vj) в графе М. Целевая функция задачи записывается следующим образом

-^тгmin,

{v^eEf

где Sn - множество всех подстановок на множестве {vi : г = 1,..., п}.

В данной работе для удобства граф расстояний М будем называть

сетью, его вершины - узлами. Не уменьшая общности, можно считать, что если в графе (сети) веса всех ребер равны, он является невзвешенным (полагаем веса всех ребер равными 1).

Если целевая функция имеет вид

max w{vi,vj)p{ir{vi),it(vj)) 6sn min,

то задача называется КЗН с минимаксным критерием в теоретико-графовой постановке.

Актуальными в настоящее время являются задачи оптимизации на сетях и дискретных структурах [13,37,39,45,46]. Постановка КЗН в терминах теории графов удобна, когда специфика прикладной задачи предполагает наличие специальных структур связей между объектами и конфигураций соединения позиций. Отметим, что любую задачу, сформулированную в терминах теории графов, можно представить в матричной постановке. Обратное не всегда возможно, так как, в частности, может не выполняться неравенство треугольника для матрицы расстояний между позициями.

Как было отмечено выше, в литературе исследованию КЗН в теоретико-графовой постановке уделяется недостаточное внимание по сравнению с матричной. Перечислим некоторые известные результаты.

N. Christofides и М. Gerrard предложили полиномиальный алгоритм динамического программирования решения КЗН для случая, когда графы связей и расстояний - это изоморфные деревья [67]. Они также доказали, что задача размещения дерева на взвешенном полном графе произвольной структуры NР-трудна. F. Rendí обобщил этот результат на графы специальной структуры - минимальные вершинно последовательно-параллельные ориентированные графы (MVSP-орграфы) [91]. Для задачи размещения двудольного графа на двудольном графе H.H. Ме-тельским был предложен эффективный алгоритм локальной оптимизации [42].

Частный случай КЗН в терминах теории графов на сети, представляющей собой цепь с равными весами ребер, называется задачей оптимальной нумерации вершин графа (оптимального линейного упорядочения) [55]. Известны эффективные алгоритмы решения задачи для деревьев специального вида [14,28,29,92].

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

Недостаточно исследована КЗН в терминах теории графов на сетях более общей структуры, чем цепь, например, на древовидных сетях. Интерес представляет как разработка полиномиальных алгоритмов решения таких задач для специальных структур связей между объектами, так и эффективных алгоритмов для общих графов связей, в том числе, с применением параллельных вычислений.

Целью данной работы является построение и анализ эффективных алгоритмов решения КЗН в теоретико-графовой постановке для различных структур связей между объектами.

Для достижения поставленной цели изучались вопросы математического моделирования прикладных задач в виде КЗН, сложности ее ре-

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

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

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

2. Разработан полиномиальный алгоритм решения КЗН с минимаксным критерием для размещения объектов со структурой связей в виде цепи на древовидной сети в случае ребер одинакового веса.

3. Предложен параллельный алгоритм динамического программирования решения КЗН с минисуммным критерием для графа связей общей структуры с произвольными весами ребер на древовидной сети с равными весами.

4. Разработан алгоритм поиска приближенного решения КЗН с минисуммным критерием для графа связей и сети общего вида с произвольными весами ребер.

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

следование эффективности параллельного алгоритма в зависимости от характеристик сети и конфигурации ЭВМ. Выполнено сравнение его работы с результатами решения задачи программным пакетом IBM ILOG CPLEX. Проведен вычислительный эксперимент по анализу эффективности алгоритма поиска приближенного решения.

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

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

Вторая глава посвящена полиномиальным алгоритмам решения КЗН на древовидных сетях для специальных структур связей между объектами. Рассматриваются задачи с минисуммным критерием размещения невзвешенных цепи и цикла на взвешенной древовидной сети. Построены полиномиальные алгоритмы решения задачи и получены оценки их трудоемкости. Разработан полиномиальный алгоритм решения задачи с минимаксным критерием размещения невзвешенной цепи на невзвешен-ной древовидной сети. Его идея заключается в поиске подсетей специального вида и последовательного размещения вершин цепи в узлы сети

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

В третьей главе описаны алгоритмы решения КЗН с минисуммным критерием для графа связей общего вида на древовидной и произвольной сетях. Разработан и реализован на ЭВМ параллельный алгоритм динамического программирования решения задачи оптимального размещения произвольного взвешенного графа на невзвешенной древовидной сети. Проведены численные эксперименты для различных структур древовидных сетей и конфигураций ЭВМ. Приведены результаты сравнения эффективности предложенного алгоритма с решением задачи с использованием программного пакета IBM ILOG CPLEX. Сделан вывод о целесообразности и перспективности применения параллельного алгоритма. Предложен алгоритм поиска приближенного решения КЗН для взвешенного графа связей общего вида на произвольной взвешенной сети. Создан программный комплекс с реализацией указанного алгоритма. Проведена оценка эффективности его работы по сравнению с известными эвристическими алгоритмами.

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

Основные результаты опубликованы в работах [18-24,40,85, 86, 95] и докладывались на IV Всероссийской конференции "Проблемы оптимизации и экономические приложения" (г. Омск, 2009), VII Международной научно-технической конференции "Динамика систем, механизмов и машин" (г. Омск, 2009), Российской конференции "Дискретная оптимизация и исследование операций" (Республика Алтай, 2010), Международной конференции "Operations Research 2010" (г. Мюнхен, Германия, 2010), 8 Международной конференции "Интеллектуализация обработки информации ИОИ-2010" (г. Пафос, Республика Кипр, 2010), XIV Всероссийской конференции "Математическое программиро�