On the facet pivot simplex method for linear programming

Este artículo propone un nuevo método simplex de pivoteo por facetas para la programación lineal que demuestra una promesa superior frente al enfoque tradicional de pivoteo por vértices en pruebas numéricas, ofreciendo nuevas esperanzas para descubrir un algoritmo de pivoteo de tiempo polinomial.

Lo esencial

Imagina que estás intentando encontrar el lugar absolutamente mejor para montar un puesto de limonada en una ciudad. La ciudad tiene forma de un edificio complejo y de múltiples lados (un polítopo), y quieres encontrar la esquina que te hará ganar más dinero.

Durante más de 70 años, la forma estándar de hacer esto ha sido el Método de Pivoteo de Vértices (inventado por George Dantzig). Piensa en este método como un turista caminando por el exterior del edificio. Comienza en una esquina (vértice), observa las esquinas vecinas y camina hacia la que parece mejor. Sigue saltando de esquina en esquina a lo largo de las aristas hasta encontrar el mejor lugar.

El problema es que, a veces, el edificio está diseñado con un laberinto tramposo de esquinas. En los peores escenarios, el turista podría tener que pasar por cada esquina individual en un orden específico y agotador antes de encontrar la mejor. Esto es como caminar por un laberinto que se vuelve exponencialmente más largo a medida que el edificio se hace más grande.

La Nueva Idea: El Método de "Pivoteo de Facetas"

En este artículo, el autor, Yaguang Yang, propone una nueva forma de resolver este problema llamado el Método Simplex de Pivoteo de Facetas.

En lugar de caminar a lo largo de las esquinas (vértices), imagina que eres un inspector de construcción mirando las facetas del edificio.

• La Vieja Forma (Vértice): Eres un turista saltando de esquina en esquina.
• La Nueva Forma (Faceta): Eres un inspector que intercambia las facetas que definen tu "base" actual para acercarte al mejor lugar.

Así es como funciona el nuevo método en términos sencillos:

1. Comienza con las Facetas, no con las Esquinas: En lugar de comenzar en una esquina, el algoritmo comienza seleccionando un conjunto de facetas (restricciones) que definen una posición temporal, quizás imperfecta.
2. Intercambia Facetas, no Esquinas: El algoritmo examina las facetas que actualmente están "violadas" o no satisfechas (como una faceta que está inclinada en la dirección incorrecta). Selecciona la peor y la intercambia por una faceta diferente que ayude a solucionar el problema.
3. Sin Desvío de "Fase 1": El método antiguo a menudo requiere un largo y costoso viaje de "Fase 1" solo para encontrar una esquina de inicio válida antes de que pueda siquiera comenzar a buscar la mejor. El nuevo método es astuto: comienza con una configuración matemáticamente garantizada para funcionar inmediatamente, omitiendo por completo ese largo desvío. Es como tener una llave mágica que abre la puerta del edificio instantáneamente, en lugar de intentar forzar la cerradura primero.

¿Por qué es esto emocionante?

El artículo afirma que este nuevo método es muy prometedor por dos razones principales:

• Es más rápido en laberintos difíciles: El autor lo probó en "cubos de Klee-Minty", que son laberintos matemáticos diseñados específicamente para engañar al viejo método del turista y hacerlo tardar una eternidad. El nuevo método de intercambio de facetas resolvió estos laberintos mucho más rápido, tomando solo unos pocos pasos en lugar de miles.
• Es más robusto: Cuando se probó en una enorme colección de problemas matemáticos del mundo real (los puntos de referencia Netlib), el nuevo método resolvió con éxito casi todos ellos. El viejo método del "turista" a veces se quedaba atascado o tardaba mucho tiempo, y el método "dual" (un tipo diferente de turista) a veces se rendía porque la geometría del edificio era demasiado tramposa. El método de intercambio de facetas manejó estas geometrías complicadas mejor.

El Truco (y la Esperanza)

El artículo admite que para problemas muy grandes y simples, el método antiguo (u otros métodos como los métodos de "Punto Interior", que son como volar un dron a través del centro del edificio) podrían seguir siendo más rápidos.

