Аноним

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

Материал из WEGA

Задача о размещении объектов (посмотреть исходный код)

Версия от 14:01, 1 октября 2023

23 548 байт добавлено ,  1 октября 2023
м
нет описания правки
мНет описания правки
 
(не показаны 24 промежуточные версии этого же участника)
Строка 3: Строка 3:


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




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




В задаче UFL заданы множество <math>\mathcal{F}</math> из <math>n_f \;</math> ''объектов'' и множество <math>\mathcal{C} \;</math> из <math>n_c \;</math> ''клиентов'' (которые также могут называться ''городами'' или ''точками спроса''). Каждому объекту <math>i \in \mathcal{F}</math> назначена ''стоимость открытия объекта'' <math>f_i \;</math>. Кроме того, для каждого объекта <math>i \in \mathcal{F}</math> и клиента <math>j \in \mathcal{C}</math> задана ''стоимость соединения'' <math>c_{ij} \;</math>. Задача заключается в открытии подмножества объектов и соединении каждого клиента с открытым объектом таким образом, чтобы общая стоимость была минимальной. Заметим, что после определения множества открытых объектов оптимальным является соединение каждого клиента с открытым объектом, имеющее минимальную стоимость. Таким образом, задача заключается в нахождении множества <math>S \subseteq \mathcal{F}</math>, минимизирующего значение <math>\sum_{i \in S} f_i + \sum_{j \in C} min_{i \in S} \{ c_{ij} \}</math>. Это определение и определения других вариантов задачи о размещении объектов далее будут предполагать единичный спрос у каждого клиента. Обобщение определений до случая с заданным спросом у каждого отдельного клиента является тривиальным. Задачу UFL можно сформулировать в виде следующей целочисленной программы, предложенной Балински [7]. Пусть <math>y_i, i \in \mathcal{F},</math> равно 1 в случае, если объект открыт, и 0 в противном случае. <math>Пусть x_{ij}, i \in \mathcal{F}, j \in \mathcal{C}</math>, – доля клиента j, назначенная объекту i.
В задаче UFL заданы множество <math>\mathcal{F}</math> из <math>n_f \;</math> ''объектов'' и множество <math>\mathcal{C} \;</math> из <math>n_c \;</math> ''клиентов'' (которые также могут называться ''городами'' или ''точками спроса''). Каждому объекту <math>i \in \mathcal{F}</math> назначена ''стоимость открытия объекта'' <math>f_i \;</math>. Кроме того, для каждого объекта <math>i \in \mathcal{F}</math> и клиента <math>j \in \mathcal{C}</math> задана ''стоимость соединения'' <math>c_{ij} \;</math>. Задача заключается в открытии подмножества объектов и соединении каждого клиента с открытым объектом таким образом, чтобы общая стоимость была минимальной. Заметим, что после определения множества открытых объектов оптимальным является соединение каждого клиента с открытым объектом, имеющее минимальную стоимость. Таким образом, задача заключается в нахождении множества <math>S \subseteq \mathcal{F}</math>, минимизирующего значение <math>\sum_{i \in S} f_i + \sum_{j \in C} min_{i \in S} \{ c_{ij} \}</math>. Это определение и определения других вариантов задачи о размещении объектов далее будут предполагать единичный спрос у каждого клиента. Обобщение определений до случая с уникальным значением спроса у каждого отдельного клиента является тривиальным. Задачу UFL можно сформулировать в виде следующей целочисленной программы, предложенной Балински [7]. Пусть <math>y_i, i \in \mathcal{F},</math> равно 1 в случае, если объект открыт, и 0 в противном случае. <math>Пусть x_{ij}, i \in \mathcal{F}, j \in \mathcal{C}</math>, – доля клиента j, назначенная объекту i.




Строка 27: Строка 27:




Хохбаум [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].
Хохбаум [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].




Строка 38: Строка 38:




