Дробно-линейные задачи об упаковке и покрытии

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

В данной статье приводится обзор быстрых алгоритмов, дающих приближенные решения для задач, которые могут быть сформулированы в виде задач линейного программирования (LP) и, следовательно, могут быть решено точно, хотя это потребует большего времени выполнения. Общий формат семейства таких задач имеет следующий вид. Дано множество из m неравенств с n переменными и оракул, который выдает решение подходящей задачи оптимизации над выпуклым множеством [math]\displaystyle{ P \in \mathbb{R}^n }[/math]. Найти решение [math]\displaystyle{ x \in P \; }[/math], удовлетворяющее неравенствам, или обнаружить, что такого решения x не существует. Принципиальная идея алгоритма заключается в следующем. Алгоритм всегда начинает работу с недопустимого решения x и использует оракул оптимизации для поиска направления, в котором степень нарушения неравенств может быть уменьшена; это выполняется при помощи расчета вектора y, представляющего собой решение двойственной задачи относительно x. После этого x аккуратно изменяется в этом направлении, и процесс повторяется до тех пор, пока x не становится «приближенно» допустимым. Далее будут рассмотрены конкретные задачи и соответствующие им оракулы оптимизации, а также определены другие нотации используемой «аппроксимации».

• Дробно-линейная задача об упаковке и ее оракул определяются следующим образом.

PACKING (упаковка): Даны матрица A размера [math]\displaystyle{ m \times n }[/math], b > 0 и выпуклое множество [math]\displaystyle{ P \in \mathbb{R}^n }[/math], такое, что [math]\displaystyle{ Ax \ge 0, \forall x \in P }[/math]. Существует ли такое [math]\displaystyle{ x \in P \; }[/math], что [math]\displaystyle{ Ax \le b \; }[/math]?

PACK_ORACLE (оракул упаковки): Даны m-мерный вектор [math]\displaystyle{ y \ge 0 \; }[/math] и вышеописанное множество P. Вернуть [math]\displaystyle{ \bar{x} := arg \; min \{ y^T Ax : x \in P \} }[/math].

• Ослабленная дробно-линейная задача об упаковке и ее оракул определяются следующим образом.

RELAXED PACKING (упаковка с ослабленными ограничениями): Даны [math]\displaystyle{ \varepsilon \gt 0 \; }[/math], матрица A размера [math]\displaystyle{ m \times n }[/math], b > 0 и выпуклые множества [math]\displaystyle{ P \in \mathbb{R}^n }[/math] и [math]\displaystyle{ \hat{P} \in \mathbb{R}^n }[/math], такие, что [math]\displaystyle{ P \subseteq \hat{P} }[/math] и [math]\displaystyle{ Ax \ge 0, \forall x \in P }[/math]. Найти такое [math]\displaystyle{ x \in \hat{P} }[/math], что [math]\displaystyle{ Ax \le (1 + \varepsilon)b \; }[/math], или показать, что [math]\displaystyle{ \nexists x \in P }[/math], такого, что [math]\displaystyle{ Ax \le b \; }[/math].

REL_PACK_ORACLE (оракул упаковки с ослабленными ограничениями): Даны m-мерный вектор [math]\displaystyle{ y \ge 0 \; }[/math] и вышеописанные множества [math]\displaystyle{ P, \hat{P} }[/math]. Вернуть [math]\displaystyle{ \bar{x} \in \hat{P} }[/math], такое, что [math]\displaystyle{ y^T Ax \le min \{y^T Ax : x \in P \} }[/math].

• Дробно-линейная задача о покрытии и ее оракул определяются следующим образом.

COVERING (покрытие): Даны матрица A размера [math]\displaystyle{ m \times n }[/math], b > 0 и выпуклое множество [math]\displaystyle{ P \in \mathbb{R}^n }[/math], такое, что [math]\displaystyle{ Ax \ge 0, \forall x \in P }[/math]. Существует ли такое [math]\displaystyle{ x \in P \; }[/math], что [math]\displaystyle{ Ax \le b \; }[/math]?

COVER _PACK_ORACLE (оракул покрытия): Даны m-мерный вектор [math]\displaystyle{ y \ge 0 \; }[/math] и вышеописанное множество P. Вернуть [math]\displaystyle{ \bar{x} := arg \; max \{ y^T Ax : x \in P \} }[/math]

• Задача об одновременных упаковке и покрытии и ее оракул определяются следующим образом.

