1 Presentation

• 
  09:00 AM - 10:00 AM

  Mathematical Programming with Linear Complementarity Constraints: Algorithms and Applications

  • Joaquim João Júdice, presenter, Instituto de Telecomunicações

  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 NP-hard 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.

  Active-set 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. Branch-and-bound 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 zero-one 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.