Strong and compact relaxations in the original space using a compact extended formulation
(2013) EURO Journal on Computational Optimization — Vol. 1, n° 1, p. 71-80 (2013)
Files
Rep2480.pdf
Open Access - Adobe PDF
- 396.03 KB
Details
- Authors
- Abstract
- 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.
- Affiliations
Citations
Van Vyve, M., & Wolsey, L. (2013). Strong and compact relaxations in the original space using a compact extended formulation. EURO Journal on Computational Optimization, 1(1), 71-80. https://doi.org/10.1007/s13675-012-0004-6 (Original work published 2013)