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

00461360?

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

КЛИМЕНТОВА КСЕНИЯ БОРИСОВНА

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

Д-< ; ^

05.13.01 - Системный анализ, управление и обработка информации (в технике, экологии и экономике)

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

2 5 НОЯ

Иркутск - 2010

004613607

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

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

профессор

Стрекаловский Александр Сергеевич.

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

профессор

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

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

Семенов Александр Анатольевич.

Ведущая организация: Институт вычислительной

математики и математической геофизики СО РАН (г. Новосибирск).

Защита состоится 2 декабря 2010 г. в 14.00 ч. на заседании диссертационного совета Д 003.021.01 в ИДСТУ СО РАН по адресу: 664033, Иркутск, ул. Лермонтова, 134.

С диссертацией можно ознакомиться в библиотеке ИДС'ТУ СО РАН.

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

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

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

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

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

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

Исследованию задач размещения различных классов посвящено большое количество работ. В России такие задачи исследуются с 70-х годов XX века под руководством В.Т. Дементьева, В.Л. Береснева, Э.Х. Гимади1), A.A. Колоколова и др.

Насколько известно, впервые модель ЗРПК была предложена и исследована P. Hanjoul и D. Peeters2). Позже аналогичные задачи изучались, в том числе, в работах В.Т. Дементьева, В.Д. Береснева, Э.Х. Гимади, A.A. Колоколова, Ю.А. Кочетова, JI.E. Горбачевской.

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

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

2>Р. Hanjoul, D. Pceters. A facility location problem with clients' preference orderings // Regional Sei. Urban Econom. - 1087 . - V. 17. -' P. 451-473.

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

Для построения нижних оценок в ЗРПК могут быть использованы так называемые правильные неравенства, которые определяют полупространства, содержащие допустимую область задачи (см., например, работы Л.Е. Горбачевской, М. ЬаЬЬё с соавторами), а также формулировки задачи в пространстве переменных большей размерности — расширенные формулировки (работы Ю.А. Кочетова, Е.В. Алексеевой).

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

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

Предмет и объект исследования. Объектом исследования являются модели ЗРПК в целочисленной постановке.

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

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

Научная новизна результатов диссертации заключается в улучшении известных к настоящему времени нижних оценок оптимальных значений ЗРПК на основе исследования взаимосвязей этих задач с задачей упаков-

ки множества и с задачей о паре матриц.

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

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

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

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

Исследования по теме диссертации проводились в рамках проектов по программам СО РАН: "Поиск глобальных решений в невыпуклых задачах исследования операций и оптимального управления" (№ гос. регистрации 01.2.007 08581) с 2007 по 2009 гг., программа СО РАН "Математическая теория управления при возмущениях и неопределенности"; "Нелокальные методы в теории управления динамическими системами" (Л'8 гос. регистрации 01201001345) в 2010 г., программа "Теория управления динамическими системами и методы их исследования" а также в рамках комплексного интеграционного проекта СО РАН 1.3 "Исследование задач двухуровневого и равновесного программирования" (2006-2008 гг.); проекта фонда "Научный потенциал" №153 "Задачи комбинаторной оптимизации в мето-

дах кластерного анализа и классификации данных" (2007-2008 гг.).

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

Апробация работы. Результаты диссертации докладывались и обсуждались на Всероссийской конференции "Дискретная оптимизация и исследование операций" (7 - 14 сентября 2007 г., Владивосток), XIV Байкальской школе-семинаре "Методы оптимизации и их приложения" (2 -8 июля 2008 г., Иркутск, Байкал), конференции "Ляпуновские чтения и презентация информационных технологий" (19 - 23 декабря 2008 г., Иркутск), Школе-семинаре молодых ученых "Информационные технологии и моделирование социальных эколого-экономических систем" (1-6 октября 2008 г., Иркутск (Россия) - Ханх (Монголия)), X и XI Всероссийски х конференциях молодых ученых по математическому моделированию и информационным технологиям (8-11 июня 2009 г., Иркутск (Россия) - Ханх (Монголия); 15 - 21 марта, 2010 г., Иркутск - Байкал), IV Всероссийской конференции "Проблемы оптимизации и экономические приложения" (29 июня - 4 июля 2009 г., Омск), XL Annual Conference Italian Operational Research Society (AIRO 2009) (September 8 - 12, 2009, Siena (Italy)), Российской конференции "Дискретная оптимизация и исследование операций" (27 июня - 3 июля 2010 г., республика Алтай).

Результаты диссертации обсуждались на научных семинарах в Институте вычислительной математики и математической геофизики СО РАН (руководитель д.ф.-м.н., проф. В.К. Попков), Институте математики им. С.Л. Соболева СО РАН (руководитель д.ф.-м.н., проф. В.Т. Дементьев) и Омском филиале Института математики им. С. Л. Соболева СО РАН (руководитель д.ф.-м.н., проф. A.A. Колоколов), а также на Инженерном факультете Университета Саннио, г. Беневенто (Италия), на семинаре в Университете г. Сиена (Италия) и неоднократно на семинарах Института динамики систем и теории управления СО РАН.

Публикации и личный вклад автора. По материалам диссертации опубликовано 12 работ, в том числе статьи [1-3] в журналах, рекомендованных ВАК РФ.

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

Разработка и реализация нового метода ветвей и отсечений, предложенного в диссертации, осуществлялись автором лично. Из совместных публикаций с Ю.А. Кочетовым, A.B. Плясуновым, Е.В, Алексеевой на защиту выносятся только результаты, полученные автором лично.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы, включающего 177 наименований. Общий объем диссертации составляет 124 страницы, из которых 107 страниц основного текста, включающего 3 рисунка и 11 таблиц. Результаты главы 2 опубликованы в работах [1,2,5,7]. Результаты главы 3 опубликованы в работах [1,3,4,6-12].

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

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

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

В §1.1 приводятся постановки задач размещения с предпочтениями клиентов. Пусть задано множество мест для возможного размещения предприятий I = {1,..., то} и множество клиентов J = {1,..., п}. Для каждого места задана стоимость размещения предприятия fc > 0, г G /, а также известны затраты на обслуживание клиентов С = {су}, где Cij > 0 — стоимость обслуживания j'-ro клиента предприятием, размещенным на г-ом месте, г е /, j € J. Кроме того, определены предпочтения клиентов в виде матрицы G = {ду}, i е I,j € J. Если gHi < gid, iui2 е I,j £ J, то j-й клиент из открытых предприятий ii или ¿2 выберет предприятие ¿1. Требуется разместить некоторое подмножество предприятий на местах

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

и = о V» 6 /.

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

В §1.4 приведены различные постановки ЗРПК в виде моделей ЦЛП. Для этого вводятся следующие переменные: г/,; = 1, если предприятие открывается на г-ом месте, в противном случае гц = 0, г € /; хц = 1, если ¿-й клиент обслуживается из предприятия на г-ом месте, хц = О в противном случае, г 6 Щ £ 3. С использованием этих переменных ЗРПК может быть записана в виде задачи двухуровневого целочисленного программирования

+ [ min, (1)

¿6/ Ш У

-и б {0,1 },iel, (2)

где х(у) - оптимальное решение задачи клиентов:

Y^ 9i]Ki] l min, (3)

iel jeJ

X>y = l, (4)

iel

хц < Vi, (5)

®ц€{0,1}, г ei, j e J. (6)

Известно, что исследуемые ЗРПК в условиях единственности оптимального выбора клиентов на нижнем уровне могут быть редуцированы к равносильной одноуровневой задаче ЦЛП путем введения дополнительных ограничений (8):

EEw + V/iW 1 min, (7)

11 ■■ ■ l j у

iel jzJ iel

Vi + xkj ^ * e IJ e Ji

(8)

keWij

^хц = l, jeJ,

(9)

0 < <yi<i, iel,jeJ, xiji Hi € {0, l}, iel,jeJ,

(10) (ii)

где И^- — множество предприятий, которые менее предпочтительны для клиента чем предприятие г: = € / | д^ > д^}.

Будем обозначать задачу (7)—(11) через (V), а многогранник данной задачи (т.е. выпуклую оболочку точек, удовлетворяющих ограничениям (8)—(11)) — через Р. Можно показать, что решение {х*,у*) задачи (V) представляет собой оптимальное решение ЗРПК.

Замечание. Отметим, что задачу о р-медиане с предпочтениями клиентов можно сформулировать в виде аналогичной модели двухуровневого целочисленного программирования. Одноуровневая постановка такой задачи будет отличаться от задачи (V) дополнительным ограничением ' у% — р при условии /. = 0 Vг £ I, где р € 2+ — параметр, определя-

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

В заключительном §1.5 первой главы представлены теоретические основы метода отсечений, метода ветвей и границ, а также метода ветвей и

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

В §2.1 представлены известные из литературы результаты, касающиеся получения нижних оценок оптимальных значений ЗРПК. Будем обозначать через LBi нижнюю оценку, которая является оптимальным значе-. нием линейной (непрерывной) релаксации (7)-(10) задачи ЦЛП (V), т.е. когда ограничение (11) не принимается в расчет.

Первая группа результатов связана с известными семействами правиль-

3'G.N. Nemhauser, L.A. Wolsey. Integer and Combinational Optimization. — New York: A Wiley-Interscience Publication, 1999.

отсечении'

