A new AMPL operator, complements, permits complementarity conditions to be specified directly in constraint declarations. Complementarity models can thereby be formulated in a natural way, and instances of such models are easily sent to special solvers for complementarity problems.
To motivate the syntax of the new operator, we begin by considering how AMPL might be extended to express the complementary slackness conditions for standard and bounded-variable linear programs. We then give a general definition of the complements operator for pairs of inequalities, and for more general "mixed" complementarity conditions via double inequalities. We also comment on an AMPL interface to Dirkse and Ferris's PATH solver for "square" mixed complementarity problems. Finally, we describe extensions to accommodate complementarity constraints in several of AMPL's existing features: the presolve phase, constraint-name suffixes, and generic synonyms for constraints.
Illustrations are taken from a collection of AMPL complementarity models that use the new syntax. See the complementarity model index for links to the complete models.
To begin, consider a linear program that has the following elementary primal form:
The corresponding "complementary slackness" conditions for optimality are easily represented like this:minimize PrimalObj: sum {j in J} c[j] * X[j]; subj to PrimalConstr {i in I}: sum {j in J} a[i,j] * X[j] = b[i]; subj to PrimalBounds {j in J}: X[j] >= 0;
Of course, AMPL does not (currently) accept the or operator in constraints, but the Complementarity[j] constraints can be written equivalently in this case as nonlinear equations:PrimalConstr {i in I}: sum {j in J} a[i,j] * X[j] = b[i]; PrimalBounds {j in J}: X[j] >= 0; DualConstr {j in J}: sum {i in I} Y[i] * a[i,j] + Z[j] = c[j]; DualBounds {i in I}: Z[i] >= 0; Complementarity {j in J}: X[j] = 0 or Z[j] = 0;
Consider now the case, only slightly more complicated, of a linear program with arbitrary bounds on the variables:Complementarity {j in J}: X[j] * Z[j] = 0;
The corresponding complementary slackness conditions are as follows:minimize PrimalObj: sum {j in J} c[j] * X[j]; subj to PrimalConstr {i in I}: sum {j in J} a[i,j] * X[j] = b[i]; subj to PrimalBounds {j in J}: l[j] <= X[j] <= u[j];
The constraints Complementarity[j] are again not recognized by AMPL, but in this case they also lack any concise and straightforward algebraic equivalent.PrimalConstr {i in I}: sum {j in J} a[i,j] * X[j] = b[i]; PrimalBounds {j in J}: l[j] <= X[j] <= u[j]; DualConstr {j in J}: sum {i in I} Y[i] * a[i,j] + Z[j] = c[j]; Complementarity {j in J}: X[j] = l[j] implies Z[j] >= 0 and X[j] = u[j] implies Z[j] <= 0 and l[j] < X[j] < u[j] implies Z[j] = 0;
It would be desirable to be able to express these two similar forms of complementary problem in similar ways. To make this possible, we observe that there are two "elements" comprising each Complementarity[j] constraint: X[j] = 0 and Z[j] = 0 in the first case, and l[j] < X[j] < u[j] and Z[j] in the second. The members of each element pair "complement" each other in a sense appropriate to their form. This suggests defining a new AMPL operator, complements, to explicitly denote the complementarity relationship. The first form of complementary slackness then becomes
and the second form is the same except for the pair of elements that complement each other:PrimalConstr {i in I}: sum {j in J} a[i,j] * X[j] = b[i]; DualConstr {j in J}: sum {i in I} Y[i] * a[i,j] + Z[j] = c[j]; Complementarity {j in J}: X[j] >= 0 complements Z[j] >= 0;
To be feasible for this new constraint type, a solution must satisfy the two inequalities that appear, and must cause the two arguments of the complements operator to complement each other. The meaning of "complement each other" for these two cases is exactly as given in our original statements of the complementary slackness conditions above.PrimalConstr {i in I}: sum {j in J} a[i,j] * X[j] = b[i]; DualConstr {j in J}: sum {i in I} Y[i] * a[i,j] + Z[j] = c[j]; Complementarity {j in J}: l[j] <= X[j] <= u[j] complements Z[j];
The same conditions can be expressed more concisely by substituting the variables Z[j] out of the constraints. We then have for the case of nonnegative variables,
and for the case of bounded variables,PrimalConstr {i in I}: sum {j in J} a[i,j] * X[j] = b[i]; Complementarity {j in J}: X[j] >= 0 complements c[j] - sum {i in I} Y[i] * a[i,j] >= 0;
The first form could also be written even more concisely asPrimalConstr {i in I}: sum {j in J} a[i,j] * X[j] = b[i]; Complementarity {j in J}: l[j] <= X[j] <= u[j] complements c[j] - sum {i in I} Y[i] * a[i,j];
In fact it makes sense to allow the arguments of complements to be any two single-inequality constraints, or any double-inequality constraint and any expression.PrimalConstr {i in I}: sum {j in J} a[i,j] * X[j] = b[i]; Complementarity {j in J}: X[j] >= 0 complements sum {i in I} Y[i] * a[i,j] <= c[j];
It turns out that these few constraint forms are sufficient to conveniently represent most linear complementarity problems of interest, regardless of whether they have any relationship to a linear program. The same is true of nonlinear complementarity problems, when these forms are extended to permit nonlinear constraints and expressions.
We next proceed to define the complements operator more formally and generally, first for the case of two complementary single inequalities, and then for the case of a double inequality complementing an expression.
single-inequality complements single-inequality ;where a single-inequality is any valid constraint expression -- linear or nonlinear -- containing one >= or <= operator. A constraint of this type is satisfied if both of the single-inequality constraints are satisfied, and at least one is satisfied with equality.
As an example, pies.mod makes the following statement about coal shipments and prices:
To satisfy this constraint, the variables Ct[c,u], Cv[c], and P["C",u] must satisfysubject to delct {c in CREG, u in USERS}: 0 <= Ct[c,u] complements ctcost[c,u] + Cv[c] >= P["C",u];
double-inequality complements expression ;where double-inequality is any AMPL constraint expression -- linear or nonlinear -- containing two >= or two <= operators. The conditions for a constraint of this type to be satisfied are as follows:
expression complements double-inequality ;
As an example, pies.mod makes the following statement about coal production:
This implies that the following conditions must be satisfied:subject to delc {c in CREG, t in CTYP}: 0 <= C[c,t] <= cmax[c,t] complements ccost[c,t] + (sum {res in R} cruse[res,c,t] * Mu[res]) - Cv[c];
For completeness, the special case in which the left-hand side equals the right-hand side of the double inequality may be written using one of the forms
equality complements expression ;A constraint of this kind is equivalent to an ordinary constraint consisting only of the equality; it places no restrictions on the expression.
expression complements equality ;
Specifically, AMPL/PATH accepts any constraint system such that the number of variables equals the number of complementarity constraints plus the number of equality constraints. There may be any number of additional inequality constraints, but there must not be any objective. The AMPL/PATH interface automatically transforms constraints from this form to the more resricted form required by PATH, and later inverts the transformation so that the results may be viewed in terms of the originally specified model.
AMPL/PATH is invoked by setting AMPL's solver option to path prior to a solve command:
An error message such asampl: model pies.mod; ampl: data pies.dat; ampl: option solver path; ampl: solve; PATH 3.0: Solution found. 14 iterations (1 for crash); 28 pivots. 30 function, 16 gradient evaluations. ampl:
indicates that the specified problem instance cannot be solved by PATH, because the number of variables does not equal the total of equality and complementarity constraints.Nonsquare complementarity system: 38 equations and 42 variables. PATH 3.0 requires a square system; this one is 38 x 42.
As an example, given a constraint of the form
expr1 >= 0 complements expr2 >= 0,if presolve can deduce that expr1 is strictly positive for all feasible points -- in other words, that it has a positive lower bound -- then it can replace the constraint by expr2 = 0. Similarly, in a constraint of the form
expr1 <= expr2 <= expr3 complements expr4,there are various possibilities, including the following:
If presolve can deduce for all feasible points that | Then the constraint can be replaced by | ||
---|---|---|---|
expr2 < expr3 | expr1 <= expr2 complements expr4 >= 0 | ||
expr1 < expr2 < expr3 | expr4 = 0 | ||
expr4 < 0 | expr2 = expr3 |
Transformations of these kinds are carried out automatically, unless you use option presolve 0 to turn off the presolve phase. As is currently the case for ordinary constraints, results are reported in terms of the original model, so that the benefits of presolving are achieved without any special attention from the user.
By displaying a few predefined parameters,
_ncons the number of ordinary constraints before presolve,or by setting option show_stats 1, you can get some information on the number of simplifying transformations that presolve has made:
_nccons the number of complementarity conditions before presolve,
_sncons the number of ordinary constraints after presolve,
_snccons the number of complementarity conditions after presolve,
When first instantiating the problem, AMPL counts each complementarity constraint as two ordinary constraints (the two arguments to complements) and also as a complementarity condition. Thus _nccons equals the number of complementarity constraints before presolve, and _ncons equals twice _nccons plus the number of non-complementarity constraints before presolve. The presolve messages at the beginning of the show_stats output indicate how much presolve was able to reduce these numbers.ampl: model pies.mod; ampl: data pies.dat; ampl: option solver path; ampl: option show_stats 1; ampl: solve; Presolve eliminates 42 constraints. Presolve resolves 8 of 42 complementarity conditions. Adjusted problem: 42 variables: 6 nonlinear variables 36 linear variables 42 constraints; 142 linear nonzeros 34 nonlinear constraints 8 linear constraints 34 complementarity conditions among the constraints: 28 linear, 6 nonlinear. 0 objectives. PATH 3.0: Solution found. 14 iterations (1 for crash); 28 pivots. 30 function, 16 gradient evaluations. ampl: display _ncons, _nccons; _ncons = 84 _nccons = 42 ampl: display _sncons, _snccons; _sncons = 42 _snccons = 34
lbound <= body <= ubound,where lbound and ubound are constants, the recognized suffixes and their values are:
cname.body bodyAny ordinary constraint can be put into this form, possibly with lbound equal to -Infinity or ubound equal to Infinity.
cname.lb lbound
cname.ub ubound
cname.lslack body - lbound
cname.uslack ubound - body
cname.slack min (cname.lslack, cname.uslack)
This feature extends to complementarity constraints, but with two collections of suffixes, of the form cname.Lsuf and cname.Rsuf, corresponding to the left and right operands of complements, respectively. Thus for example after pies.mod has been solved, you can use the following display command to look at values associated with the constraint delc:
Subscripted forms of the constraint name can also be suffixed:ampl: display delc.Llb, delc.Lbody, delc.Lub, ampl? delc.Rlb, delc.Rbody, delc.Rub; : delc.Llb delc.Lbody delc.Lub delc.Rlb delc.Rbody delc.Rub := 1 1 0 300 300 -Infinity -10.7551 Infinity 1 2 0 300 300 -Infinity -9.51119 Infinity 1 3 0 227.889 400 -Infinity -8 Infinity 2 1 0 200 200 -Infinity -10.5051 Infinity 2 2 0 300 300 -Infinity -8.91133 Infinity 2 3 0 600 600 -Infinity -8.46915 Infinity ;
Notice that since the right operand of delc is an expression, it is treated as a "constraint" with infinite lower and upper bounds, and hence infinite slack.ampl: display {t in ctyp} (delc[1,t].Lslack, delc[1,t].Rslack); : delc[1,t].Lslack delc[1,t].Rslack := 1 0 Infinity 2 0 Infinity 3 172.111 Infinity ;
The suffix cname.slack is also defined for complementarity constraints. For complementary pairs of single inequalities, it is equal to min(cname.Lslack, cname.Rslack). Hence it is nonnegative if and only if both inequalities are satisfied. For complementary double inequalities of the form
expr complements lbound <= body <= uboundcname.slack is defined to be
lbound <= body <= ubound complements expr
min(expr, body - lbound) | if body <= lbound | ||
min(-expr, ubound - body) | if body >= ubound | ||
-abs(expr) | otherwise |
Hence in this case it is always nonpositive, and is zero when one part of the double inequality is satisfied exactly.
If cname for a complementarity constraint appears unsuffixed in an expression, it is interpreted as representing cname.slack.
From the modeler's view (before presolve), the ordinary constraint synonyms remain
_ncons the number of ordinary constraints before presolve,The new complementarity constraint synonyms are
_conname names of the ordinary constraints before presolve,
_con synonyms for the ordinary constraints before presolve,
_nccons the number of complementarity constraints before presolve,Because each complementarity constraint also gives rise to two ordinary constraints, as explained in the preceding discussion of presolve, there are two entries in _conname corresponding to each entry in _cconname:
_cconname names of the complementarity constraints before presolve,
_ccon synonyms for the complementarity constraints before presolve,
ampl: model josephy.mod; ampl: data josephy.dat; ampl: display _conname,_cconname; : _conname _cconname := 1 'f[1].L' 'f[1]' 2 'f[1].R' 'f[2]' 3 'f[2].L' 'f[3]' 4 'f[2].R' 'f[4]' 5 'f[3].L' . 6 'f[3].R' . 7 'f[4].L' . 8 'f[4].R' . ;
For each complementarity constraint cname, the left and right arguments to the complements operator are the ordinary constraints named cname.L and cname.R. You can see this by using the synonym terminology to expand complementarity constraint f[1] and the corresponding two ordinary constraints from the example above:
From the solver's view (after presolve), a more limited collection of synonyms is defined:ampl: expand f[1]; s.t. f[1]: -x[1] <= 0 complements 3*x[1]*x[1] + 2*x[1]*x[2] + 2*x[2]*x[2] + x[3] + 3*x[4] >= 6; ampl: expand {i in 1..2} _con[i]; s.t. f[1].L: -x[1] <= 0; s.t. f[1].R: 3*x[1]*x[1] + 2*x[1]*x[2] + 2*x[2]*x[2] + x[3] + 3*x[4] >= 6;
_sncons the number of all constraints after presolve,Necessarily _snccons is less than or equal to _sncons, with equality only when all constraints are complementarity constraints. By using solexpand in place of expand, you can see the form in which AMPL sent complementarity constraint f[1] to the solver:
_snccons the number of complementarity constraints after presolve,
_sconname names of all constraints after presolve,
_scon synonyms for all constraints after presolve,
To simplify the problem description that is sent to the solver, AMPL converts every complementarity constraint into one of the following canonical forms,ampl: solexpand f[1]; s.t. f[1]: 3*x[1]*x[1] + 2*x[1]*x[2] + 2*x[2]*x[2] + -6 + x[3] + 3*x[4] >= 0 complements 0 <= x[1];
expr complements lbound <= var <= ubound,where var is the name of a different variable for each constraint. A predefined array of integers, _scvar, gives the indices of these canonical complementing variables in the generic variable arrays _var and _varname. This terminology can be used to display a list of names of such variables:
expr <= 0 complements var <= ubound,
expr >= 0 complements lbound <= var,
When constraint i is an ordinary equality or inequality, _scvar[i] is 0.ampl: display {i in 1.._sncons} _varname[_scvar[i]]; _varname[_scvar[i]] [*] := 1 'x[1]' 2 'x[2]' 3 'x[3]' 4 'x[4]' ;
Return to the AMPL update page.