Expressing complementarity problems in an algebraic modeling language and communicating them to solvers

Michael C. Ferris*, Robert Fourer, David M. Gay

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

Diverse problems in optimization, engineering, and economics have natural formulations in terms of complementarity conditions, which state (in their simplest form) that either a certain nonnegative variable must be zero or a corresponding inequality must hold with equality, or both. A variety of algorithms has been devised for solving problems expressed in terms of complementarity conditions. It is thus attractive to consider extending algebraic modeling languages, which are widely used for sending ordinary equations and inequality constraints to solvers, so that they can express complementarity problems directly. We describe an extension to the AMPL modeling language that can express the most common complementarity conditions in a concise and flexible way, through the introduction of a single new "complements" operator. We present details of an efficient implementation that incorporates an augmented presolve phase to simplify complementarity problems, and that converts complementarity conditions to a canonical form convenient for solvers.

Original languageEnglish (US)
Pages (from-to)991-1009
Number of pages19
JournalSIAM Journal on Optimization
Volume9
Issue number4
DOIs
StatePublished - Sep 1999

Keywords

  • Algebraic modeling languages
  • Complementarity
  • Optimization

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'Expressing complementarity problems in an algebraic modeling language and communicating them to solvers'. Together they form a unique fingerprint.

Cite this