Determinar soluciones básicas factibles en LP

Question

Considere un problema de programación lineal \begin{align*} \min_x \; &c^Tx\\ \text{s.t. } & Ax \leq b. \end{align*}Suponiendo que las restricciones forman un poliedro, ¿hay alguna forma de agrupar las restricciones de modo que cada grupo de restricciones dé una solución básica factible? Por ejemplo, en la figura siguiente, hay 4 restricciones que forman un poliedro y cuatro soluciones factibles básicas. ¿Existe una manera sencilla de determinar rápidamente todos los grupos de restricciones que dan soluciones básicas factibles sin calcular los puntos de intersección y luego probar la viabilidad? Por ejemplo, ¿cómo sabemos que las restricciones 1 y 2, en lugar de 1 y 4 (aunque también son independientes), forman un grupo porque dan una solución básica factible sin tener que calcular sus pintas de intersección y luego probar la factibilidad para ver esto? ? ¿Podemos ver esto directamente en las propiedades de la matriz A (la independencia es aparentemente uno de los factores requeridos)?

¡Cualquier comentario o sugerencia de referencia es muy apreciado!

Answer 1

Encontrar una única solución básica factible es tan difícil como resolver un programa lineal. (Eso es porque, desde la dualidad, minimizar$c^{\mathsf T}x$ sujeto a $Ax \le b$ es equivalente a encontrar vectores $x$ y $u$ tal que $Ax \le b$, $u^{\mathsf T}A = c^{\mathsf T}$y $u^{\mathsf T}b = c^{\mathsf T}x$.)

Encontrar todas las soluciones básicas factibles es incluso más difícil que eso. En primer lugar, en general, puede haber exponencialmente muchas soluciones factibles básicas. En tales casos, nuestro estándar para un algoritmo eficiente no es uno que los genere todos de manera eficiente, ¡eso es imposible! Más bien, podríamos pedir:

• Un algoritmo que genera todo $N$ soluciones básicas factibles para un tamaño$n$ problema en $N \cdot \operatorname{poly}(n)$ hora.
• Más ambiciosamente, un algoritmo que genera todas las soluciones con $\operatorname{poly}(n)$ tiempo entre cada solución y la siguiente.

Hasta donde yo sé, lo segundo todavía está fuera de nuestro alcance, pero así es como podemos hacer lo primero. A partir de una única solución factible básica, puede utilizar el método simplex sin función objetivo para encontrar todos los pivotes válidos y obtener las soluciones factibles básicas "adyacentes". Esto le permite explorar todos los rincones de su región factible utilizando, digamos, la búsqueda en amplitud.

Consulte también esta respuesta en la investigación de operaciones StackExchange para obtener más detalles.