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

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

%4.....

КОСАРЕВ Николай Александрович

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

05.13.01 — Системный анализ, управление и обработка информации (в научных исследованиях)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Омск - 2006

Работа выполнена в Омском государственном университете имени Ф.М. Достоевского

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

наук, профессор

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

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

наук, профессор

Дементьев Владимир Тихонович, кандидат физико-математических наук

Девятерикова Марина Владимировна

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

СО РАН

Защита состоится "21" сентября 2006 г. в 14:00 часов на заседании диссертационного совета ДМ 212.179.03 в Омском государственном университете им. Ф.М. Достоевского по адресу: 644077, Омск, ул. Нефтезаводская, 11.

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

Автореферат разослан " ^¿Г-^о^ 2006 г.

Ученый секретарь диссертационного совета к.ф.-м.и., доцент ^ * A.M. Семенов

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

Актуальность темы. Задачи оптимального размещения предприятий имеют широкий круг приложений, возникающих при планировании и реконструкции производства, проектировании сетей обслуживания, в стандартизации, кластерном анализе и других областях [2,3,5,15]. Значительный интерес к таким задачам связан также с ЛЛР-трудностью многих из них [1,17]. Поэтому для исследования и решения рассматриваемых задач требуется применение методов системного анализа и оптимизации.

В настоящее время исследования задач размещения предприятий ведутся в следующих основных направлениях. Изучается структура и вычислительная сложность задач, выделяются полиномиально разрешимые случаи и семейства трудных задач, разрабатываются методы решения [6,8,9,12,18]. Интенсивно развивается область, связанная с эволюционными алгоритмами, алгоритмами муравьиной колонии и другими ме-таэвристиками [10,16]. Большое внимание уделяется исследованию простейшей задачи размещения (ПЗР), задач о р-медиане (на максимум и на минимум), задач размещения с ограничениями на объемы производства, двухуровневых задач размещения [2,5,14,15].

Во многих задачах размещения предприятий, в том числе в задачах о р-медиане и ПЗР, переменные соответствующей модели целочисленного линейного программирования (ЦЛП) естественным образом делятся на две группы: целочисленные и непрерывные. Ввиду этого, для решения таких задач применяются декомпозиционные алгоритмы с отсечениями Бендерса [2,8,15]. С теоретической точки зрения указанные алгоритмы исследованы недостаточно. В частности, актуальными являются вопросы получения оценок числа итераций, построения семейств "трудных" задач, устойчивости алгоритмов при малых колебаниях исходных данных.

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

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

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

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

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

1. Построены семейства задач о р-медиане, на основе которых получены оценки числа итераций декомпозиционных алгоритмов с отсечениями Бендерса, алгоритма перебора ¿-классов и алгоритма ветвей и границ (схема Лэид и Дойг). Некоторые из этих оценок перенесены на достаточно широкий подкласс задач о р-медиане.

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

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

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

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

Кроме того, полученные результаты включены в учебный процесс на математическом факультете ОмГУ.

Апробация работы. Результаты диссертации докладывались па Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 2003), Всероссийской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2004), Международном семинаре "XIV Meeting of EURO Working Group on Location Analysis" (Корфу, Греция, 2003), Международном семинаре "Discrete Optimization Methods in Production and Logistics" (Омск-Иркутск, 2004), Международной коференции "European Chapter on Combinatorial Optimization" -ECCO XVIII (Минск, Белоруссия, 2005), XXXVII Молодежной школе-конференции "Проблемы теоретической и прикладной математики" (Екатеринбург, 2006), Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 2006), на научных семинарах в Омском филиале Института математики им. С.Л. Соболева СО РАН.

[Публикации. Основные результаты диссертации опубликованы в 12 научных работах, список которых приведен в конце автореферата.

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

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

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

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

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

Задача о р-медиане на максимум (обозначим ее Ртах) формулируется следующим образом. Имеется множество пунктов возможного размещения предприятий с номерами из / = {1,..., гп) и множество клиентов, которые

о

должны быть ими обслужены, с номерами из J = {1,...,п}. В каждом пункте размещается не более одного предприятия. Доход, полумаемый от обслуживания г-м предприятием j-vo клиента, равен c¡j, г € I, j € J. Требуется выбрать р пунктов, в которых будут размещены предприятия, и прикрепить каждого клиента к одному из открытых предприятий таким образом, чтобы максимизировать суммарный доход.

Для построения модели ЦЛП введем переменные задачи: z¡ = 1, если i-e предприятие входит в число выпускающих продукцию, в противном случае Zi = 0, i 6 /; .ту = 1, если j-й клиент обслуживается г-м предприятием, и Xij = 0 в противном случае, г 6 j Е J.

Модель ЦЛП для рассматриваемой задачи имеет вид:

Д~>х) = 2 И CiiXii max (!)

ieljeJ

при условиях

5>=Р. (2)

ш

5>у = i, jeJ, (3)

ш

Xij < z¡, г€ I, j е J, (4)

Xij, Zi e {o, i}, i 6 /, j e J. (5)

Вектор г = (zi,.., ,zm) будем называть производственным планом задачи (1)-(5), если он удовлетворяет ограничениям (2) и (5).

Пусть вместо коэффициентов дохода c¡j нам известны затраты d¡j на обслуживание г-м предприятием j-vo клиента. В этом случае рассматривается задача о р-медиане на минимум (Vtn¡n): требуется открыть р предприятий и прикрепить к ним клиентов так, чтобы суммарные затраты на обслуживание всех клиентов были минимальными.

ПЗР отличается от задачи "Ртт тем, что в ней можно открыть произвольное число предприятий, т.е. отсутствует ограничение (2), но для каждого предприятия задана стоимость его открытия c¡, г Е I, и целевая функция имеет вид

£ C¿2¿ + £ 2 dÜXij —> min •

is/ ieljeJ

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

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

