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

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

В данной статье приводится обзор быстрых алгоритмов, дающих приближенные решения для задач, которые могут быть сформулированы в виде задач линейного программирования (LP) и, следовательно, могут быть решено точно, хотя это потребует большего времени выполнения. Общий формат семейства таких задач имеет следующий вид. Дано множество из m неравенств с n переменными и оракул, который выдает решение подходящей задачи оптимизации над выпуклым множеством P 2 Rn. Найти решение x 2 P, удовлетворяющее неравенствам, или обнаружить, что такого решения x не существует. Принципиальная идея алгоритма заключается в следующем. Алгоритм всегда начинает работу с недопустимого решения x и использует оракул оптимизации для поиска направления, в котором степень нарушения неравенств может быть уменьшена; это выполняется при помощи расчета вектора y, представляющего собой решение двойственной задачи относительно x. После этого x аккуратно изменяется в этом направлении, и процесс повторяется до тех пор, пока x не становится «приближенно» допустимым. Далее будут рассмотрены конкретные задачи и соответствующие им оракулы оптимизации, а также определены другие нотации используемой «аппроксимации».

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

PACKING (упаковка): Даны матрица A размера m x n, b > 0 и выпуклое множество P в Rn, такое, что Ax > 0; 8x 2 P. Существует ли такое x 2 P, что Ax < b?

PACK_ORACLE (оракул упаковки): Даны m-мерный вектор y > 0 и вышеописанное множество P. Вернуть x := argminfyTAx : x 2 Pg:

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

RELAXED PACKING (упаковка с ослабленными ограничениями): Даны " > 0, матрица A размера m x n, b > 0 и выпуклые множества P и P в Rn, такие, что P С P и Ax > 0; 8x 2 P. Найти такое x 2 P, что Ax < (1 + ")b, или показать, что 69x 2 P, такое, что Ax<b.

REL_PACK_ORACLE (оракул упаковки с ослабленными ограничениями): Даны m-мерный вектор y > 0 и вышеописанные множества P и P. Вернуть x € P, такое, что yTAx < minfyTAx: x 2 Pg.

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

COVERING (покрытие): Даны матрица A размера m x n, b > 0 и выпуклое множество P в Rn, такое, что Ax > 0; 8x 2 P. Существует ли такое x 2 P, что Ax > b?

COVER _PACK_ORACLE (оракул покрытия): Даны m-мерный вектор y > 0 и вышеописанное множество P. Вернуть x := argmaxfyTAx: x 2 Pg:

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

SIMULTANEOUS PACKING AND COVERING (одновременные упаковка и покрытие): Даны матрицы A размера m x n и A – размера (m — in) x n, b > 0 и b > 0, а также выпуклое множество P в Rn, такое, что Ax > 0 и Ax > 0; 8x 2 P. Существует ли такое x 2 P, что Ax < b и Ax > Ы?

SIM_ORACLE (оракул упаковки и покрытия): Даны вышеописанное множество P, константа v и решение двойственной задачи (у, у). Вернуть x € P, такое, что Ax < vb, and у Ax — У^ yjujX = minfyT Ax i€l(v,x) — y j/jujX : x является вершиной P, такой, что Ax < vb}, i€l(v,x), где I(v,x) := fi : a,x < vfo,}.

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

GENERAL (общая задача): Даны матрица A размера m x n, произвольный вектор b и выпуклое множество P в Rn. Существует ли такое x 2 P, что Ax < b?

GEN _ORACLE (оракул общей задачи): Даны m-мерный вектор y > 0 и вышеописанное множество P. Вернуть x := argminfyTAx : x 2 Pg:

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