LISTA DE PROBLEMAS

El problema de asignación cuadrática ( QAP ) es uno de los problemas fundamentales de optimización combinatoria en la rama de optimización o investigación de operaciones en matemáticas , desde la categoría de los problemas de ubicación de las instalaciones .

El problema modela el siguiente problema de la vida real:

Hay un conjunto de n instalaciones y un conjunto de n ubicaciones. Para cada par de ubicaciones, se especifica una distancia y para cada par de instalaciones se especifica un peso o flujo (por ejemplo, la cantidad de suministros transportados entre las dos instalaciones). El problema es asignar todas las instalaciones a diferentes ubicaciones con el objetivo de minimizar la suma de las distancias multiplicadas por los flujos correspondientes.

Intuitivamente, la función de costos alienta a las fábricas con altos flujos entre sí a ubicarse juntas.

La declaración del problema se parece a la del problema de asignación , excepto que la función de costo se expresa en términos de desigualdades cuadráticas, de ahí el nombre.

Definición matemática formal [ editar ]

La definición formal del problema de asignación cuadrática es la siguiente:

Dados dos conjuntos, P ( "instalaciones") y L ( "sitios"), de igual tamaño, junto con una función de ponderación w  : P × P → R y una función de distancia d  : L × L → R . Encuentre la biyección f  : P → L ("asignación") tal que la función de costo:

$${\ displaystyle \ sum _ {a, b \ en P} w (a, b) \ cdot d (f (a), f (b))}

se minimiza

Por lo general, las funciones de peso y distancia se ven como matrices cuadradas de valor real , de modo que la función de costo se escribe como:

$${\ displaystyle \ sum _ {a, b \ en P} w_ {a, b} d_ {f (a), f (b)}}

En notación matricial:

$${\ displaystyle \ min _ {X \ in \ Pi _ {n}} \ operatorname {trace} (WXDX ^ {T})}

dónde $${\ displaystyle \ Pi _ {n}} es el conjunto de $${\ displaystyle n \ times n} matrices de permutación, $${\ displaystyle W} es la matriz de peso y $${\ displaystyle D} es la matriz de distancia

Complejidad computacional [ editar ]

El problema es NP-hard , por lo que no existe un algoritmo conocido para resolver este problema en tiempo polinómico, e incluso las instancias pequeñas pueden requerir un tiempo de cálculo prolongado. También se demostró que el problema no tiene un algoritmo de aproximación que se ejecute en tiempo polinómico para ningún factor (constante), a menos que P = NP. ^[1] El problema del vendedor ambulante puede verse como un caso especial de QAP si se supone que los flujos conectan todas las instalaciones solo a lo largo de un solo anillo, todos los flujos tienen el mismo valor distinto de cero (constante). Muchos otros problemas de problemas de optimización combinatoria estándar pueden escribirse de esta forma.

Aplicaciones [ editar ]

Además de la formulación original de la ubicación de la planta, QAP es un modelo matemático para el problema de la colocación de componentes electrónicos interconectados en una placa de circuito impreso o en un microchip , que es parte de la etapa de ubicación y ruta del diseño asistido por computadora en la industria electrónica. 

La programación cuadrática (QP) es el proceso de resolver un tipo especial de problema de optimización matemática , específicamente, un problema de optimización cuadrática (restringido linealmente), es decir, el problema de optimizar (minimizar o maximizar) una función cuadrática de varias variables sujetas a lineal restricciones sobre estas variables. La programación cuadrática es un tipo particular de programación no lineal .

Formulación del problema [ editar ]

El problema de programación cuadrática con n variables ym restricciones puede formularse de la siguiente manera. ^[1] Dado:

• un vector n -dimensional de valor real c ,
• una matriz simétrica real n × n -dimensional Q ,
• una matriz real m × n -dimensional A , y
• un vector real b dimensional m ,

El objetivo de la programación cuadrática es encontrar un vector n- dimensional x , que

$${\ displaystyle {\ text {minimizar}}}	$${\ displaystyle {\ tfrac {1} {2}} \ mathbf {x} ^ {\ mathrm {T}} Q \ mathbf {x} + \ mathbf {c} ^ {\ mathrm {T}} \ mathbf {x }}
$${\ displaystyle {\ text {sujeto a}}}	$${\ displaystyle A \ mathbf {x} \ preceq \ mathbf {b},}

donde x ^T denota la transposición del vector de$${\ displaystyle \ mathbf {x}}. La notación A x ⪯ b significa que cada entrada del vector A x es menor o igual que la entrada correspondiente del vector b .

Se puede plantear un problema de programación relacionado, la programación cuadrática restringida cuadráticamente , agregando restricciones cuadráticas a las variables.

Métodos de solución [ editar ]

Para problemas generales, se utilizan comúnmente una variedad de métodos, que incluyen

• punto interior ,
• conjunto activo , ^[2]
• Lagrangian aumentada , ^[3]
• gradiente conjugado ,
• proyección de gradiente ,
• extensiones del algoritmo simplex . ^[2]

