Branch-and-cut for complementarity-constrained linear programs

A Complementarity-Constrained Linear Program (CCLP) is a linear program which has additional constraints called complementarity constraints. Which are such that, for some sets of variables, at most one variable can be positive. Numerous real world problems, such as resource allocation problems, can be mapped into CCLP. Traditionally, these problems are formulated as conventional MIP problems by introducing additional binary variables and adding new constraints. In the alternative approach we proposed in this dissertation, continuous variables are kept in the model. We will derive valid inequalities (called cutting planes) for the convex hull of the feasible set, which are then added to the cut pool in a branch-and-cut algorithm. We will present three families of valid inequalities, two of which are obtained by lifting valid inequalities of the projected polytope.