Solución avanzada de LP

A pesar de la madurez de la tecnología de LP, algunos casos de uso requieren técnicas más avanzadas. Por ejemplo, hay disponibles una serie de implementaciones y algoritmos de LP diferentes, cada uno de los cuales tiene fortalezas y debilidades. Además, la inestabilidad numérica puede hacer que los solucionadores se ralenticen o no puedan resolver ciertos modelos.

En esta guía, se presentan los conceptos y se proporcionan ejemplos para ayudarte a obtener el máximo rendimiento y confiabilidad de los solucionadores de problemas de LP.

Conceptos

En esta sección, se presentan los conceptos clave para el uso avanzado de los solucionadores de LP. Suponemos que los lectores están familiarizados con el concepto de dualidad en LP.

Familias de algoritmos del LP

Se puede acceder a las siguientes clases de algoritmos para LP desde las herramientas OR.

  1. El algoritmo Simplex fue el primer algoritmo práctico de LP y sigue siendo el más popular. El algoritmo camina a lo largo de los vértices (puntos de esquina) de la región posible y mejora de forma iterativa el valor de la función objetivo hasta alcanzar una solución óptima. Existen dos tipos de algoritmos simplex:

    1. Primal simplex realiza pasos a lo largo de los vértices de la región principal viable. Esta variante es particularmente efectiva para resolver una secuencia de problemas de LP con diferentes funciones objetivas, es decir, donde se fija la región principal posible.
    2. simplex dual realiza pasos a lo largo de los vértices de la región dual posible. Esta variante es particularmente efectiva para resolver una secuencia de problemas de LP en la que la región doble factible es fija, por ejemplo, cuando solo cambian los límites de las variables. Por este motivo, el simplex doble se usa ampliamente en los solucionadores MIP.

  2. Los métodos de barrera o punto interior fueron la segunda familia práctica de algoritmos para LP. Los métodos de barrera combinan garantías teóricas de convergencia eficiente (tiempo polinómica) con un rendimiento confiable en la práctica. Complementan el algoritmo simplex cuando tienen un rendimiento deficiente. Por ejemplo, algunos solucionadores ofrecen ejecutar tanto simplex como barrera en paralelo, y muestran la solución desde el algoritmo que primero finaliza.

  3. Los métodos de primer orden son una familia de algoritmos que usan exclusivamente información de gradientes (es decir, derivadas de primer orden) para guiar las iteraciones. El descenso de gradientes es un ejemplo conocido. Estos métodos son populares en la optimización no lineal y el aprendizaje automático. Para el LP, los métodos de primer orden pueden escalar a problemas más grandes que simplex y de barrera, y también pueden tener requisitos de memoria mucho menores. Por otro lado, son más sensibles a los problemas numéricos y pueden tener dificultades para obtener soluciones altamente precisas.

En la siguiente tabla, se enumeran los solucionadores de problemas de LP disponibles en las herramientas del OR y se indica cuál de las tres familias de algoritmos se implementa en cada solucionador.

Resolutor Simplex Barrier Primer pedido
Clp X X
CPLEXL X X
GlopG X
GLPK X X
GurobiL X X
PDLPG X
XpressL X X

G indica que Google desarrolló el solucionador. L indica que el agente requiere una licencia emitida por el desarrollador externo correspondiente.

Consulta Recomendaciones para obtener sugerencias sobre qué solucionadores y algoritmos usar.

¿Qué significa realmente resolver?

Para aprovechar al máximo los solucionadores de LP, es importante comprender qué se implica cuando un solucionador afirma haber encontrado una solución a un problema de LP. En esta sección, se abordan los conceptos básicos necesarios para responder esta pregunta, en particular debido a la imprecisión numérica y la no singularidad de las soluciones.

Tolerancias

Los solucionadores de LP casi siempre usan la aritmética de punto flotante, por lo que sus soluciones están sujetas a imprecisión numérica. Para dar cuenta de esto y mejorar el rendimiento mediante la prevención de esfuerzos en soluciones que ya son lo suficientemente buenas, los solucionadores aceptan soluciones (y afirman haber resuelto un problema) cuando estas soluciones satisfacen las condiciones hasta ciertas tolerancias.

Considerar el problema de la programación lineal

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

y su problema doble correspondiente

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

Este par de problemas tiene una solución primaria óptima única de $ x_1 = 1, x_2 = 0 $ y solución dual $ y = -2 $. ¿Qué soluciones pueden aceptarse como óptimas en un solucionador? Para responder a esta pregunta, definimos las siguientes cantidades:

  • La brecha de duplicación es la diferencia entre el valor objetivo principal y el valor objetivo doble, en este caso, $ |(-2x_1 - x_2) - y| $.
  • Las incapacidades principales son el incumplimiento de las restricciones principales, en este caso, $ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2, 0\}) $.
  • Las incapacidades dobles son las infracciones de las restricciones dobles, en este caso, $ (\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \}) $.

Un solucionador declara que una solución es óptima si la brecha de la dualidad, las incapacidades principales y las incapacidades dobles son menores que una tolerancia determinada.1

