ICCP99

INTERNATIONAL CONFERENCE ON COMPLEMENTARITY PROBLEMS
Contemporary Applications and Algorithms

Informal meeting on the status and future of bilevel programming and mathematical programming with equilibrium constraints

Following the forum on the future of complementarity at ICCP99, an informal discussion was held on the status and future of bilevel programming (BLP) and and mathematical programming with equilibrium constraints (MPEC).

The following three questions were posed as discussion points.

  1. Do we need more than nonlinear programming theory and methods to analyse and solve BLPs/MPECs?
  2. What is the role of global optimization here?
  3. How can we foster links between mathematical programming and application areas (which feed or lead the research)?
The subsequent comments and discussion have been summarized below in one of the categories Applications, Analysis & Modelling, Algorithms & Software.

Applications

There is a need to extend standard forms for BLP/MPEC to:

  • Shape optimization & hemivariational inequalities (Panagiotopoulous, Stavroulakis). But caution is needed to ensure that the algorithm developer or theoretician is is working on a meaningful class of problems rather than a convenient mathematical abstraction that in fact does not say very much about the original physical situation.
  • Primal-dual formulation of contact problems with Coulomb friction (Haslinger).
  • Games such as equilibrium problems subject to equilibrium constraints, subgame perfect equilibria etc. For example in electricity generation, stage 1 of the game is an investment opportunity which takes the stage 2 game, about generating electricity in a competitive market, into account. Stochastic games are also needed in this context.

    Analysis & Modelling

  • Existence of solutions and well posedness of problems is far from being well understood (at least in comparison to nonlinear programming theory) e.g. sharper criteria for certain stability properties such as pseudo-Lipschitz continuity of set mappings related to the feasible set of such problems.
  • Question: Are complementarity methods for problems in mechanics used outside academia? Response: The topic of rigid body dynamics is now being taught in terms of complementarity problems at some institutions in Germany, see book by Pfeiffer and Glocker, "Multibody dynamics with unilateral constraints", Wiley 1996. So hopefully CP is becoming part of the mainstream.
  • Wider models are needed for stochastic problems and games. Question: In the context of a player's utility, how do we deal with the difference between globally optimal points and equilibria which represent local min or stationary points?
  • Use BLP/MPEC to examine combinatorial problems not originally posed in this way.

    Algorithms & Software

    How can we improve delivery or usefulness of solvers to practitioners?

  • There is a need for reliable and reasonably fast solvers, aiming at several hundred variables for BLP/MPEC and many thousands of variables for CP (note that software for CP is already at this stage though it can no doubt be improved).
  • Use modelling languages like AMPL or GAMS with interfaces to MATLAB so that algorithm developers can quickly and efficiently develop codes. Currently AMPL provides first and second derivatives of functions, GAMS provides first derivatives with second derivatives on the way; this means that the gap between a model and an algorithm using NLP ideas is usually much reduced.
  • On one hand, then need of and recognition for heuristics in approaching problems, since BLP/MPEC problems often, indeed usually, have multiple local minimizers. On the other hand, the division that seems to exist between researchers in nonlinear programming and those (often in the broader Operations Research area) who routinely use simulated annealing, genetic algorithms, tabu search, pattern search etc when faced with problems in combinatorial optimization.
  • Set up a ``standard'' test set of BLP/MPEC problems to provide a gauge for algorithm efficiency.
  • Need more contact with the developers of the better NLP codes, to gain from their experience and also make use of their software.
  • Use the framework of NEOS (network enabled optimization software) at Argonne National Lab to make software available to remotely solve problems.

    Danny Ralph
    Department of Mathematics & Statistics
    The University of Melbourne, Parkville, Victoria, Australia
    danny@ms.unimelb.edu.au