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

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

КОЧЕТОВ Юрий Андреевич

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

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

АВТОРЕФЕРАТ

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

о

003489524

Новосибирск - 2009

2 4 ДЕК 2009

003489524

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

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

В. К. Попков

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

A. В. Кельманов

доктор технических наук

B. И. Зоркальцев

Ведущая организация: Учреждение Российской академии

наук Вычислительный центр им. A.A. Дородницина РАН

Защита состоится 2<ре£ра.л*.- 2010 г. в 15 час. 00 мин. на заседании диссертационного совета Д 003.061.02 при Институте вычислительной математики и математической геофизики Сибирского отделения РАН по адресу: 630090 г. Новосибирск, пр. Ак. Лаврентьева, 6.

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

Автореферат разослан 3 0 ноября 2009 г.

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

д.ф.-м.н.

С. В. Сорокин

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

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

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

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

нетривиальных вопросов чисто математического плана, например, вопрос о вычислительной сложности нахождения локального оптимума.. Для дискретных задач размещения, как впрочем и для других задач исследования операций, пока не удается подтвердить или опровергнуть гипотезу о существовании полиномиальных алгоритмов нахождения локальных оптимумов. Известно [15], что эти задачи не могут быть ИР-трудными, если NP ф со-ИР, что дает надежду найти такие алгоритмы. Однако эта надежда весьма призрачна в силу плотной РЬБ-полноты таких задач локального поиска для многих "естественных" окрестностей малой мощности. Доказательство существования полиномиальных алгоритмов было бы слишком сильным результатом. Все задачи из класса РЬБ решались бы в этом случае за полиномиальное время. Парадокс состоит в том, что на практике методы локального поиска легко находят локальные оптимумы, а. метаэвристики, например, генетический локальный поиск, систематически порождая все новые и новые локальные оптимумы, часто предъявляет в качестве ответа глобальный оптимум. Требуются специальные усилия, чтобы найти действительно трудные примеры, где такой подход давал бы заметную ошибку. Однако в теории даже один шаг такого метода может оказаться экспоненциальным по сложности. Теория и практика. комбинаторной оптимизации дают здесь принципиально разные оценки возможностей численных методов. Эмпирические исследования свидетельствуют, что для многих ЫР-трудных задал, в том числе и задач размещения, методы локального поиска позволяют находить приближенные решения, близкие по целевой функции к глобальному оптимуму. Трудоемкость алгоритмов часто оказывается полиномиальной, причем степень полинома, достаточно мала.

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

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

Интерес к последней проблеме подогревается целым рядом обстоятельств. Во-первых, стремление получить локальный оптимум оказывается тесно связанным с выделением стационарных точек и условиями Куна-Такера для задач с непрерывными переменными. В идейном смысле понятие окрестности эквивалентно определению вариации в непрерывной оптимизации. Производные в методах комбинаторной оптимизации о6ычею не используются. Создается впечатление, что классические методы непрерывной оптимизации слишком далеки от комбинаторных. Тем не менее в ряде случаев условия локальной оптимальности дискретного решения эквивалентны условиям Куна-Такера. для непрерывной задачи, полученной релаксацией требования целочисленностн переменных. Для NP-трудных задач проблема часто состоит не в том, чтобы найти локальный оптимум, a. в том, что таких оптимумов оказывается слишком много. Выделить среди них глобальный оптимум представляется серьезной проблемой, что, по-видимому, и делает исходную задач}' NP-трудной. Понятие глобального оптимума не является конструктивным. Даже получив такое решение, доказать его оптимальность очень трудно. Аналогичные проблемы возникают и в непрерывной оптимизации. Там необходимые условия оптимальности также имеют локальный характер и опираются на понятие вариации. В комбинаторной оптимизации реализуется та. же идея, и понятие окрестности играет здесь центральную роль.

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

лином, что значение целевой функции задачи на любом решении ограничено этим полиномом от длины записи исходных данных. Такие задачи обладают тем свойством, что для любой полиномиально проверяемой окрестности N и любого правила выбора направления спуска стандартный алгоритм локального улучшения является полиномиальным. Для таких задач выделяют класс задач локального поиска, обладающих следующим свойством: для задачи L = (ОРN) из класса PLS существует такая константа, £ > 0, что каждый локальный оптимум имеет относительную погрешность не более е. Класс этих задач называют классом GLO (Guaranteed Local Optima). Этот класс не пуст. В нем, например, содержится задача коммивояжера, у которой веса ребер принимают значения 1 или 2. Задача выполнимости на максимум, задача о максимальном разрезе с единичными весами также принадлежат этому классу [б]. Замыкание класса GLO (GLO) определяется с помощью сведения, сохраняющего аппроксимируемость (<ptas)■ Задача О Pi принадлежит замыканию класса GLO, если существует такая задача ОР2 G GLO, что OPi <ptas ОР2. Установлено [6], что GLO =АРХ. Таким образом, класс GLO дает новую характе-ризацию класса АРХ, одного из важнейших классов NP-трудных задач. Для любой задачи ОР из класса АРХ найдется задача из класса GLO, к которой задача. ОР сводится с сохранением свойств аппроксимируемости. Другими словами, понятие локального оптимума является одним из важнейших в теории аппроксимации NP-трудных задач.

Наконец, последнее, но не менее важное обстоятельство связано с нахождением решений, равновесных по Нэшу, в игровых моделях размещения. В ряде случаев удается установить взаимнооднозначное соответствие между равновесными решениями и локальными оптимумами в специально подобранной оптимизационной задаче. Если такое соответствие обнаружено, то нахождение равновесных решений сводится к уже рассмотренной задаче поиска локальных оптимумов. Более того, если для оптимизационной задачи удается установить ее принадлежность к классу GLO, то тем самым получается оценка для цены анархии в исходной игровой модели. Таким образом проблемы, исследуемые в диссертации, действительно актуальны.

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

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

Научная новизна. Оригинальность и научная новизна полученных результатов состоит в следующем.

1. Разработаны и исследованы вероятностные методы локального поиска, для ряда дискретных задач размещения. Все рассматриваемые задачи являются ИР-трудными. Более того, одна из них, а именно конкурентная задача о р-меднане, является ¿^2 -трудной, то есть имеет более высокий статус сложности, чем любая задача из класса Ш3. Полученные методы являются итерационными и в асимптотике позволяют находить точное решение задачи. Многочисленные экспериментальные исследования показывают, что фактически оптимум находится достаточно быстро и предлагаемые методы могут с успехом применяться на практике.

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

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

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

4. Исследована вычислительная сложность задачи нахождения локальных оптимумов для дискретных задач размещения с рядом полиномиально проверяемых окрестностей. Показано, что в худшем случае стандартный алгоритм локального улучшения может потребовать экспоненциального числа шагов при любом правиле замещения для каждой из рассматриваемых окрестностей и любого обобщения простейшей задачи размещения или любого обобщения задачи о р-медиане. Установлено, что задачи поиска локального оптимума принадлежат классу PLS (polynomial time local search problems), а. некоторые из них являются плотно полными в этом классе. Если же требуется найти не произвольный локальный оптимум, а оптимум, достижимый из заданной стартовой точки, то такая задача часто оказывается PSPACE-полной.

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

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

Практическая и теоретическая ценность. Работа носит теоретический и экспериментальный характер. Полученные в ней

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

Апробация работы. Все разделы диссертации прошли апробацию на следующих конференциях в России и за рубежом:

- Российская конференция «Дискретный анализ и исследование операций», Новосибирск, 1996, 1998, 2000, 2002, 2004;

- Российская конференция «Дискретная оптимизация и исследование операций», Владивосток, 2007;

- Международный симпозиум по исследованию операций (OR), Германия, 1996, 1999, 2000, 2005, 2006, 2008;

- Международная конференция по метазвристикам (MIC), 2001 (Португалия), 2003 (Япония), 2005 (Австрия);

- Конференция Европейского общества по исследованию операций (EURO), 1998 (Бельгия), 2006 (Исландия), 2007 (Чехия);

- Европейская конференция по методам локального поиска 2005 (Испания);

- Международная конференция «Комбинаторная оптимизация» 1998 (Бельгия);

- Международный симпозиум по математическому программированию (ISMP), 1997 (Швейцария), 2009 (США);

- Байкальская международная школа-семинар «Методы оптимизации и их приложения», Иркутск, 1995, 2001, 2005, 2008;

- Всероссийская конференция «Математическое программирование и приложения», Екатеринбург, 1999, 2001, 2007;

- Всероссийская конференция «Проблемы оптимизации и экономические приложения», Омск, 1997, 2003, 2006, 2009;

- Конференция европейского общества по задачам размещения (EWGLA), 2000 (Испания);

- Симпозиум по исследованию операций (БУМ-ОР-К), 2005 (Черногория).

Результаты диссертации докладывались на семинарах:

- «Математические модели принятия решений», Институт математики им. С.Л. Соболева СО РАН, Новосибирск;

- «Дискретные экстремальные задачи», Институт математики им. С.Л. Соболева СО РАН, Новосибирск;

- «Дискретная оптимизация», Омский филиал Института математики им. С.Л. Соболева. СО РАН, Омск;

- «Комбинаторные методы в исследовании операций», Университет Монреаля, Канада.;

- Семинар высшей школы коммерции, Монреаль, Канада;

- Семинар национального университета. Чар-Тунг, Тайвань.

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

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

Публикации. По теме диссертации автором опубликовано 52 работы, в том числе 20 статей, среди них 16 в журналах из списка ВАК, 32 работы в трудах российских и международных конференций.

Основные результаты диссертации

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

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

3. Установлена вычислительная сложность нахождения локальных оптимумов для ряда задач размещения с полиномиально проверяемыми окрестностями. Показано, что эти задачи принадлежат классу РЬБ и являются наиболее трудными в этом классе. Получена экспоненциальная нижняя оценка в худшем случае на число итераций алгоритмов локального улучшения при любом правиле выбора направления спуска. Доказана РЭРАСЕ-полнота задачи локального поиска при заданной стартовой точке.

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

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

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

