An exact approach for aggregated formulations

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.