Построение и анализ алгоритмов решения квадратичной задачи о назначениях на сетях тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Лагздин, Артем Юрьевич

• Лагздин, Артем Юрьевич
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Лагздин, Артем Юрьевич

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

Заключение

Приложение 1

Приложение 2

Введение диссертации (часть автореферата) на тему «Построение и анализ алгоритмов решения квадратичной задачи о назначениях на сетях»

Введение

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

Первые попытки анализа задач оптимального размещения относятся к 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 Всероссийской конференции "Математическое программирование и приложе-

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

Автор благодарит научного руководителя профессора Г.Г. Забудского за полезные советы, постоянное внимание и поддержку в работе.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Лагздин, Артем Юрьевич

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

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

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

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

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

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

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

Заключение

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

Список литературы диссертационного исследования кандидат физико-математических наук Лагздин, Артем Юрьевич, 2012 год

Литература

[1] Айгнер М. Комбинаторная теория. - М.: Мир. 1982. - 558 с.

[2] Алексеева Е.В., Кочетов Ю.А. Генетический локальный поиск для задачи о р-медиане с предпочтениями клиентов // Дискретный анализ и исследование операций. - 2007. - Т. 1, № 14. - С. 3-31.

[3] Аоки М. Введение в методы оптимизации. - М.: Наука, 1977. -344 с.

[4] Ахмедов И.С., Сигал И.Х. Задача компоновки схемы госплана предприятий и некоторые подходы к ее решению // Деп. ВИНИТИ. -М., 1983. - № 270. - 57 с.

[5] Ахметов С.А., Сериков Т.П, Кузеев И.Р, Баязитов М.И. Технология и оборудование процессов переработки нефти и газа: Учебное пособие. - СПб: Недра, 2006. - 868 с.

[6] Береснев B.JI. Дискретные задачи размещения и полиномы от булевых переменных. - Новосибирск: Изд-во Института математики, 2005. - 408 с.

[7] Борисовский П.А., Еремеев A.B. О сравнении некоторых эволюционных алгоритмов // Автоматика и телемеханика. - 2004. - № 3. -С. 3-10.

[8] Васильев И.Л., Климентова К.Б., Кочетов Ю.А. Новые нижние оценки для задачи размещения с предпочтениями клиентов //

[9] Гимади Э.Х. О вероятностном анализе приближенного алгоритма решения задачи о р-медиане // Дискретный анализ и исследование операций. - 2010. - Т. 3, № 17. - С. 19-31.

[10] Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации ]/ Проблемы кибернетики. -М.: Наука, 1975. - Вып. 31. - С. 35-43.

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

[12] Демиденко В.М. Обобщение условий сильной разрешимости квадратичной задачи о назначениях с матрицами анти-Монжа и Теплица // Доклады НАН Беларуси. - 2003. - Т. 47, № 2. - С. 15-18.

[13] Ерзин А.И., Тахонов И.И. Задача поиска сбалансированного потока // Сибирский журнал индустриальной математики. - 2006. -Т. 9, № 4. - С. 50-64.

[14] Забудский Г.Г. Алгоритм решения одной задачи оптимального линейного упорядочения // Известия вузов. Математика. - 1997. -№ 12. - С. 73-78.

[15] Забудский Г.Г. О минимаксной и минисуммной задачах размещения на плоскости с запрещенными областями // Тр. XIII межд. Байкальской школы-семинара "Методы оптимизации и их приложения". - Иркутск, 2005. - С. 455-460.

[16] Забудский Г.Г. О некоторых задачах размещения на графах// Труды XI Байкальской международной школы-семинара "Методы оптимизации и их приложения". - Иркутск: ИСЭ им. Л.А. Мелентьева СО РАН, 1998. С. 135-138.

[17] Забудский Г.Г., Колоколов A.A., Колмычевская Н.В. Методы решения и анализа некоторых задач оптимального размещения объектов // Тезисы третьей школы-семинара по вопросам автоматизированного проектирования объектов архитектуры и строительства. — Ростов на Дону, 1989. - С. 70.

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

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

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

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

[22] Забудский Г.Г., Лагздин А.Ю. Полиномиальные алгоритмы решения квадратичных задач о назначениях на деревьях // Материалы

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

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

[25] Забудский Г.Г., Мотовилов В.А. Оптимальное размещение объектов на дереве с помощью динамического программирования // Труды XII Байкальской конференции "Методы оптимизации и их приложения". - Иркутск, 2001. - С. 144-149.

[26] Забудский Г.Г., Филимонов Д.В. Алгоритм решения минимаксной задачи размещения на дереве с ограничениями на максимальные расстояния // Омский научный вестник. - 1999. - Вып. 9. -С. 37-40.

[27] Забудский Г.Г., Филимонов Д.В. Решение дискретной минимаксной задачи размещения на сети // Известия вузов. Математика. -2004. - № 5. - С. 33-36.

[28] Иорданский М.А. Задачи размещения графов 2 // Межвузовский сборник "Комбинаторно-алгебраические методы в прикладной математике". - Горький, ГГУ им. Лобачевского. - 1982. - С. 26-65.

