Simultaneously Exploiting Two Formulations: an Exact Benders Decomposition Approach

When modelling a given problem using linear programming techniques several possibilities often exist, and each results in a different mathematical formulation of the problem. Usually, advantages and disadvantages can be identified in any single formulation. In this paper we consider mixed integer linear programs and propose an approach based on Benders decomposition to exploit the advantages of two different formulations when solving a problem. We propose to apply Benders decomposition to a combined formulation,comprised of two separate formulations, augmented with linking constraints to ensure consistency between the decision variables of the respective formulations. We demonstrate the applicability of the proposed methodology to situations in which one of the formulations models a relaxation of the problem and to cases where one formulation is the Dantzig-Wolfe reformulation of the other. The proposed methodology guarantees a lower bound that is good as the tighter of the two formulations, and we show how branching can be performed on the decision variables of either formulation. This paper also includes a discussion on the types of problems for which the method is of particular interest. Furthermore, it proves the correctness of the procedure and considers how to include interesting extensions such as cutting planes and advanced branching strategies. Finally, we test and compare the performance of the proposed approach on publicly available instances of the Bin Packing problem. Compared to the standard branch-and-price approach from the literature, the method shows promising performance and appears to be an attractive alternative.