Sin embargo, la gran esperanza es que este nuevo enfoque de "intercambio de facetas" podría ser la clave para resolver un famoso misterio matemático de 60 años: ¿Podemos encontrar un método que esté garantizado para ser rápido (tiempo polinomial) para cada problema?

Durante décadas, los matemáticos han intentado probar que el viejo método de "salto de esquinas" es lo suficientemente rápido, pero encontraron casos en los que es increíblemente lento. Este nuevo método de "intercambio de facetas" ofrece una perspectiva fresca. No depende de las mismas reglas antiguas, y las pruebas tempranas sugieren que podría ser el camino hacia una solución que sea tanto rápida como confiable para todos los tipos de problemas de programación lineal.

En resumen: El artículo introduce una nueva forma de resolver problemas de optimización matemática intercambiando "facetas" en lugar de saltar "esquinas". Omite los aburridos pasos de configuración, maneja los laberintos complicados mejor que los métodos antiguos y da a los matemáticos una nueva esperanza para encontrar una solución perfecta y rápida para todos los problemas.

Resumen técnico

Resumen Técnico: Sobre el método de pivoteo de facetas del simplex para programación lineal

Planteamiento del Problema
El artículo aborda la eficiencia computacional y las limitaciones teóricas del método simplex estándar de pivoteo de vértices para resolver problemas de Programación Lineal (PL). Si bien el método simplex de vértices de Dantzig sigue siendo altamente efectivo en la práctica, carece de un límite de complejidad en tiempo polinomial demostrado. Teóricamente, el peor caso para los métodos de vértices implica un número exponencial de iteraciones (como demuestran los cubos de Klee-Minty), y la búsqueda de un algoritmo de pivoteo en tiempo polinomial ha permanecido esquiva durante décadas. Además, los métodos de vértices tradicionales a menudo requieren un proceso "Fase I" computacionalmente costoso para encontrar una solución básica factible inicial, particularmente para problemas de PL generales que involucran restricciones de desigualdad y límites.

Metodología
Los autores proponen un método simplex de pivoteo de facetas que desplaza fundamentalmente la operación de pivoteo de los vértices a las facetas (restricciones).

• Formulación General: El método opera sobre una formulación general de PL:
  $$\min c^T x$$
  $$\text{sujeto a } A_I x = b_I, \quad A_J x \ge b_J, \quad \ell \le x \le u$$
  A diferencia de las formas estándar que convierten las desigualdades en igualdades mediante variables de holgura, este enfoque trata las restricciones de desigualdad directamente como facetas del polítopo factible.

• Lógica Algorítmica:

  • Definición de Base: En lugar de una base de variables (vértices), el algoritmo mantiene una base de $d$ facetas (restricciones) linealmente independientes, donde $d$ es la dimensión del problema.
  • Proceso Iterativo: El algoritmo comienza con una solución básica inicial (a menudo derivada directamente de las restricciones de límite) que no es necesariamente factible. En cada iteración, selecciona una faceta entrante (una restricción no básica) y una faceta saliente (una restricción básica) para actualizar la base.
  • Factibilidad y Optimalidad: El algoritmo mantiene una representación del vector objetivo $c$ como una combinación lineal no negativa de las facetas básicas actuales (satisfaciendo una condición derivada del Lema de Farkas). Mejora iterativamente la solución reemplazando facetas para reducir las violaciones de restricciones.
  • Terminación: El proceso se detiene cuando se encuentra una solución básica factible. Según los teoremas de optimalidad presentados, si el vector objetivo puede expresarse como una combinación no negativa de las facetas básicas activas en un punto factible, ese punto es óptimo.
  • Convergencia Finita: El artículo demuestra que si se aplica la "regla del índice menor/menor" para seleccionar las facetas entrantes y salientes, el algoritmo evita el ciclado y termina en un número finito de pasos.