En particular, la aplicación de las tolerancias varía por razones tanto idiosincráticas como naturales en los solucionadores y los algoritmos. Por ejemplo, la brecha de dualidad en el algoritmo simplex solo está impulsada por la imprecisión numérica, mientras que las incapacidades primarias y dobles están presentes incluso en la aritmética exacta. Algunos métodos aplican directamente las restricciones vinculadas $ x_1 \ge 0, x_2 \ge 0, $ y $ y \le 0 $, mientras que otros tratan a las infracciones de las restricciones vinculadas de forma diferente a las infracciones de las restricciones lineales, como $x_1 + x_2 \le 1$. Para algunos solucionadores, las tolerancias son absolutas y las tolerancias son absolutas y, por lo tanto, las tolerancias son absolutas y $epeficientes.

Para ver un ejemplo del efecto de las tolerancias, considera una tolerancia absoluta de $ \epsilon = \frac{1}{2} $ aplicada al par primario-dual anterior. La solución $ x_1 = 1.5, x_2 = 0, y = -3 $ tiene una brecha de dualidad cero e incapacidades menores que $ \epsilon $, por lo que un solucionador podría declarar esta solución "óptima". Sin embargo, su valor objetivo (-3) difiere en 1 del valor objetivo óptimo verdadero de -2. Los valores predeterminados típicos de $ \epsilon $ están entre $10^{-6}$ y $10^{-8}$, lo que hace que estos ejemplos extremos sean raros, pero no imposibles.

Tipos de soluciones

Los problemas de LP pueden tener más de una solución óptima, incluso más cuando se tienen en cuenta las tolerancias. Analizamos brevemente las propiedades de las soluciones que muestran las tres familias diferentes de algoritmos de LP que se presentaron anteriormente.

Los algoritmos simplex siempre muestran vértices o puntos de esquinas de la región posible. En algunas situaciones, se prefieren estas soluciones porque tienden a ser más dispersas.

Los métodos de barrera y de primer orden generalmente no devuelven vértices. (Theory proporciona caracterizaciones adicionales que están fuera del alcance de esta guía).

Por razones históricas, y debido a que las soluciones de vértices tienen propiedades atractivas, los solventes suelen, de forma predeterminada, aplicar un procedimiento de crossover para moverse a un vértice óptimo a partir de una solución que encontró un algoritmo de barrera. Por el momento, Crossover no se ofrece para soluciones que se encuentran en métodos de primer orden.

Recomendaciones

Haz las siguientes recomendaciones para un uso avanzado de los solucionadores de LP.

Escalamiento de los datos del problema

Los solucionadores pueden experimentar una convergencia lenta o fallas en los modelos debido a problemas numéricos. Esos problemas pueden surgir por muchos motivos; a continuación, te mostramos un ejemplo.

Es común que las constantes numéricas muy pequeñas o grandes aparezcan en los modelos de LP. Para ampliar el ejemplo anterior, si \(x_1\) y \(x_2\) representan la fracción de clientes asignados a "proveedor 1" o "proveedor 2", y si queremos maximizar el beneficio de la prestación de servicios a estos clientes, podemos escribir la siguiente función objetivo:

$$ \min -c_1x_1 - c_2x_2 $$

Donde:

  • $ c_1 $ es el beneficio de asignar clientes al proveedor 1.
  • $ c_2 $ es el beneficio de asignar clientes al proveedor 2.

Los dobles que cumplan con las siguientes restricciones se considerarían factibles con una tolerancia absoluta $ \epsilon $:

  • $ y \le -c_1 + \epsilon $,
  • $ y \le -c_2 + \epsilon $.

Si las unidades de beneficios de $ c_1 $ y $ c_2 $ son valores fraccionarios pequeños que suceden en la misma escala que $ \epsilon $, las condiciones de viabilidad doble se vuelven bastante débiles, por lo que un primario muy subóptimo se puede declarar como óptimo.

Si, por otro lado, las unidades de beneficios son “microdólares” (1 000,000 microdólares = 1 dólar), los valores absolutos resultantes muy grandes solicitan una precisión muy alta en la solución, posiblemente irrazonablemente alta, dados los límites de los números de punto flotante. Es posible que los solucionadores no converjan si el problema se formula de esta manera. Como parte de la formulación de un problema bien planteado, los modeladores avanzados deben considerar si los datos del problema se escalan de manera coherente con las tolerancias de los solucionadores.

Además de evitar fallas numéricas, las tolerancias también se pueden ajustar para lograr un mejor rendimiento. Los métodos simplex y de barrera no son demasiado sensibles a las tolerancias, pero, en ocasiones, pueden beneficiarse de tolerancias más grandes si se observa que el progreso se detiene al final de la solución. Por otro lado, los métodos de primer orden suelen ser mucho más sensibles. Los usuarios de métodos de primer orden pueden beneficiarse de soluciones más rápidas flexibilizando las tolerancias, según lo permita el contexto.

