LPCCbnc 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; 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 branch-and-cut. Zbl 1434.90160Yu, Bin; Mitchell, John E.; Pang, Jong-Shi 2019 all top 5 Cited by 20 Authors 2 Mitchell, John E. 2 Pang, Jong-Shi 1 Anjos, Miguel F. 1 Fomeni, Franklin Djeumou 1 Gabriel, Steven A. 1 Gondzio, Jacek 1 Jara-Moroni, Francisco 1 Kanno, Yoshihiro 1 Li, Qingna 1 Li, Zhen 1 Mastroeni, Giandomenico 1 Pellegrini, Letizia 1 Peretti, Alberto 1 Schwartz, Alexandra 1 Steffensen, Sonja 1 Thünen, Anna 1 Wächter, Andreas 1 Yildirim, Emre Alper 1 Yu, Bin 1 Zemkoho, Alain B. all top 5 Cited in 6 Serials 2 Journal of Global Optimization 1 Computers & Operations Research 1 Computational Optimization and Applications 1 Mathematical Methods of Operations Research 1 Optimization Letters 1 Mathematical Programming Computation Cited in 4 Fields 7 Operations research, mathematical programming (90-XX) 2 Calculus of variations and optimal control; optimization (49-XX) 2 Numerical analysis (65-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) Citations by Year