MPEC class
Classification of MPECs
This page briefly describes a classification scheme for Mathematical Programs with Equilibrium Constraints (MPECs) which is used to classify the problems in the MacMPEC test problem library. The scheme is an extension of the CUTE classification scheme due to Bongartz, Conn, Gould and Toint.
Each problem is identified by a string
XXX-XX-CCC-n-m-p
consisting of 3 groups of characters and 3 integers. The first two groups of characters describe the general aspect of the MPEC, the third group describes the aspect of the complementarity constraint and the integers represent the problem dimensions. Each group of characters and integers is now described in turn.
The first group of three characters describes the aspect of the objective and general constraint functions of the MPEC. The first character gives the type of objective function and can take the following values.
| char | objective type |
| N | no objective defined |
|---|---|
| C | constant |
| L | linear |
| Q | quadratic |
| S | sum of squares |
| O | none of the above |
The second character gives type of general constraint functions (other than the complementarity constraint which is handled below).
| char | constraint type |
| U | unconstrained |
|---|---|
| X | only constraints are fixed variables |
| B | only constraints are variables bounds |
| N | network constraints |
| L | linear |
| Q | quadratic |
| O | none of the above, more general |
The third character in the first group indicates the smoothness of the problem and it can take the following values:
| char | regularity |
| R | regular, all functions are twice continuously differentiable |
|---|---|
| I | irregular |
The second group of characters describes the origin of the model and states how the upper level and lower level problem are linked. The first character of the second group gives the origin of the problem and can take the following values
| char | origin of problem |
| A | the problem is academic |
|---|---|
| M | the problem is part of a modelling exercise |
| R | the problem is a real application for purposes other than testing algorithms |
The second character of the second group describes how the upper level (or control) variables are linked to the lower level (or state) variables in the general constraints. It can take the following values
| char | linking constraints |
| Y | the state and controls both appear in the same general constraints |
|---|---|
| N | there are no side constraints (other than the complementarity constraints) in which both the state and control variables appear simultaneously |
The third group of characters describes the type of the complementarity constraint. Here we follow Billups, Dirkse and Ferris, 1997.
| char-group | type of complementarity constraint |
| MCP | (general) Mixed Complementarity Problem |
|---|---|
| LMCP | Linear Mixed Complementarity Problem |
| NCP | Nonlinear Complementarity Problem |
| LCP | Linear Complementarity Problem |
| NLP | optimality conditions of a nonlinear program |
The final group of integers n-m-p represent the size of problem with the following convention.
| char | meaning of integer |
| n | number of variables (control and state) |
|---|---|
| m | number of constraints (excl. complementarity constraints) |
| p | number of complementarity constraints |