HEC Montréal, Canada, 6  8 mai 2013
Journées de l'optimisation 2013
HEC Montréal, Canada, 6 — 8 mai 2013
TAP Séance plénière III / Plenary Session III
7 mai 2013 09h00 – 10h00
Salle: Amphithéâtre IBM
Présidée par Miguel F. Anjos
1 présentation

09h00  10h00
Mathematical Programming with Linear Complementarity Constraints: Algorithms and Applications
A Mathematical Program with Linear Complementarity Constraints (MPLCC) is an optimization problem where a linear or nonlinear function is minimized on a set defined by linear constraints and complementarity conditions on pairs of complementary variables. This problem finds many applications in several areas of science, engineering and economics and is also an important tool for the solution of some NPhard structured and nonconvex optimization problems. In particular, bilevel, bilinear and nonconvex quadratic programs and the linear complementarity problem can be reduced to MPLCCs and solved by exploiting these formulations. In this talk, the most important applications and formulations of the MPLCC are first reviewed.
The problems of finding a feasible solution, a stationary point and a global minimum for the MPLCC are addressed next. Local methods and special purpose techniques can be used for computing a feasible solution in some special cases, in particular for those MPLCCs associated with the reformulations mentioned before. In general, an enumerative method is required for such a task.
Activeset algorithms have been designed for finding stationary points of the MPLCC and can be employed in a sequential complementarity algorithm for computing a global minimum to the MPLCC. Branchandbound algorithms can also be useful for finding a global minimum for the MPLCC and exploit the dichotomy of the complementary variables. RLT and SDP techniques can be incorporated in these algorithms in order to speed up the search for a global minimum. Finally the MPLCC can be shown to be equivalent to a zeroone program and solved by using a special purpose integer programming technique.
Some comments about the computational performance of the algorithms and a few topics for future research are presented in the last part of the talk.