Benders' Decomposition vs.Column & Constraint Generation, a Closer Look

Abstract

In this thesis an attempt is made to find out how the type of uncertainty (discrete and finite or polyhedral) in uences performance of Benders' decomposition [4] and Column & Constraint Generation [24] when solving the demand robust location-transportation problem. A generalization of Benders' decomposition is presented to make it applicable to a large group of demand robust optimization problems. Also, Column & Constraint Generation is adapted to be used on discrete and finite uncertainty sets. In [24] it was shown that Column & Constraint Generation is able to solve the problem a lot better than a standard implementation of Benders' decomposition. The performance comparison for discrete and finite uncertainty sets made in this thesis is new. On top of that, a number of techniques for making Benders' faster are applied. Special attention is paid to the role of the MIP-solver that is used as a black box for both algorithms.