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

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

МЕТОДЫ ЛОКАЛЬНОГО ПОИСКА

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

Специальность 05.13.18 математическое

моделирование, численные методы

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

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

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

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

Официальные оппоненты: доктор физико-математических наук В. К. Попков доктор физико-математических наук А. В. Кельманов доктор технических наук В. И. Зоркальцев

Ведущая организация: Учреждение Российской академии наук Вычислительный центр им. А.А. Дородницина РАН

Защита состоится 19 января 2010 г. в 15 час. 00 мин.

на заседании диссертационного совета Д 003.061.02 при Институте вычислительной математики и математической геофизики Сибирского отделения РАН по адресу: 630090 г. Новосибирск, пр. Ак. Лаврентьева, 6.

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

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

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

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

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

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

Именно этому направлению численных методов решения дискретных задач размещения и посвящена настоящая работа.

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

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

Выбор данного направления исследований неслучаен. С одной стороны, методы локального поиска легко адаптируются к изменениям математической модели. Их простота и гибкость открывают широкий простор для решения практических задач. С другой стороны, многие принципиальные вопросы остаются открытыми, в частности, вопросы сходимости методов, оценки их погрешности, возможности получения точного решения задачи и доказательства его оптимальности. Многие методы данного класса сконцентрированы на поиске локальных оптимумов задачи, что порождает массу нетривиальных вопросов чисто математического плана, например, вопрос о вычислительной сложности нахождения локального оптимума. Для дискретных задач размещения, как впрочем и для других задач исследования операций, пока не удается подтвердить или опровергнуть гипотезу о существовании полиномиальных алгоритмов нахождения локальных оптимумов. Известно [15], что эти задачи не могут быть NP-трудными, если NP = co-NP, что дает надежду найти такие алгоритмы. Однако эта надежда весьма призрачна в силу плотной PLS-полноты таких задач локального поиска для многих "естественных" окрестностей малой мощности.

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

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

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

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

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

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

Такие задачи обладают тем свойством, что для любой полиномиально проверяемой окрестности N и любого правила выбора направления спуска стандартный алгоритм локального улучшения является полиномиальным. Для таких задач выделяют класс задач локального поиска, обладающих следующим свойством: для задачи L = (OP, N ) из класса PLS существует такая константа > 0, что каждый локальный оптимум имеет относительную погрешность не более. Класс этих задач называют классом GLO (Guaranteed Local Optima). Этот класс не пуст. В нем, например, содержится задача коммивояжера, у которой веса ребер принимают значения 1 или 2. Задача выполнимости на максимум, задача о максимальном разрезе с единичными весами также принадлежат этому классу [6]. Замыкание класса GLO (GLO) определяется с помощью сведения, сохраняющего аппроксимируемость (P T AS ).

Задача OP1 принадлежит замыканию класса GLO, если существует такая задача OP2 GLO, что OP1 P T AS OP2. Установлено [6], что GLO =APX. Таким образом, класс GLO дает новую характеризацию класса APX, одного из важнейших классов NP-трудных задач. Для любой задачи OP из класса APX найдется задача из класса GLO, к которой задача OP сводится с сохранением свойств аппроксимируемости. Другими словами, понятие локального оптимума является одним из важнейших в теории аппроксимации NP-трудных задач.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Объем диссертации 267 страниц.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Установлено, что новое сведение может давать лучшую нижнюю оценку (обозначенную в работе через LB6 ), чем предшествующие известные оценки. Лучшая из них обозначена через LB4, причем LB6 LB4.

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

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

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

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

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

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

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

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

Теорема 23. Задача о p-медиане с каждой из окрестностей Swap, LK, LK1, F M, F M1 является плотно PLS-полной.

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

Теорема 25. Для простейшей задачи размещения с окрестностью F lip и задачи о p-медиане с окрестностями Swap, LK, LK1, F M, F M1 соответствующие стандартные задачи локального поиска являются PSPACE-полными.

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

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

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

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

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

Оптимизационную задачу OP называют псевдо-полиномиально ограниченной, если существует такой полином p от переменных |x| и M ax(x) наибольшее по величине число из входа x, что для любого входа x и любого допустимого решения s выполняется неравенство где Opt(x) глобальный минимум для входа x. Множество таких оптимизационных задач обозначают N P OP P B.

Теорема 30. Пусть OP N P OP P B, (OP, N ) P LS и целевая функция принимает только целочисленные значения. Если P=NP и задача вычисления приближенного решения с гарантированной оценкой точности является N P -трудной в сильном смысле, то найдутся исходные данные, для которых существует локальный оптимум, отклоняющийся более чем в раз от оптимального значения.

Следствие 10. Если P=NP и задача OP N P OP P B является NP-трудной в сильном смысле, то для нее не существует точных полиномиально проверяемых окрестностей.

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

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

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

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

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

Теорема 33. Задача (M ax Cut, F lip) плотно PLS–сводится к задаче (F LG, N1 ).

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

В четвертом разделе исследуется сложность получения приближенных равновесных решений. Если игрок k меняет свою стратегию, он несет расходы в размере k. Игрок не будет менять свое решение, если приращение прибыли не превосходит данной величины. Если в такой ситуации ни один из игроков не может увеличить свою прибыль при условии, что другие игроки не меняют свой выбор, то такое решение называют приближенным равновесным решением с погрешностью = (1,..., p ), где p число игроков. Задача поиска приближенных равновесий кажется более простой, так как увеличивается число подходящих состояний.

Тем не менее это не всегда так. Если k являются постоянными величинами, то поиск приближенных равновесий снова оказывается плотно PLS-полной задачей. Если же для любых стратегий (i1,..., ip ) величины k могут быть оценены снизу функционалом µ(i1,..., ip ) суммарной прибыли игроков и экономии клиентов (социальное благо от размещения предприятий и выпуска продукции), то есть k µ(i1,..., ip ) для любого k = 1,..., p, то задача может быть решена с полиномиальной трудоемкостью.

и любых стратегий (i1,..., ip ), то приближенное равновесие с погрешностью = (1,..., p ) может быть найдено за полиномиальное время от длины записи исходных данных и величины 1/.

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

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

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

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

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

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

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

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

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

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

– три класса примеров с большим разрывом целочисленности (классы GapA, GapB, GapC);

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

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

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

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

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

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

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

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

Вып. 36. С. 225–246.

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

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

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

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

[6] Ausiello G., Protasi M. 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 T., 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 dicult 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 B., 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 pmedian problem // Journal of Heuristics. 2004. V. 10. P.

[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. Алексеева Е.В., Кочетов Ю.А. Генетический локальный поиск для задачи о p-медиане с предпочтениями клиентов // Дискретный анализ и исследование операций. Серия 2. 2007. Т 14, № 1. C. 3–31.

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

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

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

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

С. 13–30.

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

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

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

C. 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. Кочетов Ю.А., Пащенко М.Г., Плясунов А.В. О сложности локального поиска в задаче о p-медиане // Дискретный анализ и исследование операций. Серия 2. 2005. Т. 12, № 2. С. 44–71.

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

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

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

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

Т. 12, № 1. С. 12–36.

18. Alekseeva E., 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 T., 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. Kоchetov 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. Формат 60х84 1/16.

Усл. печ. л. 2,0. Уч.-изд. л. 2,0. Тираж 120 экз. Заказ № 114.

пр. Ак. Лаврентьева, 6, 630090 Новосибирск