Эффективно решить систему строгих линейных неравенств со всеми коэффициентами, равными 1, без использования общего решения ЛП?

Согласно названию, кроме использования универсального LP-решателя, существует ли подход для решения систем неравенств по переменным $x_i, \ldots, x_k$ где неравенства имеют вид $\sum_{i \in I} x_i < \sum_{j \in J} x_j$ ? А как насчет особого случая неравенств, которые образуют общий порядок по суммам членов силового множества $\{x_i, \ldots, x_k\}$ ?

ds.algorithms linear-algebra linear-programming jonderry
источник

@ Ankur: не имеет значения, целые или действительные числа. Если это строгие неравенства, вы можете округлить их до рациональных, а затем умножить их на наименее общий знаменатель, чтобы получить целочисленное решение.

Питер Шор

Понятия не имею, что можно написать за 30 минут (на каком языке?). Если это критерий «простого», действительно ли это вообще вопрос теоретической информатики?

Цуёси Ито

Хороший вопрос, Питер Шор. Джондерри, я забираю свое заявление обратно. Я думал, что комбинаторная задача удовлетворения этих строгих неравенств и выпуклая аналитическая задача нахождения внутренней точки конуса качественно различны. Я был неправ.

Анкур

@Tsuyoshi: Это не должно быть тривиальным, но мне любопытно узнать, можно ли это сделать из первых принципов, не используя всю дополнительную мощь полного решателя LP, особенно для особого случая, когда у нас есть порядок всех сумм подмножеств (обратите внимание, что в этом случае полиномиальное время экспоненциально по числу переменных).

Jonderry

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

Цуёси Ито

Ответы:

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

Во-первых, давайте установим переменную $x_1>0$ , который мы называем $\epsilon$ , Теперь давайте выберем другую переменную $x_i$ , который мы будем называть $1$ , Мы хотим убедиться, что

ϵ ≪ 1 .

$\epsilon \ll 1\, .$ Для этого рассмотрим неравенства

x_{1} < x_{2},

$x_1 < x_2,$

x_{1} + x_{2} < x_{3},

$x_1 + x_2 < x_3,$

x_{2} + x_{3} < x_{4},

$x_2+x_3 < x_4,$ и так далее. С достаточно длинной цепью, это скажет нам, что

N x_{1} < x_{i}

$Nx_1 < x_i$ , или

ϵ < 1 / N

$\epsilon < 1/N$ для некоторых очень больших

N

$N$ (

N

$N$ является числом Фибоначчи, и поэтому экспоненциально растет в

i

$i$ ).

Теперь мы можем создать линейную программу с целыми коэффициентами. Если мы хотим коэффициент 3 на $x_t$ Добавляем неравенства

x_{t} < x_{t^{'}} < x_{t^{″}} < x_{t} + ϵ

$x_t < x_{t'} < x_{t''} < x_t + \epsilon$ и пусть 3 . Если вы хотите увеличить коэффициенты, вы можете получить их, выражая коэффициенты в двоичной записи и создавая неравенства, которые гарантируют, что , и так далее. Чтобы получить правую часть, мы делаем то же самое с переменной . Этот метод позволит нам использовать линейные программы в форме ОП для приблизительной проверки выполнимости произвольных линейных программ с целочисленными коэффициентами, задача, которая по сути столь же сложна, как и линейное программирование.

x_{t} + x_{t^{'}} + x_{t^{″}}

$x_t + x_{t'} + x_{t''}$

x_{t}

$x_t$

x_{u} \approx 2 x_{t}

$x_u \approx 2x_t$

x_{v} \approx 2 x_{u}

$x_v \approx 2x_u$

x_{i} = 1

$x_i = 1$

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

Питер Шор
источник