Existencia de pivotes que mejoran estrictamente el valor objetivo en presencia de degeneración

Question

Consideremos un problema de LP degenerado:

$$\min c^Tx \\\text{subject to: }\qquad\qquad\qquad\qquad\qquad$$ $$Ax=1\quad a_{i,j} \in \{0,1\}$$ $$x\ge0$$

¿Es seguro asumir que dada una base inicial no óptima $B_0$ ¿existe siempre una secuencia de pivotes para la que el valor objetivo mejora estrictamente hasta la optimización? Considerar la convexidad de un LP implica $c^TB_i^{-1}1\ge c^T\bar B^{-1}1$ donde $\bar B$ es la base óptima, de lo que puedo deducir directamente que $c^TB_i^{-1}1= c^TB_{i+1}^{-1}1$ si $B_i^{-1}1=B_{i+1}^{-1}1$ .

En ausencia de ciclismo, lo que implica un conjunto de índices de base dados $S_i$ y $S_{i+1}$ para $B_i$ y $B_{i+1}$ respectivamente los pivotes que no mejoran son cuando $S_{i+1}\not = S_i$ pero $B_{i+1}=PB_i$ donde $P$ es la matriz de permutación.

Así pues, la cuestión se reduce a determinar la necesidad de permutar una base dada para la mejora estricta del valor objetivo, o siempre hay una alternativa que mejora el valor objetivo sin permutar la base $B_i$ cuando el LP es degenerado?

Si es así, eso debería significar que si busco un pivote debería buscar un pivote que mejore estrictamente el valor objetivo y salir si no existe tal pivote, ¿verdad?

Answer 1

Llamemos a $A_{new}$ una submatriz de A de la que hemos eliminado todas las restricciones redundantes y sus correspondientes variables de holgura. El programa lineal correspondiente, $LP_{new}$ es no degenerada, por lo que cualquier base subóptima en $LP_{new}$ tiene un pivote que mejora. Elige cualquier secuencia de pivotes mejoradores.

Ahora, reconsiderando el programa lineal original, $LP_{old}$ Si no se ha hecho nada, se puede ver que la secuencia de pivotes que se ha hecho en el párrafo anterior es una secuencia de pivotes factible aquí. No hay nada malo en dejar que $LP_{old}$ se encuentran siempre en la base mientras nosotros las ignoramos, porque sólo necesitan ser no negativas, y sabemos que son no negativas porque las regiones factibles de $LP_{new}$ y $LP_{old}$ son los mismos.

Este argumento debería aplicarse a todas las LP, no sólo a aquellas en las que $Ax=1$ , $a_{i,j}\{0,1\}$ . Debe existir una secuencia de pivotes estrictamente mejoradores hasta la optimización.

---

EDITAR:

De este argumento no se deduce que, dado $any$ base subóptima, existe una secuencia de pivotes que mejora. El argumento muestra que existe tal secuencia partiendo de cualquier solución no degenerada (o de la BFS inicial, independientemente de su degeneración), pero no de todas. Sólo hay que tener en cuenta esto si se trata de emplear una estrategia de búsqueda práctica, porque parece que se está planeando una búsqueda local, que puede elegir ciegamente pivotes que conducen a un callejón sin salida.