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

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

В данной статье приводится обзор быстрых алгоритмов, дающих приближенные решения для задач, которые могут быть сформулированы в виде задач линейного программирования (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]\displaystyle{ C_{\rho}(y) \; }[/math] – минимальная стоимость [math]\displaystyle{ y^T Ax \; }[/math], достигаемая алгоритмом PACK_ORACLE для заданного y.

Теорема 3. Заменим PACK_ORACLE на оракула, который для заданного вектора [math]\displaystyle{ y \ge 0 \; }[/math] находит точку [math]\displaystyle{ \bar{x} \in P }[/math], такую, что [math]\displaystyle{ y^T A \bar{x} \le (1 + \varepsilon/2) C_{\rho}(y) + (\varepsilon / 2) \lambda y^T b }[/math], где X минимально, так что неравенство [math]\displaystyle{ Ax \le \lambda b }[/math] удовлетворяется на текущей итерации x. Тогда теоремы 1 и 2 по-прежнему верны.

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

Схожие результаты можно доказать для дробно-линейной задачи о покрытии (COVER_ORACLE[math]\displaystyle{ _l }[/math] определяется аналогично PACK_ORACLE[math]\displaystyle{ _l }[/math]):

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

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

Обозначим за [math]\displaystyle{ C_c(y) }[/math] максимальную стоимость [math]\displaystyle{ y^T Ax }[/math], достигаемую алгоритмом COVER_ORACLE для заданного y.

Теорема 6. Заменим COVER_ORACLE на оракула, который для заданного вектора [math]\displaystyle{ y \ge 0 }[/math] находит точку [math]\displaystyle{ \bar{x} \in P }[/math], такую, что [math]\displaystyle{ y^T \bar{x} \ge (1 - \varepsilon/2) C_C(y) - (\varepsilon/2) \lambda y^T b }[/math], где [math]\displaystyle{ \lambda }[/math] максимально, так что неравенство [math]\displaystyle{ Ax \ge \lambda b }[/math] удовлетворяется на текущей итерации x. Тогда теоремы 4 и 5 по-прежнему верны.

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

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

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

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

Время выполнения этих алгоритмов пропорционально ширине [math]\displaystyle{ \rho }[/math]; авторами статьи были разработаны техники уменьшения ширины для множества специальных случаев рассматриваемых задач. В качестве результата, полученного при помощи этих техник, можно привести следующий пример. Если задача об упаковке определяется при помощи выпуклого множества, являющегося произведением k выпуклых множеств меньших размерностей, т. е. [math]\displaystyle{ P = P^1 \times \cdot \cdot \cdot \times P^k }[/math], и неравенств [math]\displaystyle{ \sum_l A^l x^l \le b }[/math], тогда существует рандомизированная [math]\displaystyle{ \varepsilon }[/math]-ослабленная разрешающая процедура, предположительно использующая [math]\displaystyle{ O(\varepsilon^{-2} k \; log(m \; \varepsilon^{-1}) + k \; log \; k) }[/math] вызовов подпрограммы, вычисляющей точку с минимальной стоимостью в [math]\displaystyle{ \hat{P}^l = \{ x^l \in P^l: A^l x^l \le b \}, l = 1, ..., k }[/math], и детерминированная версия процедуры, использующая [math]\displaystyle{ O(\varepsilon^{-2} \; k^2 \; log(m \; \varepsilon^{-1})) }[/math] таких вызовов плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами. Этот результат может быть применен к задаче управления несколькими товарными потоками, при этом указанная подпрограмма должна выполнять вычисление потоков минимальной стоимости с одним источником, а не вычисление кратчайших путей, которое требуется для исходного алгоритма.