В ''задаче с ограничениями на пропускную способность'' для всех <math>i \in \mathcal{F}</math> добавляется ограничение на пропускную способность <math>\sum_{j \in C} x_{ij} \le u_i y_i</math>. Важно различать случаи ''с возможностью разделения'' и с его ''невозможностью'', а также случаи с ''мягким'' и ''жестким ограничением на пропускную способность''. В случае с возможностью разделения имеем <math>x \ge 0 \;</math>, что позволяет обслуживать клиента при помощи нескольких депо; в случае с невозможностью разделения необходимо выполнение <math>x \in \{ 0, 1 \}^{n_f \times b_c}</math>. Если каждый объект может быть открыт не более одного раза (т. е. <math>y_i \in \{ 0, 1 \} \;</math>), ограничения называются жесткими; если в задаче допускается открытие объекта i любое количество r раз для обслуживания <math>ru_i \;</math> клиентов, ограничения называются мягкими.
В ''задаче с ограничениями на пропускную способность'' для всех <math>i \in \mathcal{F}</math> добавляется ограничение на пропускную способность <math>\sum_{j \in C} x_{ij} \le u_i y_i</math>. Важно различать случаи ''с возможностью разделения'' и с его ''невозможностью'', а также случаи с ''мягким'' и ''жестким ограничением на пропускную способность''. В случае с возможностью разделения имеем <math>x \ge 0 \;</math>, что позволяет обслуживать клиента при помощи нескольких депо; в случае с невозможностью разделения должно выполняться соотношение <math>x \in \{ 0, 1 \}^{n_f \times b_c}</math>. Если каждый объект может быть открыт не более одного раза (т. е. <math>y_i \in \{ 0, 1 \} \;</math>), ограничения называются жесткими; если в задаче допускается открытие объекта i любое количество r раз для обслуживания <math>ru_i \;</math> клиентов, ограничения называются мягкими.




В k-уровневой задаче о размещении объектов заданы следующие начальные данные: множество клиентов C, k непересекающихся множеств <math>\mathcal{F}_1, ..., \mathcal{F}_k</math> объектов, стоимость открытия каждого объекта и стоимость соединения клиентов и объектов. Задача заключается в соединении каждого клиента j по пути, состоящему из открытых объектов <math>i_1, ... , i_k \;</math>, где <math>i_{\ell} = \mathcal{F}_{\ell}</math>. Стоимость соединения для этого объекта имеет вид <math>c_{ji_1} + c_{i_1 i_2} + ... + c_{i_{k - 1}i_k} \;</math>. Задача заключается в минимизации суммы стоимостей соединений и стоимостей открытия объектов.
В k-уровневой задаче о размещении объектов заданы следующие начальные данные: множество клиентов C, k непересекающихся множеств <math>\mathcal{F}_1, ..., \mathcal{F}_k</math> объектов, стоимость открытия каждого объекта и стоимость соединения клиентов и объектов. Задача заключается в соединении каждого клиента j по состоящему из открытых объектов пути <math>i_1, ... , i_k \;</math>, где <math>i_{\ell} = \mathcal{F}_{\ell}</math>. Стоимость соединения для этого объекта имеет вид <math>c_{ji_1} + c_{i_1 i_2} + ... + c_{i_{k - 1}i_k} \;</math>. Задача заключается в минимизации суммы стоимостей соединений и стоимостей открытия объектов.




Все вышеупомянутые задачи были рассмотрены в работе Шмойса, Тардош и Аардал [15] за исключением задач max-UFL, о k-центрах и k-медианах. Вариант max-UFL был добавлен по историческим причинам, а задачи о k-центрах и k-медианах включены в силу их богатой истории и близкого родства с задачей UFL. Результаты для задачи о размещении объектов с жесткими ограничениями на пропускную способность упомянуты, поскольку, по крайней мере с точки зрения приложения, эта модель более реалистична по сравнению с версией с мягкими ограничениями, рассмотренной в [51]. Для k-уровневой задачи о размещении объектов Шмойс и др. рассматривали случай k = 2. Здесь рассматривается задача для k общего вида.
Все вышеупомянутые задачи были рассмотрены в работе Шмойса, Тардош и Аардал [15] за исключением задач max-UFL, о k-центрах и k-медианах. Вариант max-UFL был добавлен по историческим причинам, а задачи о k-центрах и k-медианах включены в силу их богатой истории и близкого родства с задачей UFL. Результаты для задачи о размещении объектов с жесткими ограничениями на пропускную способность упомянуты, поскольку, по крайней мере с точки зрения практического применения, эта модель более реалистична по сравнению с версией с мягкими ограничениями, рассмотренной в [51]. Для k-уровневой задачи о размещении объектов Шмойс и др. рассматривали случай k = 2. Здесь рассматривается задача для k общего вида.




Строка 50: Строка 50:


