Алгоритмы с оценками для дискретных задач размещения

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

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

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

— выделение эффективно решаемых подзадач и построение для них точных эффективых алгоритмов с рекордными оценками трудоемкости;

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

— построение эффективных приближенных алгоритмов с априорными оценками точности.

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

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

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

Пусть имеются конечные множества I = {1,., ш} и .1 = {1,.. , п}, первое из которых задает множество возможных пунктов размещения предприятий для выпуска некоторого однородного продукта, а второе — множество потребителей этого продукта. В некоторых задачах множества I ж 3 могут совпадать. Пусть, кроме того, заданы величины сг-, г? /, определяющие начальные затраты на размещение предприятия в пункте г и величины г ?/,.?? равные затратам на доставку продукта от предприятия, размещенного в пункте г, до потребителя Требуется выбрать из множества возможных пунктов размещения предприятий подмножество пунктов 5, в которых следует разместить предприятия, таким образом, чтобы сумма начальных затрат плюс сумма наименьших затрат на доставку продукта каждому потребителю была минимальной. Формально простейшая задача размещения (ПЗР) в комбинаторной постановке записывается следующим образом:

Наряду с комбинаторной постановкой часто рассматривается постановка ПЗР в виде задачи линейного целочисленного программирования:

Хц х^ ъ I) ]? ^

Хц, Х1? {0,1}, г ?/,-?/.

Используемые в этой задаче переменные имеют следующий смысл: Х{ — 1, если в пункте г размещается предприятие, жг- = 0, в противном

Ш г’е/

X/ - ^ 5 3? случаех^ = 1, если пункт потребления ] обслуживается предприятием, размещенном в пункте г, и х^ — 0, в противном случае.

Как уже отмечалось ПЗР является достаточно хорошо изученной задачей. Она относится к числу ТУР-трудных задач поскольку содержит в себе задачу о покрытии конечного множества системой конечных подмножеств. Исследования этой задачи велись по разным направлениям по каждому из которых были достигнуты значительные успехи. Так в работах Береснева [8], Береснева, Гимади, Деменьтева [11] и Ег1епкоиег [66] описаны алгоритмы решения ПЗР с помощью алгоритмов неявного перебора. Эти методы основаны на применении известной схемы метода ветвей и границ.

Целый ряд результатов связан с рассмотрением частных случаев задачи. Было обнаружено, что если матрица (с^) удовлетворяет различным специфическим требованиям, то ПЗР полиномиально разрешима. Известно, что ПЗР принадлежит классу Р если матрица односвязна (Береснев, Гимади, Дементьев[11]), двусвязна (Береснев [9]), квазивы-пукла или обобщенно-квазивыпукла (Гимади [20]). В работе Трубина [30] приводится полиномиальный алгоритм для ПЗР на дереве, с трудоемкостью 0(ш3) (см. также [31]). Гимади [16] предложил алгоритм с существенно лучшей трудоемкостью 0(т2). Агеев [34] установил, что для очень широкого класса задач (с матрицами порожденными частичными д-деревьями) существует полиномиальный алгоритм с трудоемкостью 0{пт<1+1). ПЗР и ее обобщения также изучались в работах [2, 10, 21, 15, 17, 19, 25, 18, 5, 6, 7, 14, 22, 26, 33] как с точки зрения полиномиально разрешимых подклассов так и с точки зрения других видов анализа NP-тpyдныx задач (см. также обзор по полиномиально разрешимым подклассам для ПЗР [27]). Кроме того, Береснев [9] установил эквивалентность ПЗР и задачи минимизации булевых полиномов, что позволило выделить новые классы эффективно решаемых задач [9, 2, 4, 3]. В работе [35] Агеевым был получен отрицательный результат: ПЗР оказалась МР-трудной, даже если матрица (сг-) порождена расстояниями на плоской решетке.

