Aggregating formulations is a powerful trick for transforming problems into taking more tractable forms. An example is Dantzig-Wolfe decomposition, which shows superior performance across many applications especially when part of a branch-and-price algorithm. Variable aggregation, however, may lead to mathematical formulations with a different solution space than that for the original formulation, i.e., the aggregated formulation may be a relaxation of the original problem. In a branch-and-bound context, variable aggregation can also lead to a formulation where branching is not trivial, for example when optimality cannot be guaranteed by branching on the aggregated variables. In this presentation, we propose a general method for solving aggregated formulations, such that the solution is optimal to the original problem. The method is based on applying Benders’ decomposition on a combination of the original and aggregated formulations. Put in a branch-and-bound context, branching can be performed on the original variables to ensure optimality. We show how to apply the method on well-known optimization problems.
|Publication status||Published - 2012|
|Event||21st International Symposium on Mathematical Programming - TU Berlin, Berlin, Germany|
Duration: 19 Aug 2012 → 24 Aug 2012
Conference number: 21
|Conference||21st International Symposium on Mathematical Programming|
|Period||19/08/2012 → 24/08/2012|