SIMULTANEOUS PACKING AND COVERING (одновременные упаковка и покрытие): Даны матрицы [math]\displaystyle{ \hat{A} }[/math] и [math]\displaystyle{ A \; }[/math] размера [math]\displaystyle{ \hat{m} \times n }[/math] и [math]\displaystyle{ (m - \hat{m}) \times n }[/math], соответственно, [math]\displaystyle{ b \gt 0 \; }[/math] и [math]\displaystyle{ \hat{b} \gt 0 \; }[/math], а также выпуклое множество [math]\displaystyle{ P \in \mathbb{R}^n }[/math], такое, что [math]\displaystyle{ Ax \ge 0, \hat{A}x \ge 0, \forall x \in P }[/math]. Существует ли такое [math]\displaystyle{ x \in P \; }[/math], что [math]\displaystyle{ Ax \le b \; }[/math] и [math]\displaystyle{ \hat{A}x \ge \hat{b} }[/math]?

SIM_ORACLE (оракул упаковки и покрытия): Даны вышеописанное множество P, константа v и решение двойственной задачи [math]\displaystyle{ (y, \hat{y}) }[/math]. Вернуть [math]\displaystyle{ \bar{x} \in P }[/math], такое, что [math]\displaystyle{ A \bar{x} \lt vb }[/math] и выполняется

[math]\displaystyle{ y^T A \bar{x} - \sum_{i \in I(v, \bar{x})} \hat{y}_i \hat{a}_i \bar{x} = min \{ y^T Ax - \sum_{i \in I(v, x)} \hat{y}_i \hat{a}_i x }[/math] : x является вершиной P, такой, что [math]\displaystyle{ Ax \le vb \} }[/math], где [math]\displaystyle{ I(v,x) := \{i : \hat{a}_i x \le v b_i \} }[/math].

• Общая задача и ее оракул определяются следующим образом.

GENERAL (общая задача): Даны матрица A размера [math]\displaystyle{ m \times n }[/math], произвольный вектор b и выпуклое множество [math]\displaystyle{ P \in \mathbb{R}^n }[/math]. Существует ли такое [math]\displaystyle{ x \in P \; }[/math], что [math]\displaystyle{ Ax \le b \; }[/math]?

GEN _ORACLE (оракул общей задачи): Даны m-мерный вектор [math]\displaystyle{ y \ge 0 \; }[/math] и вышеописанное множество P. Вернуть [math]\displaystyle{ \bar{x} := arg \; min \{ y^T Ax : x \in P \} }[/math].

Определения и нотация

Для параметра ошибки [math]\displaystyle{ \varepsilon \gt x0 \; }[/math] точка [math]\displaystyle{ x \in P \; }[/math] является [math]\displaystyle{ \varepsilon \; }[/math]-приближенным решением для дробно-линейной задачи упаковки (или покрытия), если [math]\displaystyle{ Ax \le (1 + \varepsilon) \; b }[/math] (или [math]\displaystyle{ Ax \ge (1 - \varepsilon) \; b }[/math], соответственно). С другой стороны, если [math]\displaystyle{ x \in P \; }[/math] удовлетворяет условию [math]\displaystyle{ Ax \le b \; }[/math] (или [math]\displaystyle{ Ax \ge b) \; }[/math], то x является точным решением. Для общей задачи GENERAL, параметра ошибки [math]\displaystyle{ \varepsilon \gt 0 \; }[/math] и положительного вектора отклонения d значение [math]\displaystyle{ x \in P \; }[/math] является [math]\displaystyle{ \varepsilon \; }[/math]-приближенным решением, если [math]\displaystyle{ Ax \le b + \varepsilon \; d }[/math], и точным решением, если [math]\displaystyle{ Ax \le b \; }[/math]. [math]\displaystyle{ \varepsilon \; }[/math]-ослабленная разрешающая процедура для этих задач либо находит [math]\displaystyle{ \varepsilon \; }[/math]-приближенное решение, либо обоснованно сообщает о том, что точного решения не существует. В общем случае в задаче минимизации (максимизации) алгоритм [math]\displaystyle{ (1 + \varepsilon) \; }[/math]-аппроксимации ([math]\displaystyle{ (1 - \varepsilon) \; }[/math]-аппроксимации) возвращает значение, не более чем в [math]\displaystyle{ (1 + \varepsilon) \; }[/math] (не менее чем в [math]\displaystyle{ (1 - \varepsilon) \;) }[/math] раз, соответственно) отличающееся от оптимального.

