¿Resolver eficientemente un sistema de estrictas desigualdades lineales con todos los coeficientes iguales a 1 sin usar un solucionador general de LP?

Según el título, aparte de usar un solucionador de LP de propósito general, ¿hay un enfoque para resolver sistemas de desigualdades sobre las variables $x_i, \ldots, x_k$ donde las desigualdades tienen la forma $\sum_{i \in I} x_i < \sum_{j \in J} x_j$ ? ¿Qué pasa con el caso especial de las desigualdades que forman un orden total sobre las sumas de los miembros del conjunto de poder de $\{x_i, \ldots, x_k\}$ ?

ds.algorithms linear-algebra linear-programming jonderry
fuente

@Ankur: no importa si son enteros o reales. Si se trata de desigualdades estrictas, puede redondearlas a racionales y luego multiplicarlas por el mínimo común denominador para obtener una solución entera.

Peter Shor

No tengo idea de lo que puedes codificar en 30 minutos (¿en qué idioma?). Si ese es el criterio para "simple", ¿es realmente una pregunta en informática teórica?

Tsuyoshi Ito

Buen punto Peter Shor. Jonderry, retiro mi declaración. Estaba pensando que el problema combinatorio de satisfacer estas estrictas desigualdades y el problema analítico convexo de encontrar un punto interior de un cono son cualitativamente distintos. Estaba equivocado.

Ankur

@ Tsuyoshi: No es necesario que sea trivial, pero tengo curiosidad por saber si esto se puede hacer desde los primeros principios sin utilizar toda la potencia extra de un solucionador de LP completo, especialmente para el caso especial en el que tenemos un pedido de todas las sumas de subconjuntos (tenga en cuenta en este caso que el tiempo polinómico es exponencial en el número de variables).

jonderry

Entonces pienso que "¿Se puede resolver este problema de manera eficiente sin usar algoritmos generales para la programación lineal?" Es una buena forma de formular mejor su pregunta.

Tsuyoshi Ito

Respuestas:

Para su primera pregunta, sin el orden total, la respuesta a su pregunta es que es esencialmente tan difícil como la programación lineal. Aquí hay un resumen de una prueba.

Primero, establezcamos una variable , que llamamos . Ahora, elija otra variable , que llamaremos . Queremos asegurarnos de que $x_1>0$ $\epsilon$ $x_i$ $1$ Para hacer esto, considere las desigualdades y así sucesivamente. Con una cadena lo suficientemente larga, esto nos dirá que , o , para algunos muy grandes( es un número de Fibonacci, y por lo tanto crece exponencialmente en ).

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

No sé cómo analizar la segunda pregunta, preguntando sobre el caso donde hay un orden total en todos los subconjuntos.

Peter Shor
fuente