Determinar rápidamente si esta Entero problema de programación Lineal tiene solución

Question

Tengo un número entero de programación lineal de la forma $$\begin{aligned} \text{Minimize}&& c &= x_1 + \cdots + x_m \\ \text{subject to}&& A\mathbf{x} &\geq \mathbf{b} \\ \text{where} && \mathbf{x} &\in \mathbb{Z}^m,\ \mathbf{x}\geq\mathbf{0},\ \\ && \mathbf{b} &\in \mathbb{R}^n,\ \mathbf{b}\geq\mathbf{0},\ \\ && A&\in \mathbb{R}^{n\times m}\ . \end{aligned}$$ Así que, lo más importante es que, tanto mi coeficiente de vectores $\mathbf{x}$ $\mathbf{b}$ siempre no negativo en cada componente, y no hay ninguna "$\leq$" límite de nada. $A$ es una forma arbitraria (finito) con un valor real de la matriz. Esto es solucionable, en una forma sencilla y en cualquier estándar LP solver. Pero de lo que he estado tratando de averiguar es si hay una sencilla manera de determinar si el dado problema tiene una solución a todos – no tener que preocuparse de que la solución es la óptima.

En otras palabras, la pregunta es si existe una $\mathbf{x}\in\mathbb{Z}^m$, $\mathbf{x}\geq\mathbf{0}$, de modo que $A\mathbf{x}\geq\mathbf{b}$ ($\mathbf{b}\geq\mathbf{0}$).

Mike contribuciones a continuación han sido muy valiosa, y aún así parece que no hay manera más simple de determinar esto–, pero todavía no estamos muy seguros, así que voy a dejar esta pregunta abierta un poco más de tiempo.

Yo creo, sin embargo, que en mi caso especial, una cosa que se tiene: Dadas las condiciones anteriores, si existe una solución para el problema relajado (es decir,, $\mathbf{x}\in\mathbb{R}^m$, $\mathbf{x}\geq\mathbf{0}$), a continuación, una solución integral que existe. He puesto esto en una pregunta aparte. Pero suponiendo que tiene, tal vez el relajado versión tiene una manera más sencilla para comprobar la solvencia?

¿Tienes una dirección en la que se me señale, o una idea de cómo ir sobre esto? O, tal vez, es Simple la única manera de averiguarlo?

Gracias de antemano por las sugerencias!

Answer 1

Por desgracia, en general, no hay ningún método rápido. En algunos casos especiales (por ejemplo, el origen es factible) determinar si un problema de programación lineal tiene una solución es bastante fácil, pero a falta de algo así como que el problema es computacionalmente difícil como encontrar una solución óptima. Así que, sí, en general simplex es realmente la única manera de averiguarlo.

Por ejemplo, si el origen no es posible, el método simplex es necesario utilizar algún método para encontrar una primera solución factible. Los métodos más comunes (por ejemplo, el Big-M método, la Fase I de una de dos fases método dual simplex) suponen resolver problemas de programación lineal a sí mismos. Así que, en general, la búsqueda de una solución factible es equivalente a la solución de algún problema de programación lineal para la optimalidad.

Con más información sobre la estructura de $A$, sin embargo, que podría ser capaz de decir algo. Por ejemplo, el doble de su problema (como un LP, sin el entero de restricción) es

$$\begin{align} \text{Minimize}&& {\bf b}^T {\bf y} \\ \text{subject to}&& A^T {\bf y} &\leq \mathbf{1} \\ && {\bf y} &\geq 0 . \end{align}$$

El origen es factible para el dual. Con más información sobre las entradas en $A$, si usted puede demostrar que el dual es limitada, a continuación, fuerte dualidad implica que su problema original (de nuevo, como un LP) tiene una solución factible.

---

Todo lo que he dicho hasta ahora es que el LP caso. El programa entero caso es aún peor, como programación entera es mucho más difícil de programación lineal. De hecho, el problema de saber si un número entero programa tiene una solución factible es un curso de la investigación. Hay un buen resumen de la historia de este problema en la introducción de este documento "Hacia el más Rápido de Programación Entero" (que parece ser alguien de la propuesta de tesis).

---

El OP pregunta en los comentarios para ver un ejemplo de un sistema de $A {\bf x} \geq {\bf b}$, con ${\bf x} \geq {\bf 0}$, ${\bf b} \geq {\bf 0}$, y real de las entradas en $A$, pero que no tiene una solución no acotada conjunto. Este sistema es

$$\begin{align} x - y & \geq 1 \\ y - x &\geq 1 \\ x, y &\geq 0. \end{align}$$ No sólo es el conjunto solución no acotada, es vacío.