[29] Иорданский М.А. О минимаксных нумерациях вершин графа // Межвузовский сборник "Комбинаторно-алгебраические методы в

[30] Исследование операций. В 2-х томах. / Пер. с англ. Под ред. Мо-удера Дж., Элмаграби С. - М.: Мир, 1981. - 677 с.

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

[32] Колоколов A.A., Леванова Т.В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения // Вестник Омского ун-та. - Омск: Изд-во ОмГУ, 1996. - № 1. -С. 21-23.

[33] Колоколов A.A., Леванова Т.В., Лореш М.А. Алгоритмы муравьиной колонии для задач оптимального размещения предприятий // Омский научный вестник. - 2006. - № 4 (38). - С. 144-147.

[34] Кофман А. Введение в прикладную комбинаторику. - М.: Наука, 1975. - 480 с.

[35] Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и приложения. - М. - 2001. - С. 84-117.

[36] Кочетов Ю.А., Пащенко М.Г., Плясунов A.B. О сложности локального поиска в задаче о р-медиане // Дискретный анализ и исследование операций. - 2005. - Т. 12, № 2. - С. 44-71.

[37] Кристофидес Н. Теория графов. Алгоритмический подход. -М.: Мир, 1978. - 432 с.

[38] Кузнецова A.A., Стрекаловский A.C., Цэвээндорж И. Об одном подходе к решению целочисленных задач оптимизации // Журнал вычислительной математики и математической физики. - 1999. -Т. 39, № 1. - С. 9-16.

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

[41] Леванова Т.В., Лореш М.А. Алгоритм муравьиной колонии и имитации отжига для задачи о р-медиане // Автоматика и телемеханика. - 2004. - № 3. - С. 80-88.

[42] Метельский H.H. Методы локальной оптимизации для задачи размещения двудольных графов // Журнал вычислительной математики и математической физики. - 1984. - Т. 24, № 9. - С. 1428-1432.

[43] Панюков A.B., Пельцвергер Б.В. Оптимальное размещение дерева в конечном множестве // Журнал вычислительной математики и математической физики. - 1988. - Т. 28, № 4. - С. 618-620.

[44] Панюков A.B., Пельцвергер Б.В., Шафир А.Ю. Оптимальное размещение точек ветвления транспортной сети на цифровой модели местности // Автоматика и телемеханика. - 1990. - № 9. -С. 153-162.

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

[46] Попков В.К. О моделировании городских транспортных систем гиперсетями // Автоматика и телемеханика. - 2011. - № 6. -С. 179-189.

[48] Сергеев С.И. Улучшенные нижние границы для решения квадратичной задачи назначения // Автоматика и телемеханика. - 2004. -№ И. - С. 49-63.

[49] Сигал И.Х., Иванова А.П. Введение в прикладное и дискретное программирование: модели и вычислительные алгоритмы - М.: Физ-матлит, 2002. - 240 с.

[50] Теория и методы автоматизации проектирования вычислительных систем. - М.: Мир, 1977. - 284 с.

[51] Трубин В.А. Эффективный алгоритм для задачи Вебера с прямоугольной метрикой // Кибернетика. - 1978. - № 6. - С. 67-70.

[52] Хачатуров В.Р. и др. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности -М.: Наука, 2000. - 360 с.

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

[54] Adams W.P., Guignard М., Hahn P.M., Hightower W.L. A level-2 reformulation-linerization technique bound for the quadratic assignment problem // European Journal of Operations Research. -2007. - № 180. - P. 983-996.

[55] Adolfson D., Ни T.C. Optimal linear ordering // SIAM Journal on Applied Mathematics. - 1973. - V. 25, № 3. - P. 403-423.

[56] Andrews G. Foundations of multithreaded, parallel and distributed programming. - Addison-Wesley, 2000. - 664 p.

[57] Anstreicher K.M., Brixius N.W., Goux J.P., Linderoth J. Solving large quadratic assignment problems on computational grids // Math. Program. - 2002. - № 91. - P. 563-588.

[58] Arkin E.. Hassin R., Sviridenko M. Approximating the maximum quadratic assignment problem // Information Processing Letters. -2001. - V. 77. - P. 13-16.

[59] Bazaraa M.S., Sherali H.D. Bender's partitioning scheme applied to a new formulation of the quadratic assignment problem // Naval Res. Log. Quart. - 1980. - № 27. - P. 29-41.

[60] Borisovsky P.A., Dolgui A., Eremeev A.V. Genetic algorithms for a supply management problem: MIP-recombination vs greedy decoder // European Journal of Operational Research. - 2009. - V. 195(3). -P. 770-779.

[61] Brüngger A., Marzetta A., Clausen J., Perregaard M. Solving large-scale QAP problems in parallel with the Search Library ZRAM// Journal of Parallel Distrib. Comput. - 1998. - № 50. - P. 157-169.

[62] Burkard R.E., Dell'Amico M., Mortello S. Assignment problems. -Philadelphia: SIAM, 2009. - 402 p.

