Un algoritmo de subgradiente y un filtro adicional para la resolución del subproblema entero en la partición de Benders

• Autores: Jaume Barceló Bugeda , L. Olivella
• Localización: Questiió: Quaderns d'Estadística, Sistemes, Informatica i Investigació Operativa, ISSN 0210-8054, Vol. 5, Nº. 1, 1981, págs. 13-23
• Idioma: español
• Títulos paralelos:
  • A subgradient algorithm and an additional filter for the resolution of the integer subproblem in Benders partition
• Enlaces
  • Texto completo (pdf)
• Resumen

  • El método de partición de Benders es particularmente útil para resolver modelos matemáticos del tipo de "multicommodity flows" o modelos econométricos del tipo de planificación descentralizada, sin embargo, en algunos casos, el subproblema entero generado por la descomposición dual es resuelto deficientemente por los procedimientos habituales de enumeración debido a su estructura matemática, carente de función objetivo e incluyendo una variable no restringida.

    En nuestro trabajo distinguimos dos casos: uno con restricciones derivadas únicamente de los puntos extremos del politopo dual y otro que incluye además restricciones procedentes de los rayos extremos. En el primer caso, proponemos un algoritmo basado en el método del subgradiente y en el segundo una variante del algoritmo del filtro de Balas con un filtro parcial calculado a partir de una restricción compuesta