A Pivoting Algorithm for Linear Programming with Linear Complementarity Constraints

Haw-ren Fang(hrfangmcs.anl.gov)
Sven Leyffer(leyffermcs.anl.gov)
Todd Munson(tmunsonmcs.anl.gov)

Abstract: We present a pivoting algorithm for solving linear programs with linear complementarity constraints. Our method generalizes the simplex method for linear programming to deal with complementarity conditions. We develop an anticycling scheme that can verify Bouligand stationarity. We also give an optimization-based technique to find an initial feasible vertex. Starting with a feasible vertex, our algorithm always finds a minimizer or an unbounded descent search direction in a finite number of pivoting steps.

Keywords: Complementarity constraints, linear program with complementarity constraints, pivoting method

Category 1: Complementarity and Variational Inequalities

Citation: Preprint ANL/MCS-P1680-1009, Argonne National Laboratory, Mathematics and Computer Science Division, October 2009.

Download: [PDF]

Entry Submitted: 10/27/2009
Entry Accepted: 11/01/2009
Entry Last Modified: 10/27/2009

Modify/Update this entry