Время выполнения разработанных алгоритмов полиномиально зависит от [math]\displaystyle{ \varepsilon^{-1} \; }[/math] для любого параметра ошибки [math]\displaystyle{ \varepsilon \gt 0 \; }[/math], а также от ширины [math]\displaystyle{ \rho \; }[/math] выпуклого множества P, относящегося к множеству неравенств [math]\displaystyle{ Ax \le b \; }[/math] или [math]\displaystyle{ Ax \ge b \; }[/math], определяющему решаемую задачу. Более точно ширина [math]\displaystyle{ \rho \; }[/math] определяется следующим образом для каждой из рассматриваемых задач:

• PACKING: [math]\displaystyle{ \rho := max_i \; max_{x \in P} \frac{a_i x}{b_i} }[/math]

• RELAXED PACKING: [math]\displaystyle{ \hat{\rho} := max_i \; max_{x \in \hat{P}} \frac{a_i x}{b_i} }[/math]

• COVERING: [math]\displaystyle{ \rho := max_i \; max_{x \in P} \frac{a_i x}{b_i} }[/math]

• SIMULTANEOUS PACKING AND COVERING: [math]\displaystyle{ \rho := max_{x \in P} \; max \{ max_i \frac{a_i x}{b_i}, max_i \frac{\hat{a}_i x}{\hat{b}_i} \} }[/math]

• GENERAL: [math]\displaystyle{ \rho := max_i \; max_{x \in P} \frac{|a_i x - b_i|}{d_i} + 1 }[/math], где d – вышеупомянутый вектор отклонения.

Основные результаты

Многие из нижеприведенных результатов были представлены в работе [7], в которой рассматривалась модель вычислений с точной арифметикой на вещественных числах и возведением в степень, занимающим один шаг. Однако, как отмечали авторы [7], эти алгоритмы могут быть преобразованы для выполнения на RAM-модели с использованием подходящей операции возведения в степень, версии оракула, выдающего почти оптимальное решение, и ограничения на количество используемых чисел, полиномиальное относительно длины входных данных и аналогичное количеству чисел, используемых в точных алгоритмах линейного программирования. Однако они оставляют открытым вопрос построения [math]\displaystyle{ \varepsilon \; }[/math]-приближенных решений, использующих полилогарифмическую точность для общего случая рассматриваемых ими задач (что можно сделать, например, в задаче управления несколькими товарными потоками [4]).

Теорема 1. Для [math]\displaystyle{ 0 \lt \varepsilon \le 1 \; }[/math] существует детерминированная [math]\displaystyle{ \varepsilon \; }[/math]-ослабленная разрешающая процедура для дробно-линейной задачи упаковки, использующая [math]\displaystyle{ O(\varepsilon^{-2} \rho \; log(m \varepsilon^{-1})) }[/math] вызовов оракула PACK_ORACLE плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами.

Для случая, когда P записывается в виде произведения политопов меньшей размерности, т. е. [math]\displaystyle{ P = P^1 \times ... \times P^k }[/math], где каждый политоп [math]\displaystyle{ P^l \; }[/math] имеет ширину [math]\displaystyle{ \rho^l \; }[/math] (очевидно, что [math]\displaystyle{ \rho \le \sum_l \rho^l }[/math]), и имеется отдельный оракул PACK_ORACLE для каждого [math]\displaystyle{ P^l, A^l \; }[/math], тогда рандомизация может использоваться для потенциального ускорения работы алгоритма. Обозначив за PACK_ORACLE[math]\displaystyle{ _l }[/math] оракул для [math]\displaystyle{ P^l, A^l \; }[/math], получаем следующий результат:

Теорема 2. Для [math]\displaystyle{ 0 \lt \varepsilon \le 1 \; }[/math] существует рандомизированная [math]\displaystyle{ \varepsilon \; }[/math]-ослабленная разрешающая процедура для дробно-линейной задачи упаковки, предположительно использующая [math]\displaystyle{ O(\varepsilon^{-2} (\sum_l \rho^l) \; log(m \varepsilon^{-1}) + k \; log(\rho \varepsilon^{-1})) }[/math] вызовов оракула PACK_ORACLE[math]\displaystyle{ _l }[/math] для некоторого [math]\displaystyle{ l \in \{ 1, ..., k \} }[/math] (возможно, [math]\displaystyle{ l \; }[/math] различно для каждого вызова) плюс время, необходимое для вычисления [math]\displaystyle{ \sum_l A^l x^l \; }[/math] для текущего компонента итерации [math]\displaystyle{ x = (x^1, x^2, ... x^k) \; }[/math] между последовательными вызовами.

