An exact approach for aggregated formulations

Mette Gamst, Simon Spoorendonk

    Research output: Book/ReportReportResearch

    170 Downloads (Pure)

    Abstract

    Aggregating formulations is a powerful approach for transforming problems into taking more tractable forms. Aggregated formulations can, though, have drawbacks: some information may get lost in the aggregation and { put in a branch-and-bound context { branching may become very di_cult and even cause an infeasible solution. In this paper, we consider (mixed) integer program formulations and propose a method for ensuring an optimal solution to the original (disaggregated) problem using an aggregated formulation. The method is based on Benders’ decomposition on a combination of the disaggregated mathematical formulation and the aggregated formulation. The method allows usage of relaxed aggregated formulations and enables branching on both aggregated and disaggregated variables. Also, the method guarantees an LP bound at least as good as those for the disaggregated and aggregated formulations. The paper includes general considerations on types of problems for which the method is of particular interest. Furthermore, we prove the correctness of the procedure and consider how to include extensions such as cutting planes and advanced branching strategies.
    Original languageEnglish
    PublisherDTU Management Engineering
    Number of pages19
    ISBN (Electronic)978-87-92706-95-9
    Publication statusPublished - 2013
    SeriesDTU Management Engineering Report
    Number3.2013

    Fingerprint Dive into the research topics of 'An exact approach for aggregated formulations'. Together they form a unique fingerprint.

    Cite this