A class of trust-region methods is presented for solving unconstrained nonlinear and possibly nonconvex discretized optimization problems, like those arising in systems governed by partial differenti...
Eigenvectors to the second smallest eigenvalue of the Laplace matrix of a graph, also known as Fiedler vectors, are the basic ingredient in spectral graph partitioning heuristics. Maximizing this sec...
You are not logged in to this journal. Log in
On the Global Solution of Linear Programs with Linear Complementarity Constraints
SIAM J. Optim. Volume 19, Issue 1, pp. 445-471 (2008)
Published May 9, 2008
Connotea
CiteULike
del.icio.us
BibSonomy
This paper presents a parameter-free integer-programming-based algorithm for the global resolution of a linear program with linear complementarity constraints (LPCCs). 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 LPCC. 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 LPCC are the workhorses 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 LPCCs of reasonable sizes. The results establish that the algorithm can handle infeasible, unbounded, and solvable LPCCs effectively.
©2008 Society for Industrial and Applied Mathematics| History: | Received September 21, 2007; accepted December 17, 2007; published May 9, 2008 |
| Permalink: | http://dx.doi.org/10.1137/07068463x |
KEYWORDS and AMS
PUBLICATION DATA
SIAM