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

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

В данной статье приводится обзор быстрых алгоритмов, дающих приближенные решения для задач, которые могут быть сформулированы в виде задач линейного программирования (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].

Определения и нотация Для параметра ошибки " > x0 точка x 2 P является "-приближенным решением для дробно-линейной задачи упаковки (или покрытия), если Ax < (1 + ")b (или Ax > (1 — ")b, соответственно). С другой стороны, если x 2 P удовлетворяет условию Ax < b (или Ax > b), то x является точным решением. Для общей задачи GENERAL, параметра ошибки " > 0 и положительного вектора отклонения d значение x 2 P является "-приближенным решением, если Ax < b + "d, и точным решением, если Ax < b. "-ослабленная разрешающая процедура для этих задач либо находит "-приближенное решение, либо обоснованно сообщает о том, что точного решения не существует. В общем случае в задаче минимизации (максимизации) алгоритм (1 + ")-аппроксимации ((1 - ")-аппроксимации) возвращает значение, не более чем в (1 + ") (не менее чем в (1 - ")) раз отличающееся от оптимального.

Время выполнения разработанных алгоритмов полиномиально зависит от e"1 для любого параметра ошибки " > 0, а также от ширины p выпуклого множества P, родственного множеству неравенств Ax < b или Ax > b, определяющему решаемую задачу. Более точно ширина p определяется следующим образом для каждой из рассматриваемых задач:

• PACKING (упаковка): p := maxi maxx2P abi

• RELAXED PACKING (упаковка с ослабленными ограничениями): p := maxi maxx2P ^.

• COVERING (покрытие): p := maxi maxx2P abi

• SIMULTANEOUS PACKING AND COVERING (одновременные упаковка и покрытие): p  := r maxfmaxi ^, max, + 1, где d

• GENERAL (общая задача): p := maxi maxx2P jaix . bij+1 – вышеупомянутый вектор отклонения.