Теорема 2 также выполняется для задачи RELAXED PACKING, если заменить [math]\displaystyle{ \rho \; }[/math] на [math]\displaystyle{ \hat{\rho} }[/math], а PACK_ORACLE – на REL_PACK_ORACLE.

Фактически нам необходима только приближенная версия PACK_ORACLE. Пусть <math>C_{\rho}(y) \;<\math> – минимальная стоимость <math>y^T Ax \;<\math>, достигаемая алгоритмом PACK_ORACLE для заданного y.

<math><\math> Теорема 3. Заменим PACK_ORACLE на оракула, который для заданного вектора y > 0 находит точку x € P, такую, что yTAx < (1 + "/2)CP(y) + {el2)Xyrb, где X минимально, так что неравенство Ax < Xb удовлетворяется на текущей итерации x. Тогда теоремы 1 и 2 по-прежнему верны.

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

Схожие результаты можно доказать для дробно-линейной задачи о покрытии (COVER_ORACLEl определяется аналогично PACK_ORACLEL):

Теорема 4. Для 0 < " < 1 существует детерминированная "-ослабленная разрешающая процедура для дробно-линейной задачи о покрытии, использующая O(m + plog m + s~2p\og(ms~1)) вызовов оракула COVER_ORACLE плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами.

Теорема 5. Для 0 < " < 1 существует рандомизированная "-ослабленная разрешающая процедура для дробно-линейной задачи о покрытии, предположительно использующая O(mk + Q^ p')log m+ k\oge~l + E~2(Hi P/)log(m£~1)) вызовов оракула COVER_ORACLEL для некоторого l 2 f1. kg (возможно, l различно для каждого вызова) плюс время, необходимое для вычисления Pl Al xl для текущего компонента итерации x = (x1 ,x2,..; xk) между последовательными вызовами. Пусть CC(y) – максимальная стоимость cost yTAx, достигаемая алгоритмом COVER_ORACLE для заданного y.

Теорема 6. Заменим COVER_ORACLE на оракула, который для заданного вектора y > 0 находит точку x € P, такую, что yTAx > (1 — "/2)CC(y) — {el2)Xyrb, где X максимально, так что неравенство Ax > Xb удовлетворяется на текущей итерации x. Тогда теоремы 4 и 5 по-прежнему верны.

Для задачи об одновременных упаковке и покрытии верно следующее:

Теорема 7. Для 0 < " < 1 существуют рандомизированная "-ослабленная разрешающая процедура для дробно-линейной задачи одновременных упаковке и покрытии, предположительно использующая O(m2(log2p)£~2log(£~1mlogp)) вызовов оракула SIM_ORACLE, и детерминированная версия, использующая на oflog p вызовов больше, плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами.

Для общей задачи GENERAL верно следующее:

Теорема 8. Для 0 < " < 1 существует детерминированная "-ослабленная разрешающая процедура для общей задачи, использующая O(s~2p2 log(mp£~1)) вызовов оракула GEN_ORACLE плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами.

Время выполнения этих алгоритмов пропорционально ширине p; авторами статьи были разработаны техники уменьшения ширины для множества специальных случаев рассматриваемых задач. В качестве результата, полученного при помощи этих техник, можно привести следующий пример. Если задача об упаковке определяется при помощи выпуклого множества, являющегося произведением k выпуклых множеств меньших размерностей, т.е. P = P1 x • • • x Pk, и неравенств PlAlxl < b, тогда существует рандомизированная "-ослабленная разрешающая процедура, предположительно использующая O(s~2 k\og(ms~1) + klog k) вызовов подпрограммы, вычисляющей точку с минимальной стоимостью в P = {x € P : Alx l bg;l = 1... k, и детерминированная версия процедуры, использующая O{e~2k2 log(m£~1)) таких вызовов плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами. Этот результат может быть применен к задаче управления несколькими товарными потоками, при этом указанная подпрограмма должна выполнять вычисление потоков минимальной стоимости с одним источником, а не вычисление кратчайших путей, которое требуется для исходного алгоритма.