Determine soluções básicas viáveis ​​em LP

Question

Considere um problema de programação linear \begin{align*} \min_x \; &c^Tx\\ \text{s.t. } & Ax \leq b. \end{align*}Supondo que as restrições formem um poliedro, há alguma maneira de agrupar as restrições de forma que cada grupo de restrições forneça uma solução básica viável. Por exemplo, na figura abaixo, existem 4 restrições formando um poliedro e quatro soluções básicas viáveis. Existe uma maneira simples de determinar rapidamente todos os grupos de restrições que fornecem soluções básicas viáveis ​​sem calcular os pontos de interseção e, em seguida, testar a viabilidade. Por exemplo, como sabemos as restrições 1 e 2, em vez de 1 e 4 (embora também sejam independentes), formam um grupo porque fornecem uma solução básica viável sem ter que calcular seus pontos de interseção e, em seguida, testar a viabilidade para ver isso ? Podemos ver isso a partir das propriedades da matriz A diretamente (a independência é aparentemente um dos fatores necessários)?

Quaisquer comentários ou sugestões de referência são muito apreciados!

Answer 1

Encontrar uma única solução básica viável é tão difícil quanto resolver um programa linear. (Isso porque, a partir da dualidade, minimizando$c^{\mathsf T}x$ sujeito a $Ax \le b$ é equivalente a encontrar vetores $x$ e $u$ de tal modo que $Ax \le b$, $u^{\mathsf T}A = c^{\mathsf T}$e $u^{\mathsf T}b = c^{\mathsf T}x$.)

Encontrar todas as soluções básicas viáveis ​​é ainda mais difícil do que isso. Em primeiro lugar, em geral, pode haver muitas soluções básicas viáveis ​​exponencialmente. Nesses casos, nosso padrão para um algoritmo eficiente não é aquele que gera todos eles com eficiência - isso é impossível! Em vez disso, podemos pedir:

• Um algoritmo que gera todos $N$ soluções básicas viáveis ​​para um tamanho$n$ problema em $N \cdot \operatorname{poly}(n)$ Tempo.
• Mais ambiciosamente, um algoritmo que gera todas as soluções com $\operatorname{poly}(n)$ tempo entre cada solução e a próxima.

Pelo que eu sei, a segunda coisa ainda está fora de nosso alcance, mas aqui está como podemos fazer a primeira coisa. Começando com uma única solução básica viável, você pode usar o método simplex sem função objetivo para encontrar todos os pivôs válidos e obter as soluções básicas viáveis ​​"adjacentes". Isso permite que você explore todos os cantos de sua região viável usando, digamos, a pesquisa em largura.

Veja também esta resposta na pesquisa operacional StackExchange para mais detalhes.