Глава 2 посвящена исследованию свойств декомпозиционных алгоритмов с отсечениями Бендерса для рассматриваемых задач размещения.

В и. 2.1 описываются алгоритмы и способы построения отсечений.

Приведем схему декомпозиционного алгоритма для задачи РШах- Пусть О — множество всех производственных планов задачи, - рекордное значение целевой функции на к-ой итерации, = — оо.

Процесс Т>

Положим Г^1) =

Итерация к (к > 1)

Шаг 1. Находим г^ = 1ехтахГ2^. Если такой точки не существует, то процесс завершается: решение, на котором достигается рекорд является оптимальным.

Шаг 2. Формулируем задачу прикрепления клиентов для произ-

водственного плана .г^:

Е £ сцхи —► тах

при условиях

£ = 1, з е

ге1

О < х.и < г\к\ г € /, ] €

Отметим, что для данной задачи всегда существует оптимальное целочисленное решение, которое будем обозначать через х^, поэтому от условия булевости переменных х^ можно отказаться. Находим /(г"1') - оптимальное значение целевой функции задачи Т(г<-к)). Вычисляем рекорд для просмотренных точек = тах{/(г'^),

Шаг 3. Строим по некоторому правилу отсечение (линейное неравенство):

Л + + (0)

Обозначим через

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

Правила построения неравенства (6) должны гарантировать, что:

a) ему не удовлетворяет точка

b) оно не исключает никакую точку г' € для которой /(г') > -Г^'.

Свойство "а" позволяет гарантировать конечность процесса Т>, а свойство "Ь" — оптимальность найденного им решения. Данным требованиям удовлетворяют отсечения Бендерса, которые строятся следующим образом. Для полученной на шаге 1 точки формулируется задача прикрепления клиентов Т^(^). Двойственная к ней задача имеет вид:

(к)

£ + £ £ и}цг\ —* гшп при условиях ^

Щ + гиу > су, г € I, 3 € ./,

И'у >0, г £ I, j е ^

Решая ее, находим оптимальные значения двойственных переменных (двойственных оценок) г € I, 3 € J. Отсечение Бендерса, по-

строенное по точке л^' и указанным значениям оценок имеет вид:

£ £ > Г<*> - £ и^. (8)

>6/

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

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

Нами использовались следующие естественные способы вычисления величин

