Эквивалентность технико-экономического обоснования и оптимизации для линейных систем

Один из способов показать, что проверка выполнимости линейной системы неравенств так же сложна, как и линейное программирование, - это приведение с помощью метода эллипсоидов. Еще более простой способ - угадать оптимальное решение и ввести его в качестве ограничения с помощью бинарного поиска.

Оба эти сокращения являются полиномиальными, но не сильно полиномиальными (т.е. они зависят от количества битов в коэффициентах неравенств).

Существует ли сильно полиномиальное сокращение от оптимизации LP до осуществимости LP?

ds.algorithms linear-programming Суреш Венкат
источник

вообще-то, нет. Это как вы говорите. Я понимаю, что оптимизация LP решает выполнимость LP. Я прошу об обратном сокращении.

Суреш Венкат

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

Noam

Но, если проверка выполнимости не только дает ответ «да / нет», как обсуждалось Ноамом выше, но, скорее, в случае выполнимости предоставляет выполнимое решение, тогда ответ - да, по двойственности ЛП.

Кристоффер Арнсфельт Хансен

@SureshVenkat: Предположим, что первичное число - это программа максимизации переменных

x

$x$ , тогда как двойственное число является программой минимизации переменных

y

$y$ . Затем сформируйте систему неравенств по переменным

x, y

$x,y$ , взяв ограничения как из первичного, так и из двойственного, вместе с неравенством, утверждающим, что значение простого решения является по меньшей мере значением двойственного решения. Случаи того, что LP неосуществимы и неограниченны, также могут быть рассмотрены.

Кристоффер Арнсфельт Хансен

Как насчет многогранников / многогранников, определенных неявными ограничениями?

Чандра Чекури

Ответы:

Ответ - да, и на самом деле можно даже свести к решению проблемы линейных неравенств выполнимость!

$\max c^Tx\ \text{s.t.}\ Ax \leq b\ ;\ x\geq 0$

Кроме того, у нас есть доступ к оракулу, который с учетом системы неравенств возвращает да / нет, является ли система осуществимой. $S=\{Bz \leq d\}$

Сокращение теперь происходит следующим образом:

Проверьте, возможно ли . Если нет, мы можем сообщить, что P НЕОБХОДИМО. $S_1=\{Ax \leq b\ ;\ x \geq 0\}$
Сформируйте двойственную программу D: . $\min b^Ty\ \text{s.t.}\ A^Ty \geq c\ ;\ y \geq 0$
Проверьте, возможно ли . Если нет, мы можем сообщить, что P НЕ ОБЪЕДИНЕНО. $S_2=\{Ax \leq b\ ;\ x\geq 0\ ;\ A^Ty\geq c\ ;\ y\geq0 \ ;\ b^Ty \leq c^Tx\}$
Переберите неравенства и попробуйте добавить их один за другим в качестве равенств (т.е. добавить обратное неравенство) к системе . Если система остается выполнимой, мы сохраняем ограничение в , а в противном случае снимаем его снова. Пусть - система ограничений (линейных равенств), которая добавляется таким образом. Система теперь полностью определит оптимальное базовое решение для P. $S_1$ $S_2$ $S_2$ $S_3$ $S_3$
Используя метод исключения Гаусса в системе вычислим оптимальное решение для P. $S_3$ $x$

Кристоффер Арнсфельт Хансен
источник

Шаги 4 и 5 не нужны. Если осуществимо, то мы получили оптимальное решение .

S_{2}

$S_2$

P

$P$

hengxin

@hengxin. В первой строке моего ответа напишите, что ответ «да», даже если вы рассматриваете возможность решения проблемы. Ниже я, очевидно, делаю это предположение, и, следовательно, шаги 4 и 5 являются обязательными.

Кристоффер Арнсфельт Хансен