LPCCbnc
swMATH ID:  31750 
Software Authors:  Yu, Bin; Mitchell, John E.; Pang, JongShi 
Description:  Solving linear programs with complementarity constraints using branchandcut. 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 branchandcut 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%2Fs1253201801492 
Source Code:  https://github.com/mitchjrpi/LPCCbnc 
Keywords:  linear programs with complementarity constraints; MPECs; branchandcut 
Related Software:  CPLEX; Gurobi; SNOPT; Pegasos; YALMIP; CVX; SDPT3; SeDuMi; QuadProgBB; quadprogIP; MacMPEC; FEASPUMP; AMPL; SCIP; Meschach 
Cited in:  8 Documents 
Standard Articles
1 Publication describing the Software, including 1 Publication in zbMATH  Year 

Solving linear programs with complementarity constraints using branchandcut. Zbl 1434.90160 Yu, Bin; Mitchell, John E.; Pang, JongShi 
2019

all
top 5
Cited by 20 Authors
all
top 5