Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

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

Диссертация: Методы локального поиска для дискретных задач размещения
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

Содержание

  • 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.JI. Алгоритм неявного перебора для задачи типа размещения и стандартизации // Управляемые системы. / Сб. науч. тр. — Новосибирск: Ин-т математики СО АН СССР, 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. Е. Н. 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. 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. 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. 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. , A.M. (1974). Lagrangian Relaxation and its Uses in Integer Programming // Math. Prog. Study. — 1974. — V. 2. — P. 82−114.
  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. 215 228.
  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. 313 320.
  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 theincapacitated 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. 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. 291 307.
  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. 351 367.
  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. 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-Perez 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. Muhlenbein 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. 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. Schaffer 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., Schoning 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. J., Wirth H.C. (r- p)-Centroid problems on paths and trees. Tech. Report 441, — Inst. Comp. Science, University of Wurzburg, — 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. 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.
  201. Van Roy Т., Erlenkotter D. A dual-based procedure for dynamic facility location // Management Sci. 1982. — V. 28, N 10. — P. 1091−1105.
  202. Verhoeven M.G.A., Swinkels P.C.J., Aarts E.H.L. Parallel local search and the traveling salesman problem // Working paper, Philips research laboratories. — Eindhoven, 1995.
  203. 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.
  204. 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.
  205. 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.
  206. Wolpert D. H., Macready W. G. No free lunch theorem for search // Techn. Rep. SFI-TR-95−02−010. Santa Fe Inst., 1995.
  207. Vredeveld Т., Lenstra J.K. On local search for the generalized graph coloring problem // Oper. Res. Letters. — 2003. — V. 31. — P. 28−34.
  208. 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.
  209. Yannakakis M. Computational complexity // Local search in combinatorial optimization. — Chichester: Wiley, 1997. — P. 19−55.
Заполнить форму текущей работой

На отлично!