### Abstract

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.

Original language | English |
---|---|

Publication date | 2012 |

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 http://ismp2012.mathopt.org/ |

### Conference

Conference | 21st International Symposium on Mathematical Programming |
---|---|

Number | 21 |

Location | TU Berlin |

Country | Germany |

City | Berlin |

Period | 19/08/2012 → 24/08/2012 |

Internet address |

## Cite this

Gamst, M., & Spoorendonk, S. (2012).

*An exact approach for aggregated formulations*. Abstract from 21st International Symposium on Mathematical Programming, Berlin, Germany.