En el caso en que Q sea positivo definido , el problema es un caso especial del campo más general de optimización convexa .

Restricciones de igualdad [ editar ]

La programación cuadrática es particularmente simple cuando Q es positivo definido y solo hay restricciones de igualdad; específicamente, el proceso de solución es lineal. Al usar multiplicadores de Lagrange y buscar el extremo de los lagrangianos, se puede demostrar fácilmente que la solución al problema de igualdad restringida

$${\ displaystyle {\ text {Minimize}} \ quad {\ tfrac {1} {2}} \ mathbf {x} ^ {\ mathrm {T}} Q \ mathbf {x} + \ mathbf {c} ^ {\ mathrm {T}} \ mathbf {x}}

$${\ displaystyle {\ text {sujeto a}} \ quad E \ mathbf {x} = \ mathbf {d}}

está dado por el sistema lineal

{\ displaystyle {\ begin {bmatrix} Q & E ^ {T} \\ E & 0 \ end {bmatrix}} {\ begin {bmatrix} \ mathbf {x} \\\ lambda \ end {bmatrix}} = {\ begin {bmatrix } - \ mathbf {c} \\\ mathbf {d} \ end {bmatrix}}}

dónde $${\ displaystyle \ lambda} es un conjunto de multiplicadores de Lagrange que salen de la solución junto con $${\ displaystyle \ mathbf {x}}.

La forma más fácil de acercarse a este sistema es la solución directa (por ejemplo, factorización LU ), que para problemas pequeños es muy práctica. Para problemas grandes, el sistema plantea algunas dificultades inusuales, más notablemente que el problema nunca es definitivo positivo (incluso si$${\ displaystyle Q}es), lo que hace que sea muy difícil encontrar un buen enfoque numérico, y hay muchos enfoques para elegir dependiendo del problema. ^[4]

Si las restricciones no acoplan demasiado las variables, un ataque relativamente simple es cambiar las variables para que las restricciones se cumplan incondicionalmente. Por ejemplo, supongamos$${\ displaystyle \ mathbf {d} = 0}(generalizar a distinto de cero es sencillo). Mirando las ecuaciones de restricción:

$${\ displaystyle E \ mathbf {x} = 0}

introducir una nueva variable $${\ displaystyle \ mathbf {y}} definido por

$${\ displaystyle Z \ mathbf {y} = \ mathbf {x}}

dónde $${\ displaystyle \ mathbf {y}} tiene dimensión de $${\ displaystyle \ mathbf {x}}menos el número de restricciones. Luego

$${\ displaystyle EZ \ mathbf {y} = 0}

y si $${\ displaystyle Z} es elegido para que $${\ displaystyle EZ = 0}la ecuación de restricción siempre será satisfecha. Encontrar tal$${\ displaystyle Z}implica encontrar el espacio nulo de$${\ displaystyle E}, que es más o menos simple dependiendo de la estructura de $${\ displaystyle E}. La sustitución en la forma cuadrática da un problema de minimización sin restricciones:

$${\ displaystyle {\ tfrac {1} {2}} \ mathbf {x} ^ {T} Q \ mathbf {x} + \ mathbf {c} ^ {T} \ mathbf {x} \ quad \ Rightarrow \ quad { \ tfrac {1} {2}} \ mathbf {y} ^ {T} Z ^ {T} QZ ​​\ mathbf {y} + (Z ^ {T} \ mathbf {c}) ^ {T} \ mathbf {y }}

cuya solución viene dada por:

$${\ displaystyle Z ^ {T} QZ ​​\ mathbf {y} = -Z ^ {T} \ mathbf {c}}

Bajo ciertas condiciones en $${\ displaystyle Q}, la matriz reducida $${\ displaystyle Z ^ {T} QZ}Será positivo definitivo. Es posible escribir una variación en el método de gradiente conjugado que evite el cálculo explícito de$${\ displaystyle Z}. ^[5]

Dualidad lagrangiana [ editar ]

Ver también: problema dual

El dual lagrangiano de un QP es también un QP. Para ver eso, centrémonos en el caso donde$${\ displaystyle c = 0}y Q es positivo definido. Escribimos la función lagrangiana como

$${\ displaystyle L (x, \ lambda) = {\ tfrac {1} {2}} x ^ {T} Qx + \ lambda ^ {T} (Ax-b).}

Definición de la función dual (lagrangiana) $${\ displaystyle g (\ lambda)} como $${\ displaystyle g (\ lambda) = \ inf _ {x} L (x, \ lambda)}, encontramos un infimum de$${\ displaystyle L}, utilizando $${\ displaystyle \ nabla _ {x} L (x, \ lambda) = 0} y definición positiva de Q:

$${\ displaystyle x ^ {*} = - Q ^ {- 1} A ^ {T} \ lambda.}

Por lo tanto, la doble función es

$${\ displaystyle g (\ lambda) = - {\ tfrac {1} {2}} \ lambda ^ {T} AQ ^ {- 1} A ^ {T} \ lambda - \ lambda ^ {T} b,}

y entonces el dual lagrangiano del QP es

