Branch-and-cut for cardinality optimization

Abstract

A cardinality constrained linear programming problem (CCLP) is a linear programming problem with an additional constraint which restricts the number of nonnegative variables that may take on positive values. This problem arises in a large variety of applications, such as portfolio optimization, compressive sensing, metabolic engineering, and maximum feasible subsystem. In this thesis we review the branch-and-cut approach for CCLP, and we focus on the polyhedral approach to it. We rst present branching strategies to solve this model through branch-and-cut. To set the stage for important results on CCLP, we give some important results on the cardinality constrained knapsack polytope (CCKP). We then determine when the trivial inequalities de ne facets of CCKP. Finally, we discuss the nontrivial inequalities, which can be used as cuts in a branch-and-cut scheme.