Strong and compact relaxations in the original space using a compact extended formulation
For certain integer programs, one way to obtain a strong dual bound is to use an extended formulation and then solve the associated linear programming relaxation. The classical way to obtain a bound of the same value in the original variable space is through the use of Benders’ algorithm. Here, we p...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
Elsevier
2013
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/cd52db78cd6145d39f64f83427059510 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | For certain integer programs, one way to obtain a strong dual bound is to use an extended formulation and then solve the associated linear programming relaxation. The classical way to obtain a bound of the same value in the original variable space is through the use of Benders’ algorithm. Here, we propose an alternative approach based on a decomposition of the dual optimal solution of the extended formulation linear program. An example of the approach using the multi-commodity formulation of a two-level production/transportation problem is presented. |
|---|