Equivalencia de comprobación de viabilidad y optimización para sistemas lineales.

Una forma de demostrar que verificar la viabilidad de un sistema lineal de desigualdades es tan difícil como la programación lineal es a través de la reducción dada por el método elipsoide. Una forma aún más fácil es adivinar la solución óptima e introducirla como una restricción a través de la búsqueda binaria.

Ambas reducciones son polinómicas, pero no muy polinómicas (es decir, dependen del número de bits en los coeficientes de las desigualdades).

¿Existe una fuerte reducción polinómica de la optimización de LP a la factibilidad de LP?

ds.algorithms linear-programming Suresh Venkat
fuente

en realidad no. Es como tu dices. Me doy cuenta de que la optimización de LP resuelve la viabilidad de LP. Estoy pidiendo la reducción opuesta.

Suresh Venkat

Bueno, la salida para la optimización puede tener tantos bits como "el número de bits en los coeficientes", mientras que la viabilidad es sí / no. Por lo tanto, si por reducción quiere decir algo "caja negra", entonces la respuesta debe ser negativa.

Noam

Pero, si la verificación de factibilidad no solo da una respuesta sí / no como se discutió anteriormente en Noam, sino que en el caso de la factibilidad proporciona una solución factible, entonces la respuesta es sí, por dualidad LP.

Kristoffer Arnsfelt Hansen

@SureshVenkat: Supongamos que el primal es un programa de maximización en las variables

, siendo el dual un programa de minimización en las variables

. Luego, forme el sistema de desigualdades en las variables

, tomando las restricciones tanto de lo primario como de lo dual, junto con una desigualdad que indique que el valor de la solución primaria es al menos el valor de la solución dual. Los casos en los que el LP no es factible y no tiene límites también pueden tratarse.

x

$x$

y

$y$

x, y

$x,y$

Kristoffer Arnsfelt Hansen

¿Qué pasa con los politopos / poliedros definidos por restricciones implícitas?

Chandra Chekuri

Respuestas:

La respuesta es sí, y de hecho, ¡incluso se puede reducir el problema de decisión de la viabilidad de las desigualdades lineales!

Somos como entrada dada una instancia de LP P: . $\max c^Tx\ \text{s.t.}\ Ax \leq b\ ;\ x\geq 0$

Además, tenemos acceso a un oráculo que dado un sistema de desigualdades devuelve sí / no, si el sistema es factible. $S=\{Bz \leq d\}$

La reducción ahora procede de la siguiente manera:

Pruebe si es factible. Si no, podemos informar que P es INFEASIBLE. $S_1=\{Ax \leq b\ ;\ x \geq 0\}$
Forme el programa dual D: . $\min b^Ty\ \text{s.t.}\ A^Ty \geq c\ ;\ y \geq 0$
Pruebe si es factible. Si no, podemos informar que P está SIN LÍMITES. $S_2=\{Ax \leq b\ ;\ x\geq 0\ ;\ A^Ty\geq c\ ;\ y\geq0 \ ;\ b^Ty \leq c^Tx\}$
Itere sobre las desigualdades de e intente agregarlas una por una como igualdades (es decir, agregue la desigualdad inversa) al sistema . Si el sistema sigue siendo factible, mantenemos la restricción en y, de lo contrario, la eliminamos nuevamente. Deje que sea el sistema de restricciones (igualdades lineales) que se agrega de esta manera. El sistema ahora determinará por completo una solución básica óptima para P. $S_1$ $S_2$ $S_2$ $S_3$ $S_3$
Utilizando Gaussian Elimination en el sistema calcule una solución óptima a P. $S_3$ $x$

Kristoffer Arnsfelt Hansen
fuente

Los pasos 4 y 5 no son necesarios. Si

es factible, entonces hemos obtenido la solución óptima para

S_{2}

$S_2$

P

$P$

hengxin

@hengxin. Escribe en la primera línea de mi respuesta que la respuesta es sí, incluso cuando se considera reducir el problema de decisión. A continuación, obviamente, hago esa suposición y, por lo tanto, se requieren los pasos 4 y 5.

Kristoffer Arnsfelt Hansen