Mathematical Programming with Equilibrium Constraints

A Mathematical Program with Equilibrium Constraints (MPEC) is a constrained optimization problem in which the constraints include equilibrium constraints, such as variational inequalities or complementarity conditions. MPECs arise in applications in engineering design, in economic equilibrium and in multilevel games. MPECs are difficult to solve because the feasible region is not necessarily convex or connected.

A special case of an MPEC is a Mathematical Program with Complementarity Constraints (MPCC) in which the equilibrium constraints are complementarity constraints.
\mbox{minimize}_x & f(x) & & \\
\mbox{subject to} & g(x) & \geq & 0 \\
& h(x) & = & 0 \\
& 0 \leq x_1 \perp x_2 & \geq & 0
\] The complementarity constraint \(0 \leq x_1 \perp x_2 \geq 0\) can be written equivalently as \(x_1 \geq 0, x_2 \geq 0, x_1^T x_2 = 0\).

Online and Software Resources
  • MacMPEC is a collection of MPEC test problems in AMPL
  • MacEPEC is a small collection of Equilibrium Problems with Equilibrium Constraints (EPEC) test problems in AMPL
  • Luo, Z.-Q., Pang, J.-S. Pang, and Ralph, D. 1996. Mathematical Programs with Equilibrium Constraints. Cambridge University Press.