• Distinciones Clave con el Simplex Dual: Si bien el método de pivoteo de facetas comparte algunas similitudes geométricas con el método simplex dual (moviéndose entre bases de restricciones), es distinto porque opera exclusivamente sobre el problema primal sin construir ni resolver explícitamente un problema dual. Maneja la forma general directamente, evitando la conversión a la forma estándar.

Contribuciones Clave

1. Propuesta Algorítmica: El artículo introduce un algoritmo específico de pivoteo de facetas (Algoritmo 4.1) que resuelve problemas generales de PL sin requerir un paso de inicialización de Fase I.
2. Garantías Teóricas: Los autores proporcionan demostraciones matemáticas (basadas en el Lema de Farkas) que demuestran que el algoritmo encuentra una solución óptima en iteraciones finitas e identifica correctamente problemas infactibles o no acotados.
3. Implementación: Se proporciona una implementación en MATLAB del algoritmo, junto con implementaciones del simplex de Dantzig, simplex dual y métodos de punto interior para comparación.
4. Manejo de Restricciones: El método maneja naturalmente los límites inferiores y superiores y las variables libres sin introducir variables de holgura artificiales, resultando en un tamaño de problema menor en comparación con las conversiones a forma estándar.

Resultados Experimentales
Los autores realizaron pruebas numéricas en varios conjuntos de referencia:

• Referencias Netlib: En problemas estándar de Netlib con límites inferiores y superiores, el método de pivoteo de facetas generalmente requirió menos segundos de CPU que la regla de pivoteo más negativa de Dantzig. Resolvió con éxito problemas donde el método simplex dual falló debido a deficiencia de rango o mal condicionamiento.
• Problemas a Gran Escala: Para problemas muy grandes (por ejemplo, $n > 50,000$), los Métodos de Punto Interior (MPI) superaron a todos los métodos de pivoteo, como era de esperar. Sin embargo, el método de pivoteo de facetas mostró robustez donde el método simplex dual falló.
• Cubos de Klee-Minty: El método de pivoteo de facetas demostró un rendimiento significativamente mejor que el método de vértices de Dantzig en variantes de Klee-Minty, requiriendo muchas menos iteraciones (a menudo lineales o casi lineales en la dimensión $d$) en comparación con las iteraciones exponenciales requeridas por el método de vértices.
• Problemas Generales Aleatorios: Para problemas generales de PL que requieren una Fase I en los métodos estándar, el método de pivoteo de facetas fue significativamente más eficiente que el método de Dantzig porque evitó la inicialización de Fase I.
• Problemas Aleatorios Estándar: Para problemas estándar de PL donde no se requiere Fase I, se observó que el método de Dantzig fue ligeramente más eficiente en tiempo de CPU, aunque las conteos de iteraciones fueron comparables.

Significado y Afirmaciones
El artículo afirma que el método simplex de pivoteo de facetas ofrece una alternativa prometedora a los métodos basados en vértices, particularmente para problemas generales de PL con restricciones de desigualdad. Su significado principal radica en:

• Eliminación de la Fase I: Al comenzar desde una solución básica derivada de las restricciones de límite, evita la fase de inicialización costosa requerida por los métodos simplex tradicionales para problemas generales.
• Robustez: Demuestra una mayor estabilidad numérica que el método simplex dual en problemas de Netlib mal condicionados.
• Esperanza de Complejidad Polinomial: Si bien los autores no afirman haber demostrado un límite de tiempo polinomial, sugieren que este nuevo tipo de algoritmo de pivoteo (operando sobre facetas en lugar de vértices) proporciona una nueva vía de investigación para encontrar un método simplex de pivoteo en tiempo polinomial, abordando el noveno problema de Smale.
• Eficiencia Práctica: Se muestra que el método es altamente competitivo y a menudo superior al método de Dantzig para problemas que involucran muchas restricciones de desigualdad, sin la sobrecarga de convertirlas en igualdades.

Los autores mantienen un tono modesto, reconociendo que los Métodos de Punto Interior siguen siendo superiores para problemas a muy gran escala y que el método de pivoteo de facetas es una nueva dirección que requiere mayor investigación para comprender plenamente sus límites de complejidad teórica.