swMATH ID: 31750
Software Authors: Yu, Bin; Mitchell, John E.; Pang, Jong-Shi
Description: Solving linear programs with complementarity constraints using branch-and-cut. A linear program with linear complementarity constraints (LPCC) requires the minimization of a linear objective over a set of linear constraints together with additional linear complementarity constraints. This class has emerged as a modeling paradigm for a broad collection of problems, including bilevel programs, Stackelberg games, inverse quadratic programs, and problems involving equilibrium constraints. The presence of the complementarity constraints results in a nonconvex optimization problem. We develop a branch-and-cut algorithm to find a global optimum for this class of optimization problems, where we branch directly on complementarities. We develop branching rules and feasibility recovery procedures and demonstrate their computational effectiveness in a comparison with CPLEX. The implementation builds on CPLEX through the use of callback routines. The computational results show that our approach is a strong alternative to constructing an integer programming formulation using big-(M) terms to represent bounds for variables, with testing conducted on general LPCCs as well as on instances generated from bilevel programs with convex quadratic lower level problems.
Homepage: https://rd.springer.com/article/10.1007%2Fs12532-018-0149-2
Source Code:  https://github.com/mitchjrpi/LPCCbnc
Keywords: linear programs with complementarity constraints; MPECs; branch-and-cut
Related Software: CPLEX; Gurobi; YALMIP; CVX; SDPT3; SeDuMi; quadprogIP; QuadProgBB; MacMPEC; FEASPUMP; AMPL; SCIP; Meschach
Cited in: 5 Publications

Citations by Year