# Solving Linear Programs with Complementarity Constraints using Branch-and-Cut

arXiv: https://arxiv.org/abs/1802.02941 · HTML: https://mlsanity.com/paper/1802.02941/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2018.

## Built on by (most cited first, 1 of 1)

- [Conformal Prediction Regions for Time Series using Linear Complementarity Programming](https://mlsanity.com/paper/2304.01075/) (2023)

## Abstract (arXiv)

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.