Задача о размещении объектов: различия между версиями

Задачи о размещении объектов рассматривают ситуации, в которых необходимо спланировать местоположение объектов, предназначенных для обслуживания заданного множества клиентов. Цель обычно заключается в минимизации суммы затрат на открытие объектов и затрат на обслуживание их клиентами с учетом различных ограничений – таких как количество и тип клиентов, которых может обслужить объект. Существует множество вариантов этой задачи, зависящих от структуры стоимостной функции и ограничений, налагаемых на решение. Первые исследования задачи о размещении объектов выполнили Кюн и Гамбергер [35], Балински и Волф [8], Манн [40] и Балински [7]. Обзорные работы представили Краруп и Прузан [34], а также Мирчандани и Фрэнсис [42]. Любопытно отметить, что одним из самых эффективных алгоритмов решения задачи о размещении объектов без ограничений на пропускную способность с точки зрения оптимальности является сочетание прямо-двойственного алгоритма с алгоритмом ветвления и границ, предложенное Эрленкоттером [16] еще в 1978 году. Его прямо-двойственная схема близка к техникам, используемым в современной литературе, посвященной алгоритмам аппроксимации.

В последние годы были проведены масштабные исследования алгоритмов аппроксимации для задач о размещении объектов. Обзорные материалы по этим исследованиям выпустили Шмойс [49, 50] и Вайген [55]. Помимо их теоретической и практической важности, задачи о размещении объектов представляют собой яркую демонстрацию применения широко распространенных техник в области алгоритмов аппроксимации, поскольку многие из этих техник (например, округление LP-алгоритма, прямо-двойственные методы и локальный поиск) успешно применяются к этому семейству задач. Далее будут рассмотрены насколько задач о размещении объектов, выполнен экскурс в историю и перечислены алгоритмы аппроксимации с опорой на результаты, полученные в работе Шмойса, Тардош и Аардал [51]. Техники, применяемые к ''задаче о размещении объектов без ограничений на пропускную способность'' (uncapacitated facility location, '''UFL'''), будут рассмотрены более подробно.

Хохбаум [25] разработала алгоритм O(log n)-аппроксимации для задачи UFL. Путем прямой редукции задачи о покрытии множества можно показать, что его коэффициент не может быть улучшен иначе как в случае <math>NP \subseteq DTIME[n^{O(log \; log \; n)}]</math> в силу результата, полученного Фейге [17]. Однако, если ограничение стоимости связано с некоторыми свойствами расстояния в метрическом пространстве, такими как <math>c_{ij} = c_{ji} \ge 0 \;</math> для всех <math>i \in \mathcal{F}, j \in \mathcal{C}</math> (неотрицательность и симметричность) и <math>c_{ij} + c_{ji'} + c_{i'j'} \ge c_{i j'} \;</math> для всех <math>i, i' \in \mathcal{F}, j, j' \in \mathcal{C}</math> (неравенство треугольника), то можно получить гарантии константной аппроксимации. Во всех нижеупомянутых результатах, за исключением задачи максимизации, предполагается, что стоимости удовлетворяют этим ограничениям. Для случая евклидовых расстояний между объектами и клиентами были получены схемы аппроксимации для некоторых задач о размещении объектов [5].

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

Во второй модели задачи о размещении объектов с мягкими ограничениями на пропускную способность задача меняется таким образом, чтобы y-переменные могли принимать неотрицательные целочисленные значения, что соответствует возможности открытия нескольких объектов с пропускной способностью u в каждом местоположении. Алгоритмы аппроксимации в данном случае дают решение, являющееся допустимым в рамках данной модифицированной модели. Легко показать, что гарантии аппроксимации, полученные для предыдущей модели, выполняются и в данном случае – речь идет о полученных Шмойсом алгоритмах 5,69-аппроксимации для варианта с возможностью разделения спроса и 7,62-аппроксимации для варианта без возможности разделения спроса. Последняя модель чаще всего рассматривается в более современных работах, поэтому именно на нее будут ссылаться авторы в параграфе, посвященном размещению объектов с мягкими ограничениями на пропускную способность.

Первым алгоритмом с константной гарантией эффективности стал алгоритм аппроксимации с коэффициентом 3,16, разработанный Шмойсом, Тардош и Аардал (см. выше). С тех пор в него были внесены значительные улучшения. Гуха и Хуллер [19, 20] доказали, что нижняя граница аппроксимации составляет 1,463, и предложили ''жадную процедуру пополнения''. Затем была разработана серия алгоритмов аппроксимации на базе LP-округления (см., например, [10, 13]). Существуют также жадные алгоритмы, использующие LP-релаксацию только неявно, для получения нижней границы при анализе прямо-двойственного подхода. В качестве примера можно привести алгоритм аппроксимации JMS с коэффициентом аппроксимации 1,61, разработанный Джейном, Мадьяном и Сабери [29]. Некоторые алгоритмы сочетают несколько разных техник – например, алгоритм аппроксимации Мадьяна, Йе и Чжана [39] с коэффициентом 1,52, использующий алгоритм JMS и жадную процедуру пополнения. Лучшую известную на сегодня гарантию аппроксимации (1,5) получил Бырка [10]. Она достигается путем сочетания рандомизированного алгоритма LP-округления с жадным алгоритмом JMS.

Для задачи о размещении объектов с мягкими ограничениями, в которой пропускная способность всех объектов равна, первые алгоритмы аппроксимации с константным коэффициентом разработали Шмойс и др. [51] для обоих вариантов – с возможностью разделения спроса и без таковой возможности (см. выше). Недавно был предложен алгоритм аппроксимации с коэффициентом 2 для решения задачи о размещении объектов с ограничениями на пропускную способность с единичным спросом без возможности разделения, разработанный Мадьяном и др. [39]. Разрыв целостности LP-релаксации для этой задачи также равен 2. Следовательно, для улучшения гарантии аппроксимации необходимо получить улучшенную нижнюю границу в оптимальном решении.

В варианте с жесткими ограничениями на пропускную способность важно разрешить разделение спроса, поскольку в противном случае даже задача существования становится слишком сложной. В случае возможности разделения спроса можно различать случаи с равными значениями пропускной способности, в которых <math>u_i = u \;</math> для всех <math>i \in \mathcal{F}</math>, и общий случай. Для задачи с равными значениями пропускной способности Чудак и Уильямсон получили алгоритм аппроксимации с коэффициентом 5,83 [14]. Первый алгоритм с константным коэффициентом аппроксимации, <math>\gamma = 8,53 + \epsilon \;</math>, для общей задачи разработали Пал, Тардош и Уэкслер [44]. Позднее Чжан, Чен и Йе [57] улучшили его, получив коэффициент 5,83 для задачи со значениями пропускной способности общего вида.

Основными нерешенными вопросами являются определение точного порога аппроксимируемости для задачи UFL и сокращение разрыва между верхней границей 1,5 [10] и нижней границей 1,463 [20]. Еще одна важная задача заключается в поиске лучших алгоритмов аппроксимации для задачи о k-медианах. В частности, любопытно было бы найти алгоритм аппроксимации для этой задачи с коэффициентом 2 на базе LP-подхода. Такой алгоритм помог бы определить разрыв целостности естественной LP-релаксации этой задачи, поскольку существуют простые примеры, доказывающие, что этот разрыв составляет не менее 2.