Близкой к ПЗР является так называемая простейшая задача размещения на максимум (ПЗРМ), которая в комбинаторной постановке записывается следующим образом:

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

Задачи ПЗР и ПЗРМ эквивалентны в том смысле, что любой точный алгоритм одной задачи применим и к другой. Однако с точки зрения приближенных алгоритмов эти задачи отличаются. Историческая справка и обзор по ПЗР и ПЗРМ могут быть найдены в [62].

Другой классической задачей размещения является задача о р-медиане комбинаторная формулировка которой имеет следующий вид:

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

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

И/ = 1? ] ^ -1 ч Ш г? ^ ^ I ч 3? J'•>

Е <

6/ е {о, 1}, I

Капу и НаЫгш [96] показали, что задача о р-медиане является ЛТР-трудной. В этой же работе показано, что если матрица (с^) есть матрица кратчайших расстояний на дереве, то задача полиномиально разрешима. В обзоре [110] можно найти список основных результатов для этой задачи.

Задача о р-медиане может рассматриваться и как задача на максимум. Комбинаторная формулировка такой задачи имеет вид

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

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

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

Задача о р-центре ]УР-трудна [93]. Это следует из того, что известная задача о доминирующем множестве может быть сведена к задаче о р-центре. Эффективный алгоритм для задачи о р-центре существует (см. [56]) при тех же самых предположениях, что и для задачи о р-медиане, когда матрица (с^) есть матрица кратчайших расстояний на дереве. Исторические сведения, а также перечень результатов для задачи о р-центре приводится в обзорах [83], [129].

Одной из наиболее трудных для исследований задач размещения является квадратичная задача о назначении (КЗН). В виде задачи целочисленного программирования она записывается следующим обрашш < шах тш с 5с/ зом: min ЕЕ I Е Е dpqVjg Угр, ieipeJ jei q

E yip = 1i «e i, peJ

V € «7, iEl

Vip?{ 0,1}, iel, p? j.

Содержательно КЗН можно проинтерпретировать следующим образом. Пусть J = {1,., п} - множество возможных пунктов размеще-яия предприятий, а I = {1,., т] (т < п) — множество размещаемых предприятий. Пусть величины dpq, р, q Е J, задают расстояние между пунктами р и д, а величины Wij i, j Е I, являются удельными (на единицу расстояния) затратами на перевозку грузов между предприятиями г и j. Определим переменные yip, г Е I, p Е J следующим образом:

1 если предприятие i размещается в пункте р, 0 иначе.

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

КЗН относится к числу iVP-трудных задач, так как задача коммивояжера и задача о максимальной клике являются частыми случаями КЗН [54]. Несмотря на то, что КЗН является одной из самых изученных задач комбинаторной оптимизации (см. обзор [54] и обзор по

Hip полиномиально разрешимым подклассам [55]) точные решения удается получить для задач размерности не более 30×30.

Как уже отмечалось выше интересующие нас задачи являются ЫР-трудными. Это означает, что построение точных эффективных (полиномиальных) алгоритмов скорее всего невозможно (подробную дискуссию по теории Л^Р-полноты см. в [28]). Одним из основных направлений исследования таких задач является построение приближенных эфективных алгоритмов с априорными оценками их точности. Такие алгоритмы не для всякой индивидуальной задачи находят точное решение, но всегда отыскивают допустимое решение задачи, которое удовлетворяет некоторым требованиям по точности, установленными еще до получения приближенного решения.

Идея построения приближенного алгоритма настолько естественна, что невозможно проследить, кто первым ее придумал и стал использовать. Считается, что первый приближенный алгоритм и его анализ был дан в очень известной работе [80] по теории расписаний. Другими фундаментальными работами в этой области являются работы [94, 23], в которых вводятся понятия приближенного алгоритма и его точности в худшем случае.

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

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