и{Р =тах{су : г £ з € 3,

(9)

где = {г € / : = 1}. Если р > 2, то оптимальными являются также оценки, вычисленные по правилу

=тах{су : = 1, » е 3 € ^ .

«#> = (<*-««)+ г 6/, зеЗ, {Щ

где — а^тах{с,у : г €

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

С =

(М 0 ... О

о м... о ^ о о ...м)

где М > 0. (11)

Нами показано, что если двойственные оценки вычисляются согласно (9), то глубина отсечений Бендерса (8) равна 1. Это означает, что при решении задач семейства процессом ТУ с такими отсечениями происходит полный перебор производственных планов. Неравенства Бендерса в данном случае имеют вид:

£ * > 1,

где //)' ~ {; £ / : ¿¡'^ = 0}, и по своей форме напоминают вполне регулярные отсечения для задач булева программирования [7].

Если в отсечениях Бендерса используются оценки, вычисленные согласно (10), то отсечение, построенное по любой точке г е запрещает все производственные планы, т.е. задача решается за одну итерацию.

На основе семейства (11) получен широкий класс задач о р-медиане, являющихся сложными для процесса Т> с отсечениями Бендерса. Рассмотрим задачу а* с (ш х ?гг)-матрицей целевой функции, у которой элементы главной диагонали равны М, а для остальных коэффициентов имеет место неравенство М > (т — р + 1 )ас, где ас = тах{су : г € I, з 6 г ^ э}.

Процесс Т>, в котором используются отсечения Бендерса (8) с оценками (9), будем обозначать через Т>. Нами доказано, что глубина отсечений, порождаемых в процессе Т> при решении задачи Ртах, равна 1.

С использованием этого результата получена Теорема 2.1. Для

решения задачи Ртах потребуется итераций процесса Т>.

Проведен анализ вычислительной сложности задачи Ртах и установлено, что она является А^Р-трудной.

Аналогичные результаты получены и для задачи Ртщ.

В и. 2.3 строятся оценки числа итераций для прямо-двойственного алгоритма перебора ¿-классов [7] и алгоритма ветвей и границ (схема Лэнд и Донг) [13].

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

Рассмотрим задачу Vшах с матрицей коэффициентов целевой функции

С

( м о ... о \

о м ... о

о о ... м

м м м

\ т—р /п- р ■ "' т~р 1

(12)

где п > 3, 2 < р < п — 1, т = п + 1. Обозначим ее через ¿>д/. В работе доказана

Теорема 2.3. Для решения задачи 5д/ процессом Т> с отсечениями Бен-дерса требуется С?п итераций при использовании формул (9) и не менее итераций при вычислении двойственных оценок по правилу (10).

Кроме того, получены следующие результаты. Теорема 2.4. Пусть р < | и в алгоритме ветвей и границ (схема Лэнд и Дойг) ветвление осуществляется по первой дробной координате. В этом случае для решения задачи Бм потребуется не менее 2Р~2 итераций данного алгоритма.

Теорема 2.5. Если р < -¡^^ > 2, то для решения задачи Бм потребуется не менее 2Р~2 итераций прямо-двойственного алгоритма перебора ¿-классов.

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

Будем использовать обозначения Р, С для индивидуальной задачи о р-медиане и ее матрицы целевой функции и обозначения I , С для задачи и матрицы, в которой некоторые коэффициенты су были подвергнуты колебаниям, т.е. изменены на еу £ Я. Множества оптимальных решений задач обозначим через Z*(P) и Z*(P), соответственно.

Матрица целевой функции С (задача Р) называется е-изменениель

матрицы С (задачи Р), если Е £ |су — c-jjj < е. В случае, когда

ielje.f

Z*(P) С Z*(P), такое изменение называется допустимым.

Введем в рассмотрение абстрактный конечный алгоритм Л решения задачи о р-медиане, на каждой итерации к которого строится некоторый производственный план z^. Пусть S^(P) = fc = 1,2,...} - конеч-

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

Алгоритм Л называется устойчивым, если для любой задачи Р существуют число ер > 0 и полином д{т, п,р), который не зависит от коэффициентов целевой функции задачи Р, такие, что имеет место отношение

|5л(Р)| <ff(m,n,p) \SA(P)\. (13)

Алгоритм Л будем называть абсолютно устойчивьш,, если для любой задачи Р существует такое число ер > 0, что при любом допустимом £р-изменении матрицы С последовательность Sa(P) остается прежней. В работе исследована устойчивость процесса Т> и доказана следующая Теорема 2.6. Процесс V не является устойчивым.

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

вР(г\ z2, z*) = ££ w}jSf + £ «] - /(г3), (14)

ie/je./ j€J

где z1, z2, z3 € П, а г/j, wjj, i € /, j 6 J — значения двойственных оценок, вычисленные по точке г1. Положим

£р = I г3)| : ^ * (15)

и рассмотрим отсечение

£ £ ^ F(k] ~ £ "f' ~ (16)

¡el jeJ jeJ

Отметим, что данное неравенство не запрещает точку z^, поэтому нарушается свойство "а" отсечений, используемых в процессе 23, однако зацикливания процесса не происходит, благодаря условию z^ >- Декомпозиционный алгоритм, в котором вместо отсечений Бендерса применяются неравенства (1G) обозначим Т>'. Имеет место следующая

Теорема 2.7. При вычислении двойственных оценок согласно (9) или (10) процесс ТУ является абсолютно устойчивым.

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

Результаты второй главы опубликованы в [20-22,24-30].

Глава 3 посвящена разработке декомпозиционных алгоритмов решения задачи 'Ртах и их экспериментальному исследованию.

В п. 3.1 сравниваются различные методы нахождения лексикографически максимального элемента множества П^ на шаге 1 процесса Т>.

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

Еще один вариант вычисления г^ состоит в последовательной оптимизации значений координат При этом работа ЛДСМ прерывается, как только оценка сверху для значения текущей координаты становится меньше 1. В таком случае полагаем г, = 0 и переходим на следующую итерацию алгоритма перебора ¿-классов.

Другой способ возможного ускорения алгоритма перебора ¿-классов состоит в исключении неравенств ^ < 1, г € I из множества ограничений решаемых задач ЛП. Если в оптимальной симплекс-таблице значение хч больше 1, то считаем — 1.

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

Кроме того, для отыскания предложен эвристический алгоритм ЬАн, основанный на переборе булевых векторов. В нем для нахождения значения текущей координаты гч используется приближенное решение двойственной задачи. Эксперименты проводились на задачах со случайными данными и на задачах, в которых матрица коэффициентов целевой функции имела "тяжелую" диагональ, размерностью от 30 до 70 производственных переменных при р = 5, 10, 15. На всех решенных примерах алгоритм ЬАн показал значительно лучшее время счета по сравнению с указанными вариантами алгоритма перебора ¿-классов.

В п. 3.2 анализируются результаты вычислительного эксперимента с различными способами построения отсечений Бендерса. Наряду с описанными выше "чистыми" правилами вычисления двойственных оценок применяется эвристический способ адаптации алгоритма к структуре задачи: из двух отсечений Бендерса, построенных с использованием формул (9) и (Ю), выбирается то, которое запрещает больше решений среди нескольких соседних для выбранных случайным образом. Кроме того, рассматривались неравенства, являющиеся суммой двух отсечений Бендерса с оценками (9) и (10). Эксперименты проводились на тех же задачах, что и в н. 3.1. Во всех случаях результаты, показанные предложенной эвристикой, близки к лучшему из "чистых" методов для каждого примера. Это позволяет сделать вывод о целесообразности использования данного правила построения отсечений.

В п. 3.3 описывается гибридный алгоритм, разработанный для решения задачи "Ртах, основными компонентами которого являются релаксация Лагранжа и отсечения Бендерса.

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

Для получения лагранжевой релаксации задачи введем множители Лагранжа yj, j € ./, соответствующие ограничениям (3). Релаксирован-ная задача имеет вид

Д(г,.т) = Е £ Cij.ru - Е уДЕ а;у - 1) —> шах /е/^'е^ ./е./ ¿е!

при условиях

<е/2,'=р' (17)

-V

Л/ "Л ,

О < Х.и < г еТ, 3 6

Хц, е {0,1},

Отметим, что но сравнению с традиционной схемой релаксации Лагранжа для задачи о р-медиане [15] в данной постановке присутствует дополнительное ограничение z -< позволяющее не учитывать уже просмотренные решения.

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

градиентного алгоритма), удалось добиться существенного ускорения. Начальное рекордное значение, целевой функции находится с помощью известного эвристического алгоритма GRASP [18j.

Перейдем к описанию гибридного алгоритма для решения задачи о р-медиане. На каждой итерации к алгоритм ищет точку г^ = lexmax Л® такую, что -< Введем обозначения:

LG— оптимальное значение функции Лагранжа (17) при условии, что первые г координат фиксированы и равны г^',...

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

К — максимальное количество отсечений Бендерса, сохраняемых в текущей системе ограничений.

Алгоритм С13

Итерация 0. Подготовительная. С помощью алгоритма GRASP получаем начальное значение рекорда F Пусть z^ = (1,...,1,0...,0), /¿ = 1, = Находим LG(00) - оценку Лагранжа для целевой функции задачи (1)-(5).

Итерация к (к > 1)

Шаг 1. Проверка необходимости решения задачи Лагранжа. Если задача не решалась итераций подряд, то идем на шаг 2, иначе полагаем г'о = max {г : z\k '' = 1, г е 1} и переходим на шаг 3.

Шаг 2. Нахождение решения задачи Лагранжа. Решая последовательность задач Лагранжа ищем минимальный индекс г'о такой, что z^ ^ = 1 и LG'-'' < F(k~l\ Если такого индекса не существует, то считаем г'о = тах{г : zf~l) = 1, г е /}.

Шаг 3. Нахоо/сдепие решения системы неравенств Бендерса. Полах^аем

=№) _ .(¿-1) *(<■•) _ Jk-i) *(*) _ _ -(*) _ п