== Основные результаты ==
== Основные результаты ==
Для решения задач о размещении объектов было предложено множество алгоритмов. Вначале будет приведено краткое описание алгоритмов Шмойса, Тардош и Аардал [51]. Затем будет представлен сжатый обзор основных результатов. Некоторые алгоритмы, дающие наилучшие значения гарантии аппроксимации у, основаны на решении задачи LP-релаксации при помощи полиномиального алгоритма, что может потребовать значительного времени; в то же время некоторые авторы предложили быстрые комбинаторные алгоритмы для задач о размещении объектов с менее привлекательными значениями гарантии y. В свете ограничений на объем занимаемой памяти более эффективно уделять внимание алгоритмам, обеспечивающим наилучшие значения гарантии аппроксимации. Дополнительные ссылки можно найти в обзорных статьях Шмойса [49,50] и Вайгена [55].
Для решения задач о размещении объектов было предложено множество алгоритмов. Вначале будет приведено краткое описание алгоритмов Шмойса, Тардош и Аардал [51]. Затем будет представлен сжатый обзор основных результатов. Некоторые алгоритмы, дающие наилучшие значения гарантии аппроксимации <math>\gamma \;</math>, основаны на решении задачи LP-релаксации при помощи полиномиального алгоритма, что может потребовать значительного времени; в то же время некоторые авторы предложили быстрые комбинаторные алгоритмы для задач о размещении объектов с менее привлекательными значениями гарантии <math>\gamma \;</math>. В свете ограничений на объем занимаемой памяти более эффективно уделять внимание алгоритмам, обеспечивающим наилучшие значения гарантии аппроксимации. Дополнительные ссылки можно найти в обзорных статьях Шмойса [49,50] и Вайгена [55].




'''Алгоритмы Шмойса, Тардош и Аардал'''
'''Алгоритмы Шмойса, Тардош и Аардал'''


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




Алгоритм выполняет LP-релаксацию, а затем в два этапа модифицирует полученное дробное решение. Первый этап, называемый ''фильтрацией'', предназначен для ограничения стоимости соединения каждого клиента с самым удаленным объектом, частично обслуживающим его. Для этого переменные <math>y_i \;</math>, обозначающие стоимость открытия объектов, пропорционально увеличиваются на константную величину, а затем переменные <math>x_{ij} \;</math>, обозначающие стоимость соединения, корректируются для использования ближайших возможных объектов.
Алгоритм вначале решает задачу LP-релаксации, а затем в два этапа модифицирует полученное дробное решение. Первый этап, называемый ''фильтрацией'', предназначен для ограничения стоимости соединения каждого клиента с самым удаленным объектом, частично обслуживающим его. Для этого переменные <math>y_i \;</math>, обозначающие стоимость открытия объектов, пропорционально увеличиваются на константную величину, а затем переменные <math>x_{ij} \;</math>, обозначающие стоимость соединения, корректируются для использования ближайших возможных объектов.


Для второго этапа используется понятие ''кластеризации'', позднее формализованное Чудаком и Шмойсом [13]. Основываясь на дробном решении, экземпляр разбивается на фрагменты, называемые ''кластерами''. У каждого кластера имеется отдельный клиент, называемый ''центром кластера''. Это производится путем итеративного выбора клиента, не охваченного предыдущими кластерами, в качестве центра кластера, и добавления к этому кластеру объектов, обслуживающих этого клиента в дробном решении, а также других клиентов, обслуживаемых этими объектами. Такое построение кластеров гарантирует, что объекты в каждом кластере открыты для количества клиентов, в сумме равного единице и, следовательно, после открытия объекта с наименьшей возможной стоимостью в каждом кластере суммарная уплаченная стоимость открытия объекта не превышает стоимость открытия объекта у дробного решения. Более того, выбирая клиентов в качестве центров кластеров жадным образом, алгоритм добивается того, чтобы каждый центр кластера минимизировал определенную стоимостную функцию для клиентов кластера. Оставшиеся клиента кластера также соединяются с открытым объектом. Для ограничения стоимости этого соединения используется неравенство треугольника для стоимостей соединений. Для задачи UFL этот алгоритм фильтрации и округления представляет собой алгоритм 4-аппроксимации, Шмойс и др. Также показали, что в случае замены этапа фильтрации ''рандомизированной фильтрацией'' можно получить гарантию аппроксимации 3,16.