Настоящая работа посвящена построению приближенных алгоритмов для задач размещения и анализу их точности в худшем случае. Напомним определения основных понятий, используемых при таком анализе. Пусть имеется оптимизационная задача и приближенный алгоритм, А для ее решения. Обозначим через / индивидуальную оптимизационную задачу, Р (1) значение целевой функции на приближенном решении, полученном алгоритмом, а через .Р*(/) значение целевой функции на оптимальном решении. Существует несколько способов измерения точности приближенного алгоритма. Наиболее распространенной и используемой величиной, характеризующей точность приближенного алгоритма, является так называемая относительная точность, под которой понимается функция тд (1) = Оценкой (априорной) относительной точности приближенного алгоритма, А решения оптимизационной задачи на максимум (минимум) является величина КА такая, что для любой индивидуальной задачи I выполняется неравенство тА{1)>ЯА (тА (1)<�ПА).

Такую оценку IIА, не зависящую от размерности индивидуальной задачи /, называют константной.

Другими важными понятиями комбинаторной оптимизации, связанными с приближенными алгоритмами, являются понятия аппроксима-ционной схемы и полной аппроксимационной схемы. Аппрокимацион-ной схемой для некоторой оптимизационной задачи называется алгоритм, который для любого фиксированного е > 0 находит допустимое решение задачи с относительной оценкой погрешности 1-е (для задачи на максимум) и трудоемкость алгоритма полиномиальна при фиксированном е > 0. Схема называется полной, если трудоемкость алгоритма ограничена полиномом от 1/г и длины входных данных.

В конце семидесятых годов вышло много важных работ по приближенным алгоритмам и, как следствие этого, появилось несколько обзоров [72, 122, 123, 13] в которых суммируются результаты, полученные за эти годы. Затем наступило затишье и на протяжении более десяти лет количество опубликованных статей по приближенным алгоритмам было невелико. С конца восьмидесятых годов произошел взрыв популярности исследований в области приближенных алгоритмов. Очень важным открытием стало понимание того, что для получения оценок значений целевых функций исследуемых задач можно использовать различные полиномиально разрешимые релаксации этих задач. Первыми, кто использовал линейное програмирование при построении и анализе приближенных алгоритмов с относительной оценкой точности были Кл^Ьауап, Тотрэоп [120], а после работы [77] использование линейного програмирования стало основным методом построения приближенных алгоритмов. Одним из основных методов используемых в диссертации является метод округления линейных релаксаций. Суть метода заключается в следующем. Предположим, что исследуемую оптимизационную задачу можно сформулировать как задачу линейного булевого программирования. Рассмотрим линейную релаксацию этой задачу, получаемую заменой булевых переменных на непрерывные переменные из отрезка [0,1]. Эта задача является задачей линейного программирования, которая как известно полиномиально разрешима [32]. Понятно, что оптимальное значение целевой функции ре-лаксированной задачи является верхней оценкой (для задачи на максимум) оптимального значения целевой функции исходной задачи. В результате округления оптимального решения релаксированной задачи можно получить приближенное решение исходной задачи, а воспользовавшись верхней оценкой отимального значения ее целевой функции получить и оценку точности построенного приближенного решения. Важнейшей составной частью этого подхода является алгоритм округления оптимального решения релаксированной задачи. Существует широкий спектр техник, которые могут применятся при округлении. Особенно известной стала техника вероятностного округления [120]. В диссертационной работе используются некоторые из известных техник округления, в частности, вероятностное округление. Также предлагается новый метод округления для задач с ограничением на мощность.

