¿Existe en la práctica un límite en el número de restricciones en un problema de programación lineal?

Soy nuevo en programación lineal y he formulado un programa lineal (LP) con un orden de variables y restricciones, aunque la matriz de restricciones es extremadamente escasa. 10 $10^{13}$$10^{13}$

¿Quería saber si un LP de esta escala es manejable o no?

10 5 10 $10^{13}$ es más que manejable en las supercomputadoras más grandes de la actualidad debido principalmente a los límites de memoria. Los problemas más grandes que he visto prácticamente resueltos han tenido del orden de filas y columnas, pero el factor más importante tiende a ser el número de nonzeros, donde solo estamos cruzando para resolver problemas con nonzeros. Consulte la página de puntos de referencia paralelos de Mittelman para tener una idea de lo que pueden hacer los mejores solucionadores disponibles y comerciales en una variedad de problemas a este tamaño.$10^5$$10^6$

Una gran cantidad de restricciones de desigualdad generalmente es manejable mediante técnicas de generación de restricciones, procesando en cada momento solo un número limitado de restricciones y agregando restricciones violadas en la solución actual al conjunto de restricciones (al tiempo que elimina las muy satisfechas). Pero en los casos que he visto, esto requiere que el número de variables no flojas también sea limitado.

Entonces, la pregunta es si puede reformular su problema de tal manera que el problema en sí mismo o su dual tenga muchas menos variables que restricciones.

Editar: Véase también el trabajo reciente de Nesterov sobre '' Métodos de subgrado para problemas de optimización a gran escala '', http://dial.academielouvain.be/vital/access/services/Download/boreal:107876/PDF_01 . Su técnica funciona en circunstancias favorables con una complejidad de si los requisitos de precisión son moderados.$O(n\log n)$

Mi comentario sobre la respuesta de Aron se hizo demasiado largo, pero me gustaría aumentar su respuesta:

Me gusta mencionar el ejemplo de los puntos de referencia paralelos. Varios comentarios para agregar aquí. Los cuatro solucionadores probados son comerciales, pero tienen licencias académicas gratuitas disponibles. Además, la prueba reduce el tiempo de ejecución a 25000, o ~ 8 h, que es arbitrario y depende en gran medida de las limitaciones de recursos externos (es decir, en una empresa, las personas pueden no estar dispuestas a esperar más de un día para obtener resultados; en el ámbito académico, algunas personas pueden ejecutar sus simulaciones durante meses). La prueba se ejecuta en una sola máquina de cuatro núcleos, lo que no es indicativo, para mí, del rendimiento de vanguardia.

Cuando estaba buscando datos para responder a esta pregunta, encontré documentos hace más de 10 años que resolvían problemas de aproximadamente el mismo tamaño, lo que me sugiere que podríamos mejorar ahora con la infraestructura que tenemos. Ciertamente no son variables, pero basadas en la escala n 3.5 de los métodos de punto interior , si el álgebra lineal y el paralelismo se implementaron bien, y tuviste el tiempo y un grupo de tamaño modesto, no veo por qué no pudiste intentar para resolver un problema con 10 7 o tal vez 10 $10^{13}$$n^{3.5}$$10^{7}$ $10^{8}$variables (solo si tuviera una estructura especial que podría explotar con métodos de descomposición como la descomposición de Benders o Dantzig-Wolfe, además de algoritmos de generación de plano de corte). (Agregaré que estoy ignorando el efecto de las restricciones, que complican las cosas dependiendo de cuántos bits estén almacenados; este efecto solo hace que las estimaciones a continuación sean más pesimistas).

Creo que GAMS tiene una implementación paralela, y dado que utiliza solucionadores como CPLEX, Gurobi, MOSEK y Xpress (es decir, los cuatro solucionadores en las citas de referencia de Aron), no veo por qué uno no puede ejecutar instancias paralelas de esos solucionadores (de hecho, sé que esto es posible para CPLEX y Gurobi). Los factores limitantes serán la memoria (porque la memoria es cara) y la comunicación más que la potencia de procesamiento, ya que un programa lineal reduce, en última instancia, a construir y resolver un sistema de ecuaciones lineales repetidamente (una simplificación masiva, sí, pero el álgebra lineal es algo que nosotros saber paralelizar).

$10^{13}$$10^{24}$

Como una estimación de orden de magnitud muy aproximada, el Intel Core 2 Quad utilizado en las citas de referencia de Aron puede operar a una velocidad máxima de 40 gigaflops. Suponiendo que te subieras a Jaguar, la supercomputadora del Laboratorio Nacional de Oak Ridge, y pudieras usar toda la máquina (extremadamente improbable, pero soñemos en grande), tendrías aproximadamente 2 petaflops a tu alcance (según los números TOP 500 aquí , o aproximadamente 50000 veces la potencia de cómputo, sin contar las penalizaciones debido a la comunicación, las limitaciones de memoria o el hecho de que nunca nadie corre a la velocidad máxima (ni siquiera el punto de referencia LINPACK).

$10^{6}$$10^{7}$$10^{6}$$10^{13}$$10^{17}$$10^{18}$

Es una vieja pregunta, pero bueno, hace más de 25 años alguien ya podía resolver un problema de restricción de 1.1M, 2.6M variable en 3h en un clúster de PC. http://www.maths.ed.ac.uk/~gondzio/CV/finance.pdf

Me gustaría ver las ecuaciones generadoras, quizás sea inteligente hacer una descomposición seria antes de lanzar este problema a los algoritmos, y me gustaría decir como practicante que tal vez sea inteligente masticarlo antes de alimentar el hardware. También suena como el tamaño que induciría a errores numéricos en la formulación dada la memoria y precisión limitadas de la computadora.