В той же статье была выполнена адаптация алгоритма, с применением рандомизированной фильтрации и без нее, с целью получения алгоритмов аппроксимации для задачи о размещении объектов с мягкими ограничениями на пропускную способность, а также для двухуровневой задачи о размещении объектов без ограничений на пропускную способность. Далее будут обсуждаться результаты работы алгоритма с применением рандомизированной фильтрации.
Для второго этапа используется понятие ''кластеризации'', позднее формализованное Чудаком и Шмойсом [13]. Основываясь на дробном решении, экземпляр разбивается на фрагменты, называемые ''кластерами''. У каждого кластера имеется отдельный клиент, называемый ''центром кластера''. Процесс выполняется путем итеративного выбора клиента, не охваченного предыдущими кластерами, в качестве центра кластера, и добавления к этому кластеру объектов, обслуживающих этого клиента в дробном решении, а также других клиентов, обслуживаемых этими объектами. Такое построение кластеров гарантирует, что общая сумма открытых в каждом кластере объектов равна единице и, следовательно, после открытия объекта с наименьшей возможной стоимостью в каждом кластере суммарная уплаченная стоимость открытия объекта не превышает стоимость открытия объекта у дробного решения. Более того, выбирая клиентов в качестве центров кластеров жадным образом, алгоритм добивается того, чтобы каждый центр кластера минимизировал определенную стоимостную функцию для клиентов кластера. Оставшиеся клиенты кластера также соединяются с открытым объектом. Для ограничения стоимости этого соединения используется неравенство треугольника для стоимостей соединений. Для задачи UFL этот алгоритм фильтрации и округления представляет собой алгоритм 4-аппроксимации. Шмойс и др. также показали, что в случае замены этапа фильтрации ''рандомизированной фильтрацией'' можно получить гарантию аппроксимации 3,16.




