An exact approach for aggregated formulations

Mette Gamst, Simon Spoorendonk

    Research output: Contribution to conferenceConference abstract for conferenceResearchpeer-review

    9202 Downloads (Pure)

    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 languageEnglish
    Publication date2012
    Publication statusPublished - 2012
    Event21st International Symposium on Mathematical Programming - TU Berlin, Berlin, Germany
    Duration: 19 Aug 201224 Aug 2012
    Conference number: 21
    http://ismp2012.mathopt.org/

    Conference

    Conference21st International Symposium on Mathematical Programming
    Number21
    LocationTU Berlin
    CountryGermany
    CityBerlin
    Period19/08/201224/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.