A Branch-and-Cut Approach to Nonconvex Combinatorial Optimization
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 branch-and-cut 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 branch-and-cut algorithm. To illustrate the ideas we focus on k-cardinality constraints.