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