EURO Journal on Computational Optimization (May 2013)

Strong and compact relaxations in the original space using a compact extended formulation

  • Mathieu Van Vyve,
  • Laurence A. Wolsey

Journal volume & issue
Vol. 1, no. 1
pp. 71 – 80

Abstract

Read online

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.

Keywords