ных неравенств для многогранников Р и Рт4''5'. Лучшая из известных нижняя оценка оптимального значения для данной группы результатов получена с помощью следующих правильных неравенств5'. Для каждого подмножества ji,...,js G J и г G I введем обозначения U(i,jt) ={к G

<7=1

s

+1С 11 Xk*+- ^ e J>¿ e 7' (12)

fceWi^ t=2 keu(ijt)

•Ciu ÍÍ

u,v e J,i & I, Biv с Biu, (13)

xiu = xiv% u, v e J,i & I, Biu - Biy, (13')

где Bij =={k € I : gkj < 9ij} — это множество предприятий, которые более предпочтительны для клиента j, чем предприятие i. Будем далее обозначать через LB$ нижнюю оценку оптимального значения ЗРПК, которую определяет оптимальное значение непрерывной задачи линейного программирования (7), (9), (10), (13), (13') со всеми неравенствами (12), а через LB2 — оптимальное значение в задаче (7), (9), (10), (13), (13') с подмножеством неравенств (12). Известно, что представленные оценки связаны следующей цепочкой неравенств: LBi < ЬВ2 < LB35'.

Вторая группа известных результатов, связанных с нижними оценками оптимального значения ЗРПК, основана на расширенной постановке задачи в пространстве переменных более высокой размерности. При этом непрерывная релаксация расширенной формулировки определяет нижнюю оценку оптимального значения исходной задачи. Расширенные постановки ЗРПК представляют собой модели ЦЛП для известной комбинаторной формулировки в виде задачи о паре матриц6'. Будем обозначать нижнюю оценку, получаемую с помощью такой расширенной формулировки, через LBi. Известно, что LB4 > LB\.

В §2.2 исследуются свойства многогранников ЗРПК. Чаще всего при анализе задач размещения, например, простейшей задачи размещения или задачи о р-медиане, исследуют многогранник, в котором ограничения xij = Ijj £ J заменяются на неравенства J2x>j — 1>J S J. В Ш iel

■''Л-Е. Горбачевская. Полиномиально разрешимые и IVP-трудные двухуровневые задачи стандартизации: дис.... канд. физ.-мат.наук. Новосибирск, 1998.

Cánofvas, S. Garcia, M. Labbé, A. Marin. A strengthened formulation for the simple plant location problem with older // Operations Research Letters. - 2007. - V. 35, N 2. — P. 141-150.

C'E.B. Алексеева, Ю.А. Кочетов. Генетический локальный поиск для задачи о р-медиане с предпочтениями клиентов // Дискр. анализ и исследование операций. — 2007. — Т. 14, Л"' 1. — С. 3-31.

случае задачи о р-медиане помимо этого на № Р заменяются и огра-

¿е/

ничения = р. Известно, что путем преобразования коэффициентов

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

Обозначим ЗРПК с неравенствами через (Р-), а ее многогранник через Р- (соответственно (Р^) и для задачи о р-медиане с предпочтениями клиентов).

Предложение 1. Многогранник Р- является полноразмерным: сИт(Р-) = т + тп.

Далее приводятся предложения о некоторых фасетных неравенствах для многогранников ЗРПК. Неравенство называется фасетным, если размерность его грани (т.е. пересечения гиперплоскости, соответствующей этому неравенству, с многогранником) на единицу меньше размерности многогранника.

Предложение 2. Неравенства х^ < 0, г £ I, ] £ ,/ и хг] < г £ /, 1 6 J являются фасетными дм многогранника Р-.

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

Теорема 1. Если Ву = 0 для некоторых г 6 ^ € J, то неравенства у-1 + ^ хщ < 1, г £ I, ^ £ 3, являются фасетными для многогранника

кт^

Р*.

Аналогичные утверждения справедливы и для многогранника Р^.

В §2.3 на основе анализа расширенной формулировки задачи о паре матриц и известных результатов о ее взаимосвязи с задачами (V) и (Рт)6) построено новое семейство правильных неравенств для многогранников Р

и Рт -

Для каждого j ё J рассмотрим перестановку р{]) = (¿1,... ,гт), упорядочивающую по возрастанию элементы столбца ] € J матрицы С:

Ли - 9Ы < < 9гтЬ 3 е Введем величины А^ =тт{0; - си,}, I = \,...,тп—\,з 6 </. Множества индексов, соответствующих отрицательным Д?, обозначим через ={/ € {1,..., ш — 1} | Д/ < 0}, у € J.

Теорема 2. Неравенства

+ X] х™ - и^и, (14)

являются правильными для многогранников Р и Рт задач {V) и СРт) соответственно.

Обозначим через ЬВ$ значение линейной (непрерывной) релаксации для новой постановки (7)-(11) с неравенствами (14). Следующий результат является весьма важным как с теоретической точки зрения, так и для построения эффективных методов решения ЗРПК.

Следствие 1. ЬВ4 < ЬВ5.

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

Предложение 3. Неравенства (Ц) определяют грани многогранника Р (Р±).

С формальной точки зрения это предложение означает, что Р(1,и,у)={(х,у) е Р ((х,у) е Р*) | Е + Е = 1} Ф 0 Для

всех / € Ьи, и, V е «/, и фи.

Как правило, доказать, что построенные правильные неравенства являются фасетными для многогранника исследуемой задачи, не всегда удается. Показано, что предложенные правильные неравенства (14) в общем случае не являются фасетными. Рассмотрен пример ЗРПК небольшой размерности, для которого все грани неравенств (14) имеют размерность меньшую, чем размерность многогранника без единицы. Несмотря на то, что новые неравенства в общем случае не являются фасетными, они оказываются весьма эффективными для численного решения задачи.

В §2.4 на основе взаимосвязей ЗРПК с задачей упаковки множества исследована задача упаковки множества специального вида, такая, что ее допустимое множество включает в себя допустимое множество ЗРПК. Обозначим многогранник этой специальной задачи через Р$з- По построению справедливы включения

РтСР33. (15)

Другими словами, задача упаковки множества с многогранником Pss является специальной релаксацией для задач размещения с предпочтениями клиентов. Этот факт позволяет использовать известные результаты о правильных неравенствах многогранника задачи упаковки множества для построения новых нижних оценок оптимального значения ЗРПК. Действительно, в силу включения (15) любые правильные неравенства для многогранника Pss будут также правильным для Р и Рт. В частности, в диссертационной работе предлагается рассмотреть правильные неравенства клик, которые конструируются для многогранника P$s в соответствии с известными результатами о взаимосвязи задачи упаковки множества с задачей поиска независимого множества3'.

При этом удалось доказать следующую теорему, устанавливающую взаимосвязь неравенств, предложенных в работе М. Labbe и др.5', и неравенств клик.

Теорема 3. Для каждого из неравенств (12)

S

+¿С Y1 Хкл+Vi --71' • ■ • € J' t=2 t-1 J1 *ewijtn(nsy,)

q=1

существует определяющая его клика в графе, порожденном специальной релаксацией ЗРПК. Иными словами, неравенства (12) являются подмножеством неравенств клик.

Рассмотрим новую постановку ЗРПК с целевой функцией (7). Неравенства клик, сконструированные для многогранника Pss, добавим к ограничениям (9) (11), (13), (13'). Аналогичная формулировка использована и для анализа задачи о р-медиане с предпочтениями клиентов. Обозначим через LBq нижнюю оценку, получаемую при решении линейной релаксации такой задачи ЦЛП.

Следствие 2. ЬВц > LR3.

Суммируя результаты, касающиеся соотношений между различными нижними оценками оптимального значения ЗРПК, получаем следующую схему:

< ьв\ | ьв\ <> LB*>

которая представляется новой и весьма важной, например, при использовании метода ветвей и отсечений для решения ЗРПК.

Таким образом, благодаря использованию нового семейства неравенств (14), а также неравенств клик, удалось обобщить известные из

литературы результаты, касающиеся нижних оценок оптимального значения ЗРПК.

В заключение главы в §2.5 разработаны различные схемы метода отсечений для нового семейства правильных неравенств (14):

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

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

3) схема, где на итерациях метода отсечений добавляется не более М невыполненных неравенств, косинус угла между гиперплоскостями которых не превышает некоторого порогового значения т].

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

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

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

Первая группа — тестовые примеры задач о р-медиане с предпочтениями клиентов из библиотеки "Дискретные задачи размещения"7'. В библиотеке представлено 29 примеров в которых т = 100, п = 100, р = 14, общее число переменных 1100.

Тестовые задачи второй группы представляют собой примеры простейшей задачи размещения с предпочтениями клиентов5'. Данная группа задач делится на 3 блока, по 12 примеров в каждом: в первом блоке то = 50, п — 50, общее число переменных 2550; во втором блоке то = 50, п = 75, число переменных 3800; в третьем блоке т — 75, п = 100, число переменных 7575.

В §3.2 представлены результаты численного сравнения новых и известных нижних оценок.

Для всех тестовых задач удалось улучшить известные оценки LB\ и LB-i,- При этом для первой группы задач оказалось достаточно использо-

Гончаров, Д.А. Иваненко, Ю.А. Кочетов, H.A. Кочетова. Библиотека "Дискретные задачи размещения". URL: http://math.nsc.ru/AP/benchmarks/.

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

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

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

Для тестовых примеров первой группы из библиотеки "Дискретные задачи размещения" использовались верхние оценки, полученные с помощью генетического алгоритма, предложенного в упоминавшейся выше работе Е.В. Алексеевой, Ю.А. Кочетова6^. Для второй группы тестовых примеров в диссертации была реализована стандартная схема известного метода имитации отжига8). В результате проведения вычислительного эксперимента с помощью этого метода были получены хорошие верхние оценки оптимальных значений для этой группы тестовых задач.

В §3.4 представлены результаты поиска оптимальных решений в упомянутых тестовых примерах. Применение метода ветвей и отсечений для поиска оптимальных решений в ЗРПК осуществлялось посредством известного пакета Xpress9\ в котором реализована "стандартная" схема метода ветвей и границ. Этот пакет представляет собой библиотеку вызываемых' функций. Была разработана программа на языке С-Ь-Ь, осуществляющая вызов функций пакета, которые выполняют поиск оптимального решения рассматриваемой задачи с помощью метода ветвей и границ. При этом для поиска нижних оценок на шагах этого метода использовался разработанный автором модуль, реализующий метод отсечений для нового семейства неравенств, т.е. применялась схема метода ветвей и отсечений.

Вычислительный эксперимент для первой группы задач подтвердил эффективность реализованного метода ветвей и отсечений. По сравнению с результатами работы М. Labbe5' время решения 14 из 29 рассмотренных

s'S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi. Optimization by simulated annealing // Science. — 1983. —

V. 220(4598). - P. 671-680.

9'Fak Isaac Corporation: Xpvess Optimization Suite. URL: vvww.fico.com/

примеров удалось уменьшить в среднем на 12%. Для задач второй группы наиболее существенного уменьшения времени решения с использованием разработанного метода ветвей и отсечений по сравнению с результатами М. ЬаЬЬё5) удалось получить для второго и третьего блоков задач — на 30 и 37 % соответственно.

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

Разработанная методика решения ЗРПК была применена к решению прикладной задачи кластерного анализа.

В §3.5 обсуждаются общие постановки задач кластерного анализа и их взаимосвязи с задачами размещения. Отметим, что задачи кластерного анализа имеют широкий спектр приложений в технике, экономике, экологии, медицине и других областях. Пусть имеется некоторое множество V = {1,... ,п} объектов, которое нужно разбить на непересекающиеся подмножества, называемые кластерами. Каждый объект г € V описан некоторыми характеристиками, которые чаще всего представляются в виде вектора Vх £ Ш. " Сходные" с точки зрения некоторого критерия объекты должны оказаться в одинаковых кластерах, а "различные" — в разных. Для оценки схожести объектов часто используются нормы или выборочный коэффициент корреляции.

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

