MPEC Comments
This file briefly describes the MPEC test problems.
bar-truss
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.
bard
MPECs from J.F. Bard, "Convex two-level optimization", Mathematical Programming 40(1), 15-27, 1988.
bardm
MPECs from J.F. Bard, "Convex two-level optimization", Mathematical Programming 40(1), 15-27, 1988. Formulation as in S. Dirkse's mpeclib.
bem-milanc30
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.
bilevel
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.
bilevelm
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.
bilin
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.
dempe
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.
df1
S.P. Dirkse and M.C. Ferris, "Modeling & Solution Environment for MPEC: GAMS & MATLAB", University of Wisconsin CS report, 1997.
design-cent
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, [problems/design-init-1.mod design-init-1.mod], [problems/design-init-2.mod design-init-2.mod], [problems/design-init-3.mod design-init-3.mod], [problems/design-init-4.mod design-init-4.mod].
The solution to Problems 1,2 and 4 can be found [solutions.html#design-cent 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.
desilva
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.
ex9.1
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.
- Solution to ex9.1.6: x=16, y=11, s=[28 12 0 0 12 11], l=[0 0 3 0 0 0], objective=-49
- Solution to ex9.1.7: x= [0, 0.9], y= [0, 0.6, 0.4], s = [0, 0, 0, 0, 0.6, 0.4], l = [0, 1, 3, 6, 0, 0], objective =-26
ex9.2
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.
- Solution to ex9.2.1, ex9.2.7: x = 1, y = 0, s = [0, 3, 6, 0],l = [3.5, 0, 0, 0], objective=17
- Solution to ex9.2.5: x = 1, y = 3, s = [0, 7, 7], l = [4, 0, 0], objective = 6
flp2
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.
flp4
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 [tools/genflp4.m genflp4.m]
gnash1
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.
gnash1m
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.
gauvin
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.
hakonsen
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.
hs044-i
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.
incid-set
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.
incid-setc
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.
jr
QPEC from ideas by Jiang & Ralph illustrating the effect of the complementarity multiplier.
kth
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.
liswet1-inv
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.
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.
monteiroB
"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).
nash1
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.
outrata
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.
pack-comp
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.
pack-compc
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.
pack-compp
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.
pack-rig
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.
pack-rigc
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.
pack-rigp
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.
portfl-i
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.
qpec
A QPEC from H. Jiang and D. Ralph, "Smooth SQP methods for mathematical programs with nonlinear complementarity constraints", University of Melbourne, December 1997.
qpecgen
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 [tools/qpecgen/write_qpec.m write_qpec.m] writes a QPEC generated by QPECgen to an ampl file.
ralphmod
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.
scholtes
Two MPEC from S. Scholtes, Research Papers in Management Studies, 26/1997, The Judge Institute, University of Cambridge, England.
scholtes3
A QPEC from S. Scholtes, The Judge Institute, University of Cambridge, England.
scholtes4
An LPEC from S. Scholtes, The Judge Institute, University of Cambridge, England.
scholtes5
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.
siouxfls
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 [images/tollmpec.gif figure of the network].
siouxfls1
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 [images/tollmpec.gif figure of the network].
scale
A series of badly scaled 2 variable MPECs from Gabriel Lopez-Calva.
sl1
A QPEC obtained by varying the rhs of HS21 (a QP) from an idea communicated by S. Scholtes.
stackelberg1
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.
tap-09
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 [images/tap-09.gif figure of the network].
tap-15
MPEC formulation of traffic equilibrium problem minimizing congestion. Made up data extended from tap-09.
Click here for a [images/tap-15.gif figure of the network].
taxmcp
MPEC formulation of optimal tax with two factors of production no other Frills, by Miles Light, Department of Economics, University of Colorado, Boulder, 1999.
TrafficSignalCycle
Optimal cycle for a signalized intersection, see Isabel M. Ribeiro and M. Lurdes Simoes in Sociedad de Estadistica e Investigacion Operativa 2010, DOI 10.1007/s11750-010-0167-3. AMPL Model coded by Teofilo Melo, Teresa Monteiro, and Joao Matias.
The solution values were obtained by Teofilio Melo, Politecnico do Porto, using an SLCP approach.
water
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 [images/water-net.gif figure of the small network] and here for a [images/water-FL.gif figure of the large network].