AMPL > >Faqs

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 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 17 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, leave the `linelim`

option at its default setting of `1`

.

Yes, AMPL fixes the variables first, and then analyzes the model to determine whether it is linear. So if you make your model linear by fixing certain variables, you can direct AMPL to send the resulting problem instance to a linear solver for optimization.