В некоторых прикладных задачах кластерного анализа каждый объект г Е V описан не одним, а двумя векторами разнородных характеристик V* £ и;1 £ Ш!9, г £ V, которые необходимо учитывать одновременно при разбиении на кластеры. Для таких задач кластерного анализа в диссертациониой работе предлагается следующий подход. Выбор медиан осуществлять, минимизируя несхожесть согласно одной характеристике, а остальные объекты прикреплять к наиболее сходным согласно второй характеристике медианам.

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

р-мсдиане с предпочтениями клиентов. В этом случае величины dy(u) и dij(ui), которые обозначают степени схожести между объектами г и j, вычисленные с использованием векторов первой и второй характеристик соответственно, используются в целевых функциях верхнего и нижнего уровня (1) и (3).

В §3.6 приведена постановка задачи кластерного анализа раковых клеток и описано применение разработанного в диссертации метода ветвей и отсечений для ее решения. Эта задача кластерного анализа является примером задачи с двумя векторами характеристик10^.

Первую характеристику v1 G i € V, описывающую раковые клетки, называют вектором действия медикаментов — это значения изменения уровня белка в клетке после 48 часов действия на нее одним из медикаментов.

Второй вектор wl € WLq, i € V характеризует раковые клетки с точки зрения так называемой экспрессии генов (gene expression), которая представляет собой значение уровня белка в некотором гене клетки i £ I.

В диссертационной работе рассмотрен пример задачи кластерного анализа раковых клеток, предложенный Национальным институтом рака США (National Cancer Institute, USA), и опубликованный в сети интернет. Этот пример представляет собой результат исследования экспертами п — 60 раковых клеток из L = 9 различных видов рака.

Нетривиальным вопросом в кластерном анализе является вопрос оценки качества полученных кластеров. Для этих целей в рассматриваемой задаче кластерного анализа раковых клеток используются средний коэффициент корреляции, энтропия и так называемая F-мера.

Проведенные расчеты свидетельствуют о конкурентоспособности предложенного в диссертации подхода по сравнению с другими известными подходами11)'12).

В заключении сформулированы основные результаты диссертационной работы.

1D'U. Scherf, D. T. Ross et al. A Gene Expression Database for the Molecular Pharmacology of Cancer. URL-.hUp://discover.nci.nih.gov/nature2000/natureintromain.jsp

11 ^E. Fersini, I. Giordani, E. Messina, F. Archctti. Relational clustering and Bayesiaii networks for linking gene expression profiles and drug activity patterns / // Bioinformaties and Biomedicine Workshop 2009 (BIBMW 2009) (November 1-4 2009). - 2009. - P. 20-25.

12'B.T. Zhang, J.H. Cliatig, K.B. Hwang. Analysis of gene expression profiles and drug activity patterns by clustering and bayesian network learning. In Methods of Microarray Data Analysis II, chapter 11. (Edito by Lin S.M., Jhonson K.F.) Iiluwer Academic Publishers, 2002.

РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ

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

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

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

СПИСОК ОСНОВНЫХ ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Васильев И.Л., Климентова К.Б. Метод ветвей и отсечений для задачи размещения с предпочтениями клиентов // Дискретный анализ и исследование операций. 2009. Т. 16. № 2. С. 21-41.

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

3. Климентова К.Б. Приложение задачи о ^медиане с предпочтениями клиентов для кластерного анализа клеток рака // Современные технологии. Системный анализ. Моделирование. 2009. № 3(23). С. 33-38.

4. Алексеева Е.В., Васильев И.Л., Климентова К.Б., Кочетов Ю.А. Точные и эвристические методы решения задачи о р-медиане с предпочтениями клиентов // Материалы Российской конференции "Дискретная оптимизация и исследование операций" (Владивосток, 7-14 сентября 2007 г.). Новосибирск: Изд-во Института математики, 2007. С. 118.

5. Васильев И.Л., Климентова К.Б., Плясунов A.B. Метод отсечений для двухуровневой задачи размещения // Труды XIV Байкальской

школы-семинара "Методы оптимизации и их приложения" (2-8 июля 2008 г., Иркутск, Байкал) Т.1. Иркутск: ИСЭМ СО РАН, 2008. С. 577-585.

6. Васильев И.Л., Климентова К.Б. Классификация данных и двухуровневая задача о р-медиане // Материалы школы-семинара молодых ученых "Информационные технологии и моделирование социальных эколого-экономических систем"' (1-6 октября 2008 г., Иркутск(Россия) -Ханх(Монголия)). С. 11-14.

7. Васильев И.Л., Климентова К.Б. Метод ветвей и отсечений для двухуровневой задачи размещения // Материалы конференции "Ляпуновекис чтения и презентация информационных технологий" (19-23 декабря 2008 г., Иркутск). С. 11.

8. Климентова К.Б. Кластерный анализ клеток рака и задача о р-медиаие с предпочтениями клиентов // Материалы X Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (8-11 июня 2009 г., Иркутск (Россия) — Ханх (Монголия)). С. 23.

9. Васильев И.Л., Климентова К.Б. Численный поиск оптимального решения задачи размещения с предпочтениями клиентов // Материалы IV Всероссийской конференции "Проблемы оптимизации и экономические приложения"(29 июня-4 июля 2009 г., Омск). С. 116.

10. Vasilycv I., Klimentova X., Salerno S. Clustering Analysis of Gene Expression Profiles and Drug Activity Patterns by p-Median Problem with Order // Abstracts book of XL Annual Conference Italian Operational Research Society "Decision and optimization models for evaluation and management "(AIRO 09) (September 8-11, 2009, Siena, Italy), P. 190.

11. Васильев И.Л., Климентова К.Б. Метод имитации отжига для задачи размещения с предпочтениями клиентов // Материалы XI Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (15-21 марта 2010 г., Иркутск-Байкал). С. 17.

12. Васильев И.Л., Климентова К.Б. Задача о р-медиане с предпочтениями клиентов для кластеризации раковых клеток // Материалы Российской конференции "Дискретная оптимизация и исследование операций". Новосибирск: Изд-во Ин-та математики, 2010. С. 157.

• Редакционноиздательский отдел Учреждения Российской академии наук Института динамики систем и теории управления СО РАН 664033, Иркутск, ул. Лермонтова, д. 134

Подписано к печати 28.10.2010 Формат бумаги 60x84 1/16, объем 1,0 п.л. Заказ 14. Тираж 120 экз.

Отпечатано в ИДСТУ СО РАН

Введение

Глава 1 Задачи размещения с предпочтениями клиентов и методы целочисленного программирования

1.1 Постановка задачи.

1.2 Различные понятия решения.

1.3 Взаимосвязь с задачей о паре матриц.

1.4 Целочисленные формулировки задачи.

1.5 Методы целочисленного программирования.

1.5.1 Основные определения и понятия.

1.5.2 Метод отсечений.

1.5.3 Метод ветвей и границ.

1.5.4 Эвристические методы.

1.5.5 Метод ветвей и отсечений

1.6 Заключительные замечания.

Глава 2 Нижние оценки и метод отсечений для задач размещения с предпочтениями клиентов

2.1 Известные нижние оценки.

2.1.1 Известные правильные неравенства.

2.1.2 Редукция к задаче о паре матриц.

2.2 Свойства многогранника задачи размещения с предпочтениями клиентов

2.3 Новые правильные неравенства.

2.4 Взаимосвязь с задачей упаковки множества.

2.4.1 Задача упаковки множества.

2.4.2 Неравенства клик для задач размещения с предпочтениями клиентов

2.5 Метод отсечений для нового семейства правильных неравенств.

2.6 Заключительные замечания.

Глава 3 Численная реализация метода ветвей и отсечений для задач размещения с предпочтениями клиентов

3.1 Тестовые задачи.

3.2 Численное сравнение нижних оценок.

3.3 Верхние оценки и метод имитации отжига.

3.4 Поиск оптимального решения задачи.

3.5 Задача кластерного анализа.

3.6 Кластеризация раковых клеток.

3.7 Заключительные замечания.

Задачи размещения известны достаточно давно благодаря широкому спектру практических приложений. Еще в XVII веке П.Ферма (1601-1665) рассматривал вариант задачи размещения, где на евклидовой плоскости имеется некоторый набор точек, и требуется разместить еще одну точку (называемую медианой) так, чтобы сумма расстояний от нее до всех точек из набора была минимальной. Им исследовался простейший случай, когда набор состоит из трех точек. Первое решение такой задачи было получено учеником Галилея Е. Торричелли (1608-1647). Ее изучением занимался также итальянский математик Б. Ковальери (1598-1647).

Немецкий экономист и социолог, основоположник экономической теории размещения промышленности А. Вебер (1868-1958) в своей работе 1909 года ([174], рус. перевод [18]) исследовал влияние основных факторов производства на размещение предприятий с целью минимизации издержек. С математической точки зрения задача Вебера заключается в поиске центра тяжести для взвешенных точек, т.е. представляет собой обобщение задачи, исследовавшейся Ферма. В [174] Вебером рассмотрен пример практической задачи с тремя предприятиями.

В середине XX века новый импульс исследованиям задач размещения придало развитие целочисленного программирования (ЦП) и возникновение вычислительной техники. В настоящее время большое количество практических задач такого типа моделируется и решается посредством теории и методов ЦП [129, 145, 152, 175]. При этом развитие математического аппарата ЦП и в целом математического программирования позволяет изучать более сложные модели технических и социально-экономических систем, в том числе с точки зрения их численного решения.

В частности, большой интерес специалистов в последнее время вызывают системы, обладающие иерархической структурой [20, 26, 50, 51]. При их исследовании принимается во внимание необходимость учета несовпадения интересов элементов рассматриваемой системы, наличия неопределенных факторов и различной степени информированности о них органов управления уровней иерархии. Простейший пример двухуровневой иерархической системы состоит из одного элемента верхнего уровня, называемого центром управления и М элементов нижнего уровня (подсистем) не связанных между собой. Однако исследование иерархических задач даже с такой, казалось бы, простейшей структурой сопряжено с большими теоретическими и вычислительными трудностями [20, 26, 50, 51, 73, 101, 171]. Подобного сорта задачи с двухуровневой структурой часто формулируются в виде задач двухуровневого программирования, основы которого представлены, например, в работах зарубежных авторов [73, 101, 171]. В СССР и России иерархические структуры изучались H.H. Моисеевым, Ю.Б. Гермейером, В.А. Гореликом, А.Ф. Кононенко, Н.С. Кукушкиным, Ф.И. Ерешко и др. [20, 26].