Объем и структура диссертации. Диссертация состоит из введения, шести глав и списка литературы (212 наименований). Объем диссертации — 267 страниц.

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

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

Первая глава диссертации дает краткий обзор моделей размещения и тесно связанных с ними моделей стандартизации и унификации, которыми занимался автор с 1979 года. В первую очередь это простейшая задача размещения или, следуя [3], задача выбора оптимального ряда изделий. Этой задаче посвящены десятки статей, главы в монографиях [3, 4, 5]. Хорошо известна связь задачи с псевдобулевыми функциями (полиномами от булевых переменных). Этот вопрос подробно исследуется в книге В. Береснева [2]. Однако до сих пор эквивалентность простейшей задачи размещения специальному классу псевдобулевых функций использовалась только в теории. В [1] отмечено, что одной псевдобулевой функции могут соответствовать разные примеры простейшей задачи размещения. Бесконечное число примеров может порождать одну и ту

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

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

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

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

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

Теорема 4. Решение задачи ВР сводится к решению т задач выбора ряда изделий, т — число изделий исходного ряда.

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

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

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

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

Теорема 7. Задачи И] и полиномиально разрешимы.

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

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

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

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

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

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

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

Третий раздел посвящен вероятностному методу поиска с запретами. Излагается общая схема метода, предложенная Ф. Глове-ром [8], и ее новый рандомизированный вариант. Показано, что вероятностный алгоритм поиска с запретами при определенных ограничениях на структуру и длину списка запретов порождает неразложимую цепь Маркова. Как следствие получается, что при любом стартовом решении вероятность получения точного решения задачи стремится к единице с ростом числа шагов алгоритма. Так как нетривиальных оценок на скорость сходимости получить не удается. а в силу КР-трудностн рассматриваемых задач, по-видимому, и не удастся, то наибольший интерес представляют экспериментальные исследования поведения таких методов на различных классах тестовых примеров. Проведенные исследования свидетельствуют о высокой частоте получения точного решения даже на трудных в вычислительном отношении тестах. Показано положительное влияние рандомизации окрестности на результаты работы алгоритма, исследованы различные стратегии диверсификации поиска, получены доверительные интервалы на вероятность получения точного решения задачи при заданном числе итераций и приближенного решения с погрешностью не более одного процента.

Четвертый раздел посвящен генетическому локальному поиску. Приводятся общая схема этого популярного в комбинаторной оптимизации итерационного метода, обсуждение ключевых элементов данной схемы, асимптотических свойств и интерпретация в терминах цепей Маркова. чЭффективность данного метода во многом зависит от выбора применяемых операций скрещивания, мутаций и процедур локального улучшения, то есть от того, насколько удачно адаптированы эти ключевые элементы под специфику решаемой задачи. В данном разделе исследуются возможности генетического локального поиска для решения задачи о р-медиане с предпочтениями клиентов (МПК). Рассматриваются четыре оператора, скрещивания и две окрестности: стандартная окрестность Swap и новая окрестность для задач размещения, построенная на идеях Лина и Кернигана [9]. Исследуется влияние разных стратегий селекции и мутаций на поведение алгоритма. Для получения нижних оценок оптимума рассмотрены различные возможности сведения задачи к целочисленному линейному программированию. Получено новое сведение, основанное на известной задаче о паре матриц. Установлено, что новое сведение может давать лучшую нижнюю оценку (обозначенную в работе через LBq), чем предшествующие известные оценки. Лучшая из них обозначена через L В4, причем LBq > ЬВА.

Теорема 12. Для любого N > 0 существуют такие исходные данные задачи МПК, что LBq/LB4 > N.

Предложена конструкция таких исходных данных.

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

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

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

Теорема 19. Задача поиска локального минимума для простейшей задачи размещения с окрестностью Flip является PLS-полной.

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

Следствие 5. Для полноты задачи (р-медиана, N) из класса PLS достаточно, чтобы окрестность N была не слабее окрестности FM1-

В четвертом разделе исследуется временная сложность стан-

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

Теорема 23. Задача о р-медиане с каждой т окрестностей Swap, LK, LK\, FM, FM\ является плотно PLS-полной.

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

Теорема 25. Для простейшей задачи размещения с окрестностью Flip и задачи о р-медиане с окрестностями Swap, LK, LK\, FM, FM\ соответствующие стандартные, задачи локального поиска являются PSPACE-полными.

В пятом разделе исследуется связь задачи нахождения локальных оптимумов с классическими условиями Куна-Такера,. Для задачи минимизации произвольного полинома от булевых переменных на заданном слое гиперкуба вводится функция Лагранжа и понятие седловой точки относительно окрестности Swap. Установлено, что точка гиперкуба будет локальным минимумом относительно окрестности Swap тогда и только тогда, когда соответствующее ей решение удовлетворяет условиям Куна-Такера.

В шестом разделе исследуются возможности получения приближенных локальных оптимумов. Допустимое решение se задачи (OP,N) называют е-локальным минимумом, если F(se) < (1 + e)F(s) для всех s £ A'(s£). F —целевая функция задачи ОР. Другими словами, в окрестности N(se) могут содержаться решения с меньшим значением целевой функции, но их относительное уклонение от s£ не должно превышать е. Показано, что для дискретных задач размещения из класса PLS, имеющих линейную целевую функцию, существует полностью полиномиальная г-локальная оптимизационная схема, то есть семейство алгоритмов (АЕ)£>о, позволяющее находить е-локальный минимум для любого е > 0 за

время, ограниченное полиномом от длины записи исходных данных и величины 1/в.

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

Теорема 29. Если P^NP, то для любого р > 1 xi любой тюлино-миально проверяемой окрестности найдутся исходные данные задачи о -р-медиане, для которых существует локальный минимум, отклоняющийся более чем в р раз от оптимального значения задачи.

Следствие 9. Если РфNP. т.о для задачи о р-медиане не существует точных полиномиально проверяемых окрестностей.

Оптимизационную задачу ОР называют псевдо-полиномиально ограниченной, если существует такой полином р от переменных ].т| и Мах(х) — наибольшее по величине число из входа х, что для любого входа х и любого допустимого решения s выполняется неравенство

F(s,x) - Opt(x) <р(\х\,Мах(х)),

где Opt(x) — глобальный минимум для входа, х. Множество таких оптимизационных задач обозначают NPOppb-

Теорема 30. Пусть ОР G NPOppb, (ОР, N) S PLS и целевая функг^ия принимает только целочисленные значения. Если P^=NP и задача вычис/генгия приближенного решения с гарантированной оценкой точности р является NP-трудной в сильном смысле, то найдутся исходные данные, для которых существует локальный оптимум, отклоняющийся более чем в р раз от оптимального значения.

Следствие 10. Если P^NP и задача ОР G NPOppb является NP-трудной в сильном смысле, то для нее не существует точных полиномиально проверяемых окрестностей.

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

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

Пятая глава посвящена игровым моделям размещения. В отличие от игр Штаккельберга, рассматривающихся в первой и третьей главах, здесь исследуется ситуация равноправных игроков. Они не образуют коалиций и преследуют чисто эгоистические цели: максимизация собственной прибыли от открытия предприятий и обслуживания клиентов. Игроки принимают решения одновременно. Тот факт, что они не образуют коалиций и имеют полную информацию о поведении друг друга, приводит к падению цен на рынке и перераспределению доходов между игроками и потребителями. Решение называют равновесным по Нэшу, если ни один из игроков не может увеличить свою прибыль при условии, что другие игроки не меняют свои решения. Понятие равновесного решения в чистых стратегиях оказывается тесно связанным с понятием локального оптимума в соответствующей оптимизационной задаче. Таким образом удается установить сложностной статус задачи поиска равновесных решений. Показано, что задача поиска равновесия принадлежит классу PLS и является плотно полной в нем. Отсюда, в частности, следует, что доказательство существования полиномиального алгоритма вычисления равновесного решения было бы слишком сильным результатом. Все задачи из класса PLS решались бы в этом случае за полиномиальное время. Доказательство обратного утверждения приводит к выводу, что P^NP. Таким образом, вопрос о сложности нахождения равновесных решений в чистых стратегиях является интригующим и может иметь грандиозные последствия.

В первом разделе приводится описание игровой модели. Во втором разделе устанавливается взаимно-однозначное соответствие между равновесными по Нэшу решениями и локальными максимумами некоторой специально сконструированной задачи FLG (Facility Location Game). В качестве окрестности Ni текущего решения рас-

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

Теорема 33. Задача (Мах — Cut,, Flip) плотно PLS-с.водится к задаче (FLG,N\).

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

