A BranchandCut Approach to Nonconvex Combinatorial Optimization George
L. Nemhauser Many optimization models that arise in practical applications are very difficult to solve because of combinatorial constraints imposed on sets of continuous variables. Examples of these combinatorial structures include:
Traditionally such constraints are dealt with by reformulating the problem as a mixed integer program by including auxiliary binary variables and additional constraints in the model. However, reformulation has serious disadvantages, including increasing the size of the problem significantly and hiding the structure of the model. Here we present a branchandcut approach that considers the combinatorial constraints without the introduction of binary variables. We show how strong cuts can be developed for such models that only contain continuous variables and we use these cuts in a branchandcut algorithm. To illustrate the ideas we focus on kcardinality constraints.