Сложность в задачах двухуровневого программирования возникает уже на этапе определения понятия решения. Специалисты вводят понятия оптимистического и пессимистического решения [101], когда интересы нижнего уровня могут быть согласованы с действиями верхнего уровня или наоборот, нижний уровень действует наихудшим для верхнего уровня образом. Пессимистическое решение также называют гарантированным [20], имея ввиду другую трактовку поведения игроков. Кроме того, иногда используются термины кооперативная и антикооперативная постановки двухуровневой задачи [1, 3, 44, 45].

Наряду с различными двухуровневыми непрерывными и дискретными задачами, большое количество работ посвящено исследованиям и двухуровневых задач размещения [3, 30, 44, 45, 83].

Приведем постановки некоторых классов задач размещения. Общим элементом в таких задачах являются два заданных множества — множество мест для размещения предприятий (пунктов обслуживания) / = {1,., т] и множество клиентов J = {1,. ,п}. Кроме того, для каждого места задана стоимость открытия на нем предприятия /,• > 0, г G I, а также для каждой пары i £ I,j Е J известны затраты су > 0 на обслуживание j-vo клиента предприятием, размещенным на г-ом месте. В постановке так называемой простейшей задачи размещения требуется открыть некоторое подмножество предприятий S С I и обслужить из них всех клиентов с минимальными суммарными затратами [5, 6, 62, 97, 103, 105, 129, 145, 152, 175].

Комбинаторная формулировка простейшей задачи размещения может быть записана следующим образом: s °ij + ^ msin' S - L j€J íes

Задачу в такой постановке принято изображать на двудольном графе (см. рис. 1) [97, 145, 152]. Вершины графа — множество пунктов обслуживания I и множество клиентов J — соединены дугами с весами сц. Кроме того, каждая вершина i £ I имеет вес /¿. На рис. 1 представлен пример задачи размещения, в которой имеется 4 места для размещения пунктов обслуживания и 5 клиентов. Здесь открыты 2 пункта обслуживания — на втором и четвертом месте, при этом клиенты 1 и 3 обслуживаются из пункта 2, а клиенты 2, 4, 5 — из пункта 4.

I J

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

Иногда задачи размещения формулируются так, что множества клиентов и мест для размещения пунктов обслуживания совпадают (I — </) [97, 103, 129, 145, 152]. Другими словами, предполагается, что пункты обслуживания могут размещаться только у клиентов. В этом случае решение задачи имеет структуру так называемых "звезд", в центрах которых располагаются открытые предприятия (см. рис. 2).

