Description of MacMPEC Test Problems
This file briefly describes the MPEC test problems.
From a GAMS model of a 3-bar truss min weight design problem
by M.C. Ferris and F. Tin-Loi, "On the solution of a minimum
weight elastoplastic problem involving displacement and
complementarity constraints", Comp. Meth. in Appl. Mech & Engng,
174:107-120, 1999.
MPECs from J.F. Bard, "Convex two-level optimization",
Mathematical Programming 40(1), 15-27, 1988.
MPECs from J.F. Bard, "Convex two-level optimization",
Mathematical Programming 40(1), 15-27, 1988. Formulation
as in S. Dirkse's mpeclib.
MPECs from F. Facchinei, H. Jiang and L. Qi, "A smoothing method for
mathematical programs with equilibrium constraints", Universita di Roma
Technical report, 03.96. Problems number 7, 10 & 11.
MPECs from F. Facchinei, H. Jiang and L. Qi, "A smoothing method for
mathematical programs with equilibrium constraints", Universita di Roma
Technical report, 03.96. Problems number 7, 10 & 11.
Formulated in original mixed complementarity format.
A bilevel linear program due to Hansen, Jaumard and Savard,
"New branch-and-bound rules for linear bilevel programming,
SIAM J. Sci. Stat. Comp. 13, 1194-1217, 1992. See also book
Mathematical Programs with Equilibrium Constraints,
by Luo, Pang & Ralph, CUP, 1997, p. 357.
BEM Quasibrittle Fracture Identification (N, mm).
From GAMS file by F. Tin-Loi : 24 Feb 99,
b_pn2.mod = Two-branch law, Penalty, 2-norm, Imposed displacement q.
An MPEC from S. Dempe, "A necessary and sufficient optimality
condition for bilevel programming problems", Optimization 25,
pp. 341-354, 1992. From book Math. Progr. with Equil. Constr,
by Luo, Pang & Ralph, CUP, 1997, p. 354.
S.P. Dirkse and M.C. Ferris, "Modeling & Solution
Environment for MPEC: GAMS & MATLAB", University of Wisconsin
CS report, 1997.
Design centering problem cast as an MPEC, from an idea by
O. Stein and G. Still, "Solving semi-infinite optimization
problems with Interior Point techniques", Lehrstuhl C fuer
Mathematik, Rheinisch Westfaelische Technische Hochschule,
Preprint No. 96, November 2001.
Maximize the volume of the parameterized body B(x) contained
in a second body G, described by a set of convex inequalities,
maximize volume( B(x) )
subj. to B(x) \subset G
where B(x) is a circle (problem 1), an ellipsoid (problems 2 & 3)
and a box (problem 4). The set G is a nonconvex wedge in all cases.
Starting points were generated according to Stein and Still using the
following AMPL models,
design-init-1.mod,
design-init-2.mod,
design-init-3.mod,
design-init-4.mod.
The solution to Problems 1,2 and 4 can be found
here.
Two problems (design-cent-2 and design-cent-3) involve division by
design variables, which could be small giving rise to badly scaled
constraints. This can be remedied by multiplying through by the
denominators. Two new problems are added, design-cent-21 and design-cent-31,
which have better scaled constraints.
Problem number 5 from F. Facchinei, H. Jiang and L. Qi, "A smoothing method for
mathematical programs with equilibrium constraints", Universita di Roma
Technical report, 03.96.
Bilevel linear programming problems. From GAMS models of test
problems 9.1.(1-10) on
the web page of
"Nonconvex Optimization and its Applications", Volume 33
Kluwer Academic Publishers, Dordrecht, Hardbound, ISBN 0-7923-5801-5.
Bilevel quadratic programming problems. From GAMS models of test problems
9.2.(1-9) on
the web page of
"Nonconvex Optimization and its Applications", Volume 33
Kluwer Academic Publishers, Dordrecht, Hardbound, ISBN 0-7923-5801-5.
Gournot Nash equilibrium, see
F. Facchinei, H. Jiang and L. Qi, "A smoothing method for
mathematical programs with equilibrium constraints", Universita di Roma
Technical report, 03.96. Problem number 8.
Gournot Nash equilibrium, see
F. Facchinei, H. Jiang and L. Qi, "A smoothing method for
mathematical programs with equilibrium constraints", Universita di Roma
Technical report, 03.96. Problem number 8.
Formulated in original mixed complementarity format.
Problem 2 from Fukushima, M., Luo, Z.-Q. and Pang, J.-S.,
"A globally convergent Sequential Quadratic Programming
Algorithm for Mathematical Programs with Linear Complementarity
Constraints", Computational Optimization and Applications, 10(1),
pp. 5-34, 1998.
Problem 4 from Fukushima, M., Luo, Z.-Q. and Pang, J.-S.,
"A globally convergent Sequential Quadratic Programming
Algorithm for Mathematical Programs with Linear Complementarity
Constraints", Computational Optimization and Applications, 10(1),
pp. 5-34, 1998.
These are 4 instances of a randomly generated LCP constraint MPEC.
The random generator used is available as
genflp4.m
MPEC from Gauvin and Savard, "Working Paper G9037",
GERAD, Ecole Polytechnique de Montreal (1992) (first version).
From a GAMS model by S.P. Dirkse & M.C. Ferris
mpeclib.
MPEC of taxation model taken from (6)-(10) of
Light, M., "Optimal taxation: An application of mathematical
programming with equilibrium constraints in economics",
Department of Economics, University of Colorado, Boulder, 1999.
Attributed to Hakonsen, L. "Essays on Taxation, Efficiency and the
Environment", PhD thesis, Norwegian School of Economics & Business
Administration, April 1998.
Find the perturbation of the rhs & gradient of HS44 which
gives the primal solution which is closest to the solution
of HS44. From an idea communicated by S. Scholtes.
An MPEC from Outrata, Kocvara & Zowe, Nonsmooth Approach to
Optimization Problems with Equilibrium Constraints, Kluwer, 1998.
The incidence set identification problem of Section 9.4:
Aim is to bring the membrane of a surface into contact with
the obstacle in a prescribed region whose shape is also to
be determined.
There are two different obstacles and 3 discretizations.
An MPEC from Outrata, Kocvara & Zowe, Nonsmooth Approach to
Optimization Problems with Equilibrium Constraints, Kluwer, 1998.
The incidence set identification problem of Section 9.4:
Aim is to bring the membrane of a surface into contact with
the obstacle in a prescribed region whose shape is also to
be determined.
There are two different obstacles and 3 discretizations.
With additional constraint which ensures free boundary is convex.
QPEC from ideas by Jiang & Ralph illustrating the effect of the
complementarity multiplier.
Three simple MPECs which illustrate the three generic cases of
strong stationarity. The first solution is (0,0) and both
multipliers are 1; the second solution is (0,1) and the
complementarity constraint multiplier is 0 (i.e. we could have
ignored complementarity in both cases). The third problem's
solution is also (0,1) but now the multiplier of the complementarity
constraint is 1 and in this case, the lower bound z1 >= 0 is
redundant.
QPEC from an idea Stefan Scholtes, University of Cambridge.
Take a QP problem and its solution. Perturb the right hand
side of the constraints by some control variable z and look
for the controls that give a solution closest to the original
QP solution (measured in l2 norm). This gives rise to a QPEC,
where the constraints include the first order conditions of
the original QP and possibly some polyhedral constraints on
the controls.
"Strategic Gaming Analysis for Electric Power Systems:
an MPEC Approach", by Benjamin F. Hobbs, Carolyn Metzler and
Jong Shi-Pang. Coded by Helena Rodrigues and Teresa Monteiro.
"Strategic Gaming Analysis for Electric Power Systems:
an MPEC Approach", by Benjamin F. Hobbs, Carolyn Metzler and
Jong Shi-Pang. Coded by Helena Rodrigues and Teresa Monteiro.
Here firm B is the leader (rather than firm A in monteiro).
Nash equilibrium, see
F. Facchinei, H. Jiang and L. Qi, "A smoothing method for
mathematical programs with equilibrium constraints", Universita di Roma
Technical report, 03.96. Problem number 9.
MPECs from S. Scholtes, Research Papers in Management Studies, 26/1997,
The Judge Institute, University of Cambridge, England.
See also Outrata, SIAM J. Optim. 4(2), pp.340ff, 1994.
A packaging problem (see Section 9.2, Example 9.3):
Minimize membrane surface under the condition that
the membrane comes into contact with a compliant obstacle.
A 2D obstacle problem on [0,1] x [0,1]. Two different obstacles (1,2)
and several discretizations available
8x8, 16x16 and 32x32 grid. See Outrata, Kocvara & Zowe, "Nonsmooth Approach
to Optimization Problems with Equilibrium Constraints", Kluwer, 1998.
A packaging problem (see Section 9.2, Example 9.3):
Minimize membrane surface under the condition that
the membrane comes into contact with a compliant obstacle.
With additional constraint which ensures free boundary is convex.
A 2D obstacle problem on [0,1] x [0,1]. Two different obstacles (1,2)
and several discretizations available
8x8, 16x16 and 32x32 grid. See Outrata, Kocvara & Zowe, "Nonsmooth Approach
to Optimization Problems with Equilibrium Constraints", Kluwer, 1998.
A packaging problem (see Section 9.2, Example 9.3):
Minimize membrane surface under the condition that
the membrane comes into contact with a compliant obstacle.
Here penalize the constraint that membrane is fixed to obstacle in given region.
A 2D obstacle problem on [0,1] x [0,1]. Two different obstacles (1,2)
and several discretizations available
8x8, 16x16 and 32x32 grid. See Outrata, Kocvara & Zowe, "Nonsmooth Approach
to Optimization Problems with Equilibrium Constraints", Kluwer, 1998.
A packaging problem (see Section 9.2, Example 9.1):
Minimize membrane surface under the condition that
the membrane comes into contact with a rigid obstacle.
A 2D obstacle problem on [0,1] x [0,1].
Two different obstacles (1,2) and several discretizations are available
8x8, 16x16 and 32x32 grid. See Outrata, Kocvara & Zowe, "Nonsmooth Approach
to Optimization Problems with Equilibrium Constraints", Kluwer, 1998.
Problem pack-rig3 corrects a mistake in pack-rig2 which made
that problem inconsistent.
A packaging problem which
minimizes membrane surface under the condition that
the membrane comes into contact with a rigid obstacle.
A 2D obstacle problem on [0,1] x [0,1]. The unit square is discretized
by 8x8, 16x16, 32x32 grid of uniform triangles.
These problems have an with additional constraint which ensures
free boundary is convex.
Two different obstacles (1,2) are available. The links below show
the discretization and obstacle 2 respectively (click on the picture to
enlarge).
See Outrata, Kocvara & Zowe, "Nonsmooth Approach
to Optimization Problems with Equilibrium Constraints", (Section 9.2,
Example 9.1), Kluwer, 1998.
Problem pack-rig3c corrects a mistake in pack-rig2c which made
that problem inconsistent.
A packaging problem (see Section 9.2, Example 9.1):
Minimize membrane surface under the condition that
the membrane comes into contact with a rigid obstacle.
A 2D obstacle problem on [0,1] x [0,1].
Formulation with penalty on state constraints.
Two different obstacles (1,2) and several discretizations are available
8x8, 16x16 and 32x32 grid. See Outrata, Kocvara & Zowe, "Nonsmooth Approach
to Optimization Problems with Equilibrium Constraints", Kluwer, 1998.
A QPEC obtained by varying the grad of portfl1-6,
a portfolio optimization problem from CUTE.
This is almost a sensible problem. Here, ask what
vector r of minimum norm perturbations to returns R,
gives a solution that is as close as possible to the
given solution (obtained by rounding soln to portfl1-6).
Problem has data files portfl1.dat - portfl6.dat with
different parameters F & R.
A QPEC from H. Jiang and D. Ralph, "Smooth SQP methods for mathematical
programs with nonlinear complementarity constraints", University of
Melbourne, December 1997.
A series of QPECs generated using
H. Jiang and D. Ralph, "QPECgen: A MATLAB generator for
mathematical programs with quadratic objectives and affine variational
inequality constraints", Computational Optimization and Applications.
The matlab program write_qpec.m
writes a QPEC generated by QPECgen to an ampl file.
An LPEC and a QPEC that illustrate the need for second order
conditions for NLP reformulations of MPECs. From Danny Ralph,
Judge Institute, University of Cambridge.
Two MPEC from S. Scholtes, Research Papers in Management Studies, 26/1997,
The Judge Institute, University of Cambridge, England.
A QPEC from S. Scholtes, The Judge Institute, University of Cambridge,
England.
An LPEC from S. Scholtes, The Judge Institute, University of Cambridge,
England.
An QPEC from S. Scholtes, see page 930 of "Convergence properties of a
regularization scheme for MPCCs", SIAM J. Optimization 11(4):918-936, 2001.
MPEC formulation of traffic equilibrium problem maximizing profit.
Data from Siouxfalls. From a GAMS model by S.P. Dirkse & M.C. Ferris
mpeclib,
see also "Traffic Modeling and Variational Inequalities using
GAMS", by Dirkse & Ferris, University of Wisconsin, CS, 1997.
Click here for a figure of the network.
MPEC formulation of traffic equilibrium problem
minimizing congestion.
Data from Siouxfalls. From a GAMS model by S.P. Dirkse & M.C. Ferris
mpeclib,
see also "Traffic Modeling and Variational Inequalities using
GAMS", by Dirkse & Ferris, University of Wisconsin, CS, 1997.
Click here for a figure of the network.
A series of badly scaled 2 variable MPECs from Gabriel Lopez-Calva.
A QPEC obtained by varying the rhs of HS21 (a QP)
from an idea communicated by S. Scholtes.
Stackelberg game MPEC from
F. Facchinei, H. Jiang and L. Qi, "A smoothing method for
mathematical programs with equilibrium constraints", Universita di Roma
Technical report, 03.96. Problem number 6.
MPEC formulation of traffic equilibrium problem
minimizing congestion.
Data from Hearn & Ramana, "Solving congestion toll pricing models",
University of Florida report.
Click here for a figure of the network.
MPEC formulation of traffic equilibrium problem
minimizing congestion. Made up data extended from tap-09.
Click here for a figure of the network.
MPEC formulation of optimal tax with two factors of production no other Frills,
by Miles Light, Department of Economics, University of Colorado, Boulder, 1999.
MPEC formulation of the design of water distribution systems.
Usually formulated as a MINLP. However, here use complementarity instead
to model the flow direction (pressure in pipes).
The first model (-net) captures the main features of an actual application
for a city in indonesia. The second model is made up but much larger.
Click here for a figure of the small network
and here for a figure of the large network.
Maintained by Sven Leyffer
Email:
leyffer@mcs.anl.gov
Last modified: April 8, 2004