Programación lineal: Más variables o más restricciones, que es mejor?

Question

Esta es más una cuestión práctica, en lugar de la pregunta de Matemática.

Tengo un LP que ha $n$ variables e $m$ constriñe, donde $ n << m $. Si puedo convertir esto en su doble forma, tendré $m$ variables e $n$ restricciones.

Desde el punto de vista práctico, que de estos casos (Doble o Primal), es más fácil (más rápido) para ser resuelto con paquetes comerciales (decir Gurobi) ?

Answer 1

Comercial solucionadores como Gurobi analizar la estructura de un problema y decidir si el problema es el más adecuado para resolver en primal o dual formulario.

Como regla general, los usuarios no deben preocuparse por esto. De hecho, a menudo puede ser contraproducente para un usuario para intentar sonsacarle el problema en forma estándar---por ejemplo, por la separación de variables libres, la conversión de las restricciones de igualdad en las ecuaciones, etc. Después de todo, el solucionador puede haber hecho una elección diferente de lo que ustedes hicieron.

Cada solver es diferente, y no necesariamente saben qué norma interna de la forma que cada uno utiliza. Así que vamos a considerar un ejemplo prototípico, un solucionador llamado GuroPlex construido en torno a los siguientes interna de la forma estándar: $$ \begin{array}{ll} \text{minimize} & c^T x \\ \text{subject to} & A x = b \\ & x \geq 0 \end{array} $$ El dual de este modelo es la desigualdad limitada formulario: $$ \begin{array}{ll} \text{maximize} & b^T y \\ \text{subject to} & A^T y \leq c \end{array} $$ Como usted probablemente sabe, en todos, pero la mayoría de los degenerados de los casos, resolver el problema primal fácilmente conduce a una solución para el problema dual, y viceversa. En efecto, GuroPlex resuelve ambos problemas al mismo tiempo.

Ahora, supongamos que hemos construido un LP a resolver, y que pasa a parecerse a la desigualdad de la forma. Sabiendo GuroPlex interna de forma estándar, se podría convertir a nosotros mismos mediante la creación de variables de holgura $z \geq 0$ y la división de las variables libres $y$ en la diferencia de nonnegatives $y_+-y_-$: $$ \begin{array}{ll} \text{maximize} & b^T ( y_+ - y_- ) \\ \text{subject to} & A^T ( y_+ - y_- ) + z = c \\ & y_+,y_-,z\geq 0 \end{array} $$ El resultado es una forma que se adapte a GuroPlex estándar de forma perfectamente---bien, guardar el maximizar/minimizar la diferencia, pero que es fácilmente fijado por la negación de la objetivo. También es más grande de lo que era antes, con más de dos veces la cantidad de variables (dos para cada una de las $y_i$ y uno para cada una de las desigualdades).

Usted podría hacer esto, pero usted no. Sólo pienso GuroPlex el problema original. GuroPlex se detecta que el problema coincide con el doble de su forma estándar, y construir y resolver el dual del problema en su lugar. La solución a tu problema será extraído de la interna de multiplicadores de Lagrange. (Uno podría argumentar que, dado que está resolviendo el primal y dual problemas al mismo tiempo, no hay nada para "extraer". ¡Que así sea! El punto es el mismo.)

¿Qué pasa si su problema no está en cualquiera de estas formas? Por ejemplo, ¿qué pasa si contiene una mezcla de ecuaciones y de desigualdades? Lo que si parece que la forma primordial, a excepción de algunas de las variables sin restricciones? Lo que si tiene límites inferior y superior? Puede ser difícil para que usted decida si GuroPlex sería más eficiente de resolver el primal o dual de la forma de su problema.

Así que no decidir. Dejar que el software haga que.

Y ciertamente no se dividen las variables libres, dividir las ecuaciones, o agregar variables de holgura. Que puede hacer que sea más difícil para el solver para hacer la determinación correcta. De hecho, algunos de los mejores solucionadores de saber que a la gente hacer este tipo de trucos, porque ellos fueron enseñados a hacerlo en el colegio---y puede revertir los cambios. Pero no presolver es perfecto.

Sin duda, cada vez en un rato, hay un problema que engaña al solver, y alimentar manualmente el doble o hacer otros cambios en el modelo de mejora de rendimiento. Pero en general, usted estará mejor servido por salir de su problema en la forma natural en que se presenta.