Déterminer les solutions de base réalisables en LP

Question

Considérons un problème de programmation linéaire \begin{align*} \min_x \; &c^Tx\\ \text{s.t. } & Ax \leq b. \end{align*}En supposant que les contraintes forment un polyèdre, existe-t-il un moyen de regrouper les contraintes de telle sorte que chaque groupe de contraintes donne une solution de base faisable. Par exemple, sur la figure ci-dessous, il y a 4 contraintes formant un polyèdre et quatre solutions de base réalisables. Existe-t-il un moyen simple de déterminer rapidement tous les groupes de contraintes qui donnent des solutions de base réalisables sans calculer les points d'intersection et ensuite tester la faisabilité. Par exemple, comment pouvons-nous connaître les contraintes 1 et 2, au lieu de 1 et 4 (bien qu'elles soient également indépendantes), former un groupe parce qu'elles donnent une solution de base faisable sans avoir à calculer leurs pintes d'intersection et ensuite tester la faisabilité pour voir cela ? Pouvons-nous voir cela directement à partir des propriétés de la matrice A (l'indépendance est apparemment l'un des facteurs requis)?

Tous les commentaires ou suggestions de références sont très appréciés!

Answer 1

Trouver une seule solution faisable de base est tout aussi difficile que de résoudre un programme linéaire. (C'est parce que, à partir de la dualité, minimiser$c^{\mathsf T}x$ sujet à $Ax \le b$ équivaut à trouver des vecteurs $x$ et $u$ tel que $Ax \le b$, $u^{\mathsf T}A = c^{\mathsf T}$, et $u^{\mathsf T}b = c^{\mathsf T}x$.)

Trouver toutes les solutions de base réalisables est encore plus difficile que cela. Tout d'abord, en général, il peut exister de manière exponentielle de nombreuses solutions de base réalisables. Dans de tels cas, notre standard pour un algorithme efficace n'est pas celui qui les génère tous efficacement - c'est impossible! Nous pourrions plutôt demander:

• Un algorithme qui génère tout $N$ solutions de base réalisables pour une taille$n$ problème dans $N \cdot \operatorname{poly}(n)$ temps.
• Plus ambitieux, un algorithme qui génère toutes les solutions avec $\operatorname{poly}(n)$ temps entre chaque solution et la suivante.

Autant que je sache, la deuxième chose est toujours hors de notre portée, mais voici comment nous pouvons faire la première chose. À partir d'une seule solution faisable de base, vous pouvez utiliser la méthode simplex sans fonction objectif pour trouver tous les pivots valides et obtenir les solutions faisables de base «adjacentes». Cela vous permet d'explorer tous les coins de votre région réalisable en utilisant, par exemple, la recherche en largeur d'abord.

Voir également cette réponse sur la recherche opérationnelle StackExchange pour plus de détails.