Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
• '''Дробно-линейная задача об упаковке''' и ее оракул определяются следующим образом. | • '''Дробно-линейная задача об упаковке''' и ее оракул определяются следующим образом. | ||
PACKING (упаковка): Даны матрица A размера m | PACKING (упаковка): Даны матрица A размера <math>m \times n</math>, b > 0 и выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0, \forall x \in P</math>. Существует ли такое <math>x \in P \;</math>, что <math>Ax \le b \;</math>? | ||
PACK_ORACLE (оракул упаковки): Даны m-мерный вектор y > 0 и вышеописанное множество P. Вернуть x := argminfyTAx : x 2 Pg: | PACK_ORACLE (оракул упаковки): Даны m-мерный вектор y > 0 и вышеописанное множество P. Вернуть x := argminfyTAx : x 2 Pg: | ||
| Строка 12: | Строка 12: | ||
• Ослабленная дробно-линейная задача об упаковке и ее оракул определяются следующим образом. | • Ослабленная дробно-линейная задача об упаковке и ее оракул определяются следующим образом. | ||
RELAXED PACKING (упаковка с ослабленными ограничениями): Даны " > 0, матрица A размера m | RELAXED PACKING (упаковка с ослабленными ограничениями): Даны " > 0, матрица A размера <math>m \times n</math>, b > 0 и выпуклые множества <math>P \in \mathbb{R}^n</math> и <math>P \in \mathbb{R}^n</math>, такие, что P С P и A<math>Ax \ge 0, \forall x \in P</math>. Найти такое 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. | REL_PACK_ORACLE (оракул упаковки с ослабленными ограничениями): Даны m-мерный вектор y > 0 и вышеописанные множества P и P. Вернуть x € P, такое, что yTAx < minfyTAx: x 2 Pg. | ||
| Строка 19: | Строка 19: | ||
• Дробно-линейная задача о покрытии и ее оракул определяются следующим образом. | • Дробно-линейная задача о покрытии и ее оракул определяются следующим образом. | ||
COVERING (покрытие): Даны матрица A размера m | COVERING (покрытие): Даны матрица A размера <math>m \times n</math>, b > 0 и выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0, \forall x \in P</math>. Существует ли такое x 2 P, что Ax > b? | ||
COVER _PACK_ORACLE (оракул покрытия): Даны m-мерный вектор y > 0 и вышеописанное множество P. Вернуть x := argmaxfyTAx: x 2 Pg: | COVER _PACK_ORACLE (оракул покрытия): Даны m-мерный вектор y > 0 и вышеописанное множество P. Вернуть x := argmaxfyTAx: x 2 Pg: | ||
| Строка 26: | Строка 26: | ||
• Задача об одновременных упаковке и покрытии и ее оракул определяются следующим образом. | • Задача об одновременных упаковке и покрытии и ее оракул определяются следующим образом. | ||
SIMULTANEOUS PACKING AND COVERING (одновременные упаковка и покрытие): Даны матрицы A размера m | SIMULTANEOUS PACKING AND COVERING (одновременные упаковка и покрытие): Даны матрицы A размера <math>m \times n</math> и A – размера <math>m \times n</math> (m — in) x n, b > 0 и b > 0, а также выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0, Ax \ge 0, \forall x \in P</math>. Существует ли такое x 2 P, что Ax < b и Ax > Ы? | ||
SIM_ORACLE (оракул упаковки и покрытия): Даны вышеописанное множество P, константа v и решение двойственной задачи (у, у). Вернуть x € P, такое, что | SIM_ORACLE (оракул упаковки и покрытия): Даны вышеописанное множество P, константа v и решение двойственной задачи (у, у). Вернуть x € P, такое, что | ||
| Строка 34: | Строка 34: | ||
• Общая задача и ее оракул определяются следующим образом. | • Общая задача и ее оракул определяются следующим образом. | ||
GENERAL (общая задача): Даны матрица A размера m | GENERAL (общая задача): Даны матрица A размера <math>m \times n</math>, произвольный вектор b и выпуклое множество <math>P \in \mathbb{R}^n</math>. Существует ли такое x 2 P, что Ax < b? | ||
GEN _ORACLE (оракул общей задачи): Даны m-мерный вектор y > 0 и вышеописанное множество P. Вернуть x := argminfyTAx : x 2 Pg: | GEN _ORACLE (оракул общей задачи): Даны m-мерный вектор y > 0 и вышеописанное множество P. Вернуть x := argminfyTAx : x 2 Pg: | ||
Версия от 11:38, 21 сентября 2018
Постановка задачи
В данной статье приводится обзор быстрых алгоритмов, дающих приближенные решения для задач, которые могут быть сформулированы в виде задач линейного программирования (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-мерный вектор y > 0 и вышеописанное множество P. Вернуть x := argminfyTAx : x 2 Pg:
• Ослабленная дробно-линейная задача об упаковке и ее оракул определяются следующим образом.
RELAXED PACKING (упаковка с ослабленными ограничениями): Даны " > 0, матрица A размера [math]\displaystyle{ m \times n }[/math], b > 0 и выпуклые множества [math]\displaystyle{ P \in \mathbb{R}^n }[/math] и [math]\displaystyle{ P \in \mathbb{R}^n }[/math], такие, что P С P и A[math]\displaystyle{ Ax \ge 0, \forall x \in P }[/math]. Найти такое 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 размера [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]. Существует ли такое x 2 P, что Ax > b?
COVER _PACK_ORACLE (оракул покрытия): Даны m-мерный вектор y > 0 и вышеописанное множество P. Вернуть x := argmaxfyTAx: x 2 Pg:
• Задача об одновременных упаковке и покрытии и ее оракул определяются следующим образом.
SIMULTANEOUS PACKING AND COVERING (одновременные упаковка и покрытие): Даны матрицы A размера [math]\displaystyle{ m \times n }[/math] и A – размера [math]\displaystyle{ m \times n }[/math] (m — in) x n, b > 0 и b > 0, а также выпуклое множество [math]\displaystyle{ P \in \mathbb{R}^n }[/math], такое, что [math]\displaystyle{ Ax \ge 0, Ax \ge 0, \forall x \in P }[/math]. Существует ли такое 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 размера [math]\displaystyle{ m \times n }[/math], произвольный вектор b и выпуклое множество [math]\displaystyle{ P \in \mathbb{R}^n }[/math]. Существует ли такое x 2 P, что Ax < b?
GEN _ORACLE (оракул общей задачи): Даны m-мерный вектор y > 0 и вышеописанное множество P. Вернуть x := argminfyTAx : x 2 Pg:
Определения и нотация