Optimization Online


On the Global Solution of Linear Programs with Linear Complementarity Constraints

Jing Hu (huj***at***rpi.edu)
John E. Mitchell (mitchj***at***rpi.edu)
Jong-Shi Pang (pangj***at***rpi.edu)
Kristin P. Bennett (bennek***at***rpi.edu)
Gautam Kunapuli (kunapg***at***rpi.edu)

Abstract: This paper presents a parameter-free integer-programming based algorithm for the global resolution of a linear program with linear complementarity constraints (LPEC). The cornerstone of the algorithm is a minimax integer program formulation that characterizes and provides certificates for the three outcomes---infeasibility, unboundedness, or solvability---of an LPEC. An extreme point/ray generation scheme in the spirit of Benders decomposition is developed, from which valid inequalities in the form of satisfiability constraints are obtained. The feasibility problem of these inequalities and the carefully guided linear programming relaxations of the LPEC are the workhorse of the algorithm, which also employs a specialized procedure for the sparsification of the satifiability cuts. We establish the finite termination of the algorithm and report computational results using the algorithm for solving randomly generated LPECs of reasonable sizes. The results establish that the algorithm can handle infeasible, unbounded, and solvable LPECs effectively.


Category 1: Complementarity and Variational Inequalities

Citation: Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, New York 12180-3590, U.S.A. March 7, 2007. http://www.rpi.edu/~mitchj/papers/LPEC_global.html

Download: [PDF]

Entry Submitted: 03/07/2007
Entry Accepted: 03/08/2007
Entry Last Modified: 03/08/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society