"1 > • • ■ 1 -¡о—1 ' "iо ' " " ~т

Используя алгоритм ЬАн из п. 3.1, находим план z^ такой, что z^ -< z^K Вычисляем значение рекорда F^ = ma

Шаг 4. Добавление нового отсечения Бендерса. Строим отсечение Бендерса по точке двойственные оценки при этом выбираются с помощью описанной в п. 3.2 эвристики. Добавляем его в систему ограничений мно-

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

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

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

В п. 3.4 приводятся результаты вычислительного эксперимента на задачах из известных электронных библиотек OR-Library, TSPL1B и библиотеки тестовых задач Института математики СО РАН. Для 15 из 18 примеров OR-Library удалось заметно опередить но времени решения известный алгоритм для задачи о р-медиане, опубликованный в [14] (обозначим его ASV).

При решении задач из TSPL1B алгоритм СБ был незначительно быстрее алгоритма ASV при небольших значениях р и уступал ему при р > 20. Однако следует отметить, что с помощью алгоритма СБ была решена задача, содержащая 5934 производственные переменные, для значений р, равных 5 и 10, чего не удалось сделать алгоритмом ASV. Более того, его авторы сообщают, что оптимальное решение данной задачи нм не известно [14].

В экспериментах на тестовых задачах библиотеки Института математики СО РАН алгоритм СБ сравнивался но времени работы с пакетом для целочисленного программирования ILOG CPLEX G.5. Преимущество алгоритма СБ над этим пакетом в среднем было более чем трехкратным.

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

Материалы данной главы опубликованы в [19,23].

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

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

[1] Агеев A.A. О сложности задач митшизации полиномов от булевых переменных // Управляемые системы,- Новосибирск, 1983 - Вып. 23,- С. 3-19.

[2] Бахтин А.Е., Колоколов A.A., Коробкова З.В. Дискретные задачи производственно-транспортного типа — Новосибирск: Наука, 1978,-1G0 с.

[3] Береснсв B.JI., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации - Новосибирск, 1978.- 333 с.

[4] Девятерикова М.В, Колоколов A.A.. Анализ устойчивости по целевой функции некоторых алгоритмов дискретной оптимизации // Труды 13-й Байкальской международной школы-семинара.-Иркутск-Северобайкальск, 2005 - Т. 1- С. 449-454.

[5] Дементьев В.Т., Ерзин А.Н., Ларин P.M., Шамардин Ю.В. Задачи оптимизации иерархических структур - Новосибирск, 1996. - 168 с.

[6] Ильев В.П. Оценка точности алгоритма жадного спуска для задачи минилшзации супермодулярной функции. // Дискретный анализ и исследование операций,- Серия 1 - 1998,- Т. 5 - JV- 4 - С. 45-60.

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

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

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

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

[11] Леонтьев В.К., Мамутов К.Х. Устойчивость решений в задачах линейного булева программирования // ЖВМ и МФ. - 1988. - С. 21-24.

1С

[12] Стрекаловский А.С., Васильева A.M. Поиск глобального решения в задаче размещения // Материалы международной конференции "Дискретный анализ и исследование операций". - Новосибирск, 2000.

- С. 121.

[13] Схрейвер А. Теория линейного и целочисленного программирования

- Москва, "Мир" , 1991. - В 2 т.

[14] Avella P., Sassano A., Vasil'ev I. Computational study of large scale p-median problems // Mathematical Programming. - 200G. - DOI: 10.1007/sl0107-005-0700-G.

