Thursday, 13:45 - 14:10 h, Room: H 2032


Mette Gamst
An exact approach for aggregated formulations

Coauthor: Simon Spoorendonk


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.


Talk 2 of the invited session Thu.2.H 2032
"Branch-and-price III: New techniques" [...]
Cluster 11
"Integer & mixed-integer programming" [...]


  California Payday Loans. You can buy Levitra Super Force profitably on our web-site; we offer the medications only of the highest quality and at reasonable prices.