$${\ displaystyle {\ text {maximizar}} \ quad - {\ tfrac {1} {2}} \ lambda ^ {T} AQ ^ {- 1} A ^ {T} \ lambda - \ lambda ^ {T} b }

Además de la teoría de la dualidad lagrangiana, hay otros emparejamientos de dualidad (por ejemplo , Wolfe , etc.).

Complejidad [ editar ]

Para Q positivo definido , el método elipsoide resuelve el problema en un tiempo polinomial (débilmente) . ^[6] Si, por otro lado, Q es indefinido, entonces el problema es NP-duro . ^[7] De hecho, incluso si Q tiene solo un valor propio negativo , el problema es (fuertemente) NP-duro . ^[8]

Solventes y lenguajes de scripting (programación) [ editar ]

Nombre	Breve informacion
OBJETIVOS	Un sistema de software para modelar y resolver problemas de optimización y programación
ALGLIB	Biblioteca numérica con doble licencia (GPL / propietaria) (C ++, .NET).
AMPL	Un lenguaje de modelado popular para la optimización matemática a gran escala.
Monitor de AP	Conjunto de modelado y optimización para sistemas LP , QP, NLP , MILP , MINLP y DAE en MATLAB y Python.
CGAL	Un paquete de geometría computacional de código abierto que incluye un solucionador de programación cuadrática.
CPLEX	Solucionador popular con una API (C, C ++, Java, .Net, Python, Matlab y R). Gratis para académicos.
Función de solucionador de Excel	Un solucionador no lineal ajustado a hojas de cálculo en las que las evaluaciones de funciones se basan en las celdas de recálculo. Versión básica disponible como complemento estándar para Excel.
GAMS	Un sistema de modelado de alto nivel para la optimización matemática.
Gurobi	Solucionador con algoritmos paralelos para programas lineales a gran escala, programas cuadráticos y programas de enteros mixtos. Gratis para uso académico.
IMSL	Un conjunto de funciones matemáticas y estadísticas que los programadores pueden integrar en sus aplicaciones de software.
IPOPT	Ipopt (Interior Point OPTimizer) es un paquete de software para la optimización no lineal a gran escala
Artelys Knitro	Un paquete integrado para la optimización no lineal
Arce	Lenguaje de programación de propósito general para las matemáticas. La solución de un problema cuadrático en Maple se logra a través de su comando QPSolve .
MATLAB	Un lenguaje de programación de propósito general y orientado a la matriz para la computación numérica. La programación cuadrática en MATLAB requiere la Caja de herramientas de optimización además del producto base de MATLAB
Mathematica	Un lenguaje de programación de propósito general para las matemáticas, que incluye capacidades simbólicas y numéricas.
MOSEK	Un solucionador para la optimización a gran escala con API para varios lenguajes (C ++, Java, .Net, Matlab y Python)
Biblioteca numérica NAG	Una colección de rutinas matemáticas y estadísticas desarrolladas por el Grupo de Algoritmos Numéricos para múltiples lenguajes de programación (C, C ++, Fortran, Visual Basic, Java y C #) y paquetes (MATLAB, Excel, R, LabVIEW). El capítulo de Optimización de la Biblioteca NAG incluye rutinas para problemas de programación cuadrática con matrices de restricciones lineales dispersas y no dispersas, junto con rutinas para la optimización de sumas de cuadrados lineales, no lineales, de funciones lineales o no lineales con restricciones no lineales, acotadas o sin restricciones. . La Biblioteca NAG tiene rutinas para la optimización local y global, y para problemas continuos o enteros.
Octava GNU	Un lenguaje de programación gratuito (su licencia es GPLv 3) de propósito general y orientado a matrices para computación numérica, similar a MATLAB. La programación cuadrática en GNU Octave está disponible a través de su comando qp
R (Fortran)	Marco de cómputo estadístico universal multiplataforma con licencia GPL , consulte su página quadprog . Portado a javascript bajo licencia MIT . Portado a C # bajo LGPL .
SAS / OR	Un conjunto de solucionadores para la optimización lineal, entera, no lineal, sin derivados, de red, combinatoria y de restricción; el lenguaje de modelado algebraico OPTMODEL ; y una variedad de soluciones verticales dirigidas a problemas / mercados específicos, todos los cuales están completamente integrados con el Sistema SAS .
TK Solver	Sistema de software de modelado matemático y resolución de problemas basado en un lenguaje declarativo basado en reglas, comercializado por Universal Technical Systems, Inc ..
TOMLAB	Admite la optimización global, la programación de enteros, todos los tipos de mínimos cuadrados, la programación lineal, cuadrática y sin restricciones para MATLAB . TOMLAB admite solucionadores como Gurobi , CPLEX , SNOPT y KNITRO .
XPRESS	Solucionador para programas lineales a gran escala, programas cuadráticos, programas generales no lineales y enteros mixtos. Tiene API para varios lenguajes de programación, también tiene un lenguaje de modelado Mosel y funciona con AMPL, GAMS . Gratis para uso académico.