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

15

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

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

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

Суреш Венкат
источник
1
вообще-то, нет. Это как вы говорите. Я понимаю, что оптимизация LP решает выполнимость LP. Я прошу об обратном сокращении.
Суреш Венкат
3
Что ж, выходные данные для оптимизации могут иметь столько же битов, сколько «количество битов в коэффициентах», тогда как выполнимость равна да / нет. Таким образом, если под сокращением вы подразумеваете что-то «черный ящик», то есть ответ должен быть отрицательным.
Noam
1
Но, если проверка выполнимости не только дает ответ «да / нет», как обсуждалось Ноамом выше, но, скорее, в случае выполнимости предоставляет выполнимое решение, тогда ответ - да, по двойственности ЛП.
Кристоффер Арнсфельт Хансен
2
@SureshVenkat: Предположим, что первичное число - это программа максимизации переменных x , тогда как двойственное число является программой минимизации переменных y . Затем сформируйте систему неравенств по переменным x,y , взяв ограничения как из первичного, так и из двойственного, вместе с неравенством, утверждающим, что значение простого решения является по меньшей мере значением двойственного решения. Случаи того, что LP неосуществимы и неограниченны, также могут быть рассмотрены.
Кристоффер Арнсфельт Хансен
1
Как насчет многогранников / многогранников, определенных неявными ограничениями?
Чандра Чекури

Ответы:

8

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

maxcTx s.t. Axb ; x0

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

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

  1. Проверьте, возможно ли . Если нет, мы можем сообщить, что P НЕОБХОДИМО.S1={Axb ; x0}
  2. Сформируйте двойственную программу D: .minbTy s.t. ATyc ; y0
  3. Проверьте, возможно ли . Если нет, мы можем сообщить, что P НЕ ОБЪЕДИНЕНО.S2знак равно{AИксб ; Икс0 ; ATYс ; Y0 ; бTYсTИкс}
  4. Переберите неравенства и попробуйте добавить их один за другим в качестве равенств (т.е. добавить обратное неравенство) к системе . Если система остается выполнимой, мы сохраняем ограничение в , а в противном случае снимаем его снова. Пусть - система ограничений (линейных равенств), которая добавляется таким образом. Система теперь полностью определит оптимальное базовое решение для P.S 2 S 2 S 3 S 3S1S2S2S3S3
  5. Используя метод исключения Гаусса в системе вычислим оптимальное решение для P. xS3Икс
Кристоффер Арнсфельт Хансен
источник
Шаги 4 и 5 не нужны. Если осуществимо, то мы получили оптимальное решение . PS2п
hengxin
@hengxin. В первой строке моего ответа напишите, что ответ «да», даже если вы рассматриваете возможность решения проблемы. Ниже я, очевидно, делаю это предположение, и, следовательно, шаги 4 и 5 являются обязательными.
Кристоффер Арнсфельт Хансен