Para conocer las tolerancias de Glop, consulta primal_feasibility_tolerance, dual_feasibility_tolerance y solution_feasibility_tolerance en GlopParameters. Ten en cuenta que primal_feasibility_tolerance y dual_feasibility_tolerance se usan dentro del algoritmo, mientras que solution_feasibility_tolerance se verifica después de la resolución para marcar problemas numéricos. Para PDLP, consulta eps_optimal_absolute y eps_optimal_relative.

Si deseas obtener más información sobre este tipo de problemas, consulta los Lineamientos para problemas numéricos de Gurobi. Si bien los lineamientos están redactados para los usuarios de Gurobi, muchos de los principios se aplican en general.

Elección de solucionadores y algoritmos

Comenzamos con un ejemplo de lo grande que puede ser el impacto de la elección de solucionadores de problemas y algoritmos y, luego, presentamos una guía para elegir solucionadores de problemas de LP.

Variabilidad en la práctica

A fin de ilustrar la variabilidad del rendimiento en los algoritmos y los solucionadores de LP, comparamos los tiempos de resolución en una selección de instancias que Hans Mittelmann usó para realizar comparativas en solucionadores de LP. Las instancias se eligen de manera explícita para mostrar los extremos del rendimiento relativo y no son necesariamente representativas del comportamiento típico.

Los métodos simplex primario y doble de Glop se comparan con el método de barrera de Gurobi (con y sin el cruce, que encuentra una solución de vértice) y el PDLP, un método de primer orden, con alta y baja precisión. La siguiente tabla informa los tiempos en segundos, con un límite de 20 minutos (1,200 segundos).

Instancia Glop
Primal simplex		 Glop
simplex dual		 La barrera Gurobi
con Crossover		 Barrera Gurobi
sin Crossover		 Alta precisión de
PDLP		 Baja precisión
de PDLP
ex10 >1200 >1200 79.7 63.5 8.2 2.7
nug08-3 >1200 252.8 144,6 3.2 1.1 0.9
savsched1 >1200 >1200 156.0 22.6 46.4 32.4
wide15 >1200 20,8 >1200 >1200 916.4 56.3
energía para la construcción 178.4 267.5 12.8 12.3 >1200 157.2
S250R10 12.1 520.6 15.2 16.4 >1200 >1200
Versión de solucionador Herramientas de OR 9.3 Herramientas de OR 9.3 Gurobi 9.0 Gurobi 9.0 Herramientas de OR 9.3 Herramientas de OR 9.3
solver_specific_parameters (valores predeterminados) use_dual_simplex: true Method 2, Threads 1 Method 2, Crossover 0, Threads 1 termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 } termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }

De estos resultados concluimos lo siguiente.

  • El rendimiento relativo de los algoritmos y los solucionadores puede variar según órdenes de magnitud en una sola instancia.
  • Ningún algoritmo y solucionador es uniformemente mejor que otros.
  • El uso combinado (habilitado de forma predeterminada) aumenta el tiempo de resolución, a veces de manera considerable.
  • El PDLP puede resolverse con una precisión baja a veces 10 veces más rápido que con una precisión alta.

Una breve guía para elegir solucionadores de problemas de LP

Dado que ningún algoritmo de LP o solucionador es lo mejor, recomendamos los siguientes pasos a fin de descubrir lo mejor para tu caso de uso. Comienza con el primer paso y continúa con el siguiente si el rendimiento no es suficiente.

  1. Prueba Glop. Por qué: Glop es la implementación interna de Google de los métodos simplex primario y doble. Glop es de código abierto y es confiable para las cargas de trabajo de producción de Google.
    • Si la configuración predeterminada (simplex principal) no funciona bien, intenta cambiar a simplex doble mediante use_dual_simplex: true.
  2. Si hay una licencia disponible, prueba un solucionador comercial (CPLEX, Gurobi o Xpress). Experimenta con métodos simplex y de barrera. Por qué: Estos solucionadores son estándar de la industria y están altamente optimizados. Además, los métodos de barrera complementan los algoritmos simplex que ofrece Glop.
    • Si usas una barrera, inhabilita el “crossover” en caso de que no necesites una solución de Vertex.
  3. Prueba PDLP. Ajusta las tolerancias de convergencia a tu aplicación. Por qué: El PDLP está diseñado para los problemas más grandes, en los que los métodos simplex y de barrera alcanzan los límites de memoria o son demasiado lentos. El PDLP funciona mejor cuando se prefiere una solución aproximada pero rápida en lugar de una exacta pero lenta.
  4. Si llegaste hasta aquí, ahora eres un usuario avanzado de LP. Consulta las opciones de asistencia de OR-Tools para obtener más ayuda.

  1. Suele ser más complejo que esto. Los solucionadores suelen verificar estas condiciones en una versión transformada o simplificada del problema, denominado problema resuelto. En algunos casos, una solución al problema resuelto puede estar muy lejos de una solución al problema de entrada. Esta situación puede generar estados inusuales, como OptimalInfeas de CPLEX o IMPRECISE de Glop.↩