Другая постановка, которую также можно считать базовой моделью размещения, носит называние задачи о />мсдиане. В классической постановке этой задачи предполагается, что цены на открытие предприятий не заданы (/* = 0 Уг € /), однако определено целое положительное число р, задающее максимальное количество пунк

VJ 4 7

Рис. 2: Простейшая задача размещения при / = J. тов обслуживания, которое может быть открыто [68, 69, 96, 103, 129, 145]. Открытые пункты в такой модели принято называть медианами. Комбинаторная постановка задачи о р-медиане записывается следующим образом:

У^ min Cjj | min, SQI, |S| < р. jeJ ге

В простейшей задаче размещения и задаче о р-медиане предполагается, что любой пункт может обслужить неограниченное количество клиентов. Однако на практике такое возможно крайне редко. Поэтому требуется уточнение рассмотренных моделей задач размещения. Пусть пункт обслуживания, расположенный па месте г € I может произвести не более щ единиц продукции, а каждый клиент j Е J имеет спрос dj. Очевидно, что суммарный спрос клиентов, обслуживаемых из каждого пункта, не должен превышать производственной мощности этого пункта. Задача размещения, в которой учитывается вышеперечисленная информация, называется задачей размещения с ограничениями на мощность производства [6, 103, 129, 145, 152].

Известны постановки задач размещения, пункты обслуживания в которых могут иметь более сложную структуру, чем простои набор вершин графа. Примерами таких моделей являются задача поиска медианного пути, где эти пункты представляют собой путь на графе [67, 138], и задача поиска медианного цикла, где пункты образуют цикл [138, 139]. Также исследуются различные постановки задач размещения взаимосвязанных объектов: задачи на сетях и дискретных множествах [32]. Кроме того, интерес специалистов вызывают динамические постановки задач размещения, которые рассматривались в работах [6, 61, 62]. В работе [4] представлены в том числе многопродуктовые" формулировки.

В диссертационной работе исследуется одно из простейших двухуровневых обобщений базовых моделей задач размещения — так называемые задачи размещения с 71редпочтеииями клиентов (ЗРПК) [1, 3, 6, 24, 25, 83|. В них предполагается, что прикрепление клиентов к открытым предприятиям осуществляется не поставщиком (по матрице Ci3, г € I,j G J), как это происходит в базовым моделях размещения, а исходя из некоторых предпочтений клиентов. Эти предпочтения обычно представлены в виде матрицы G размерности (т х п). Если gll0 < gi2], гг, г2 S I,j € J то j-й клиент из открытых предприятий i\ или г2 выберет предприятие Комбинаторная постановка простейшей задачи размещения с предпочтениями клиентов может быть записана следующим образом: i mjn. S С I, (1) jeJ гes s(j) € I(j, S) = Argmin gh, j € J. (2) kes

Аналогично можно записать и задачу о р-медиане с предпочтениями клиентов.

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

Актуальность темы. Исследование задач размещения различных классов является актуальной математической проблемой. В СССР первые модели размещения исследовались В.П. Чечериным и В.Р. Хачатуровым. Изучению задач такого класса посвящены работы B.J1. Берсснева, Э.Х. Гимади, В.Т. Дементьева, A.A. Колоколо-ва, Ю.А. Кочетова, A.B. Плясунова, JI.E. Горбачевской и др. В частности, задачи размещения вызывают интерес с точки зрения теории сложности [29] задач целочисленного программирования. В ряде работ [21, 39, 46] исследуются полиномиально разрешимые случаи и семейства труднорешаемых задач такого типа. Тем не менее известно, что в общем случае базовые модели размещения — простейшая задача размещения и задача о р-медиане — и их обобщения являются ЛГР-трудными [46, 127], и разработка эффективных численных методов их решения является актуальной задачей современной теории методов оптимизации.

Кроме того, задачи размещения имеют широкий спектр практических приложений, в том числе в технике, в экологии и экономике. Простейшая задача размещения, задача о р-медиане, задачи размещения с ограничениями на мощность производства [62, 152] сами по себе имеют практические экономические постановки и могут быть использованы при решении различных экономических задач проектирования сетей обслуживания: размещении предприятий, филиалов фирмы или банка, нефтяных и газовых месторождений [30, 62, 96, 97]. Приложения этих моделей к задачам стандартизации и унификации исследовались, например, в работах [6, 25].

Практическое приложение задачи о р-медиане к задачам, возникающим в автомобильной промышленности, рассматривалось в работах [7, 82]. Рассмотрим для примера подробную формулировку этой прикладной задачи. Каждый легковой автомобиль может комплектоваться различным набором опций. Такой набор называют конфигурацией. Покупатель по своему желанию может дополнительно к базовой комплектации выбрать установку подушек безопасности, системы ABS, кондиционера и т. д. В соответствии с набором опций должен быть установлен определенный набор электропроводки, гарантирующий подключение указанных дополнительных устройств. В современном автомобиле число опций может достигать 30-50, а число их комбинаций может превышать несколько десятков тысяч. В силу технологических особенностей каждый набор электропроводки изготавливается как единое целое, и только ограниченное количество этих наборов может быть доступно на сборочном конвейере. Если необходимая конфигурация электропроводки недоступна, то она должна быть замещена совместимой. Под совместимой подразумевается такая конфигурация, которая содержит по крайней мере электропроводку для подключения всех необходимых опций. При такой замене часть электропроводки не используется (дарится покупателю), и в связи с этим возникают избыточные производственные издержки, которые необходимо минимизировать. Сформулированная задача носит название задачи оптимального замещения. В работах [7, 82] для ее моделирования и решения использовалась задача о р-медиане.

Задачи поиска медианного пути и медианного цикла на графе [67, 138, 139] также вызывают интерес с точки зрения практических приложений. Они могут быть использованы при разработке маршрутов транспорта (например, линий метро), при проектировании автодорог и трубопроводов. Кроме того, задача поиска медианного цикла использовалась для размещения почтовых ящиков и мусорных контейнеров [137]. Модели задач размещения взаимосвязанных объектов применялись для решения задачи проектирования расположения модулей технологического оборудования швейного производства и при анализе оптимальности размещения технологического оборудования нефтехимического предприятия [32].

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

В задаче кластерного анализа имеется некоторое множество объектов, которое нужно разбить на непересекающиеся подмножества, называемые кластерами. "Сходные" с точки зрения некоторого критерия объекты должны оказаться в одинаковых кластерах, а "различные" — в разных. Для решения задачи кластерного анализа естественным образом могут быть использованы задачи размещения. В этом случае предполагается, что множество клиентов и множество мест для размещения пунктов обслуживания совпадают {I = J) и представляют собой множество объектов, которые требуется разбить на кластеры. Как упоминалось выше, решение задач размещения в такой постановке представляет собой "звезды" с открытым пунктом обслуживания (или медианой) посредине (см. рис. 2). В задаче кластерного анализа каждая такая "звезда" представляет собой кластер, а соответствующая медиана называемся представителем кластера. Задача о р-медиане применялась для кластерного анализа в работах [17, 119, 120, 126, 130, 149, 157, 172]. Например, в [17] исследовалась задача автоматического распознавания и классификации дефектов, которая возникает при разработке системы машинного зрения, работающей в режиме реального времени при производстве полупроводников. Задача о р-медиане здесь использовалась для решения задачи кластерного анализа на этапе обучения системы. Модели ЗРПК также могут быть использованы при решении задач обработки данных, например, в [86] предложен подход к решению задач классификации с помощью задачи о р-медиане с предпочтениями клиентов.

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

Задача состоит в том, чтобы выбрать такое подмножество типов машин, чтобы, несмотря на потерю части клиентов, добиться максимальной прибыли от продаж. Для решения данной задачи была построена математическая модель в виде задачи о р-медиане с предпочтениями клиентов, которая использовалась как интеллектуальное ядро системы поддержки принятия решений [1].

В качестве специального случая задачи о р-медиане с предпочтениями клиентов может быть рассмотрена, так называемая, обратная задача о р-медиане, представленная в [77]. Здесь требуется открыть не более р загрязняющих окружающую среду предприятий, расположив их как можно дальше от множества городов. В работе [44] рассматривается еще одна двухуровневая модель задачи размещения, имеющая экономическую постановку, — задача об (г, р)-центроиде. Эта задача моделирует поведение конкурентов в условиях рынка. В ней два игрока стремятся захватить как можно большую долю рынка, при этом один из игроков, называемый Лидером, имеет преимущество, так как открывает свои р предприятий первым. Второй игрок (Конкурент) открывает свои г предприятий, выбирая из списка оставшихся.

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

Известные подходы к решению задач ЦЛП. Большинство задач размещения представляют собой задачи комбинаторной оптимизации [152, 175]. При этом для численного решения комбинаторных задач зачастую осуществляется редукция к задаче математического программирования. Например, известно [53, 152], что многие задачи комбинаторной оптимизации, могут быть сформулированы в виде задач целочисленного программирования. Этот факт справедлив и для задач размещения. В подавляющем большинстве работ, посвященных численному решению задач размещения, рассматриваются модели ЦП, и для них разрабатываются методы поиска оптимальных решений.

В последние три десятилетия наблюдается значительный прогресс в разработке методов решения задач ЦП. Наглядным примером может служить известная задача о коммивояжере [65]. До 80-х годов прошлого столетия было возможно решить задачи, в которых рассматривалось только несколько сотен городов [100]. В последних работах приведены примеры, содержащие более миллиона городов [65, 168]. Этот впечатляющий прогресс объясняется многими факторами. В первую очередь, значительно возросла мощность вычислительной техники, что позволило исследовать и решать на практике задачи большой размерности. Кроме того, оказалось, что многие известные теоретические результаты, применение которых было неэффективно для задач малой размерности, удалось успешно использовать для решения задач большой размерности. Наконец, интенсивно развивающаяся в настоящее время область параллельных вычислений является рычагом для повышения эффективности вычислительных методов [19].

Наиболее универсальным и вместе с тем наиболее эффективным методом решения задач ЦП является метод ветвей и границ, а также его модификации — метод ветвей и отсечений; метод ветвей, отсечений и оценок [51, 52, 53, 60, 79, 80, 152, 156, 175]. Впервые идея метода ветвей и границ была предложена Ленд и Дойг в 1960 г. [140]. Она заключается в использовании конечности множества допустимых точек и замене полного их перебора сокращенным. Главную роль в сокращении перебора играет оценка и удаление из рассмотрения неперспективных (т.е. заведомо не содержащих оптимального решения) подмножеств допустимых точек. Эта идея реализуется путем последовательного разбиения множества допустимых точек задачи на подмножества [51, 53, 79, 80, 152]. При этом для каждого подмножества, последовательно порождаемого на каждом шаге процесса, находятся верхние и нижние оценки оптимального значения задачи. На основании этих оценок могут обнаружиться как подмножества, пе содержащие допустимых точек, так и подмножества, которые заведомо не могут содержать оптимальных решений. Удаление из дальнейшего рассмотрения таких подмножеств позволяет заменить полный перебор частичным и тем самым делает реализуемым вычислительный процесс [51, 53, 62, 152, 156, 175]. Качество оценок, получаемых для каждого рассматриваемого подмножества, может существенно влиять на время работы метода [53, 152, 156, 175].

Традиционным способом поиска верхних оценок оптимального решения (для задач на минимум) является использование различных эвристик [53, 79, 80, 152, 175]. В настоящее время разработано огромное количество эвристических методов, которые применяются для решения различных задач ЦП (см., например, [79, 80, 87]). Вопрос выбора подходящей эвристики требует индивидуального подхода к каждой исследуемой задаче, более того, к каждой серии тестовых примеров.

При решении задач целочисленного линейного программирования (ЦЛП) для поиска нижних оценок в простейшей схеме метода ветвей и границ используется линейная (непрерывная) релаксация задачи на рассматриваемой подобласти [53, 79, 80, 152, 156, 175], т.е. решается задача линейного программирования, получающаяся из задачи ЦЛП путем исключения из нее ограничений на целочисленность переменных. Для этих целей может быть использована и любая другая релаксация, например, релаксация Лагранжа [80, 152, 175], когда часть ограничений задачи помещается в целевую функцию с множителями Лагранжа, и предполагается, что получившаяся в результате задача ЦЛП решается проще, чем исходная.

Одним из приемов исследования задач ЦЛП является также исследование их полиэдральной структуры, в частности, многогранника задачи — выпукл011 оболочки допустимой области целочисленной задачи — с целью построения новых семейств так называемых правильных неравенств, т.е. неравенств, которые целиком погружают многогранник задачи в соответствующее пересечение полупространств [52, 60, 63, 79, 80, 152, 175]. Такие неравенства используются для конструирования новых нижних оценок оптимального значения исследуемых задач ЦЛП, которые, в свою очередь, могут быть использованы при разработке методов поиска оптимальных решений задач, например, в методе ветвей и отсечений [79, 80, 152, 156, 175]. Правильные неравенства не нарушают структуру многогранника задачи, но отсекают часть допустимого многогранника линейной релаксации. Идеальным случаем является построение неравенств, которые участвуют в описании многогранника целочисленной задачи — так называемых фасетных или гранеобразующих неравенств [60, 63, 80, 152, 175]. Однако даже в случае удачного исхода исследования полиэдральной структуры задачи можно столкнуться еще с одной трудностью. Неравенств в сконструированном семействе часто оказывается чрезвычайно много, при этом большинство из них бесполезны для получения оценки непрерывной релаксации, связанной с этим семейством неравенств. Во избежание неоправданного увеличения числа ограничений в формулировке задачи используется метод отсечений [52, 60, 63, 79, 80, 152, 156, 175]. Впервые его идея была предложена P.E. Гомори [115, 116). Неравенства Гомори, предложенные им в упомянутых работах вместе с идеей метода отсечений, представлялись в то время красивым теоретическим результатом, однако с развитием вычислительной техники в 80-е—90-е годы теория правильных неравенств начала широко применяться и для численного решения задач.

В [95] представлен обзор "классических" правильных неравенств, которые могут быть использованы для любой задачи ЦЛП, и обсуждаются их взаимосвязи. К ним относятся неравенства расширения и проекции (lift-and-project cuts) [72, 142, 163], отсечения Гомори [52, 60, 63, 79, 80, 115, 152, 175], неравенства Хватала [52, 63, 90, 152], смешанное целочисленное округление [151, 152, 175], неравенства расщепления [89, 94] и неравенства пересечения [71]. В настоящее время во многих коммерческих и бесплатных решателях задач ЦЛП реализованы методы отсечения для большинства классических правильных неравенств [93, 106, 114, 125]. В связи с этим, в настоящее время наиболее перспективным направлением выглядит исследование специфики конкретной задачи и построение правильных неравенств на основе свойств и особенностей ее многогранника для получения хороших нижних оценок оптимального значения задачи. Зачастую в таких исследованиях оказываются полезны известные результаты для классических моделей ЦЛП [152]. Например, в [70, 81, 84, 123, 173] авторами рассмотрены взаимосвязи ряда задач ЦЛП с задачей поиска независимого множества максимальной мощности. Структура многогранника такой задачи достаточно хорошо изучена [152, 155), и известно большое количество правильных неравенств, в том числе фасетных. Известные для задачи поиска независимого множества правильные неравенства использовались в [70, 81, 84, 123, 173] для разработки реализации точных и приближенных методов решения исследуемых задач.

В 1991 году М. Падберг и Д. Риналди, исследуя задачу о коммивояжере, предложили использовать метод отсечений для улучшения нижних оценок линейной релаксации, получаемых на шагах метода ветвей и границ [154], см. также [53, 79, 80, 152, 156, 175]. Эта комбинация двух подходов послужила основой для создания метода ветвей и отсечений. Использование такой схемы часто позволяет существенно сократить время решения задач. В дополнение к методу отсечений в методе ветвей, отсечений и оценок используется, так называемый, метод генерации столбцов, предназначенный для решения задач линейного программирования большой размерности [79, 110, 111]. Идея метода генерации столбцов схожа с идеей метода отсечений, но применяется к неизвестным переменным исследуемой задачи. Переменные добавляются в формулировку последовательно на основе анализа их двойственных оценок, получаемых симплекс-методом [63, 79, 80, 152].

Оригинальным подходом к решению задач ЦЛП является подход, основанный на теории глобального поиска, разработанной A.C. Стрекаловским [54]. Для дискретной задачи строится эквивалентная ей непрерывная задача математического программирования, которая оказывается невыпуклой. Затем к непрерывной задаче применяется теория глобального поиска [54], базирующаяся на условиях глобальной оптимальности. В зависимости от типа невыпуклости в задаче (в целевой функции или в допустимом множестве) используется соответствующая стратегия глобального поиска (СГП). Основными этапами стратегий являются: а) специальный метод локального поиска, который разрабатывается для исследуемой задачи с учетом ее структуры; б) процедура выхода из полученной локальным методом критической точки [54].

В частности, такой подход был успешно применен для задачи поиска максимальной и максимальной взвешенной клики на графе [27, 47, 135]. В работах [47, 135] задача о максимальной клике записывается в непрерывной постановке в виде задачи оптимизации невыпуклой квадратичной функции на каноническом симплексе. Эта функция оказывается представимой в виде разности двух выпуклых функций, следовательно, задача относится к классу задач d.c. минимизации, методика решения которых была разработана в [54, 55]. Для поиска локально и глобально максимальных клик в [47] разработаны специальные методы локального поиска и алгоритм глобального поиска соответственно, которые были успешно протестированы на примерах из известной библиотеки DIMACS [102]. В работе [27] задачи о клике сводятся к задачам минимизации выпуклой квадратичной функции на каноническом симплексе с дополнительным невыпуклым ограничением. Далее для решения полученных непрерывных задач используется СГП для задач с d.c. ограничением [28, 56]. Разработанный подход был также успешно протестирован на тестовых примерах из библиотеки DIMACS.

Для задачи о многомерном рюкзаке подход на основе теории глобального поиска исследовался в работе [164]. Задача сводится к эквивалентной непрерывной задаче с обратно-выпуклым ограничением [54, 59], к которой применяется соответствующая СГП [54]. Отметим, что обратно-выпуклые задачи являются частным случаем задач с d.c. ограничением. Разработанный алгоритм был успешно протестирован на задачах из известной библиотеки OR-Library [153, 164].

В [8, 58] проведено исследование квадратичной задачи о назначениях. Рассмотрено ее сведение к задаче максимизации выпуклой квадратичной функции на параллелепипеде. Для решения последней используется стратегия глобального поиска для задач выпуклой максимизации [54], которые, в свою очередь, являются частным случаем задач d.c. минимизации. Кроме того, для одной упрощенной задачи размещения, известной под названием задачи Вебера [169], теория глобального поиска для задач d.c. программирования и обратно-выпуклой оптимизации применялась в работе [57].

Таким образом, за более чем полувековой период существования и развития ЦП накоплен большой теоретический и практический багаж алгоритмов и методов численного решения задач, общие идеи которых были описаны выше. Исследование и разработка алгоритмов решения конкретных задач ЦП проводится на основе представленных общих принципов, с учетом специфики решаемой задачи. В частности, исследованию свойств и особенностей задач размещения различных классов, таких как простейшая задача размещения и задача о р-медиане в настоящее время уделяется большое внимание [48, 62, 68, 69, 97, 103, 105, 129, 145].

Современное состояние исследований и методов решения задач размещения. Прежде всего, отдельно упомянем алгоритмы поиска оптимальных решений, разработанные специально для простейшей задачи размещения и задачи о р-медиане на основе общих идей численных методов решения задач ЦЛП. Как упоминалось выше, большое значение для скорости работы алгоритмов типа ветвей и границ имеют верхние и нижние оценки, получаемые в ходе их работы. В [74, 78, 159] для задачи о р-медиане исследуются нижние оценки, получаемые с помощью релаксации Лагран-жа, и на их основе реализованы точные методы решения задачи. Под руководством А.А. Колоколова ведется исследование декомпозиционных подходов на основе отсечений Бендерса [4, 39, 97]. При этом применяется разработанный А.А. Колоколовым подход, основу которого составляют регулярные разбиения допустимой области с использованием лексикографического отношения порядка — ¿-разбиения [38]. В работах [34, 35] представлены результаты исследования оценок среднего числа итераций связанного с таким разбиением алгоритма перебора ¿-классов, а также других известных алгоритмов решения задач ЦЛП. В работах [39, 40, 42, 133] методика на основе ¿-разбиения и отсечений Бендерса применялась для решения задач размещения. Например, в работах [40, 42, 133] декомпозиционные алгоритмы с использованием неравенств Бендерса применены к решению задачи о р-медиане. Предложены способы улучшения эффективности этих алгоритмов путем использования различных правил вычисления двойственных оценок для построения отсечений Бендерса. В [42] разработан гибридный декомпозиционный алгоритм, в котором осуществляется лексикографический перебор допустимых точек в сочетании с релаксацией Лагранжа и отсечениями Бендерса.

Исследованию полиэдральных свойств базовых задач размещения с целью улучшения нижних оценок оптимального значения посвящены работы [68, 69, 84, 91, 92, 107]. Напомним, что нижние оценки играют большую роль при разработке численных методов решения задач ЦЛП, в частности, методов, базирующихся на схеме ветвей и отсечений. В [68] рассматриваются семейства правильных неравенств, возникающих из взаимосвязи с задачей поиска независимого множества на графе. Авторами доказано, что такие неравенства являются фасетными (гранеобразующими) для многогранника задачи о р-медиане. В [69] представлено обобщение одного из семейств правильных неравенств из [68]. Кроме того, авторам удалось успешно использовать метод отсечений для одного известного семейства правильных неравенств задачи поиска независимого множества [117, 123] при реализации своего метода ветвей, отсечений и оценок.

В [107] построено еще одно семейство фасетных неравенств для задачи о р-медиане, с помощью которого получены хорошие результаты при проведении вычислительного эксперимента, представленного автором. В работах [84, 91, 92] проводится исследование многогранника простейшей задачи размещения: построены несколько семейств правильных неравенств, в том числе фасетных.

Как упоминалось выше, наряду с нижними оценками, для ускорения работы методов поиска оптимальных решений методами типа ветвей и границ очень эффективными часто оказываются и верхние оценки оптимального значения, поиск которых осуществляется, как правило, с помощью различных эвристик. Охватить весь объем работ, посвященных разработке эвристических методов поиска верхних оценок оптимального решения в задачах размещения, не представляется возможным. Попытка обзора и классификации методов, предложенных для задачи о р-медиане предпринята в работе [146]. Здесь остановимся на некоторых основных публикациях для двух упомянутых базовых моделей задач размещения. Из так называемых "классических" эвристик можно упомянуть жадную эвристику [88, 134], двойственный подъем [85, 109], основанный на релаксации двойственной формулировки ЦЛП. Методы локального поиска разработаны в [131, 144, 167]. Эвристика, основанная на идеях динамического программирования, предложена в [124], а эвристика Лагранжа и ее модификации исследованы, например, в работах [75, 96, 160]. Большое количество работ посвящено разработке, так называемых, "метаэвристик". Среди них можно отметить работы по поиску с запретами [112. 113, 147, 148, 165, 166]. Данный подход также исследовался в работах [23, 43]. Разработке методов поиска с чередующимися окрестностями посвящены работы [99, 119, 122|. Из последних работ, посвященных генетическому алгоритму для задачи о р-медиане, можно упомянуть [64]. Алгоритмы имитации отжига и муравьиных колоний изучаются в работах [131, 141], а также в работе [150]. Разработке гибридного подхода посвящена, например, работа [158].

Изучению задач размещения с иерархической структурой и разработке численных методов их решения посвящены, например, работы [3, 30, 44, 45, 77, 83]. Далее уделим особое внимание работам, посвященным задачам размещения с предпочтениями клиентов.

Современное состояние исследований и методов решения задач размещения с предпочтениями. Впервые модели ЗРПК рассматривались в [118]. Позже аналогичные формулировки независимо были предложены в [24, 25]. В [5, 24] установлена тесная связь ЗРПК с задачами минимизации псевдобулевых функций. Показано, что эти задачи эквивалентны, т.е. по исходным данным ЗРПК можно за полиномиальное время построить эквивалентную задачу минимизации псевдобулевой функции и наоборот. В [45, 121] показано, как, используя данное свойство задачи размещения, можно сократить ее размерность.

Для поиска оптимального решения в ЗРПК используется редукция к равносильным задачам ЦЛП. Например, В [41] для ЦЛП модели задачи предложен декомпозиционный подход с отсечениями Бендерса и методом перебора ¿-классов.

Как упоминалось выше, решающую роль для скорости работы методов поиска оптимальных решений типа ветвей и границ играют верхние и нижние оценки оптимального значения исследуемой задачи, использующиеся в таких методах для сокращения полного перебора допустимых точек. Правильные неравенства для построения нижних оценок оптимальных значений ЗРПК использовались в работах [24, 83]. В частности, в работе [83] предложены семейства правильных неравенств, с помощью которых удается получить лучшую нижнюю оценку оптимального значения задачи, не реализуя при этом метод отсечении. В [3, 121] также рассмотрены различные постановки задачи в терминах ЦЛП, предложена формулировка, основанная на редукции ЗРПК к задаче о паре матриц. Эта формулировка представляет собой так называемую расширенную формулировку задачи, т.е. является задачей в пространстве переменных большей размерности. Использую такую постановку также удается получить лучшую нижнюю оценку оптимального решения ЗРПК.

Для поиска верхних оценок в задаче о р-медиане с предпочтениями клиентов был разработан генетический алгоритм, использующий в качестве популяции локальные решения по окрестности Лина-Кернигана [3]. Предложенный подход тестировался авторами на примерах с большим разрывом целочисленности [22] и показал хорошие результаты.

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

Предмет и объект исследования. Объектом исследования являются модели ЗРПК в виде задач ЦЛП. Предмет исследования — построение эффективных методов поиска оптимальных решений в задачах размещения с двухуровневой структурой.

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

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

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

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

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

Исследования но теме диссертации проводились в рамках проектов по программам СО РАН: "Поиск глобальных решений в невыпуклых задачах исследования операций и оптимального управления" (№ гос. регистрации 01.2.007 08581) с 2007 по 2009 гг., программа СО РАН "Математическая теория управления при возмущениях и неопределенности"; "Нелокальные методы в теории управления динамическими с:истемами" (№ гос. регистрации 01201001345) в 2010 г., программа "Теория управления динамическими системами и методы их исследования", а также в рамках комплексного интеграционного проекта СО РАН 1.3 "Исследование задач двухуровневого и равновесного программирования"(2006-2008 гг.) и проекта фонда "Научный потенциал" №153 "Задачи комбинаторной оптимизации в методах кластерного анализа и классификации данных"(2007-2008 гг.).

Соответствие диссертации паспорту научной специальности. В соответствии с паспортом и областью исследований специальности 05.13.01, в диссертации проведено теоретическое исследование сложных задач комбинаторной оптимизации — задач размещения с предпочтениями (п.1); разработан метод решения этих оптимизационных задач (п.4), таким образом, разработано специальное математическое и программное обеспечение для решения оптимизационной задачи (п.5).

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

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

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

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

Публикации и личный вклад автора. По материалам диссертации опубликовано 12 научных работ [2, 9, 10, 11, 12, 13, 14, 15, 16, 36, 37, 170], включая 3 статьи в периодических изданиях, рекомендованных БАК РФ ¡12, 15, 36].

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

Разработка и реализация нового метода ветвей и отсечений, предложенного в работе, осуществлялись автором лично. Из совместных публикаций с Ю.А. Кочето-вым, A.B. Плясуновым, Е.В. Алексеевой на защиту выносятся только результаты, полученные автором лично.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы, включающего 177 наименований. Общий объем диссертации составляет 124 страницы, из которых 107 страниц основного текста, включающего 3 рисунка и 11 таблиц.

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

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

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

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

Заключение

1. Алексеева E.B. Алгоритмы локального поиска для задачи о р-медиане с предпочтениями клиентов: дис. . канд. физ.-мат.наук. Новосибирск, 2007.

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

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

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

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

6. Васильев И. Л. . Метод декомпозиции для задачи о р-медиане на несвязном графе // Дискретный анализ и исследование операций. 2007. Т. 14, № 1. С. 43-58.

7. Васильев И.Л. Поиск глобального решения в задачах выпуклой максимизации: дис. . канд. физ.-мат.наук. Иркутск, 1998.

8. Васильев И.Л., Климентова К.Б. Метод ветвей и отсечений для задачи размещения с предпочтениями клиентов // Дискретный анализ и исследование операций. 2009. Т. 16, № 2. С. 21-41.

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

10. Васильев И.Л, Сидоров Д.Н. Приложение кластерного анализа к автоматическому распознаванию дефектов // Проблемы управления. 2007. № 4. С. 36-42.

11. Вебер А. Теория размещения промышленности / М.-Л-, 1926.

12. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: Изд-во БХВ-Петербург, 2002. 608 с.

13. Гермейер Ю.Б. Игры с непротивоположными интересами. М.: Наука, 1976.

14. Гимади Э. X. Эффективный алгоритм решения задачи размещения с областями обслуживания, связанными относительно ациклической сети // Управляемые системы. Новосибирск: Ин-т математики СО АН СССР, 1983. Вып. 23. С. 12-23.

15. Гончаров E.H., Иваненко Д.А., Кочетов Ю.А., Кочетова H.A. Библиотека "Дискретные задачи размещения". URL: http://inath.nsc.ru/AP/benchmarks/.

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

17. Горбачевская Л.Е. Полиномиально разрешимые и пр-трудные двухуровневые задачи стандартизации: дис. . канд. физ.-мат.наук. Новосибирск, 1998.

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

19. Горелик В.А., Кононенко А.Ф. Теоретико-игровые модели принятия решений в эколого-экономических системах. М.: Радио и связь, 1982.

20. Груздева Т.В. Решение задачи о клике сведениме к задаче с d.c. ограничением // Дискретный анализ и исследование операций. 2008. Т. 15, № 6. С. 20-33.

21. Груздева Т. В., Стрекаловский A.C. Локальный поиск в задачах с невыпуклыми ограничениями // Журн. вычисл. математики и мат. физики. 2007. Т. 47, № 3. С. 397—413.

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

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

24. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М: Наука, 1981. 344 с.

25. Забудский Г.Г. Модели и методы решения задач оптимального размещения на сетях, в пространствах и дискретных множествах: дис. . доктора физ.-мат. наук. Омск, 2005.

26. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. Новосибирск: Изд-во Института математики, 1999.

27. Заозерская Л.А., Колоколов A.A. Оценки среднего числа итераций для некоторых алгоритмов решения задачи об упаковке множества // Журн. вычисл. математики и мат. физики. 2010. Т. 50, № 2. С. 242-248.

28. Климентова К.Б. Приложение задачи о р-медиане с предпочтениями клиентов для кластерного анализа клеток рака // Современные технологии. Системный анализ. Моделирование. 2009. № 3(23). С. 33-38.

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

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

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

32. Косарев H.A. Разработка и анализ декомпозиционных алгоритмов для задач оптимального размещения предприятий: дис. . канд. физ.-мат.наук. Омск, 2006.

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

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

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

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

37. Мандель И.Д. Кластерный анализ. М.: Финансы и статистика, 1988.

38. Моисеев H.H. Элементы теории оптимальных систем. М.: Наука, 1975.

39. Современное состояние теории исследования операций / под редакцией Моисеева H.H. М: Наука, 1979.

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

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

42. Стрекаловский A.C. Элементы невыпуклой оптимизации Новосибирск: Наука, 2003. 356 с.

43. Стрекаловский A.C. О минимизации разности двух выпуклых функций на.допустимом множестве // Журн. вычисл. математики и мат. физики. 2003. Т. 43, № 3. С. 399-409.

44. Стрекаловский А. С. Минимизирующие последовательности в задачах с d.c. ограничениями // Журн. вычисл. математики и мат. физики. 2005. Т. 45, № 3. С. 435-447.

45. Стрекаловский А.С., Васильев И.Л. Об одном подходе к решению квадратичной задачи о назначениях / Труды 11-ой международной Байкальской школы-семинара. 1998. Т.1. С. 183-186.

46. Стрекаловский А.С., Груздева Т.В. Модификация метода Розена в обратно-выпуклой задаче // Известия вузов. Математика. 2005. № 12(523). С. 70-75.

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

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

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

50. Шевченко В.Н. Качественные вопросы целочисленного линейного программирования. М.: ФИЗМАТЛИТ, 1995.

51. Alp О., Erkut Е., Drezner D. Ап efficient genetic algorithm for the p-median problem // Annals of Operations Research. 2003. N 122. P. 21—42.

52. Applegate D., Bixby R.E., Chvatal V., Cook W. The traveling salesman problem. A computational study. Princeton: Princeton University Press, 2006. 593 p.

53. Avella P., D'Auria В., Salerno S., Vasil'ev I. A computational study of local search algorithms for Italian high-school timetabling // Journal of Heuristic. 2007. V.13, N 6. P. 543—556.

54. Avella I., Boccia M., Sforza A., Vasil'ev I. A branch-and-cut algorithm for the median-path problem // Computational Optimization and Applications. 2005. V 32, N 3. P. 215-230.

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

56. Avella P., Sassano A., Vasil'ev I. Computational study of large-scale p-mcdian problems // Mathematical Programming. 2006. V. 109, N 1. P. 89-114.

57. Avella P., Vasil'ev I. A computational study of a cutting plane algorithm for university course timetabling author // Journal of Scheduling. 2005. V. 8, N 6. P. 497-514.

58. Balas E. Intersection cuts a new type of cutting planes for integer programming // Operations Research. 1971. V. 19. P. 19-39.

59. Balas E., Ceria S., Cornuejols G. A lift-and-project cutting plane algorithm for mixed 0-1 programs // Mathematical Programming. 1993. V. 58. P. 295-324.

60. Bard J.F. Practical Bilevel Optimization. Dordrecht: Kluwer Academic Publishers, 1998.

61. Beasley, J. E. A Note on Solving Large p-Mcdian Problems // European Journal of Operational Research. 1985. V. 21. P. 270-273.

62. Beasley, J. E. Lagrangian heuristics for location problems // European Journal of Operational Research. 1993. V.65, N 4. P.383-399.

63. Beisiegel B., Kallrath J., Kochetov Yu., Rudnev A. Simulated Annealing Based Algorithm for the 2D Bin Packing Problem with Impurities // Operations Research Proceedings-2005. Heidelberg: Springer, 2006. P. 309-314

64. Belotti P., Labbe M., Maffioli F., Ndiaye M.M. A branch-and-cut method for the obnoxious p -median problem // 40R: A Quarterly Journal of Operations Research. 2007. V. 5, N 4. P. 299-314.

65. Beltran C., Tadonki C., Vial J.Ph. Solving the p-median problem with a semi-lagrangian relaxation // Computational Optimization and Applications. 2006. V.35, N.2. P. 239-260. ■

66. Bertsimas D., Tsitsiklis J.N. Introduction to Linear Optimization. Belmont, Massachusetts: Athena Scientific, 1997. 587 p.

67. Bertsimas D., Weismantel R. Optimization over Integers. Belmont, Massachusetts: Dynamic Ideas, 2005. 603 p.

68. Borndorfer R., Weismantel R. Set packing relaxations of some integer programs // Mathematical Programming. 2000. V. 88. P. 425-450.

69. Briant O., Naddef D. The optimal diversity management problem // Operations Research. 2004. V.52, N 4. P. 515-526.

70. Cánovas L., Garcia S., Labbé M., Marin A. A strengthened formulation for the simple plant location problem with order // Operations Research Letters. 2007. V. 35, N 2. P. 141-150.

71. Cánovas L., Landete M., Marin A. On the facets of the simple plant location packing polytope // Discrete Applied Mathematics. 2002. V. 124, N 1-3. P. 27-53.

72. Captivo E.M. Fast primal and dual heuristics for the pmedian location problem // European Journal of Operational Research. 1991. V. 52. P. 65—74.

73. Carrizosa E., Martin-Barragán B., Plastria F., Morales D.R. On the selection of the globally optimal prototype subset for Nearest-Neighbor classification // INFORMS Journal on Computing. 2007. V.19, N.3. P. 470-479.

74. Qela E. The Quadratic Assignment Problem. Dordrecht: Kluwer Academic Publishers, 1998. 287 P.

75. Charikar M., Guha S. Improved combinatorial algorithms for the facility location and k-median problems // 40th IEEE Symp. on Foundations of Computer Science: proceedings. 1999. P. 378-388.

76. Chvátal V., Cook W., Hartmann M. On cutting-plane proofs in combinatorial optimization // Algebra and its Applications. 1989. V. 114/115. P. 455-499.

77. Chvátal V. Edmonds polytopes and a hierarchy of combinatorial optimization // Discrete Mathematics. 1973. V. 4. P. 305-337.

78. Cho D.C., Johnson E.L., Padberg M., Rao M.R. On the uncapacitated plant location problem I: valid inequalities and facets // Mathematics of Operations Research. 1983. V. 8. P. 579-589.

79. Cho D.C., Padberg M., Rao M.R. On the uncapacitated plant location problem II: facets and lifting theorems // Mathematics of Operations Research. 1983. V. 8. P. 590-612.

80. COIN-OR. URL: http://www.coin-or.org/

81. Cook W., Kannan R., Schrijver A. Chvatal closures for mixed integer programming problems // Mathematical Programming. 1990. V. 47. P. 155-174.

82. Cornuéjols G. Valid inequalities for mixed integer linear programs // Mathematical Programming. 2008. V. 112, N.l. P. 3-14.

83. Cornuéjols G., Fisher M.L., Nemhauser G.L. Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms // Management Science. 1977. V. 23. P. 789-810.

84. Cornuéjols G., Nemhauser G.L., Wolsey L.A. The uncapacitated facility location problem // Discrete Location Theory / Edited by Mirchandani P.B., Franscis R.L. New-York: Wiley and Sons. Inc, 1990. P. 119-171.

85. Cornuéjols G., Thizy J.-M. Some facets of the simple plant location polytope // Mathematical Programming. 1982. V. 23. P. 50-74

86. Crainic T., Gendreau M., Hansen P., Mladenovic N. Cooperative parallel variable neighborhood search for the pmedian // Journal of Heuristics. 2004. V. 10 P., 293-314.

87. Crowder H., Padberg M.W. Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality // Management Science. 1980. V.26, N 5. P. 495-509.

88. Dempe S. Foundations of Bilevel Programming. Dordrecht/Boston/London: Kluwer Academic Publishers, 2002.

89. DIMACS — Discrete Mathematics and Computer Science. URL: ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks

90. Facility Location: Applications and Theory / Edited by Drezner Z., Hamacher H.W. Berlin,Heidelberg: Springer. 2004. 457 p.

91. Eisen M.B., Spellman P.T., Brown P.O., Botstein D. Cluster analysis and display of genome-wide expression patterns / The National Academy of Science of the USA: proceedidngs. Genetics. 1998. V. 95. P. 14863-14868.

92. Erlenkotter D. A dual-based procedure for uncapacitated facility location // Operations Research. 1978. V. 26, N 6. P. 992—1009.

93. Fair Isaac Corporation: Xpress Optimization Suite. URL: http://www.fico.com/.107. de Farias I.R. A family of facets for the uncapacitated p-median polytope // Operations Research Letters. 2001. V. 28. P. 161-167.

94. Galvao R.D. A dual-bounded algorithm for the p-Median problem // Operations Research. 1980. V. 28. P. 1112—1121.

95. Gilmore P.C., Gomory R.E. A linear programming approach to the cutting stock problem // Operations Research. 1961. V. 9. P. 849-859.

96. Gilmore P.C., Gomory R.E. A linear programming approach to the cutting stock problem part II // Operations Research. 1963. V.ll. P. 863-888.

97. Glover F. Tabu Search Part I // ORSA Journal on Computing. 1989. V. 1. P. 190-206.

98. Glover F. Tabu Search Part II // ORSA Journal on Computing. 1990. V. 2. P. 4—32.

99. GLPK — GNU Linear Programming Kit. URL: http://www.gnu.org/software/glpk/

100. Gomory R.E.An algorithm for integer solutions to linear programs // Recent Advances in Mathematical Programming /Edited by Graves R.L. and Wolfe P. New York: McGraw-Hill, 1963. P. 269-302.

101. Gomory R.E. Some polyhedra related to combinatorial problems // Linear Algebra and Applications. 1969. V. 2, N 4. P. 451-558.

102. Grotschel M., Lovasz L., Schrijver A. Geometric Algorithms and Combinatorial Optimization. Berlin, Heidelberg: Springer-Verlag, 1988.

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

104. Hansen P., Brimberg J., Urosevic D., Mladenovic N. Solving large p-median clustering problems by primal-dual variable neighborhood search // Data Mining and Knowledge Discovery. 2009. V.19, N.3. P. 351-375.

105. Hansen P., Jaumard B. Cluster analysis and mathematical programming // Mathematical Programming. 1997. V.79. P. 191—215.

106. Hansen P., Kochetov Y., Mladenovic N. Lower bounds for the uncapacitated facility location problem with user preferences. Les Charies du GERAD G-2004-24, 2004.

107. Hansen P., Mladenovic N. Variable neighborhood search for the p-inedian // Location Science. 1997. V. 5. P. 207—226.

108. Hoffman K., Padberg M. Solving airline crew scheduling problems by branch-and-cut // Management Science. 1993. V. 39, N 6. P. 657-682.

109. Hribar M., Daskin M. A dynamic programming heuristic for the p-median problem // European Journal of Operational Research. 1997. V. 101. P. 499—508.

110. IBM ILOG CPLEX. URL: http://www-01.ibm.com/software/integration/optimization/cplex/

111. Jain A.K., Murty M.N., Flynn P.J. Data clustering: a review // ACM Computing Surveys. 1999. V.31, N.3. P. 264-323.

112. Kariv O., Hakimi S. An algoritmic approach to network Location Problems. The p-medians // SIAM Journal of Applied Mathematics. 1979. V. 37. P. 539-560.

113. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing // Science. 1983. V. 220(4598). P. 671-680.

114. Klamroth K. Single Facility Location Problems with Barriers. New York: Springer, 2002. 216 p.

115. Klastorin T. The p-median problem for cluster analysis: A comparative test using the mixture model approach // Management Science. 1985 . V. 31. P. 84-95.

116. Kochetov Yu., Alekseeva E., Levanova T., Lorcsh M. Large neighborhood local search for the p-median problem // Yugoslav Journal of Operations Research. 2005. V. 15, N 1. R 53—63.

117. Kuehn A.A., Hamburger M.J. A heuristic program for locating warehouses // Management Science. 1963. V. 9, N 4, P. 643—666.

118. Labbé M., Laporte G. Maximizing user Convenience and Postal Service Efficiency in Post Box Location // Belgian Journal of Operations Research, Statistics and Computer Science. 1986. V. 26. P. 21-35.

119. Labbé, M., Laporte G., Rodriguez I. Path, Tree and Cycle Location // Fleet Management and Logistics / Edited by Crainic T.G., Laporte G. Boston: Kluwer, 1998. P. 187-204.

120. Labbé, M., Laporte G., Rodrigues I., Salazar J.J. The Median Cycle problem // Technical report ULB-SMG-01. 2001.

121. Land A.H., Doig A.G. An automatic method of solving discrete programming problems // Economctrica. 1960. V. 28, N 3. P. 497-520.

122. Levanova T., Loresh M.A. Algorithms of ant system and simulated annealing for the p-median problem // Automation and Remote Control. 2004. V. 65. P. 431—438.

123. Lovász L., Schrijver A. Cones of matrices and set-functions and 0-1 optimization // SIAM Journal of Optimization. 1991. V. 1. P. 166-190.

124. MacQueen J.B. Some methods of classification and analysis of multivariate observations / The fifth Berkeley symposium of mathematical statistics and probability: proceedings. Berkley: University of California Press, 1967. P. 281-297.

125. Maranzana F.E. On the location of supply points to minimize transportation costs // Operations Research Quarterly. 1964. V. 12. P. 138—139.

126. Discrete Location Theory / edited by Mirchandani P., Francis R. NY: Wiley-Intersience, 1990.

127. Mladenovic N., Brimberg J., Hansen P., Moreno-Pérez J.A. The p-median problem: A survey of metaheuristic approaches // European Journal of Operations Research. 2007. V. 179. P. 927-939.

128. Mladenovic N., Moreno-Pertez J.A., Moreno-Vega J.M. Tabu search in solving p-facility location-allocation problems. Les Cahiers du GERAD, G-95-38. Montreal, 1995.

129. Mladenovic N., Moreno-Pefrez J.A., Moreno-Vega J.M. A chain-interchange heuristic method // Yugoslav Journal of Operations Research. 1996. V. 6. P. 4154.

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

131. Murray A.T., Church R.L. Applying simulated annealing to planning-location models // Journal of Heuristics. 1996. V. 2. P. 31—53.

132. Nemhauser G.L., Wolsey L.A. A recursive procedure to generate all cuts for 0-1 mixed integer programs // Mathematical Programming. 1990. V. 46. P. 379-390.

133. Nemhauser G.N., Wolsey L.A. Integer and Combinatiorial Optimization. New-York: A Wiley-Interscience Publication, 1999.

134. OR-Library. URL: http://people.brunel.ac.uk/ mastjjb/jeb/info.html

135. Padberg M., Rinaldi G. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems // SIAM Review. 1991. V. 30, N 1. P. 60-100.

136. Padberg M.W. On the facial structure of the set packing polyhedra // Mathematical Programming. 1973. V. 5. P. 199-215.

137. Pochet Y., Wolsey L.A. Production Planning by Mixed Integer Programming. New-York: Springer, 2006.

138. Rao M.R. Cluster analysis and mathematical programming // Journal of the American Statistical Association. 1971. V. 6. P. 622—626.

139. Resende M., Werneck R.F. A hybrid heuristic for the p-median problem // Journal of Heuristics. 2004. V. 10, N 1. P. 59—88.

140. Senna E.L.F., Lorena L.A.N., Pepeira M.A. A branch-and-price approach to p-median location problems // Computers and Operations Research. 2005. V. 32, N 6. P. 1655-1664.

141. Scherf U., Ross D.T., Waltham M., Smith L.H. et al. A gene expression database for the molecular pharmacology of cancer // Nature Genetics. 2000. V. 24. P. 236-244.

142. Scherf U., Ross D.T. A Gene Expression Database for the Molecular Pharmacology of Cancer. URL: http://discover.nci.nih.gov/nature2000/natureintromain.jsp

143. Sherali H., Adams W. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems / / SIAM Journal on Discrete Mathematics. 1990. V. 3. P. 311-430.

144. Sun M. A Tabu Search Heuristic for the Uncapacitated Facility Location Problem // Operations Research. Metaheuristic Optimization via Memory and Evolution. 2006. V. 30. Part II. P. 191-211.

145. Sun M. Solving the uncapacitated facility location problem using tabu search // Computers & Operations Research. 2006. V. 33, N 9. P. 2563-2589.

146. Teitz M.B., Bart P. Heuristic methods for estimating the generalized vertex median of a weighted graph // Operations Research. 1968. V. 16. P. 955—961.

147. The Traveling Salesman Problem. URL: http://www.tsp.gatecli.edu/index.html

148. Tuy H., Al-Khayyal F., Zhou F. Optimization Method for Single Facility Location Problem // Journal of Global Optimization. 1995. V. 7. P. 209-227.

149. Vicente L. N., Calamai P. H. Bilevel and Multilevel Programming: A bibliography Review // Journal of Global Opt. 1994. V. 5. P. 291-306.

150. Vinod H.D. Integer programming and the theory of groups // Journal of the American Statistical Association. 1969. V. 6. P. 506—519.

151. Waterer H., Johnson E.L., Nobili P., Savelsbergh M.W.P. The relation of time indexed formulations of single machine scheduling problems to the node packing problem // Mathematical Programming. 2002. V. 93. P. 477-494.

152. Weber A. Über den Standort der Industrien, Teil 1: Reine Theorie des Standortes. Tübingen: J.C.B. Mohr, 1909.

153. Wolsey L.A. Integer Programming. New York: Wiley & Sons, Inc., 1998.

154. Zololykh N.Y. Skeleton 02.01.01 Manulal. URL:http://www.uic.unn.ru/ zny/skeleton/. 2010.