Resolución de problemas con un objetivo cuadrático (QP)

Describe la resolución de problemas de programación cuadrática (QP) con CPLEX.

CPLEX resuelve programas cuadráticos; es decir, un modelo en el que las restricciones son lineales, pero la función de objetivo puede contener uno o más términos cuadráticos. Estos problemas también se conocen como QP. Cuando estos problemas son convexos, CPLEX normalmente los resuelve eficazmente en tiempo polinómico. Sin embargo, se sabe que los QP no convexos son bastante difíciles. En términos teóricos, se caracterizan como NP difícil. CPLEX aplica diversos enfoques a estos problemas, como por ejemplo métodos de algoritmos de barrera o algoritmos de ramificación y acotamiento. Especialmente en el enfoque de ramificación y acotamiento, no hay garantía teórica sobre la complejidad de dicho tipo de problema. En consecuencia, la solución de un problema de ese tipo (es decir, un QP no convexo) puede tener muchas órdenes de magnitud con una longitud mayor que la solución de un QP convexo de dimensiones comparables. En los temas siguientes se trata la cuestión de cómo distinguir dichos problemas y se describen los recursos que ofrece CPLEX para solucionarlos.