[63] Burkard R.E., Qela E., Rote G., Woeginger G.J. The quadratic assignment problem with a monotone anti-Monge matrix and a symmetric Toeplitz matrix: Easy and hard cases // Mathematical Programming (Series B). - 1998. - V. 82. - P. 125-158.

[64] Burkard R.E., Fincke U. On random quadratic bottleneck assignment problems // Math. Programming. - 1982. - V. 23, № 1. - P. 227-232.

[65] Qela E. The quadratic assignment problem: Theory and algorithms. -Dordrecht: Kluwer Academic Publishers, 1998. - 287 p.

[67] Christofides N., Gerrard M. Special cases of the quadratic assignment problem. - Management Science Research Report 361. - Pittsburgh: Carnegie Melon University, 1976. - 22 p..

[68] Clausen M., Perregaard M. Solving large quadratic assignment problems in parallel // Computational Opt. Alg. - 1997. - № 8. - P. 111-127.

[69] Connolly D.T. An improved annealing scheme for the QAP // European Journal of Operations Research. - 1990. - № 46. - P. 93-100.

[70] Demidenko V.M., Finke G., Gordon V.S. Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices // Journal of Mathematical Modelling and Algorithms. -2006. - V. 5, № 2. - P. 167-187.

[71] Elshafei A. Hospital layout as a quadratic assignment problem // Operations Research Quart. - 1977. - V. 28, № 1. - P. 167-179.

[72] Erkut E., Francis R.L., Tamir A. Distance-constrained multifacility minimax location problems on tree network // Networks. - 1992. -№ 22. - P. 37-54.

[73] Farahani R.Z., Hekmatfar M. Facility location: Concepts, models, algorithms and case studies. - Heidelberg: Physica-Verlag, 2009. -543 p.

[74] Finke G., Burkard R.E., Rendl F. Quadratic assignment problems j/ Annals of Discrete Mathematics. - 1987. - № 31. - P. 61-82.

[75] Gilmore P.C. Optimal and suboptimal algorithms for the quadratic assignment problem // SIAM J. Appl. Math. - 1962. - № 10. -P. 305-313.

[77] Haralambides J., Makedon F. Approximation algorithms for the bandwidth minimization problem for a large class of trees // Theory Comput. Syst. - 1997. - V. 30, № 1. - P. 67-90.

[78] Hardy G.H., Littlewood J.E., Polya G. The maximum of a certain bilinear form // Proc. London Math. Society. - 1926. - V. 25. -P. 265-282.

[79] Hassin R., Levin A., Sviridenko M. Approximating the minimum quadratic assignment problems // ACM Transactions on Algorithms. -2009. - V. 6, № 1.

[80] Karp R.M., Held M. Finite-state processes and dynamic programming // SIAM Journal on Applied Mathematics. - 1967. -V. 15, № 3. - P. 693-718.

[81] Kaufman L., Broeckx F. An algorithm for the quadratic assignment problem using Benders' decomposition // European Journal of Operations Research. - 1978. - № 2. - P. 207-211.

[82] Kolokolov A., Kosarev N. Analysis of decomposition algorithms with Benders cut for p-median problem // Journal of Mathematical Modelling and Algorithms. - 2006. - V. 5, № 2. - P. 189-199.

[83] Koopmans T.C., Beckmann M. Assignment problems and the location of economic activities // Econometric. - 1957. - № 25. - P. 53-76.

[84] Lawler E.L. The quadratic assignment problem // Management Science. - 1963. - № 9. - P. 586-599.

[85] 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.

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

[87] Miranda G., Luna H.P.L., Mateus G.R., Ferreira R.P.M. A performance guarantees heuristic for electronic components placement problems including thermal effects // Comput. Operations Research. - 2005. -№ 32. - P. 2937-2957.

[88] Nugent C.E., Vollmann T.E., Ruml J. An experimental comparison of techniques for the assignment of facilities to locations // Operations Research. - 1968. - № 16. - P. 150-173.

[89] Pardalos P.M., Ramakrishnan K.G., Resende M.G.C., Li Y. Implementation of a variance reduction-based lower bound in a branch-and-bound algorithm for the quadratic assignment problem // SIAM J. Optim. - 1997. - № 7. - P. 280-294.

[90] Picard J.C., Queyranne M. On the one-dimensional space allocation problem // Operations Research. - 1981. - V. 29, № 2. - P. 371-391.

[91] Rendl F. Quadratic assignment problem on series-parallel digraphs // Z. Operations Research. - 1986. - № 30. - P. 161-173.

[92] Shiloach Y. A minimum linear arrangement algorithm for undirected trees // SIAM J. Comput. - 1979. - V. 8, № 1. - P. 15-32.

[93] Steinberg L. The backboard wiring problem: A placement algorythm // SIAM. - 1961. - V. 3, № 1. - P. 37-50.

[94] Taillard E.D. FANT: fast ant system // Technical Report IDSIA-46-98. - IDSIA: Lugano, 1998.

[95] 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). - M.: BUi PAH, 2011. - P. 220-223.