On Linear Bilevel Optimization Problems with Complementarity-Constrained Lower Levels

We consider a novel class of linear bilevel optimization models with a lower level that is a linear program with complementarity constraints (LPCC). We present different single-level reformulations depending on whether the linear complementarity problem (LCP) as part of the lower-level constraint set depends on the upper-level decisions or not as well as on whether … Read more

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 … Read more

An LPCC Approach to Nonconvex Quadratic Programs

Filling a gap in nonconvex quadratic programming, this paper shows that the global resolution of a feasible quadratic program (QP), which is not known a priori to be bounded or unbounded below, can be accomplished in finite time by solving a linear program with linear complementarity constraints, i.e., an LPCC. Alternatively, this task can be … Read more