[15] Cornuejols G., Nemha.user G.L., Wolsey L.A. The [Incapacitated Facility Location Problem // In Discrete Location Theory (Ed. by Pitu B. Mirchandani and Richard L. Franscis), by John Wiley and Sons, Inc.

- 1990. - P. 119-171.

[16] Hansen P., Mladenovic N. Variable neighbourhood search for the p-median // Location Science. - 1997. - № 5. - P. 207-226.

[17] Kariv O., Hakimi S.L. An Algorithmic Approach, to Network Location Problems. Part 2. The p-Median. // SIAM J. Appl. Math. - 1979. - № 37. - P. 539-560.

[18] Resende M.G.C., Werneck R.F. A GRASP with path-relinking for the p-median problem j/ AT&T Labs Research Technical Report TD-5E53XLKA, - 2002.

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

[19] Колоколов А.А., Косарев Н.А. Гибридный алгоритм для решения задачи о р-медианс j j Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения" . - Омск, 2006. -С. 101.

[20] Колоколов А.А., Косарев Н.А. Исследование отсечений Вендерс.а для задачи о р-медиане j j Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения" . - Омск, 2003. -С. 96.

[21] Колоколов А.А., Косарев Н.А., Рубанова Н.А. Исследование отсечений Бендерса в декомпозиционных алгоритлшх решения некоторых задач размещения // Омский научный вестник. - 2005. - № 2(31). -С. 76-80.

[22] Косарев Н.А. Оценки числа итераций для некоторых алгоритмов решения задачи о р-медиане // Труды 37-й Региональной молодежной конференции "Проблемы теоретической и прикладной математики". - Екатеринбург: УрО РАН, 2006. - С. 386-390.

[23] Косарев Н.А. Разработка и экспериментальные исследования декомпозиционных алгоритмов для задачи о р-медиане. // Препринт. Ом-ГУ: Омск, 2006. - 23 с.

[24] Косарев Н.А., Рубанова Н.А. Об отсечениях Бендерса для некоторых задач разлъещения предприятий // Материалы Всероссийской конференции "Дискретный анализ и исследование операций". - Новосибирск, 2004. - С. 164.

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

[26] Kolokolov A.A., Kosarev N.A. Analysis of decomposition algorithms with Benders cuts for p-median problem // Proceedings of The 2nd International Workshop "Discrete Optimization Methods in Production and Logistics". - Omsk-Irkutsk, 2004. - P. 66-69.

[27] Kolokolov A.A., Kosarev N.A. Analysis of some Benders decomposition algorithms for the p-median problem // Proceedings of XIV Meeting of EURO Working Group on Location Analysis, Corfu, 2003. - P. 36.

[28] Kolokolov A.A., Kosarev N.A. Study of some decomposition algorithms for p-median problems // Proceedings of XV Meeting of EURO Working Group on Location Analysis, Saarbruecken, Germany, 2004. - P. 58.

[29] Kosarev N.A., Kolokolov A.A. On Stability of Some Benders Decomposition Algorithms for p-median Problem // Proceedings of European Chapter on Combinatorial Optimization XVIII. - Minsk, 2005. - P. 26.

[30] Kosarev N.A., Kolokolov A.A., Rtibanova N.A. On Iterations Number of Benders Decomposition Algorithms for Some Facility Location Problems // Proceedings of European Chapter on Combinatorial Optimization XVIII. - Minsk, 2005. - P. 27.

Отпечатано с оригинал-макета,-предоставленного автором

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

Усл. печ. л. ... Уч.-изд. л. ... Тираж 100 экз. Заказ № ...

Отпечатано в "Полиграфическом центре КАН" 644050, г. Омск, пр. Мира, 11а тел.: (3812) 65-47-31 Лицензия ПЛД №58-47 от 21.04.1997.

Введение.

1 Задачи оптимального размещения предприятий и методы их решения.

1.1 Постановки задач 1.2 Вычислительная сложность и методы решения

1.3 Схема декомпозиции Бендерса.

2 Исследование декомпозиционных алгоритмов

2.1 Декомпозиционные алгоритмы решения задачи о р-медиане.

2.2 Оценки числа итераций для алгоритмов с отсечениями Бендерса

2.3 Анализ некоторых релаксационных алгоритмов целочисленного программирования.

2.4 Вопросы устойчивости декомпозиционных алгоритмов

3 Разработка алгоритмов и их экспериментальное исследование.

3.1 Алгоритмы поиска "перспективных" производственных планов.

3.2 Оптимизация выбора значений двойственных оценок при построении отсечений Бендерса.

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

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

Задачи оптимального размещения предприятий имеют широкий круг приложений, возникающих при планировании и реконструкции производства, проектировании сетей обслуживания, в стандартизации, кластерном анализе и других областях [3,4,10,15,50,51,84]. Значительный интерес к таким задачам связан также со сложностью многих из них. Поэтому для исследования и решения рассматриваемых задач требуется применение методов системного анализа и оптимизации.

В настоящее время исследования задач размещения предприятий ведутся в следующих основных направлениях. Анализируется структура и вычислительная сложность задач, выделяются полиномиально разрешимые случаи и семейства трудных задач, разрабатываются и изучаются методы решения [16,22,26,34,91]. Интенсивно развивается область, связанная с эволюционными алгоритмами, алгоритмами муравьиной колонии и другими метаэвристиками [29,52, 62]. Большое внимание уделяется простейшей задаче размещения (ПЗР) [28,46,51,54], задаче о р-медиане [29,40,44,49,80,93], задачам с ограничениями на объемы производства [27], динамическим задачам размещения предприятий [4,37]. В работах [3,10] и других исследуются многопродуктовые и многоуровневые задачи размещения.

В общих чертах многие задачи оптимального размещения предприятий могут быть сформулированы следующим образом. Даны пункты возможного размещения предприятий и множество клиентов, которые должны быть ими обслужены. Требуется открыть предприятия в некоторых из указанных пунктов, прикрепить к ним клиентов и выполнить обслуживание таким образом, чтобы полученное решение было оптимальным в определенном смысле. Под обслуживанием может пониматься, например, транспортировка продукции от поставщиков к ее потребителям. Задачи различаются между собой имеющимися ограничениями, в частности, возможностями предприятий по обслуживанию клиентов, числом открываемых предприятий, затратами на их открытие, и т.п. Многие из рассматриваемых задач являются АГР-трудными [1,9,67].

Для исследования и решения задач оптимального размещения предприятий широко используется аппарат целочисленного линейного программирования (ЦЛП) [4,44,51,54]. Значительная часть известных точных алгоритмов решения основаны на методе ветвей и границ и различных схемах перебора допустимых решений [40,49]. Часто при этом исходная задача сводится к последовательности более простых, которые могут быть решены методами непрерывной оптимизации. Для построения оценок значений целевой функции используется решение соответствующей задачи линейного программирования (ЛП) или двойственной к ней задачи. С целыо исключения просмотренных и "неперспективных" решений применяются отсечения. В частности, достаточно эффективными оказались фасетные неравенства, порождаемые выпуклой оболочкой множества целочисленных решений [55].

Во многих задачах размещения предприятий, в том числе в задачах о р-медиане и ПЗР, переменные соответствующей модели ЦЛП естественным образом делятся на две группы: целочисленные и непрерывные. Ввиду этого для их решения применяются декомпозиционные алгоритмы с отсечениями Бендерса [3,22,51], в которых решение исходной задачи размещения сводится к анализу и решению последовательности производственных (целочисленных) и транспортных (непрерывных) подзадач.

Для построения производственных подзадач используются дополнительные неравенства (отсечения Бендерса).

Основное направление исследований метода Бендерса - разработка и экспериментальное исследование декомпозиционных алгоритмов для различных задач частично целочисленного программирования [57, 59, 90,92]. С теоретической точки зрения указанные алгоритмы исследованы недостаточно. В частности, актуальными являются вопросы получения оценок числа итераций, построения семейств "трудных" задач, устойчивости алгоритмов при малых колебаниях исходных данных.

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

В области целочисленного программирования (ЦП) получил развитие предложенный А.А.Колоколовым подход, основанный на регулярных разбиениях евклидова пространства [17,70]. Применение такого подхода позволило изучить структуру некоторых задач ЦП, ввести и исследовать новые классы отсечений, построить оценки числа итераций (отсечений) для ряда алгоритмов. Многие результаты получены на основе использования элементов ¿-разбиения, называемых ¿-классами. В работах [22,69] алгоритм перебора ¿-классов в сочетании с декомпозицией Бендерса применяется для решения задач размещения предприятий.

Важное место в дискретной оптимизации занимают вопросы устойчивости задач и алгоритмов ЦП [11,30,33,53]. На практике исходные данные задачи могут быть неточными, и даже в случае их достаточно малых колебаний оптимальное решение задачи может сильно изменяться. Задачи, решение которых при этом остается прежним, либо меняется незначительно, называются устойчивыми в том или ином смысле. Но и при сохранении оптимального решения число итераций алгоритма может существенно возрасти, и его естественно считать неустойчивым. Некоторые последние результаты по устойчивости задач и алгоритмов получены с использованием ¿-разбиения [18,53]. Представляет интерес исследование устойчивости декомпозиционных алгоритмов с отсечениями Бендерса.

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

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

Выделено семейство трудных задач для известных релаксационных алгоритмов ЦЛП: прямо-двойственного алгоритма перебора ¿-классов и алгоритма ветвей и границ (схема Лэнд и Дойг). Построены оценки числа итераций этих алгоритмов при решении задач из указанного семейства.

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

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

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

1. Построены семейства задач о р-медиане, на основе которых получены оценки числа итераций для декомпозиционных алгоритмов с отсечениями Бендерса, алгоритма перебора ¿-классов и алгоритма ветвей и границ (схема Лэнд и Дойг). Некоторые из этих оценок перенесены на достаточно широкий подкласс задач о р-медиане.

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

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

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

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

Заключение

В работе проведено исследование декомпозиционных алгоритмов с отсечениями Бендерса и некоторых алгоритмов целочисленного программирования при решении классических задач оптимального размещения предприятий — задачи о р-медиане (на минимум и на максимум) и простейшей задачи размещения. Разработаны новые декомпозиционные алгоритмы для решения задачи о р-медиане на максимум, проведены их экспериментальные исследования.

1. Агеев A.A. О сложности задач минимизации полиномов от булевых переменных //Управляемые системы. - Новосибирск, 1983. -Вып. 23. - С. 3-19.

2. Агеев A.A. Точные и приблиэюенные алгоритмы для задач размещения: обзор последних достижений //Труды междунар. конференции. "Сибирская конференция по исследованию операций" , Новосибирск, 1998. С. 4-10.

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

4. Береснев B.JL, Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск, 1978. - 333 с.

5. Гимади Э.Х. Задача размещения на сети с центрально-связными областями обслуживания //Управляемые системы. 1979. -Вып. 19. - С. 3-13.

6. Гончаров E.H., Иваненко Д.А., Кочетов Ю.А., Кочетова H.A. Электронная библиотека "Дискретные задачи размещения" //Труды Байкальской междунар. конференции, Иркутск, 2001. Т. 1. -С. 132-137. http://math.nsc.ru/AP/benchmarks/

7. Гончаров E.H., Кочетов Ю.А. Вероятностный жадный алгоритм с ветвлением для многостадийной задачи размещения //Труды XI междунар. Байкальской школы-семинара "Методы оптимизации и их приложения", Иркутск, 1998. С. 121-124.

8. Горбачевская JI.E., Кочетов Ю.А. Вероятностная эвристика для двухуровневой задачи размещения //Труды XI междунар. Байкальской школы-семинара "Методы оптимизации и их приложения" , Иркутск, 1998. С. 249-252.

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

10. Дементьев В.Т., Ерзин А.И., Ларин P.M., Шамардин Ю.В. Задачи оптимизации иерархических структур Новосибирск: НГУ, 1996. - 167 с.

11. И. Емеличев В. А, Кузьмин К., Леонович А., Устойчивость в векторных комбинаторных задачах оптимизации //Автоматика и телемеханика. 2004. - №2. - с. 79-92.

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

13. Заблоцкая O.A. L-разбиеиие многогранника стандартизации //Моделирование и оптимизация систем сложной структуры: Меж-вуз. сб. научн. труд., Омск: ОмГУ, 1987. С. 151-154.

14. Забудский Г.Г. Некоторые свойства многогранника о р-медиане //Вестник Омского гос. университета. 1998. - № 2. - С. 11-13.

15. Заозерская Л.А., Китриноу Е., Колоколов A.A. Задача оптимального размещения центров телекоммуникаций в регионе //Труды XIII междунар. Байкальской школы-семинара, Иркутск-Северобайкальск, 2006. Т. 1. - С. 469-474.

16. Ильев В.П. Оценка точности алгоритма жадного спуска для задачи минимизации супермодулярной функции //Дискретный анализ и исследование операций. Серия 1. 1998. - Т. 5. - № 4. - С. 45-60.

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

18. Колоколов A.A., Девятерикова М.В. Анализ устойчивости L-разбиения мноэюеств в конечномерном пространстве //Дискретный анализ и исследование операций, 2000. Серия 2. Т. 7. - № 2. -С. 47-53.

19. Колоколов A.A., Косарев H.A. Гибридный алгоритм для решения задачи о р-медиане //Труды Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2006. -С. 101.

20. Колоколов A.A., Косарев H.A. Исследование отсечений Бендерса для задачи о р-медиане //Труды Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2003. -С. 96.

21. Колоколов A.A., Косарев H.A., Рубанова H.A. Исследование отсечений Бендерса в декомпозиционных алгоритмах решения некоторых задач размещения //Омский научный вестник. 2005.2(31). С. 76-80.

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

23. Косарев H.A. Оценки числа итераций для некоторых алгоритмов решения задачи о р-медиаие //Труды 37-й Региональной молодежной конференции "Проблемы теоретической и прикладной математики" , Екатеринбург: УрО РАН, 2006. С. 386-390.

24. Косарев H.A. Разработка и экспериментальные исследования декомпозиционных алгоритмов для задачи о р-медиане. //Препринт. Омск: ОмГУ, 2006. 23 с.

25. Косарев H.A., Рубанова H.A. Об отсечениях Бендерса для некоторых задач размещения предприятий// Труды всероссийской конф. "Дискретный анализ и исследование операций". Новосибирск, 2004. С. 164.

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

27. Леванова Т.В. Некоторые алгоритмы решения задачи размещения с ограничениями на объемы производства //Труды междунар. конференции. "Сибирская конференция по исследованию операций", Новосибирск, 1998. С. 103.

28. Леванова Т.В. Разработка и анализ алгоритмов решения дискретных задач оптимального размещения //Диссертация на соискание ученой степени кандидата физ.-мат. наук. Иркутск, 2000.

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

30. Леонтьев В.К., Мамутов К.Х. Устойчивость решений в задачах линейного булева программирования //ЖВМ и МФ. 1988. -С. 21-24.

31. Пащенко M.Г. Нижние оценки для целевой функции в динамической задаче выбора оптимального состава двухуровневой системы технических средств //Дискретный анализ и исследование операций. Серия 2. 1997. - Т. 4. - № 1. - С. 40-53.

32. Попков В.К. Математические модели связности Новосибирск, 2006. - 490 с.

33. Сергиенко И.В., Козерацкая Л.Н., Лебедева Т.Т. Исследование устойчивости и параметрический анализ дискретных оптимизационных задач Киев: Наукова думка, 1995. - 170 с.

34. Стрекаловский A.C., Васильева A.M. Поиск глобального решения в задаче размещения //Труды междунар. конференции "Дискретный анализ и исследование операций", Новосибирск, 2000. С. 121.

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

36. Трубин В.А. Эффективный алгоритм размещения на сети в форме дерева //Докл. АН СССР. 1976. - Т. 231. - № 3. - С. 547-550.

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

38. Ageev A.A., Sviridenko M.I. Approximation Algorithms for some Problems with cardinalyty-type contraints //Труды XI междунар. Байкальской школы-семинара "Методы оптимизации и их приложения" , Иркутск, 1998. С. 107-110.

39. Avella P., Sassano A. On the p-median polytope //Mathematical Programming. 2001. - № 89. - P. 395-411.

40. Avella P., Sassano A., VasiPev I. Computational study of large scale p-median problems //Mathematical Programming. 2006. - DOI: 10.1007/sl0107-005-0700-6.

41. Balinski M.L. Integer Programming: Methods, Using, Computation //Management Science. 1965. - № 12. - P. 253-313.

42. Barany I., Edmonds J., Wolsey L.A. Packing and Covering Trees by Subtrees //Combinatorica. 1986. - № 6. - P. 245-257.

43. Beasley J.E. A note on solving large p-median problems //European Journal of Operational Research. 1985. - № 21. - P. 270-273.

44. Beasley J.E. Lagrangean heuristic for location problems //European Journal of Operational Research. 1993. - № 65. - P. 383-399.

45. Benders J. F. Partitioning Procedures for Solving Mixed-variables Programming Problems //Numerische Mathematik 1962. - Vol. 4. -№.3.- P. 238-252.

46. Charikar M., Guha S. Improved Combinatorial Algorithms for the Facility Location and k-Median Problems //Proceedings of the 40th Annual IEEE Conference on Foundations of Computer Science, 1999. -P. 378-388.

47. Charikar M., Guha S., Tardos E., Shmoys D.B. A constant factor approximation algorithm for the k-median problem //Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999. -P. 1-10.

48. Chiyoshi F., Galvao D. A statistical analysis of simulated annealing applied to the p-median problem //Annals of Operations Research. -2000. № 96. - P. 61-74.

49. Christofides N., Beasley J.E. A tree search algorithm for the p-median problem J/European Journal of Operational Research. 1982. - № 10. -P. 196-204.

50. Cornuejols G., Fisher M.L., Nemhauser G.L. Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms //Management Science. 1977. - № 23. - P. 789-810.

51. Cornuejols G., Nemhauser G.L., Wolsey L.A. The Uncapacitated Facility Location Problem //In "Discrete Location Theory" (Ed. by Pitu B. Mirchandani and Richard L. Franscis), by John Wiley and Sons, Inc., 1990. P. 119-171.

52. Correa E.S., Steiner M.T.A., Freitas A.A., Carnieri C. A genetic algorithm for the p-median problem// Proceedings of 2001 Genetic and Evolutionary Computation Conf. (GECCO-2001), P. 1268-1275.

53. Devyaterikova M.V., Kolokolov A.A. On the stability of some integer programming algorithms //Operation Research Letters. 2006. -№34(2).-P. 149-154.

54. Galvao R. D. A dual-bounded algorithm for the p-median problem //Operation Research. 1980. - № 28. - P. 1112-1121.

55. Gascon V., Benchakroun A., Ferland J. Benders decomposition for network design problems with underlying tree structure //Investigación Operativa. 1997. - № 6. - P. 165-180.

56. Garfinkel R.S., Neebe A.W., Rao M.R. An algorithm for the M-median plant location problem //Transportation Science. 1974. - № 25. -P. 183-187.

57. Geoffrion A.M., Graves G.W. Multicomodity distribution system design by Benders decomposition //Management Science. 1974. - № 20. -P. 822-844.

58. Hakimi S.L. Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph //Operation Research.- 1964. -№ 12. P. 450-459.

59. Handler G.Y., Mirchandani P.B. Location on Networks: Theory and Algorithms MIT Press, Cambridge, Massachusetts, 1979.

60. Hansen P., Mladenovic N. Variable neighbourhood search for the p-median //Location Science. 1997. - № 5. - P. 207-226.

61. Held M., Wolfe P., Crowder H. Validation of Subgradient Optimization //Mathematical Programming. 1974. - № 6. - P. 62-88.

62. Hosage C.M., Goodchild M.F. Discrete space location-allocation solutions from genetic algorithms //Annals of Operational Research. -1986. № 6. - P. 35-46.

63. Hua L.K. et al. Applications of Mathematical Methods to Wheat Harvesting. //Chinese Mathematics. 1962. - № 2. - P. 77-91.

64. Jain K., Vazirani V.V. Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation //Journal of ACM. 2001. - P. 274-296.

65. Kariv O., Hakimi S.L. An Algorithmic Approach to Network Location Problems. Part 2. The p-Median. //SIAM J. Appl. Math. 1979. -№ 37. - P. 539-560.

66. Kolen A. Solving Covering Problems and the Uncapacitated Plant Location Problem on Trees. //European Journal of Operational Research. 1983. - № 12. - P. 266-278.

67. Kolokolov A.A. Decomposition Algorithms for Solving of some Production-Transportation Problems //Triennal Symposium on Transportation Analysis II. Preprints. Vol. 1. Capri, Italy, 1994. -P. 179-183.

68. Kolokolov A.A. Regular partitions and cuts in integer programming// Discrete Analysis and Operation Research. 1996. - P. 59-79.

69. Kolokolov A.A., Kosarev N.A. Analysis of decomposition algorithms with Benders cuts for p-median problem //Journal of Mathematical Modelling and Algorithms. 2006. - № 5. - P. 189-199.

70. Kolokolov A.A., Kosarev N.A. Analysis of decomposition algorithms with Benders cuts for p-median problem //Proceedings of The 2nd International Workshop "Discrete Optimization Methods in Production and Logistics", Omsk-Irkutsk, Russia, 2004. P. 66-69.

71. Kolokolov A.A., Kosarev N.A. Analysis of some Benders decomposition algorithms for the p-median problem //Proceedings of XIV Meeting of EURO Working Group on Location Analysis, Corfu, Greece, 2003. -P. 36.

72. Kolokolov A.A., Kosarev N.A. Study of some decomposition algorithms for p-median problems //Proceedings of XV Meeting of EURO Working Group on Location Analysis, Saarbruecken, Germany, 2004. P. 58.

73. Kosarev N.A., Kolokolov A.A. On Stability of Some Benders Decomposition Algorithms for p-median Problem //Proceedings of European Chapter on Combinatorial Optimization XVIII, Minsk, Byelorussia, 2005. P. 26.

74. Kosarev N.A., Kolokolov A.A., Rubanova N.A. On Iterations Number of Benders Decomposition Algorithms for Some Facility Location Problems //Proceedings of European Chapter on Combinatorial Optimization XVIII, Minsk, Byelorussia, 2005. P. 27.

75. Krarup J., Pruzan P.M. The simple plant location problem: survey and synthesis. //European Journal of Operational Research. 1983. -№ 12. - P. 36-81.

76. Levy J. An Extended Theorem for Location on a Network //Operation Research Quarterly. 1967. - № 18. - P. 433-442.

77. Mirchandani P.B., Oudjit A., Wong R. Multidimensional Extensions and a Nested Dual Approach for the m-Median Problem //European Journal of Operational Research. 1985. - № 21. - P. 121-137.

78. Mirchandani P.B., Reilly J.M. Spatial Distribution Design for Fire Fighting Units //In "Spatial Analysis and Location-Allocation Models" (Ed. by A. Ghosh and G. Rushton), 1987. P. 203-222.

79. Moon D.I., Chaudhry S.S. An Analysis on Network Location Problems with Distant Constraints //Management Science. 1984. - № 30. -P. 290-307.

80. Mulvey J., Crowder H. Cluster analysis: an application of lagrangian relaxation //Management Science. 1979. - № 25. - P. 329-340.

81. Narula S.C. Hierarhical Location-Allocation Problems: A Classification Scheme //European Journal of Operational Research. 1984. - № 15. -P. 93-99.

82. Nemhauser G.L., Wolsey L.A. and Fisher M.L. An analysis of approximations for maximizing submodular set functions. I. //Mathematical Programming. 1978. - № 14. - P. 265-294.

83. Reinelt G. TSPLIB: A traveling salesman problem library //ORSA Journal on Computing. № 1991. - № 3. - P. 376-384. http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.

84. Randazzo D., Luna H. P. L., Mahey P. Benders Decomposition For Local Access Network Design With Two Technologies //Discrete Mathematics and Theoretical Computer Science. 2001. - № 4. -P. 235-246.

85. Resende M.G.C., Werneck R.F. A GRASP with path-relinking for the p-median problem //AT&T Labs Research Technical Report TD-5E53XLKA. 2002.

86. Richardson R. An optimization approach to routing aircraft //Transportation Science. 1976. - № 10. - P. 52-71.

87. Rolland E. , Schilling D. A., Current J.R. An efficient tabu search procedure for the p-median problem //European Journal of Operational Research. 1996. - № 96. - P. 329-342.

88. Teitz M.B., Bart P. Heuristic methods for estimating the generalized vertex median of a weighted graph //Operation Research. 1968. -№ 16 - P. 955-961.

89. Whitaker R.A. A fast algorithm for the greedy interchange for large-scale clustering and median location problems //INFORS. 1983. -№ 21. - P. 95-108.