Были рассмотрены два варианта задачи о размещении объектов с мягкими ограничениями на пропускную способность. Оба предполагают равную пропускную способность, т.е. ui = u для всех i 2 F . В первом варианте решение является «допустимым», если y-переменные либо принимают значение 0, либо имеют значение между 1 и y' > 1. Заметим, что y' не обязательно должно быть целым, так что построенное решение не обязательно является целочисленным. Это можно интерпретировать так, что каждому объекту i дозволяется расширяться, обеспечивая пропускную способность y'u со стоимостью y'fi. Алгоритм (y, y')-аппроксимации представляет собой полиномиальный алгоритм, приводящий к такому допустимому решению, общая стоимость которого не более чем в у раз превышает истинную оптимальную стоимость, а именно, с 2 f0; 1gnf. Шмойс и др. разработали алгоритм (5,69; 4,24)-аппроксимации для варианта этой задачи с возможностью разделения и алгоритм (7,62; 4,29)-аппроксимации для варианта без возможности разделения.
В той же статье была выполнена адаптация алгоритма, с применением рандомизированной фильтрации и без нее, с целью получения аппроксимационных алгоритмов для задачи о размещении объектов с мягкими ограничениями на пропускную способность, а также для двухуровневой задачи о размещении объектов без ограничений на пропускную способность. Далее будут обсуждаться результаты работы алгоритма с применением рандомизированной фильтрации.




Во второй модели о размещении объектов с мягкими ограничениями на пропускную способность задача меняется таким образом, чтобы y-переменные могли принимать неотрицательные целочисленные значения, благодаря чему можно открывать несколько объектов с пропускной способностью u в каждом местоположении. Алгоритмы аппроксимации в данном случае дают решение, являющееся допустимым в рамках данной модифицированной модели. Легко показать, что гарантии аппроксимации, полученные для предыдущей модели, выполняются и в данном случае – речь идет о полученных Шмойсом алгоритмах 5,69-аппроксимации для варианта с возможностью разделения спроса и 7,62-аппроксимации для варианта без возможности разделения спроса. Последняя модель чаще всего рассматривается в более современных работах, поэтому именно на нее будут ссылаться авторы в параграфе, посвященном размещению объектов с мягкими ограничениями на пропускную способность.
Были рассмотрены два варианта задачи о размещении объектов с мягкими ограничениями на пропускную способность. Оба предполагают равную пропускную способность, т. е. <math>u_i = u \;</math> для всех <math>i \in \mathcal{F}</math>. В первом варианте решение является «допустимым», если y-переменные либо принимают значение 0, либо имеют значение между 1 и <math>\gamma' \ge 1 \;</math>. Заметим, что <math>\gamma' \;</math> не обязательно должно быть целым, так что построенное решение не обязательно является целочисленным. Это можно интерпретировать так, что каждому объекту i дозволяется расширяться, обеспечивая пропускную способность <math>\gamma' u \;</math> со стоимостью <math>\gamma' f_i \;</math>. Алгоритм <math>(\gamma, \gamma') \;</math>-аппроксимации представляет собой полиномиальный алгоритм, приводящий к такому допустимому решению, общая стоимость которого не более чем в <math>\gamma \;</math> раз превышает истинную оптимальную стоимость, имеющую место в случае <math>y \in \{0, 1 \}^{n_f} \;</math>. Шмойс и др. разработали алгоритм (5,69, 4,24)-аппроксимации для варианта этой задачи с возможностью разделения и алгоритм (7,62, 4,29)-аппроксимации для варианта без возможности разделения.




UFL
Во второй модели задачи о размещении объектов с мягкими ограничениями на пропускную способность задача меняется таким образом, чтобы y-переменные могли принимать неотрицательные целочисленные значения, что соответствует возможности открытия нескольких объектов с пропускной способностью u в каждом местоположении. Аппроксимационные алгоритмы в данном случае дают решение, являющееся допустимым в рамках данной модифицированной модели. Легко показать, что гарантии аппроксимации, полученные для предыдущей модели, выполняются и в данном случае – речь идет о полученных Шмойсом алгоритмах 5,69-аппроксимации для варианта с возможностью разделения спроса и 7,62-аппроксимации для варианта без возможности разделения спроса. Последняя модель чаще всего рассматривается в более современных работах, поэтому именно на нее будут ссылаться авторы в параграфе, посвященном размещению объектов с мягкими ограничениями на пропускную способность.
 
 
'''UFL'''
 
Первым алгоритмом с константной гарантией эффективности стал аппроксимационный алгоритм с коэффициентом 3,16, разработанный Шмойсом, Тардош и Аардал (см. выше). С тех пор в него были внесены значительные улучшения. Гуха и Хуллер [19, 20] доказали, что нижняя граница аппроксимации составляет 1,463, и предложили ''жадную процедуру пополнения''. Затем была разработана серия аппроксимационных алгоритмов на базе LP-округления (см., например, [10, 13]). Существуют также жадные алгоритмы, использующие LP-релаксацию только неявно, для получения нижней границы при анализе прямо-двойственного подхода. В качестве примера можно привести аппроксимационный алгоритм JMS с коэффициентом аппроксимации 1,61, разработанный Джейном, Мадьяном и Сабери [29]. Некоторые алгоритмы сочетают несколько разных техник – например, аппроксимационный алгоритм Мадьяна, Йе и Чжана [39] с коэффициентом 1,52, использующий алгоритм JMS и жадную процедуру пополнения. Лучшую известную на сегодня гарантию аппроксимации (1,5) получил Бырка [10]. Она достигается путем сочетания рандомизированного алгоритма LP-округления с жадным алгоритмом JMS.
 
 
'''max-UFL'''
 
Первый алгоритм с константным коэффициентом аппроксимации в 1977 году разработали Корнюжо и др. [15] для задачи max-UFL. Они показали, что при открытии одного объекта за раз жадным образом, выбирая для открытия объект с самой высокой маржинальной прибылью, до тех пор, пока не останется объектов с положительной маржинальной прибылью, получается алгоритм с коэффициентом аппроксимации <math>(1 - 1/e) \approx 0,632 \;</math>. Лучший известный на сегодня коэффициент аппроксимации (0,828) получили Агеев и Свириденко [2].
 
 
'''k-медианы, k-центры'''
 
Первый алгоритм с константным коэффициентом аппроксимации для задачи о k-медианах был разработан Чарикаром, Гухой, Тардош и Шмойсом [11]. Этот алгоритм LP-округления имеет коэффициент аппроксимации 6 2/3. Лучший известный на сегодня коэффициент аппроксимации, <math>3 + \epsilon \;</math>, при помощи эвристики локального поиска получили Арья и др. [6] (см. также отдельные разделы для метода k-медиан и задачи о размещении объектов).
 
 
Первый алгоритм с константным коэффициентом аппроксимации (равным 2) для задачи о k-центрах разработали Хохбаум и Шмойс [26]. Эта гарантия эффективности является наилучшей за исключением случая P = NP.
 
 
'''Задача о размещении объектов с ограничениями на пропускную способность'''
 
Для задачи о размещении объектов с мягкими ограничениями, в которой пропускная способность всех объектов равна, первые аппроксимационные алгоритмы с константным коэффициентом разработали Шмойс и др. [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 для задачи со значениями пропускной способности общего вида.
 
 
'''k-уровневая задача'''
 
Первый алгоритм с константным коэффициентом аппроксимации для k = 2 разработали Шмойс и др. [51], получив <math>\gamma = 3,16 \;</math>. Для k общего вида первый алгоритм с <math>\gamma = 3 \;</math> предложили Аардал, Чудак и Шмойс [1]. Для случая k = 2 Чжан [56] разработал алгоритм с коэффициентом аппроксимации 1,77. Он также показал, что для k = 3 и k = 4 задачу можно аппроксимировать с <math>\gamma = 2,523 \;</math>* и <math>\gamma = 2,81 \;</math>, соответственно.
''(* Это значение у слегка отличается от значения 2,51, приведенного в статье. Исходное рассуждение содержало небольшую ошибку в расчетах)''.
 
== Применение ==
Задача о размещении объектов широко применяется в области исследования операций. В книге под редакцией Мирчандани и Фрэнсиса [42], а также в книге Немхаузера и Уолси [43] можно найти обзоры и описания способов применения алгоритмов размещения объектов в таких задачах, как размещение заводов и локализация банковских счетов. Недавно эти алгоритмы также нашли применение в таких задачах проектирования сетей, как размещение маршрутизаторов и кэш-памяти [22, 36], агломерация трафика или данных [4, 21], а также репликация веб-серверов в сети распространения контента [31, 45].
 
== Открытые вопросы ==
Основными нерешенными вопросами являются определение точного порога аппроксимируемости для задачи UFL и сокращение разрыва между верхней границей 1,5 [10] и нижней границей 1,463 [20]. Еще одна важная задача заключается в поиске лучших аппроксимационных алгоритмов для задачи о k-медианах. В частности, любопытно было бы найти аппроксимационный алгоритм для этой задачи с коэффициентом 2 на базе LP-подхода. Такой алгоритм помог бы определить разрыв целостности естественной LP-релаксации этой задачи, поскольку существуют простые примеры, доказывающие, что этот разрыв составляет не менее 2.
 
== Экспериментальные результаты ==
Джейн и др. [28] опубликовали результаты экспериментального сравнения различных прямо-двойственных алгоритмов. Более комплексное экспериментальное исследование нескольких алгоритмов – прямо-двойственных, на базе локального поиска и эвристических – было выполнено Хефером [27]. Коллекцию наборов данных для UFL и некоторых других задач о размещении объектов можно найти в библиотеке OR-library под руководством Бизли [9].
 
== См. также ==
* [[Задача присваивания]]
* [[Упаковка контейнеров]] (задача о размещении объектов с жесткими ограничениями на пропускную способность без возможности разделения спроса)
* [[Компоновка схемы]]
* [[Жадные алгоритмы покрытия множества]] (вариант UFL с жесткими ограничениями, в котором объекты могут строиться в любых местоположениях по одной и той же стоимости)
* [[Локальные аппроксимации задач упаковки и покрытия]]
* [[Локальный поиск для задачи о k-медианах и задачи о размещении объектов]]
 
== Литература ==
1. Aardal, K., Chudak, F.A., Shmoys, D.B.: A 3-approximation algorithm for the k-level uncapacitated facility location problem. Inf. Process. Lett. 72,161-167 (1999)
 
2. Ageev, A.A., Sviridenko, M.I.: An 0.828-approximation algorithm for the uncapacitated facility location problem. Discret.Appl. Math. 93,149-156 (1999)
 
3. Anagnostopoulos, A., Bent, R., Upfal, E., van Hentenryck, P.: A simple and deterministic competitive algorithm for online facility location. Inf. Comput. 194(2), 175-202 (2004)
 
4. Andrews, M., Zhang, L.:The access network design problem. In: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 40-49. IEEE Computer Society, Los Alamitos, CA, USA (1998)
 
5. Arora, S., Raghavan, P., Rao, S.: Approximation schemes for Euclidean k-medians and related problems. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), pp. 106-113. ACM, New York (1998)
 
6. Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pp. 21 -29. ACM, New York (2001)
 
7. Balinski, M.L.: On finding integer solutions to linear programs. In: Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems, pp. 225-248 IBM, White Plains, NY (1966)
 
8. Balinski, M.L., Wolfe, P.: On Benders decomposition and a plant location  problem. In ARO-27. Mathematica  Inc. Princeton (1963)
 
9. Beasley, J.E.: Operations research library. http://people.brunel.ac.uk/~mastjjb/jeb/info.html. Accessed 2008
 
10. Byrka, J.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. In: Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Lecture Notes in Computer Science, vol. 4627, pp. 29-43. Springer, Berlin (2007)
 
11. Charikar, M., Guha, S., Tardos, E., Shmoys, D.B.: A constant-factor approximation algorithm for the k-median problem. In: Proceedings of the 31 st Annual ACM Symposium on Theory of Computing (STOC), pp. 1-10. ACM, New York (1999)
 
12. Charikar, M., Khuller, S., Mount, D., Narasimhan, G.: Facility location with outliers. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 642-651. SIAM, Philadelphia (2001)
 
13. Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM JComput.33(1), 1-25(2003)
 
14. Chudak, F.A., Wiliamson, D.P.: Improved approximation algorithms for capacitated facility location problems. In: Proceedings of the 7th Conference on Integer Programing and Combinatorial Optimization (IPCO). Lecture Notes in Computer Science, vol. 1610, pp. 99-113. Springer, Berlin (1999)
 
15. Cornuejols, G., Fisher, M.L., Nemhauser, G.L.: Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Manag. Sci.8, 789-810 (1977)
 
16. Erlenkotter, D.: A dual-based procedure for uncapacitated facility location problems. Oper. Res. 26,992-1009 (1978)
 
17. Feige, U.: A threshold of lnn for approximating set cover. J. ACM 45,634-652 (1998)
 
18. Fotakis, D.: On the competitive ratio for online facility location. In: Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 2719, pp. 637-652. Springer, Berlin (2003)
 
19. Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. In: Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 228-248. SIAM, Philadelphia (1998)
 
20. Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. J. Algorithms 31, 228-248 (1999)
 
21. Guha, S., Meyerson, A., Munagala, K.: A constant factor approximation for the single sink edge installation problem. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pp. 383-388. ACM Press, New York (2001)
 
22. Guha, S., Meyerson, A., Munagala, K.: Hierarchical placement and network design problems. In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 603-612. IEEE Computer Society, Los Alamitos, CA, USA (2000)
 
23. Gupta, A., Pal, M., Ravi, R., Sinha, A.: Boosted sampling: approximation algorithms for stochastic optimization. In: Proceedings of the 36st Annual ACM Symposium on Theory of Computing (STOC), pp. 417-426. ACM, New York (2004)
 
24. Hajiaghayi, M., Mahdian, M., Mirrokni, V.S.: The facility location problem with general cost functions. Netw. 42(1), 42-47 (2003)
 
25. Hochbaum, D.S.: Heuristics for the fixed cost median problem. Math. Program. 22(2), 148-162(1982)
 
26. Hochbaum, D.S., Shmoys, D.B.: A best possible approximation algorithm for the k-center problem. Math. Oper. Res. 10, 180-184(1985)
 
27. Hoefer, M.: Experimental comparison of heuristic and approximation algorithms for uncapacitated facility location. In: Proceedings of the 2nd International Workshop on Experimental and Efficient Algorithms (WEA). Lecture Notes in Computer Science, vol. 2647, pp. 165-178. Springer, Berlin (2003)
 
28. Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Approximation algorithms for facility location via dual fitting with factor-revealing LP. J. ACM 50(6), 795-824 (2003)
 
29. Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of the 34st Annual ACM Symposium on Theory of Computing (STOC) pp. 731-740, ACM Press, New York (2002)
 
30. Jain, K., Vazirani, V.V.: An approximation algorithm for the fault tolerant metric facility location problem. In: Approximation Algorithms for Combinatorial Optimization, Proceedings of APPROX (2000), vol. (1913) of Lecture Notes in Computer Science, pp. 177-183. Springer, Berlin (2000)
 
31. Jamin, S., Jin, C., Jin, Y., Raz, D., Shavitt, Y., Zhang, L.: On the placement of internet instrumentations. In: Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), vol. 1, pp. 295-304. IEEE Computer Society, Los Alamitos, CA, USA (2000)
 
32. Karger, D., Minkoff, M.: Building Steiner trees with incomplete global knowledge. In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, pp. 613-623. Los Alamitos (2000)
 
33. Krarup, J., Pruzan, P.M.: Ingredients of locational analysis. In: Mirchandani, P., Francis, R. (eds.) Discrete Location Theory, pp. 1-54.Wiley,NewYork(1990)
 
34. Krarup, J., Pruzan, P.M.:The simple plant location problem: Survey and synthesis. Eur. J.Oper. Res. 12, 38-81 (1983)
 
35. Kuehn, A.A., Hamburger, M.J.: A heuristic program for locating warehouses. Manag. Sci.9, 643-666 (1963)
 
36. Li, B., Golin, M., Italiano, G., Deng, X., Sohraby, K.: On the optimal placement of web proxies in the internet. In: Proceedings of the 18th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pp. 1282—1290. IEEE Computer Society, Los Alamitos (1999)
 
37. Mahdian, M.: Facility Location and the Analysis of Algorithms through Factor-Revealing Programs. Ph.D. thesis, MIT, Cambridge (2004)
 
38. Mahdian, M., Pal, M.: Universal facility location. In: Proceedings of the 11th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 2832, pp. 409-421. Springer, Berlin (2003)
 
39. Mahdian, M., Ye, Y., Zhang, J.: Approximation algorithms for metric facility location problems. SIAM J. Comput. 36(2), 411-432 (2006)
 
40. Manne, A.S.: Plant location under economies-of-scale - decentralization and computation. Manag. Sci.11,213-235 (1964)
 
41. Meyerson, A.: Online facility location. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 426-431. IEEE Computer Society, Los Alamitos (2001)
 
42. Mirchandani, P.B., Francis, R.L.: Discrete Location Theory. Wiley, New York (1990)
 
43. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1990)
 
