Resolva com eficiência um sistema de desigualdades lineares estritas com todos os coeficientes iguais a 1 sem usar um solucionador de LP geral?

Pelo título, além de usar um propósito LP solver geral, existe uma abordagem para sistemas de desigualdades mais variáveis resolver $x_i, \ldots, x_k$ onde as desigualdades têm a forma $\sum_{i \in I} x_i < \sum_{j \in J} x_j$ ? E o caso especial de desigualdades que formam uma ordem total sobre as somas dos membros do conjunto de poderes de $\{x_i, \ldots, x_k\}$ ?

ds.algorithms linear-algebra linear-programming jonderry
fonte

@ Ankur: não importa se é números inteiros ou reais. Se essas são desigualdades estritas, você pode arredondá-las para racionais e depois multiplicá-las pelo denominador menos comum para obter uma solução inteira.

315 Peter Peter Shor

Não faço ideia do que você pode codificar em 30 minutos (em qual idioma?). Se esse é o critério para "simples", isso é realmente uma questão em ciência da computação teórica?

Tsuyoshi Ito

Bom ponto Peter Shor. jonderry, retiro minha declaração. Eu estava pensando que o problema combinatório de satisfazer essas desigualdades estritas e o problema analítico convexo de encontrar um ponto interior de um cone são qualitativamente distintos. Eu estava errado.

Ankur

@Tsuyoshi: Não precisa ser trivial, mas estou curioso para saber se isso pode ser feito desde os primeiros princípios sem usar toda a energia extra de um solucionador de LP completo, especialmente no caso especial em que temos pedidos de todas as somas de subconjunto (observe, neste caso, que o tempo polinomial é exponencial no número de variáveis).

perfil completo de jonderry

Depois, penso que "esse problema pode ser resolvido com eficiência sem o uso de algoritmos gerais para programação linear?" é uma boa maneira de formular sua pergunta melhor.

Tsuyoshi Ito

Respostas:

Para sua primeira pergunta, sem o pedido total, a resposta é que é essencialmente tão difícil quanto a programação linear. Aqui está um esboço de uma prova.

$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$

$x_t$

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

$x_t < x_{t'} < x_{t''} < x_t + \epsilon$

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$ . Essa técnica nos permitirá usar programas lineares da forma do OP para verificar aproximadamente a viabilidade de programas lineares arbitrários com coeficientes inteiros, uma tarefa que é essencialmente tão difícil quanto a programação linear.

Não sei como analisar a segunda pergunta, perguntando sobre o caso em que há uma ordem total em todos os subconjuntos.

Peter Shor
fonte