В начале 90-х произошел другой прорыв в понимании приближенных алгоритмов, обусловленный появлением теоретических основ для доказательства отрицательных результатов. Бурное развитие в этой области было инициировано двумя работами [70, 117]. В первой работе впервые был получен отрицательный результат для задачи о клике, и предложена техника, которая в дальнейшем усовершенствовалась и оттачивалась в целом ряде работ. Во второй работе предложено синтаксическое определение некоторого класса сложности, который назвали MAXSNP, и введено понятие L-сводимости. Оказалось, что почти все естественные задачи комбинаторной оптимизации лежат в этом классе и многие из них оказались полными в этом классе относительно L-сводимости. Papadimitrou и Yannakakis предположили, что для задач полных в классе MAXSNP не существует аппроксимационной схемы. Эта гипотеза была доказана в работе [46] при условии, что Р ф. NP. Хорошими введениями в эту бурно развивающуюся область являются диссертация Агога [38] и обзор Агога и Lund [45], а также обзоры [126, 87] о последних достижениях в области приближенных алгоритмов.

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

Как уже отмечалось, настоящая диссертация посвящена построению и анализу приближенных алгоритмов для дискретных задач размещения. В первой главе рассматривается простейшая задача размещения на максимум. Для этой задачи строится приближенный алгоритм с оценкой точности 2(д/2 — 1) ~ 0.828, что лучше оценки точности жадного алгоритм [61]. Основу предложенного алгоритма составляет процедура вероятностного округления оптимального решения линейной релаксации задачи. Показано, что в случае использования такой релаксации, полученная оценка не может быть улучшена. Кроме того, доказано, что для простейшей задачи размещения на максимум не существует аппроксимационной схемы при условии, что Р ф МР.

Вторая глава посвящена исследованию обобщений задачи о р-медиане на максимум. Рассматривается обобщенная задача о р-медиане с двумя видами ограничений: с обычным мощностным ограничением |5| < рис более общим ограничением «ранцевого» вида < О. Целевая функция задачи определяется как оптимальное значение целевой функции некоторой оптимизационной задачи. Эта оптимизационная задача является более общей, чем, например, рассмотренная в [132], и имеет к дополнительных ресурсных ограничений. Для обеих задач о р-медиане (с двумя видами ограничений) получены оценки точности жадных алгоритмов. При к = 0 эти оценки совпадают с оценками из [61, 132]. В этой главе рассматривается также еще одно обобщение задачи о р-медиане на максимум так называемая динамическая задача о р-медиане. Динамическая задача описывает ситуацию, когда размещение предприятий производится в течение некоторого периода времени, состоящего из нескольких единичных отрезков (лет). Требуется в каждом году разместить ограниченное число предприятий так, чтобы максимизировать суммарную прибыль за весь рассматриваемый период времени. Для этой задачи предлагается приближенный алгоритм с оценкой точности (1 — е-1). При построении алгоритма используется техника вероятностного округления решения линейной релаксации задачи.

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

В четвертой главе исследуется задача выполнимости на максимум с мощностным ограничением. Для этой задачи предлагается алгоритм с оценкой точности равной 1-е-1. Алгоритм построен с использованием техники вероятностного округления решения линейной релаксации. Полученная оценка является неулучшаемой при условии, что Р ф NP [68].

В пятой главе рассматривается квадратичная задача о назначениях. Для этой задачи дается положительный ответ на поставленный в [118] вопрос о существовании приближенного алгоритма с константной оценкой точности для частного случая задачи, когда матрица (dpq) удовлетворяет неравенству треугольника, а все элементы матрицы равны единице. Для указанного частного случая задачи построен алгоритм с оценкой точности равной 2.

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

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

Основные результаты диссертации опубликованы и докладывались на 2-ом Сибирском конгрессе по индустриальной и прикладной математике (Новосибирск, 1996), Международной конференции «Проблемы оптимизации и экономические приложения» (Омск, 1997), 16-ом Симпозиуме по математическому программированию (Лозанна, Швейцария, 1997), Сибирской коференции по исследованию операций (Ново

Заключение

Сформулируем основные результаты проведенных исследований.

1. Для простейшей задачи размещения на максимум построен полиномиальный приближенный алгоритм с оценкой точности равной 2(у/2 — 1). Доказано, что для этой задачи не существует полиномиальной аппроксимационной схемы при условии, что Р ф NP.

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

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