Description
When modeling a given problem using linear programming techniques several possibilities often exist, each resulting 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 applying 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 as good as the tighter of the two formulations, and we show how branching can be performed on the decision variables of either formulation. Computational results are reported for the Bin Packing Problem and the Split Delivery Vehicle Routing Problem.| Period | 9 Jul 2018 |
|---|---|
| Event title | 29th European Conference On Operational Research |
| Event type | Conference |
| Conference number | 29 |
| Location | Valencia, SpainShow on map |