A variable is ineligible to be substituted out of a problem if (a) it is
subject to any bounds or integrality conditions, or (b) it has already appeared
on the right-hand side of a constraint that was used to make a substitution.
Case (a) includes bounds or integrality conditions specified in the
variable's declaration, and also bounds that are added by AMPL's presolve phase.
Thus turning presolve off (by setting option presolve
0) may permit a greater number of substitutions.
For constraints indexed over a set, the incidence of case (b) may depend on
the ordering of the set. Consider for example the constraints
var x {1..10};
subj to step {j in 1..9}: x[j] = x[j+1] + 1;
The first several constraints generated are
step[1]: x[1] = x[2] + 1
step[2]: x[2] = x[3] + 1
step[3]: x[3] = x[4] + 1
step[4]: x[4] = x[5] + 1
Constraint step[1] may be used to substitute for x[1].
Constraint step[2] may not be used to substitute for x[2],
however, because x[2] has already appeared on the right-hand side of a
constraint, namely step[1], that was used to make a substitution.
Similarly, step[3] may be used to substitute for x[3], but
step[4] may not be used to substitute for x[4], and so forth.
Only the odd-numbered constraints step[j] are eliminated by
substitution in this case.
If instead you write the declaration with the ordered index set reversed,
subj to step {j in 9..1 by -1} x[j] = x[j+1] + 1;
then the constraints are generated as
step[9]: x[9] = x[10] + 1
step[8]: x[8] = x[9] + 1
step[7]: x[7] = x[8] + 1
step[6]: x[6] = x[7] + 1
and case (b) does not occur. All of the constraints step[j] can be
eliminated, and every variable except x[10] is substituted out as a
result.
Close attention to formulation may thus be necessary to get the substitutions
that you want. Set option show_stats 1 to see how
many substitutions are being made, and use AMPL's new constraint expansion commands to see
the constraints (in order) before and after substitution.
Symptoms of this problem are an option show_stats
1 listing that refers to nonlinear variables and constraints, and
rejection by the solver with a "contains nonlinear
constraints" message. The cure may be (a) to reformulate the model so
that certain unintended nonlinearities are made linear, or (b) set
option linelim 1 so that substituted linear variables
do not become nonlinear.
Case (a) can occur because you have overlooked a simple nonlinearity, such as
a variable multiplying or dividing another variable. AMPL's built-in arithmetic
functions, including simple ones such as abs and max, are
treated as nonlinear when applied to variables; if ...
then ... else ... expressions are also
nonlinear if variables appear in the expression following the if. You
may be able to convert these kinds of "nonlinearities" to equivalent linear
expressions, but AMPL cannot do the conversion automatically. (The only such
conversions currently built into AMPL are for the piecewise-linear functions
described in Chapter 14 of the AMPL
book.)
Case (b) occurs when AMPL's defined variable feature is invoked to substitute
an expression for a variable -- either by using the = operator in
declarations of variables, or by setting option substout
1 to infer substitutions from the constraints. Under option
linelim 0, AMPL does not substitute explicitly in the
constraints, but instead records the substitution as an additional piece of
information in the file sent to the solver. This affords very efficient handling
of sub-expressions that appear at many places in a problem, but it has the
side-effect of causing all variables in a substituted expression to be treated
as nonlinear. To request explicit substitution, so that linearity is preserved,
set option linelim 1. This is the default for AMPL versions 20000327 and later, but if
you're using an earlier version you'll need to set option
linelim 1 explicitly.
Versions of AMPL prior to
20000128 are unable to recognize linearity in this case. If you are using one of
these earlier versions and cannot obtain
an update, you may be able to handle this situation in a more indirect way,
such as by writing a script to alternate between related linear models in which
the fixed variables are replaced by parameters.
As a simple example, suppose you want to minimize a quadratic function of
variables X[i] and Y[j]:
param q {1..n,1..n};
var X {1..n} >= 0;
var Y {1..n} >= 0;
minimize Quadratic:
sum {i in 1..n, j in 1..n} X[i] * q[i,j] * Y[j];
The objective becomes linear when you fix either all the X[i] or all
the Y[j]. This suggests creating two new linear objectives in which
parameters are substituted for the variables to be fixed:
param xfix {1..n};
param yfix {1..n};
minimize QuadX:
sum {i in 1..n, j in 1..n} X[i] * q[i,j] * yfix[j];
minimize QuadY:
sum {i in 1..n, j in 1..n} xfix[i] * q[i,j] * Y[j];
Given some initial yfix[j] values, you can use a linear programming
solver to minimize QuadX. Then you can assign the optimal values of
X[i] to xfix[i], after which you can use a linear programming
solver to minimize QuadY. Finally you can assign the optimal values of
Y[j] to yfix[j], and repeat. This iteration is readily written
using AMPL's new repeat loop
construct as:
repeat {
objective QuadX;
solve;
let {i in 1..n} xfix[i] := X[i];
objective QuadY;
solve;
let {j in 1..n} yfix[j] := Y[j];
} until abs(QuadX - QuadY) < 0.001;
For brevity we have not shown constraints, which can alternated like the
objectives by use of drop and restore (Section 10.8 of the AMPL book) or AMPL's new named problem feature. We also
caution that an iterative scheme like this may never stop; a guarantee of
termination can be supplied only for certain special cases.
|
