Оценки оптимальных значений и методы решения задач размещения с предпочтениями клиентов тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Климентова, Ксения Борисовна

• Климентова, Ксения Борисовна
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Климентова, Ксения Борисовна

Введение

Глава 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. Разработан метод поиска оптимальных решений в задачах размещения с предпочтениями клиентов, основанный на методе отсечений для нового семейства правильных неравенств. Проведен вычислительный эксперимент, подтвердивший эффективность разработанного метода на известных из литературы сериях тестовых примеров и одной прикладной задаче кластерного анализа.

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Климентова, Ксения Борисовна, 2010 год

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.