В четвертом разделе исследуется сложность получения приближенных равновесных решений. Если игрок к меняет свою стратегию, он несет расходы в размере Д*.. Игрок не будет менять свое решение, если приращение прибыли не превосходит дайной величины. Если в такой ситуации ни один из игроков не может величать свою прибыль при условии, что другие игроки не меняют свой выбор, то такое решение называют приближенным равновесным решением с погрешностью Д = (А\,...,АР), где р — число игроков. Задача поиска приближенных равновесий кажется более простой;, так как увеличивается число подходящих состояний. Тем не менее это не всегда так. Если Аь являются постоянными величинами, то поиск приближенных равновесий снова, оказывается плотно PLS-полной задачей. Если же для любых стратегий (¿1,..., у'р) величины Ak могут быть оценены снизу функционалом /¿(¿1,.... гр) суммарной прибыли игроков и экономии клиентов (социальное благо от размещения предприятий и выпуска продукции), то есть Ak > £fi{ii, ■.. ,ip) для любого к = 1,... ,р, то задача может быть решена с полиномиальной трудоемкостью.

Теорема 35. Если Ak > £ц{г\,...,ip) для любого к — 1,...,р и любых С7пратегий (г\,..., ip), то приближенное равновесие с погрешностью А = (Дх,.... Ар) может быть найдено за полиномиальное время от длины записи исходных данных и величины 1/е.

Теорема 36. Если А{; являются постоянными величинами, то поиск приближенного равновесия является плотно PLS-полной задачей.

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

Теорема 38. Нахождение равновесного решения при заданной начальной позиции игроков является РвРА С Е- полной задачей.

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

Шестая глава диссертации посвящена электронной библиотеке тестовых примеров «Дискретные задачи размещения».

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

- примеры, использующие конструкцию конечных проективных плоскостей;

- примеры, использующие совершенные коды с расстоянием 3;

- примеры, базирующиеся на шахматных торах;

- три класса примеров с большим разрывом целочисленности (классы СарА, С ар В, варС);

- примеры с матрицами расстояний на двумерной евклидовой плоскости;

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

Первый класс является полиномиально разрешимым. Зная способ порождения примеров, легко найти точное решение задачи. Однако для методов локального поиска он оказывается достаточно трудным [13, 14], так как каждому пучку прямых соответствует локальный минимум задачи с большим бассейном притяжения.

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

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

Три класса с большим разрывом целочисленности являются сложными для метода ветвей и границ [10]. Разрыв составляет более 20%, что приводит к огромному дереву ветвлений с несколькими десятками миллионов вершин даже при небольшой размерности задачи, n = m = 100. Самый сложный из этих классов, Gap-C является также трудным и для методов локального поиска: вероятностного поиска с запретами, генетического локального поиска и схемы GRASP [7, 12]. Частота нахождения оптимального решения не превышает 0,53 при выполнении этими алгоритмами 104 итераций, соответствующих переходу от текущего решения к соседнему для объединения окрестностей Flip и Swap. Последние два. класса являются наиболее легкими. При заданной размерности тг = m =100 такие примеры легко решаются как методом ветвей и границ, так и метазвристиками.

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

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

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

[1] Береснев В.Л. Алгоритмы минимизации полиномов от булевых переменных // Проблемы кибернетики. — М.: Наука, 1979. — Вып. 36. - С. 225-246.

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

[3] Береснев В. Л., Гимади Э. X., Дементьев В. Т. Экстремальные задачи стандартизации. — Новосибирск: Наука, 1978. — 335 с.

[4] Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование. — М: Физматлит, 2007. 304 с.

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

[6] Ausiello G., Protasi М. Local search, reducibility and approximability of NP-optimization problems// Information Processing Letters. - 1995. - V. 54. - P. 73-79.

[7] Dreo J., Petrowski A., Siarry P., Taillard E., Metaheuristics for Hard Optimization, — Springer, 2006.

[8] Glover F., Laguna M. Tabu Search. — Dordrecht: Kluwer Acad. Publ., 1997.

[9] Kochetov Y., Alekseeva E., Levanova Т., Loresh M. Large neighborhood local search for the p-median problem // Yugoslav Journal of Oper. Res. - 2005. - V. 15, № 1. — P. 53-63.

[10] Kochetov Yu., Ivanenko D. Computationally difficult instances for the uncapacitated facility location problem. In: T. Ibaraki et al. (eds.) Metaheuristics: progress as real solvers. — Springer, 2005, — P. 351-367.

[11] Korte В., Vygen J. Combinatorial Optimization. Theory and Algorithms / Third Edition. — Springer, 2005. — 588 p.

[12] Osman I.H., Laporte G. Metaheuristics: a bibliography // Ann. Oper. Res. - 1996. - V. 63. - P. 513-628.

[13] Resende M. G. C., Werneck P. F. A hybrid heuristic for the p-median problem // Journal of Heuristics. — 2004. — V. 10. — P. 59-88.

[14] Resende M. G. C., Werneck P. F. A hybrid multistart heuristic for the uncapacitated facility location problem // European Journal of Oper. Res. - 2006. - V. 174, - P. 54-68.

[15] Yannakakis M. Computational complexity // Local search in combinatorial optimization. Chichester: Wiley, 1997. — P. 19-55.

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

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

2. Береснев В.Л., Ибрагимов Г.И., Кочетов Ю.А. Алгоритмы решения задачи оптимального выбора динамического ряда изделий // Управляемые системы. — Новосибирск: Ин-т математики СО АН СССР, 1984. - Вып. 24. - С. 3-19.

3. Васильев И.Л., Климентова К.Б., Кочетов Ю.А. Новые нижние оценки для задачи размещения производства с предпочтениями клиентов // Журнал вычислительной математики и математической физики. — 2009. - Т. 49, № 6. - С. 1055-1066.

4. Гончаров E.H., Кочетов Ю.А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения // Дискретный анализ и исследование операций. Серия 2. — 1999. — Т. 6, № 1. - С. 12-32.

5. Гончаров E.H., Кочетов Ю.А. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации // Дискретный анализ и исследование операций. Серия 2. — 2002. — Т.9, JV« 2. - С. 13-30.

6. Кононов A.B., Кочетов Ю.А., Плясунов A.B. Конкурентные модели размещения производства // Журнал вычислительной математики и математической физики. — 2009. — Т. 49, N2 6. — С. 1037— 1054.

7. Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения. Сборник лекций молодежных и научных школ по дискретной математике и ее приложениям. — М: МГУ, 2001. — С. 87117.

8. Кочетов Ю.А. Вычислительные возможности локального поиска в комбинаторной оптимизации // Журнал вычислительной математики и математической физики. — 2008. — Т.48, № 5. — С. 747-764.

9. Кочетов Ю., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискретный анализ и исследование операций. Серия 2. - 2003. - Т. 10, № 1. - С.11-43.

10. Кочетов Ю.А., Пащенко М.Г. Лагранжевы релаксации в задаче выбора оптимального состава системы технических средств // Управляемые системы. — Новосибирск: ИМ СО РАН, 1993, — вып.31. - С. 26-39.

11. Кочетов Ю.А., Пащенко М.Г. Динамические задачи выбора оптимального состава системы технических средств // Дискретный анализ и исследование операций — 1995. — Т. 2, № 1. — С. 36-49.

12. Кочетов Ю.А., Пащенко М.Г. Нижние границы в задаче выбора состава двухуровневой системы технических средств // Дискретный анализ и исследование операций. — 1995. — Т. 2, № 4. —

С. 32-41.

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

14. Кочетов Ю.А., Плясунов А.В. Полиномиально разрешимый класс задач двухуровневого линейного программирования // Дискретный анализ и исследование операций. Серия 2. — 1997. - Т. 4, № 2. - С. 23-33.

15. Кочетов Ю.А., Плясунов А.В. Задача выбора ряда изделий с частичным внешним финансированием // Дискретный анализ и исследование операций. Серия 2. — 2002. — Т. 9, № 2. С. 78-96.

16. Кочетов Ю.А., Столяр А.А. Использование чередующихся окрестностей для приближенного решения задачи календарного планирования с ограниченными ресурсами // Дискретный анализ и исследование операций. Серия 2. — 2003. — Т. 10, № 2. — С. 29-55.

17. Кочетов Ю.А., Столяр А.А. Новые жадные эвристики для задачи календарного планирования с ограниченными ресурсами // Дискретный анализ и исследование операций. Серия 2. — 2005. — Т. 12, № 1. — С. 12-36.

18. Alekseeva Е., Kochetov Yu., Plyasunov A. Complexity of local search for the p-median problem // European Journal of Operational Research. - 2008. - V. 191, N 3. - P. 736-752.

19. Kochetov Yu., Alekseeva E., Levanova Т., Loresh M. Large neighborhood local search for the p-median problem // Yugoslav Journal of Operations Research. - 2005. - V. 15, N 1. - P. 53-63.

20. Kochetov Yu., Kononova P., Paschenko M. Formulation Space Search Approach for the Teacher/Class Timetabling Problem // Yugoslav Journal of Operations Research. — 2008. — V. 18, N 1. — P. 1-17.

Кочетов Юрий Андреевич

Методы локального поиска для дискретных задач

размещения

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

Подписано в печать 08.10.09. Формат 60x84 1/16. Усл. печ. л. 1,7. Уч.-изд. л. 2,0. Тираж 120 экз. Заказ № 114.

Отпечатано в ООО "Омега Принт" пр. Ак. Лаврентьева, 6, 630090 Новосибирск

Введение

1 Дискретные модели размещения

1.1 Простейшая задача размещения.

1.2 Многостадийная задача размещения.

1.3 Задачи размещения с предпочтениями клиентов.

1.4 Антагонистические размещения

1.5 Задачи стандартизации и унификации.

1.5.1 Задача выбора состава системы технических средств

1.5.2 Двухуровневые системы технических средств

1.5.3 Динамическая задача с ограничениями на мощности

1.5.4 Задача выбора состава системы с частичным внешним финансированием.

2 Лагранжевы релаксации

2.1 Общая схема.

2.1.1 Методы субградиентной оптимизации.

2.1.2 Геометрическая интерпретация

2.1.3 Лагранжева декомпозиция

2.2 Лагранжевы релаксации для задачи ВСС.

2.2.1 Сильные и слабые формулировки

2.2.2 Нижние оценки оптимума.

2.2.3 Алгоритм решения задачи ЬЛг (А).

2.2.4 Построение допустимого решения

2.2.5 Численные эксперименты.

2.3 Лагранжевы релаксации для задачи В2СС.

2.3.1 Две нижние оценки.

2.3.2 Соотношение величин ^ и Н.

2.3.3 Результаты тестовых расчетов.

2.4 Лагранжевы релаксации для задачи ВДСС.

2.4.1 Нижние оценки.

2.4.2 Общая схема алгоритма.

2.4.3 Задачи с ограничениями на номенклатуру изделий

2.4.4 Задачи с фактором серийности.

2.4.5 Результаты тестовых расчетов.

3 Метаэвристики

3.1 Метаэвристики для задач комбинаторной оптимизации

3.2 Вероятностные жадные алгоритмы.

3.2.1 Алгоритм «лидер группы» .'.

3.2.2 Условия дополняющей нежесткости.

3.2.3 Алгоритм «случайный аутсайдер».

3.2.4 Принцип ветвления.

3.2.5 Модификации алгоритмов ЛГ и СА.

3.3 Вероятностный поиск с запретами.

3.3.1 Общая схема.

3.3.2 Асимптотические свойства

3.3.3 Варианты алгоритмов.

3.3.4 Вычислительные эксперименты.

3.3.5 Направления дальнейших исследований.

3.4 Генетический локальный поиск.

3.4.1 Генетический алгоритм

3.4.2 Генетический алгоритм для задачи МПК.

3.4.3 Тестовые примеры.

3.4.4 Выбор параметров алгоритма.

3.4.5 Нижние оценки оптимума

3.5 Гибридные методы.

3.5.1 Гибридный генетический локальный поиск.

3.5.2 Верхние оценки

3.5.3 Тестовые расчеты.'.

4 Вычислительная сложность локального поиска

4.1 Задачи локального поиска.

4.2 Класс PLS.

4.3 PLS-полные задачи размещения.

4.4 Временная сложность локального спуска.

4.5 Локально седловые точки.

4.6 Приближенный локальный поиск.

4.7 Погрешность локальных оптимумов.

5 Равновесия по Нэшу в игровых моделях размещения

5.1 Игровая модель размещения предприятий.

5.2 Связь с локальными оптимумами

5.3 Сложность нахождения равновесных решений.

5.4 Поиск приближенных равновесий

5.5 Сложность алгоритмов локального улучшения.

6 Электронная библиотека «Дискретные задачи размещения»

6.1 Структура библиотеки.

6.2 Простейшая задача размещения.

6.2.1 Полиномиально разрешимые примеры.

6.2.2 Примеры с экспоненциальным числом строгих локальных минимумов.

6.2.3 Примеры с большим разрывом целочисленности

6.2.4 Поведение метаэвристик.

6.3 Примеры с кластеризацией локальных минимумов.

6.4 Примеры для конкурентной задачи о р-медиане.

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

Выбор данного направления исследований неслучаен. С одной стороны, методы локального поиска легко адаптируются к изменениям математической модели. Их простота и гибкость открывают широкий простор для решения практических задач. С другой стороны, многие принципиальные вопросы остаются открытыми, в частности, вопросы сходимости методов, оценки их погрешности, возможности получения точного решения задачи и доказательства его оптимальности. Многие методы данного класса сконцентрированы на поиске локальных оптимумов задачи, что порождает массу нетривиальных вопросов чисто математического плана, например, вопрос о вычислительной сложности нахождения локального оптимума. Для дискретных задач размещения, как впрочем и для других задач исследования операций, пока не удается подтвердить или опровергнуть гипотезу о существовании полиномиальных алгоритмов нахождения локальных оптимумов. Известно [212], что эти задачи не могут быть ЫР-трудными, если ЫР -ф со-ЫР, что дает надежду найти такие алгоритмы. Однако эта надежда весьма призрачна в силу плотной РЬБ-полноты таких задач локального поиска для многих "естественных" окрестностей малой мощности. Доказательство существования полиномиальных алгоритмов было бы слишком сильным результатом. Все задачи из класса РЬЭ решались бы в этом случае за полиномиальное время. Парадокс состоит в том, что на практике методы локального поиска легко находят локальные оптимумы, а метаэвристики, например, генетический локальный поиск, систематически порождая все новые и новые локальные оптимумы, часто предъявляет в качестве ответа глобальный оптимум. Требуются специальные усилия, чтобы найти действительно трудные примеры, где такой подход давал бы заметную ошибку. Однако в теории даже один шаг такого метода может оказаться экспоненциальным по сложности. Теория и практика комбинаторной оптимизации дают здесь принципиально разные оценки возможностей численных методов. Эмпирические исследования свидетельствуют, что для многих ^-трудных задач, в том числе и задач размещения, методы локального поиска позволяют находить приближенные решения, близкие по целевой функции к глобальному оптимуму. Трудоемкость алгоритмов часто оказывается полиномиальной, причем степень полинома достаточно мала.

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

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

Вторая причина пристального внимания к локальным оптимумам связана с приближенными алгоритмами, имеющими гарантированные оценки качества. Если комбинаторная задача допускает построение приближенного решения с константной оценкой точности за полиномиальное время, то она по определению принадлежит классу АРХ [81]. Полиномиальный алгоритм может иметь любую природу и, в частности, может быть не связан с понятием окрестности. Многие комбинаторные задачи не принадлежат этому классу, например, задача о р- медиане, если нет дополнительных предположений о структуре матрицы транспортных затрат. Если же матрица удовлетворяет неравенству треугольника, то задача попадает в класс АРХ [160]. Оптимизационную задачу Р называют полиномиально ограниченной, если существует такой полином, что значение целевой функции задачи на любом решении ограничено этим полиномом от длины записи исходных данных. Такие задачи обладают тем свойством, что для любой полиномиально проверяемой окрестности N и любого правила выбора направления спуска стандартный алгоритм локального улучшения является полиномиальным. Для таких задач выделяют класс задач локального поиска, обладающих следующим свойством: для задачи L = (Р, N) из класса PLS существует такая константа s > 0, что каждый локальный оптимум имеет относительную погрешность ие более е. Класс этих задач называют классом GLO (Guaranteed Local Optima). Этот класс не пуст. В нем, например, содержится задача коммивояжера, у которой веса ребер принимают значения 1 или 2. Задача выполнимости на максимум, задача о максимальном разрезе с единичными весами также принадлежат этому классу [81]. Замыкание класса ОЬО (СЬО) определяется с помощью сведения, сохраняющего аппроксимируемость (<ртаб)• Задача Р\ принадлежит замыканию класса СЬО, если существует такая задача Р2 СЬО, что Р\ <ртлв Р'2• Установлено [81], что ОЬО =АРХ. Таким образом, класс СЬО дает новую характе-ризацию класса АРХ, одного из важнейших классов КР-трудных задач. Для любой задачи Р из класса АРХ найдется задача из класса ОЬО, к которой задача Р сводится с сохранением свойств аппроксимируемости. Другими словами, понятие локального оптимума является одним из важнейших в теории аппроксимации КР-трудных задач.

Наконец, последнее, но не менее важное обстоятельство связано с нахождением решений, равновесных по Нэшу, в игровых моделях размещения. В ряде случаев удается установить взаимно-однозначное -соответствие между равновесными решениями и локальными оптимумами в специально подобранной оптимизационной задаче. Если такое соответствие обнаружено, то нахождение равновесных решений сводится к уже рассмотренной задаче поиска локальных оптимумов. Более того, если для оптимизационной задачи удается. установить ее принадлежность к классу СШ, то тем самым получается оценка для цены анархии в исходной игровой модели. Таким образом проблемы, исследуемые в диссертации, действительно актуальны.

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

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

Научная новизна. Оригинальность и научная новизна полученных результатов состоит в следующем.

1. Разработаны и исследованы вероятностные методы локального поиска для ряда дискретных задач размещения. Все рассматриваемые задачи являются NP-трудными. Более того, одна из них, а именно конкурентная задача о р-медиане, является ^^"-трудной, то есть имеет более высокий статус сложности, чем любая задача из класса NP. Полученные методы являются итерациоиными и в асимптотике позволяют находить точное решение задачи. Многочисленные экспериментальные исследования показывают, что фактически оптимум находится достаточно быстро и предлагаемые методы могут с успехом применяться на практике.

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

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

4. Исследована вычислительная сложность задачи нахождения локальных оптимумов для дискретных задач размещения с рядом полиномиально проверяемых окрестностей. Показано, что в худшем случае стандартный алгоритм локального улучшения может потребовать экспоненциального числа шагов при любом правиле замещения для каждой из рассматриваемых окрестностей и любого обобщения простейшей задачи размещения или любого обобщения задачи о р-медиане. Установлено, что задачи, поиска локального оптимума принадлежат классу PLS (polynomial time local search problems), а некоторые из них являются плотно полными в этом классе. Если же требуется найти не произвольный локальный оптимум, а оптимум, достижимый из заданной стартовой точки, то такая задача часто-оказывается PSPACE-полной.

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

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

Практическая и теоретическая ценность. Работа носит теоретический и экспериментальный характер. Полученные в ней результаты позволяют лучше понять природу задач локального поиска, их сложность и границы возможностей полиномиальных алгоритмов. Разработанные методы реализованы в виде программ. Они показали свою эффективность и могут применяться при решении практических задач, а также при преподавании университетских курсов «Методы оптимизации» и «Теория принятия решений». Электронная библиотека активно используется в научных исследованиях в России и за рубежом для тестирования алгоритмов дискретной оптимизации и сравнительного анализа их эффективности.

Апробация работы. Все разделы диссертации прошли апробацию на следующих конференциях в России и за рубежом:

- Российская конференция «Дискретный анализ и исследование операций», Новосибирск, 1996, 1998, 2000, 2002, 2004;

- Российская конференция «Дискретная оптимизация и исследование операций», Владивосток, 2007;

- Международный симпозиум по исследованию операций (OR), Германия, 1996, 1999, 2000, 2005, 2006, 2008;

- Международная конференция по метаэвристикам (MIC), 2001 (Португалия), 2003 (Япония), 2005 (Австрия);

- Конференция Европейского общества по исследованию операций (EURO), 1998 (Бельгия), 2006 (Исландия), 2007 (Чехия);

- Европейская конференция по методам локального поиска 2005 (Испания);

- Международная конференция «Комбинаторная оптимизация» 1998 (Бельгия); *

- Международный симпозиум по математическому программированию (ISMP), 1997( Швейцария);

- Байкальская международная школа-семинар «Методы оптимизации и их приложения», Иркутск, 1995, 2001, 2005, 2008;

- Всероссийская конференция «Математическое программирование и приложения», Екатеринбург, 1999, 2001, 2007;

- Всероссийская конференция «Проблемы оптимизации и экономические приложения», Омск, 1997, 2003, 2006, 2009;

- Конференция европейского общества по задачам размещения (EWGLA), 2000 (Испания);

- Симпозиум по исследованию операций (SYM-OP-IS), 2005 (Черногория).

Результаты диссертации докладывались на семинарах:

- «Математические модели принятия решений», Институт математики им. C.JI. Соболева СО РАН, Новосибирск;

- «Дискретные экстремальные задачи», Институт математики им. C.JI. Соболева СО РАН, Новосибирск;

- «Дискретная оптимизация», Омский филиал Института математики им. C.JI. Соболева СО РАН, Омск;

- «Комбинаторные методы в исследовании операций», Университет Монреаля, Канада;

- Семинар высшей школы коммерции, Монреаль, Канада;

- Семинар национального университета Чар-Тунг, Тайвань.

Публикации. По теме диссертации автором опубликовано 52 работы, в том числе 20 статей, среди них 16 в журналах из списка ВАК, 32 работы в трудах российских и международных конференций.

Основные результаты диссертации

1. Разработаны и исследованы новые вероятностные методы локального поиска для решения МР-трудных задач о £>-медиане, простейшей и многостадийной задач размещения, размещения с предпочтениями клиентов, задач стандартизации и унификации, а также для решения более сложной задачи о (г, р)-центроиде (конкурентной задачи о р-медиане), являющейся Е^-трудной. Эти итерационные методы позволяют находить оптимальные решения и в ряде случаев применяются для доказательства оптимальности получаемых решений.

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

3. Установлена вычислительная сложность нахождения локальных оптимумов для ряда задач размещения с полиномиально проверяемыми окрестностями. Показано, что эти задачи принадлежат классу РЬБ и являются наиболее трудными в этом классе. Получена экспоненциальная нижняя оценка на число итераций для алгоритмов локального улучшения при любом правиле выбора направления спуска. Доказана РБРАСЕ-полнота задачи локального поиска при заданной стартовой точке.

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

5) Для экспериментального исследования численных методов и тестирования комплексов программ разработана электронная библиотека «Дискретные задачи размещения». В ней представлены тесты разной вычислительной сложности, оптимальные решения и результаты численных исследований для точных и итерационных методов локального поиска.

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

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

Объем и структура диссертации. Диссертация состоит из введения, шести глав и списка литературы (212 наименований). Объем диссертации — 267 страниц.

Заключение

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

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

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

3. Установлена вычислительная сложность нахождения локальных оптимумов для ряда задач размещения с полиномиально проверяемыми окрестностями. Показано, что эти задачи принадлежат классу РЬЭ и являются наиболее трудными в этом классе. Получена экспоненциальная нижняя оценка на число итераций для алгоритмов локального улучшения при любом правиле выбора направления спуска. Доказана РЯРАСЕ-полнота задачи локального поиска при заданной стартовой точке.

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

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

1. Александров Д. А. Алгоритм муравьиной колонии для задачи о минимальном покрытии // Методы оптимизации и их приложения: Тр. 11-й Байкальской школы-семинара. — 1998. — Т. 3. — С. 17-20.

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

3. Алексеева Е.В., Кочетов Ю.А., Кочетова H.A. Критические параметры простейшей задачи размещения // Труды XIII Байкальской международной школы-семинара. — 2005. — Т.1. — С. 407-412

4. Архипова Т.Т., Сергиенко И.В. О формализации и решении некоторых задач организации вычислительного процесса в системах обработки данных // Кибернетика. — 1973. — № 5.— С. 79-86.

5. Архипова Т.Т., Сергиенко И.В. Метод возможных направлений и метод вектора спада в целочисленном программировании // Кибернетика. 1975. - № 5. - С. 125-129.

6. Береснев B.J1. Алгоритм неявного перебора для задачи типа размещения и стандартизации // Управляемые системы. / Сб. науч. тр. — Новосибирск: Ин-т математики СО АН СССР, 1974. — Вып. 12. С. 24-34.

7. Береснев B.JI. О задаче выбора оптимальных радов изделей и комплектующих узлов. I // Управляемые системы. / Сб. науч. тр. — Новосибирск: Ин-т математики СО АН СССР, 1977. — Вып. 16. — С. 35-46.

8. Береснев B.JT. Алгоритмы минимизации полиномов от булевых переменных // Проблемы кибернетики. — М.: Наука, 1979. — Вып. 36. С. 225-246.

9. Береснев В. J1. Дискретные задачи размещения и полиномы от булевых переменных. — Новосибирск: Изд-во Инст. математики, 2005.- 408 с.

10. Береснев В. Л., Гимади Э. X., Дементьев В. Т. Экстремальные задачи стандартизации. — Новосибирск: Наука, 1978. — 335 с.

11. Береснев В. Л., Гончаров Е. Н. Приближенный алгоритм для задачи минимизации полиномов от булевых переменных // Дискрет, анализ и исслед. операций. Сер. 2. — 1998. — Т. 5, № 2. — С. 3-19.

12. Береснев В.Л., Ибрагимов Г.И., Кочетов Ю.А. Алгоритмы решения задачи оптимального выбора динамического ряда изделий // Управляемые системы / Сб. науч. тр. — Новосибирск: Ин-т математики СО АН СССР, 1984. Вып. 24. - С. 3-19.

13. Боровков А. А. Теория вероятностей. — М.: Наука, 1986. — 432 с.

14. Васильев И.Л. Климентова К.Б. Кочетов Ю.А. Новые нижние оценки для задачи размещения с предпочтениями клиентов // Журнал вычисл. матем. и матем. физики. — 2009. — Т. 49, К5 6.- С. 1055-1966.

15. Васильев И.Л. Климентова К.Б. Плясунов A.B. Метод отсечений для двухуровневой задачи размещения // Труды XIV-й международной школы-семинара «Методы оптимизации и их приложения».- Иркутск, 2008. Т. 1. - С. 577-585.

16. Волконский В.А., Левина Л.В. Поманский A.B. и др. Об одном итеративном методе решения задач целочисленного программирования // Доклады АН СССР. 1966. - Т. 169, № 6. - С. 1289-1292

17. Глебов Н.И., Дементьев В.Т., Сычев А.Н. О динамике развития однородных технических систем // Управляемые системы / Сб. науч. тр. — Новосибирск: Ин-т математики СО АН СССР, 1971. — Вып. 8. С. 51-67.

18. Гончаров Е. Н. Метод ветвей и границ для простейшей двухуровневой задачи размещения предприятий // Дискрет, анализ и исслед. операций. Сер. 2. 1998. - Т. 5, № 1. - С. 19-39.

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

20. Гончаров Е. Н., Кочетов Ю. А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения // Дискрет, анализ и исслед. операций. Сер. 2. — 1999. — Т. 6, № 1. — С. 12-32.

21. Гончаров Е. Н., Кочетов Ю. А. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации // Дискрет, анализ и исслед. операций. Сер. 2. — 2002. — Т. 9, К0- 2. — С. 13-30.

22. Горбачевская JI. Е. Полиномиально разрешимые и NP-трудные задачи стандартизации: дис. . канд. физ.-мат. наук. — Новосибирск: Ин-т математики им. С. JI. Соболева СО РАН. — 1998. — 123 с.

23. Горбачевская JI. Е., Дементьев В. Т, Шамардин Ю. В. Двухуровневая задача стандартизации с условием единственности оптимального потребительского выбора // Дискрет, анализ и исслед. операций. Сер. 2. 1999. - Т. 6, № 2. - С. 3-11.

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

25. Емеличев В.А., Ковалев М.М., Кононенко A.M. Два приближенных метода решения задач целочисленного линейного программирования с булевыми переменными // — Автоматизированные системы управления. — Вып. 5. — Минск: ЦНИИТУ, 1971.

26. Еремеев А. В. Генетический алгоритм для задачи о покрытии // Дискрет, анализ и исслед. операций. Сер. 2. — 2000. Т. 7, № 1. -С. 47-60.

27. Еремеев А. В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации: дис. . канд. физ.-мат. наук. — Омск: Омский филиал Ин-та математики им. С. Л. Соболева СО РАН. 2000.

28. Журавлев Ю.И. Локальные алгоритмы вычисления информации // Кибернетика. — 1965. № 1. - С. 12-19.

29. Ивахненко А. Г. Системы эвристической самоорганизации в технической кибернетике. — Киев: Техника, 1971.

30. Корбут A.A., Сигал И.Х., Финкелынтейн Ю.Ю. Гибридные методы в дискретном программировании// Изв. АН СССР. Техн. кибернет. 1988. - № 1. — С. 65-77.

31. Ковалев М.М., Пирьянович В.А. Случайный поиск локально-оптимальных планов задач дискретной оптимизации // Вопросы совершенствования планирования и управления народным хозяйством. Минск, НИИЭМП, 1975.

32. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М.: МЦНМО, 1999. - 960 с.

33. Кочетов Ю.А. Двухуровневые задачи размещения // Труды ИВМ и МГ / Серия Информатика — Новосибирск: Изд. ИВМиМГ СО РАН, 2007. Вып. 7. - С. 97-104.

34. Кочетов Ю.А. Задача О (г,р)-центроиде // Материалы IV Всероссийской конференции Проблемы оптимизации и экономические приложения. Омск: ОФ ИМ СО РАН, 2009. - С. 68-73.

35. Кочетов Ю. А., Пащенко М. Г. Лагранжевы релаксации в задаче выбора оптимального состава системы технических средств // Управляемые системы: Сб. науч. тр. Новосибирск, 1993. — Вып. 31: Оптимизация дискретных структур. — С. 26-39.

36. Кочетов Ю.А., Пащенко М.Г. Динамические задачи выбора оптимального состава системы технических средств // Дискрет, анализ и исслед. операций. Сер. 2. — 1995. — Т. 2, № 1. — С. 36-49.

37. Кочетов Ю.А., Пащенко М.Г. Нижние границы в задаче выбора состава двухуровневой системы технических средств // Дискрет, анализ и исслед. операций. Сер. 2. — 1995. — Т. 2, № 4. — С. 32-41.

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

39. Кочетов Ю.А., Плясунов A.B. Полиномиально разрешимый класс задач двухуровневого линейного программирования // Дискрет, анализ и исслед. операций. Сер. 2. — 1997. — Т. 4, № 2. — С. 23-33.

40. Кочетов Ю.А., Плясунов A.B. Задача выбора ряда изделий с частичным внешним финансированием // Дискрет, анализ и исслед. операций. Сер. 2. 2002. - Т. 9, № 2. - С. 78-96.

41. Кочетов Ю.А., Столяр A.A. Использование чередующихся окрестностей для приближенного решения задачи календарного планирования с ограниченными ресурсами // Дискрет, анализ и исслед. операций. Сер. 2. 2003. - Т. 10, Ж 2. - С. 29-55.

42. Крамер Г. Математические методы статистики. — М.: Мир, 1975. 468 с.

43. Кротов Д.С. Нижние оценки числа m-квазигрупп порядка 4 и числа совершенных двоичных кодов// Дискрет, анализ и исслед. операций. Сер. 1. 2000. - Т. 7, Ж 2. - С. 47-53//

44. Лбов Г.С. Выбор эффективной системы зависимых признаков // Вычислительные системы. — 1965. — Вып. 19. — С. 21-34.

45. Лебедев С.С., Ковалевская М.И. Множители Лагранжа в простейшей задаче размещения // Исследования по дискретной оптимизации. М.: Наука, 1976. - С. 170-180.

46. Михалевич В. С., Трубин В. А., Шор Н. 3. Оптимизационные задачи производственно-транспортного планирования. — М.: Наука, 1986. 264 с.

47. Мулен Э. Теория игр с примерами из математической экономики. М.: Мир, 1985. - 200 с.

48. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. — М.: Мир, 1985.

49. Пащенко М.Г. Лагранжевы релаксации в динамических задачах выбора оптимального состава системы технических средств. Дис. . канд. физ.-мат. наук. — Новосибирск: Ин-т математики им. С. Л. Соболева СО РАН. 1998. - 79 с.

50. Пащенко М.Г. Применение Лагранжевых релаксаций в локальном поиске для обобщенной задачи о назначении // Труды 12-й Байкальской международной конференции "Методы Оптимизации и их Приложения", 2001, Т. 1, — С. 180-185.

51. Растригин Л. А. Статистические методы поиска. — М.: Наука, 1968.

52. Растригин Л. А. Случайный поиск — специфика, этапы истории и предрассудки // Вопросы кибернетики. — 1978. — Вып. 33. — С. 3-16.

53. Сергиенко И.В. Применение метода вектора спада для решения задач целочисленного программирования // Управляющие системы и машины. — 1975. — № 3.

54. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. — Киев: Наук.думка, 1981.

55. Сигаев В. С. О свойствах локальных оптимумов задачи размещения буферных накопителей // Вестник Омского университета. — 2006.- № 4. С. 1-3.

56. Сигал И.Х. Последовательность применения алгоритмов приближенного решения в комбинированном алгоритме решения задачи коммивояжера // Журн. вычисл. матем. и матем. физики. — 1989.- Т. 29, № 11. С. 1714-1721.

57. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование. — М: Физматлит, 2007. 304 с.

58. Трубин В.А. О методе решения задач целочисленного линейного программирования специального вида // Доклады АН СССР. — 1969. Т. 189, № 5.

59. Трубин В.А., Чумаков Б.М. Задачи унификации и размещения технических средств // Теория оптимальных решений. — Киев: ИК АН УССР, 1979. С. 69-75.

60. Финкелыптейн Ю-Ю. Приближенные методы и прикладные задачи дискретного программирования. — М.: Наука, 1976.

61. Финкелыптейн Ю.Ю. Об одном классе задач дискретного программирования // Эконом, и матем. методы. — 1968. — Т. 4, № 4. — С. 652-655.

62. Финкелыптейн Ю.Ю. О решении задач дискретного программирования специального вида // Эконом, и матем. методы. — 1965. — Т. 1, № 2. С. 262-270.

63. Фогель JI., Оуэне А., Уолш М. Искусственный интеллект и эволюционное моделирование. — М.: Мир, 1969.

64. Форд JL, Фалкерсон Д. Потоки в сетях. — М.: Мир, 1966.

65. Хачатуров В.Р., Астахов Н.Д. Динамические задачи размещения (модели и методы решения) // Экономика и математические методы. 1976. - Т. 12, Вып. 1. - С. 93-109.

66. Хачатуров В. Р., Веселовский В. Е., Злотов А. В. и др. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности. — М.: Наука, 2000.

67. Черенин В.П., Хачатуров В.Р. Решение методом последовательных расчетов одного класса задач о размещении производства // Экономико-математические методы. М.: Наука, 1965. — Вып. 2. — С. 279-290.

68. Aarts Е. Н. L., Korst J. Н. М., Laarhoven P. J. М. Simulated annealing // Local search in combinatorial optimization. Chichester: John Wiley & Sons, 1997. P. 91-120.

69. Aarts E. H. L., Lenstra J. K. (Eds.) Local Search in Combinatorial Optimization. — Chichester: John Wiley & Sons, 1997.

70. Aggarwal C.C., Orlin J.B., Tai R.P. Optimized crossover for maximum independent set // Oper. Res. 1997. - V. 45. — P. 225-234.

71. Ahuja R.K., Ergun O., Orlin J.B., Punnen A.P. A survey of very large-scale neighborhood search techniques // Discrete Appl. Math. — 2002.- V. 123, Issue 1-3. P. 75-102.

72. Ahuja R.K., Orlin J. A milti-exchange heuristic for the single-source capacitated facility location problem. // Manag. Sci. — 2004. — V. 50,- C. 749-760.

73. Alekseeva E., Kochetov Yu., Plyasunov A. Complexity of local search for the p-median problem // European J. Oper. Res. — 2008. — V. 191- P.736-752.

74. Alexandrov D., Kochetov Y. Simple plant location problem with partial external finance: lower bound, heuristic and exact solution // Operations Research Proceedings 1996 — Berlin: Springer, 1997. — C. 90-94.

75. Anderson E.J., Glass C.A., Potts C.N. Machine scheduling// In: E.Aarts, J.K. Lenstra Local Search in Combinatorial Optimization. — Chichester: John Wiley & Sons, 1997, P. 361-414.

76. Angel E., Zissimopoulos V. On the classification of NP-complete problems in terms of their correlation coefficient // Discrete Appl. Math. 2000. - V. 99. - P. 261-277.

77. Arora S., Raghavan P., Rao S. Approximation schemes for Euclidean k-medians and related problems // Proc. 30th Annual ACM Symposium on Theory of Computing. — 1998. — P. 106-113.

78. Ausiello G., Crescenzi P., Gambosi G., Kann V., Marehetti-Spaccamela A., Protasi M. Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties. — Berlin: Springer-Verlag, 1999.

79. Ausiello G., Protasi M. Local search, reducibility and approximability of NP-optimization problems// Information Processing Letters. — 1995. V. 54. - P. 73-79.

80. Avella P., Boccia M., Martino C.D., Oliviero G., Sforza A., VasiFev I. A decomposition approach for a very large scale optimal diversity management problems // 40R. 2005. — V. 3. — P. 23-37.

81. Avella P., Sassano A., Vasil'ev I. Computational study of large-scale p-median problems // Math. Program. Ser. A. — 2007. — V. 109. — P. 89-114.

82. Bahiense, L., N. Maculan, and C. Sagastizabal. The volume algorithm revisited: relation with bundle methods // Math. Prog. — 2002. — V. 94, N 1. P. 41-70.

83. Balas E., Niehaus W. Finding large cliques in arbitrary graphs by bipartite matching // D.S. Johnson and M.A. Trick (eds.) Cliques, coloring, and satisfiability. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 1996. - V. 26. - P. 29-49.

84. Balas E., Niehaus W. Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems //J. Heuristics. 1998. - V. 4, N 4, - P. 107-122.

85. Barahona, F. and R. Anbil. The Volume Algorithm: Producing Primal Solutions with a Subgradient Method // Math. Prog. — 2000. — V. 87, N.3. P. 385-400.

86. Barros A.I., Labbe M. A general model for the uncapacitated facility and depot location problem // Location Science. — 1994. — V. 2, N 3.- P. 173-191.

87. Battiti R., Protasi M. Reactive local search for maximum clique // Proc. of Workshop on Algorithm Engineering, 1997. — P. 74-82.

88. Benati S., Laporte G. Tabu search algorithms for the (r|Xp)-medianoid and (r|p)-centroid problems. // Location Science.— 1994. — V.2, N.2,- P. 193-204.

89. Bhadury J., Eiselt H.A., Jaramillo J.H. An alternating heuristic for medianoid and centroid problems in the plane. // Computers and Operations Research. 2003. - V.30. — P. 553-565.

90. Bilde O., Krarup J. Sharp lower bounds and efficient algorithms for the simple plant location problem // Annals Discrete Math. 1. — Amsterdam: North Holland Publ. — 1977. P. 79-97.^

91. Blum C. Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison // ACM Computing Surveys (CSUR). 2003. - V.35, Issue 3. — P. 268-308.

92. Boese K. D., Kahng A. B., Muddu S. A new adaptive multi-start technique for combinatorial global optimizations // Oper. Res. Lett. 1994. — V. 16, N 2. - P. 101-113.

93. Bock F. An algorithm for solving "travelling-salesman"and related network optimization problems // Bulletin Fourteenth National Meeting of the Operations Research Society of America. — 1958. — P. 897.

94. Boros E., Hammer P. L. Pseudo-Boolean optimization // Discrete. Appl. Math. 2002. - V. 123. - P. 155-225.

95. Bremermann H. J., Roghson J., Salaff S. Global properties of evolution processes. In Natural automata and useful simulations. Edited by Pattee H. H. etc. — London: Macmillan, 1966. — P. 3-42.

96. Burke E.K., Kendall G. (Eds.) Search Methodologies. Introductory Tutorials // Optimization and Decision Support Techniques. — Berlin: Springer, 2005.

97. Charon I. Hudry H. The noising methods. A survey. In: Ribeiro C.C. Hansen P. (eds.) Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization. — Boston: Kluwer. Acad. Publ., 1998. — P. 245-262.

98. Christofides N. Beasley R. Extensions to a Lagrangean relaxation approach for the capacitated warehouse location problem // European Journal of Operational Research — 1984. — V.12 — P. 19-28.

99. Cornuejols G. Sridharan R. Thizy J.M. A comparison of heuristics and relaxation for the capacitated plant location problem // European Journal of Operational Research — 1991. — V. 50 P. 280-297.

100. Croes G. A. A method for solving traveling salesman problems // Oper. Res. 1958. - V. 6. - P. 791-812.

101. Dobson G., Karmarkar U. Competitive location on a network. // Oper. Res. 1987, - V. 35. - P. 565-574.

102. Dolgui A., Eremeev A., Kolokolov A., Sigaev V. A Genetic Algorithm for the Allocation of Buffer Storage Capacities in a Production Line with Unreliable Machines // Journal of Mathematical Modelling and Algorithms. 2002. - V.l, N 2. - P. 89-104.

103. Dreo J., Petrowski A., Siarry P., Taillard E., Metaheuristics for Hard Optimization, — Springer, 2006.

104. Drezner Z. (Ed.) Facility Location. A Survey of Applications and Methods. — Springer, 1995. — 571 p.

105. Drenzer Z., Eiselt H.A. Consumers in competitive location models // Z. Drenzer, H. Hamacher (Eds.) Facility Location. Applicatios and Theory. — Springer, 2004. — P. 151-178.

106. Drezner Z., Klamroth K., Schobel A., Wesolowsky G. The Weber Problem // Z. Drezner, H. Hamacher (Eds.) Facility Location. Applications and Theory. — Springer, 2004. — P. 1-36.

107. Dyer M.E. A O(n) algorithm for the multiple-choice knapsack linear program // Math. Programming. 1984. - V.29, N.l. - P. 57-63.

108. Everett H. Generalized Lagrange multiplies method for solving problems of optimum allocation of resources // Oper. Res. — 1963. V. 11 - P. 399-417.

109. Eiselt H. A., Sandblom C. -L. Decision Analysis, Location Models, and Scheduling Problems. — Springer, 2004. — 380 p.

110. Erlenkotter D. A dual-based procedure for uncapacitated facility location // Oper. Res. 1978. - V. 26. - P. 992-1009.

111. Erlenkotter D. A comparative study of approaches to dynamic location problems // European J. Oper. Res. — 1981. — V. 6, N 2. — P. 36-81.

112. Fabrikant, A., Papadimitriou C., Talwar K. The complexity of pure Nash equilibria // Proc. 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, 2004. P. 604-612.

113. Faigle U., Kern W. Some convergence results for probabilistic tabu search // ORSA J. Comput. 1992. - V. 4, N 4. - P. 32-37.

114. Fathian M., Amiri B., Maroosi A. Application of honey-bee mating optimization algorithm on clustering // Applied Mathematics and Computation. 2007. - V. 190(2). - P. 1502-1513.

115. Feige U. A threshold of Inn for approximating set cover // Proceedings of the 28 annual ACM symposium on the theory of computing. — N.Y.: ACM Press, 1996. P. 314-318.

116. Feo T. A. Greedy randomized adaptive search procedures //J. Global Optim. 1995. - V. 6. - P. 109-133.

117. Festa P., Resende M. G. C., GRASP: An annotated bibliography. In: C. C. Ribeiro, P. Hansen (Eds.) Essays and surveys in metaheuristics.- Kluwer Academic Publishers, 2002. — P. 325-368.

118. Fiduccia C.M., Mattheyses R.M. A linear-time heuristic for improving network partitions // Proc. 19th Design Automation Conference. Los Alamitos, CA: IEEE Comput. Soc. Press, 1982. — P. 175-181.

119. Fischetti M., Lodi A. Local branching. // Math. Programming. — 2003.- V. 98, N. 2. P. 23-47.

120. Fisher M. L. Worst-case analysis of heuristic algorithms // Manag. Sci.- 1980. V. 26, N. 1. - P. 1-18.

121. Fisher M., Kedia P. Optimal solution of set covering partitiong problems using dual heuristics // Management Science. — 1990. — V. 36, N.6. P.674-688.

122. Fischer S. T. A note on the complexity of local search problems // Information Processing Letters. — 1995. — V. 53. — P. 69-75.

123. Frangioni A. About Lagrangian methods in integer optimization // Annals of Operations Research, — 2005. V. 139. — P. 163-193.

124. Fridman M. L., Johnson D. S., McGeoch L. A., Ostheimer G. Data structures for traveling salesman //J. Algorithms. — 1995. — V. 18. — P. 432-479.

125. Geoffrion, A.M. (1974). Lagrangian Relaxation and its Uses in Integer Programming // Math. Prog. Study. — 1974. — V. 2. — P. 82-1-14.

126. Glover F. Future paths for integer programming and links to artificial intelligence. // Comp. Oper. Res. 1986. — V. 13. - P. 533-549.

127. Glover F., Laguna M. Tabu Search. — Dordrecht: Kluwer Acad. Publ., 1997.

128. Goldberg D. E. Simple genetic algorithms and the minimal deceptive problem. Genetic Algorithms and Simulated Annealing. Chapter 6. — Los Altos, CA, Morgan Kauffman, 1987. — P. 74-88.

129. Goldberg D. E. Genetic algorithm in search, optimization and machine learning. — Reading, MA: Addison-Wesley. 1989.

130. Guha S., Khuller S. Greedy strikes back: improved facility location algorithms. // J. Algorithms. 1999. - V. 31. - P. 228-248.

131. Guignard, M. Lagrangean Relaxation // TOP. — 2003. V. 11, N.2.- P. 151-228.

132. Guignard M., Kim S. Lagrangian decomposition: a model yelding stronger Lagrangian bounds // Math. Prog. — 1987. — V. 39. — P. 215228.

133. Gusfield D., Martel C., Fernandez-Baca D. Fast algorithms for bipartite network flow // SIAM J. Comput. 1987. - V. 16, N 2. - P. 237-251.

134. Gutin G. Exponential neighborhood local search for the traveling salesman problem // Comput. Oper. Res. — 1999. — V. 26. — P. 313320.

135. Gutin G., Yeo A. Small diameter neighborhood graphs for the traveling salesman problem: four moves from tour to tour // Comput. Oper.,Res.- 1999. V. 26. - P. 321-327.

136. Hakimi S. L. On locating new facilities in a competitive environment // European J. Oper. Res. — 1983. — V. 12, N 1. — P. 29-35.

137. Hakimi S. L. Locations with spatial interactions: competitive locations and games // P. B. Mirchandani, R. L. Francis (Eds.) Discrete Location Theory. Wiley & Sons, 1990. - P. 439-478.

138. Hall M.Jr. Combinatorial Theory. Blaisdell. Waltham. MA, 1967.

139. Hammer P.L., Rudeanu S. Boolean method in operations research and related areas. — Berlin: Springer-Verlag, 1968.

140. Hanjoul P., Peeters D. A facility location problem with clients' preference orderings // Regional Science and Urban Economics. —1987.- V. 17. P. 451-473.

141. Hansen, P., Brimberg, J., Urosevic, D., Mladenovic, N. Primal-Dual Variable Neighbourhood for the Simple Plant Location Problem // INFORMS J. Computing. 2007. - V. 19, N 4. - P. 552-564.

142. Hansen P., Kochetov Yu., Mladenovic N. Lower bounds for the uncapacitated facility // Discrete Optimization Methods in Production and Logistics (DOM'2004) / 2nd International Workshop; proceedings.- Omsk: Nasledie Dialog-Sibir., 2004. P. 50-55.

143. Held, M., R. Carp. The travelling salesman problem and minimum spanning trees: Part II // Math. Prog. — 1971. — V. 1. — P. 6-25.

144. Held M., Wolfe P., Crowder H. P. Validation of subgradient optimization // Math. Programming. — 1974. — V. 6, N 1. — P. 62-88.

145. Hertz A., Plumettaz M., Zufferey N. Variable Space Search for Graph Coloring // Discrete Appl. Math. 2008. - V. 156. — P. 2551-2560.

146. Hertz A., Taillard E., de Werra D. Tabu search // Local search in combinatorial optimization. — Chichester: John Wiley & Sons, 1997.- P. 121-136.

147. Holland J. H. Adaptation in Natural and Artificial Systems. — Ann Arbor: University of Michigan Press, 1975.

148. Ibaraki T., Nonobe K., Yagiura M. (Eds.) Metaheuristics: progress as real solvers. — Berlin: Springer, 2005.

149. Jacobsen S.K. Heuristic solutions to dynamic plant location problems // Advances in Operations Research: Proc. EURO II / The second European Congress on Operations Research. — Amsterdam, 1977. — P. 207-213.

150. Johnson D.S. Local optimization and the traveling salesman problem // Automata, Languages, and Programming. — Berlin: Springer Verlag, 1990. (Lecture Notes in Computer Science, V. 443) — P. 446-461.

151. Johnson D.S., McGeoch L.A. The traveling salesman problem: A case study. // In: E.H.L. Aarts, J.K. Lenstra (eds) Local Search in Combinatorial Optimization. — Chichester: John Wiley & Sons, 1997.- P. 215-310.

152. Johnson D.S., Papadimitriou C.H., Yannakakis M. How easy is local search? // J. of Computer and System Sciences. — 1988. — V. 37. — P. 79-100.

153. Kellerer H., Pferschy U., Pisinger D. Knapsack Problems. — Berlin: Springer. 2004. — 546 p.

154. Kernighan B.W., Lin S. An efficient heuristic procedure for partitioning graphs // Bell System Technical Journal. — 1970. — V. 49. — P. 291307.

155. Kochetov Y., Alekseeva E., Levanova T., Loresh M. Large neighborhood local search for the p-median problem // Yugoslav Journal of Oper. Res. 2005. - V. 15, № 1. - P. 53-63.

156. Kochetov Yu., Ivanenko D. Computationally difficult instances for the uncapacitated facility location problem. In: T. Ibaraki et al. (eds.) Metaheuristics: progress as real solvers. — Springer, 2005, — P. 351367.

157. Kochetov Yu., Kononova P., Paschenko M. Formulation Space Search Approach for the Teacher/Class Timetabling Problem // Yugoslav Journal of Operations Research. — 2008, — V. 18, N 1. — P. 1-11.

158. Korte B., Vygen J. Combinatorial Optimization. Theory and Algorithms / Third Edition. — Springer, 2005. — 588 p.

159. Koutsoupias E., Papadimitriou C. Worst-case equilibria // Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science. — Trier: Germany, 1999. — P. 404-413.

160. Koza J. R. Genetic Programming II. Automatic Discovery of Reusable Programs (Complex Adaptive Systems). — MIT Press, 1994.

161. Krarup J., Pruzan P. M. The simple plant location problem: survey and synthesis. // European J. Oper. Res. — 1983. — V. 12, N 1. — P. 36-81.

162. Krasnogor N., Hart W., Smith J. (eds) Resent Advances in Memetic Algorithms, Studies in Fuzziness and Soft Computing. V. 166. — Berlin: Springer, 2004

163. Krentel M.W. On finding and-verifying locally optimal solutions // SIAM J. on Comput. 1990. - V.19. - P. 742-751.

164. Lemarechal, C. . Lagrangian Relaxation. In: M. Jiinger and D. Naddef (eds.), Computational Combinatorial Optimization, — Springer Verlag, Heidelberg, 2001. P. 115-160.

165. Martello S., Toth P. Knapsack Problems. Algorithms and Computer Implementations. — Chichester: John Wiley & Sons, — 1990. — 296 p.

166. Mautor T. Intensification neighborhoods for local search methods // Essays and surveys in metaheuristics. — Boston: Kluwer Academic Publishers, 2002. P. 493-508.

167. Mirchandani P. B., Francis R. L.(Eds.) Discrete Location Theory. — Wiley, 1990. 576 p.

168. Mladenovic N.,Brimberg J.,Hansen P., Moreno-Pérez J. The p-median problem: A survey of metaheuristic approaches // European J. of Oper. Res. 2007. - V. 179, N 3. - P. 927-939.

169. Mladenovic N , Brimberg J, Hansen P and Moreno-Perez J. The p-median problem: A survey of metaheuristic approaches. // European J Operational Research. 2007, - V. 179. — P. 927-939.

170. Mladenovic, N., Plastria, F., Urosevic, D. Reformulation descent applied to circle packing problems. // Computers and Operations Research. 2005. - V. 32, N. 9. - P. 2419-2434.

171. Moscato P. Memetic algorithms: a shot introduction. // In: D. Corne, M. Dorigo, F. Glover (eds.) New Ideas in Optimization. — London: McGraw-Hill, 1999. - P. 219-234.

172. Moscato P., Cotta C. A gentle introduction to memetic algorithms. In: F. Glover, G. Kochenberger (eds) Handbook of Metaheuristics. — Norwell, MA: Kluwer Acad. Publ., 2003.

173. Mühlenbein H. Parallel genetic algorithm, population dynamics and combinatorial optimization // Proc. Third Inter. Conf. Genetic Alg. — San Mateo: Morgan Kaufman, 1989. — P. 416-421.

174. Nicholson T.A.J. A sequential method for discrete optimization problems and its application to the assignment, traveling salesman and tree scheduling problems //J. Inst. Math. Appl. — 1965. — V. 13. — P. 362-375.

175. Noltermeier H., Spoerhose J., Wirth H.C. Muliple voting location and single voting location on trees. // European J. Oper. Res.— 2007. — V. 181. P. 654-667.

176. Orlin J.B., Punnen A.P., Schulz A. Approximate local search in combinatorial optimization // SI AM J. Comput. — 2004. — V. 33. P. 1201-1214.

177. Osman I.H., Laporte G. Metaheuristics: a bibliography // Ann. Oper. Res. 1996. - V. 63. - P. 513-628.

178. Papadimitriou C.H. The complexity of the Lin-Kernighan heuristic for the traveling salesman problem // SIAM J. on Comput. — 1992. — V. 21. P. 450-463.

179. Papadimitriou C. H. Computational complexity. — Addison-Wesley, 1994.

180. Plastria F., Vanhaverbeke L. Discrete models for competitive location with foresight // Computers and Operations Research. — 2008. — V. 35, N 3. P. 683-700.

181. Poljak, B.T. Subgradient Methods: A Survey of Soviet Research. In: C. Lemarechal and R. Mifflin (eds.), Nonsmooth Optimization, IIASA Proceedings Series, 1977. — vol. 3.

182. Rechenberg I. Evolutionsstrategie: Optimerung Technischer Systeme nach Prinzipen der Biologischen Evolution. — Stuttgart: Formann-Holzboog Verlag, 1973. .

183. Resende M. G. C., Werneck P. F. A hybrid heuristic for the p-median problem // Journal of Heuristics. — 2004. — V. 10. — P. 59-88.

184. Resende M. G. C., Werneck P. F. A hybrid multistart heuristic for the uncapacitated facility location problem // European Journal of Oper. Res. 2006. - V. 174, - P. 54-68.

185. Reeves C. R. Genetic algorithms for the operations researcher // INFORMS J. Comput. 1997. - V. 9, N 3. - P. 231-250.

186. Rhys J.M.W. A selection problem of shared fixed costs and network flows // Manag. Sci. 1970. V. 17. - P. 200-207.

187. Ribeiro C.C. Hansen P. (Eds.) Meta-heuristics: advances and trends in local search paradigms for optimization. Boston: Kluwer. Acad. Publ., 1998.

188. Rodriguez C. M. C., Perez J. A. M. Multiple voting location problems // European J. Oper. Res. 2008. - V. 191, N 2. - P. 437-453.

189. Rudolph G. Finite Markov chain results in evolutionary computation: a tour d'horizon // Fundamenta Informaticae. — 1998. — V. 35, N 1-4, P. 67-89.

190. Shor N.Z. Minimization methods for non-differentiable functions. — Berlin: Springer, 1985.

191. Sastry K., Goldberg D., Kendall G. Genetic algorithms. // In: E.K. Burke, G. Kendall (Eds.) Search Methodologies. Introductory Tutorials in Optimization and Decision Support Techniques. — New York: Springer, 2005. P. 97-126.

192. Schrijver A. Combinatorial optimization. Polyhedra and efficiency. — Berlin. Springer, 2003. 1881 p.

193. Schäffer A. A., Yannakakis M. Simple local search problems that are hard to solve // SIAM J. on Comput. 1991. - V. 20, N. 1. - P. 56-87.

194. Schuler R., Schöning U., Watanabe O. An improved randomized algorithm for 3-SAT // Techn. Rep., Dept. of Math, and Comput. Sei. Tokyo Inst, of Technology, 2001.

195. Schumacher C. Black box search — framework and methods. Ph. D. Thesis. — The Univ. of Tennessee, Knoxville, USA, 2000.

196. Schwefel H. P. Numerical optimization of computer models. — Chichester: Wiley, 1981.

197. Spoerhose J., Wirth H.C. (r; p)-Centroid problems on paths and trees. Tech. Report 441, — Inst. Comp. Science, University of Würzburg, — 2008.

198. Stadler P.F. Corelation in landscapes of combinatorial optimization problems // Europhys. Lett. 1992. — V. 20. — P. 479-482.

199. Stadler P.F., Schnabl W. The landscape of the traveling salesman problem // Physics Letters A. — 1992. V. 161. - P. 337-344.

200. Talbi E.G. A taxonomy of hybrid metaheuristics // Journal of Heuristics. 2002, - V. 8. - P. 541-564.1. Литература2671. С.---"

201. Tcha D. W., Lee B.-Y. A branch-and-bound algorithm for the multilevel uncapacitated facility location problem. // European J. Oper. Res. — 1984. V. 18, N 1. - P. 35-43.

202. Van Roy Т., Erlenkotter D. A dual-based procedure for dynamic facility location // Management Sci. 1982. - V. 28, N 10. - P. 1091-1105.

203. Verhoeven M.G.A., Swinkels P.O.J., Aarts E.H.L. Parallel local search and the traveling salesman problem // Working paper, Philips research laboratories. — Eindhoven, 1995.

204. Vetta A. Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions // Proceedings of 43rd Annual IEEE symposiun on foundations of computer science. — Vancouver: Canada, 2002. — P. 416-425.

205. Weiner P., Savage S.L., Bagchi A. Neighborhood search algorithms for guaranteeing optimal traveling salesman tours must be inefficient //J. of Computer and System Sciences. — 1976. — V.12. — P.25-35.

206. Wilbaut C., Hanafi S., Freville A., Balev S. Tabu search: global intensification using dynamic programming. // Control and Cybernetics. 2006. - V. 35, N. 3. - P. 579-588.

207. Wolpert D. H., Macready W. G. No free lunch theorem for search // Techn. Rep. SFI-TR-95-02-010. Santa Fe Inst., 1995.

208. Vredeveld Т., Lenstra J.K. On local search for the generalized graph coloring problem // Oper. Res. Letters. — 2003. — V. 31. — P. 28-34.

209. Yagiura M., Ibaraki Т., Glover F. An ejection chain approach for the generalized assignment problem // INFORMS Journal on Computing. 2004, - V. 16, N. 2. - P. 133-151.

210. Yannakakis M. Computational complexity // Local search in combinatorial optimization. — Chichester: Wiley, 1997. — P. 19-55.