44. Pal, M., Tardos, E., Wexler, T.: Facility location with nonuniform hard capacities. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 329-338. IEEE Computer Society, Los Alamitos (2001)
 
45. Qiu, L., Padmanabhan, V.N., Voelker, G.: On the placement of web server replicas. In: Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ), pp. 1587-1596. IEEE Computer Society, Los Alamitos (2001)
 
46. Ravi, R., Sinha, A.: Hedging uncertainty: Approximation algorithms for stochastic optimization problems. Math. Program. 108(1),97-114(2006)
 
47. Ravi, R., Sinha, A.: Integrated logistics: Approximation algorithms combining facility location and network design. In: Proceedings of the 9th Conference on Integer Programming and Combinatorial Optimization (IPCO). Lecture Notes in Computer Science, vol. 2337, pp. 212-229. Springer, Berlin (2002)
 
48. Ravi, R., Sinha, A.: Multicommodity facility location. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 342-349. SIAM, Philadelphia (2004)
 
49. Shmoys, D.B.: Approximation algorithms for facility location problems. In: Jansen, K., Khuller, S. (eds.) Approximation Algorithms for Combinatorial Optimization. Lecture Notes in Computer Science, vol. 1913, pp. 27-33. Springer, Berlin (2000)
 
50. Shmoys, D.B.: The design and analysis of approximation algorithms: Facility location as a case study. In: Thomas, R.R., Hosten, S., Lee, J. (eds) Proceedings of Symposia in Appl. Mathematics, vol. 61, pp. 85-97. AMS, Providence, RI, USA (2004)
 
51. Shmoys, D.B., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), pp. 265-274. ACM Press, New York (1997)
 
52. Svitkina, Z., Tardos, E.: Facility location with hierarchical facility costs. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA), pp. 153-161. SIAM, Philadelphia, PA, USA (2006)
 
53. Swamy, C., Kumar, A.: Primal-dual algorithms for connected facility location problems. Algorithmica 40(4), 245-269 (2004)
 
54. Swamy, C., Shmoys, D.B.: Fault-tolerant facility location. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 735-736. SIAM, Philadelphia (2003)
 
55. Vygen, J.: Approximation algorithms for facility location problems (lecture notes). Technical report No. 05950-OR, Research Institute for Discrete Mathematics, University of Bonn (2005) http://www.or.uni-bonn.de/~vygen/fl.pdf
 
56. Zhang, J.: Approximating the two-level facility location problem via a quasi-greedy approach. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 808-817. SIAM, Philadelphia (2004). Also, Math. Program. 108,159-176(2006)
 
57. Zhang, J., Chen, B., Ye, Y.: A multiexchange local search algorithm for the capacitated facility location problem. Math. Oper. Res. 30(2), 389-403 (2005)
Irina
4430

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/12951...15174