A  Branch-and-Cut Approach to Nonconvex Combinatorial Optimization

George L. Nemhauser
School of Industrial and Systems Engineering
Georgia Institute of Technology

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:

• k-cardinality constraints : no more than k variables from a set of n nonnegative variables may be positive;
• special ordered set constraints: no more than 2 variables from a sequence of n nonnegative variables may be positive, and if 2 are positive, they must be adjacent in the sequence. (This structure is used to model nonconvex piecewise linear objective functions.);
• semi-continuous constraints: if a nonnegative variable is positive, it must be at least some positive constant.

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.