ampl: model mod/diet.mod; ampl: data dat/diet.dat; ampl: solve; MINOS 5.4: optimal solution found. 6 iterations, objective 88.2 ampl: option omit_zero_rows 1; ampl: display Buy; Buy [*] := MCH 46.6667 MTL -1.07823e-16 SPG -1.32893e-16 ;To help clean up displays in these cases, AMPL's display_eps option (Section 10.5 of the AMPL book) specifies the smallest magnitude that is treated as being different from zero in the output of the display command:
ampl: option display_eps .000001; ampl: display Buy; Buy [*] := MCH 46.6667 ;See also the discussion in Section 10.5 concerning the care that must be taken in rounding solution values.
Most of AMPL's tolerances relate to the simplifications that are applied by the presolve phase (Section 10.2), after you type solve but before the solver is invoked. Presolve makes a series of passes through the linear part of an optimization problem, applying a number of tests that can tighten various bounds without changing the optimum. (Conventions for viewing these bounds are explained in Section A.13.3.) The tightened bounds may imply that some variables can be fixed and some constraints can be dropped, while constraints that have only one unfixed variable may be folded into the variable's bounds. As a consequence of these changes, presolving can significantly reduce the size of the problem sent to the solver.
Because the decisions made by the presolve phase rely on numerical computations, small differences between numbers can have a large effect on the results. The following tolerance options have been introduced to deal with a variety of situations in which this can occur. Fortunately, the default values of these options produce acceptable results in a large majority of cases. Warnings are displayed if a small change in tolerance settings could affect the optimal values in any significant way.
The presolve option specifies the maximum number of passes to be made by the presolve phase. Thus option presolve 0 turns off all presolving, and option presolve 1 applies only the more elementary simplifications. The default value is 10.
ampl: model steel3.mod; ampl: data steel3.dat; ampl: let market["bands"] := 500; ampl: solve; inconsistent bounds for var Make[bands]: lower bound = 1000 > upper bound = 500; difference = 500 Ignoring solve command because presolve finds no feasible solution possible.This is a simple case, because the upper bound on variable Make["bands"] has clearly been reduced below the lower bound. Presolve's more sophisticated tests can also find infeasibilities that are not due to any one variable. As an example, consider the constraint in this model:
subject to Time: sum{p in PROD} 1/rate[p]*Make[p] <= avail;
If you reduce the value of avail to 13 hours, presolve deduces that
this constraint can't possibly be satisfied:
ampl: let market["bands"] := 5000; ampl: let avail := 13; ampl: solve; presolve: constraint Time cannot hold: body <= 13 cannot be >= 13.2589; difference = -0.258929 Ignoring solve command because presolve finds no feasible solution possible.The "body" of constraint Time is sum {p in PROD} 1/rate[p]*Make[p], the part that contains the variables (see Section 10.7). Presolve reports that, given the bounds on the variables that it has found, this expression must have a value of at least 13.2589 (to six digits); on the other hand, the value of avail that we gave requires that this expression have a value of at most 13.
Presolve reports the difference between its two bounds for constraint Time as (again to six digits) -0.258929. Thus in this case we can guess that 13.258929 is, approximately, the smallest value of avail that allows for a feasible solution. Indeed, we get:
ampl: let avail := 13.258929; ampl: solve; MINOS 5.4: optimal solution found. 0 iterations, objective 61750.00214If we make avail just slightly lower, however, we again get the infeasibility message:
ampl: let avail := 13.258928; ampl: solve; presolve: constraint Time cannot hold: body <= 13.2589 cannot be >= 13.2589; difference = -5.71429e-07 Setting $presolve_eps >= 5.714285720159751e-07 might help. Ignoring solve command because presolve finds no feasible solution possible.Although the lower bound is here the same as the upper bound to six digits, it is greater than the upper bound in full precision, as the negative value of the difference indicates.
Typing solve a second time in this situation tells AMPL to override presolve and send the seemingly inconsistent deduced bounds to the solver:
ampl: solve; MINOS 5.4: optimal solution found. 0 iterations, objective 61749.99714 ampl: option display_precision 10; ampl: display commit,Make; : commit Make := bands 1000 999.9998857 coils 500 500 plate 750 750 ;The MINOS solver declares that it has found an optimal solution, though with Make["bands"] being slightly less than its lower bound commit["bands"]! Here MINOS is applying an internal tolerance that allows small infeasibilities to be ignored; the AMPL/MINOS documentation explains how this tolerance works and how it can be changed. Each solver applies feasibility tolerances in its own way, so it's not surprising that a different solver gives different results:
ampl: option solver cplex; ampl: solve; CPLEX 2.1: All rows and columns eliminated. CPLEX 2.1: infeasible problem 0 iterationsHere CPLEX has applied its own presolve and has detected the same infeasibility that AMPL did.
AMPL's presolve has its own tolerances that you can set. They are mainly useful for problems that, due to some property of the formulation, cause computed lower bounds to be equal to their corresponding upper bounds. Due to imprecision in the computations, some lower bounds in this case will come out slightly higher than their upper bounds, resulting in a "no feasible solution possible" message such as those above. You can tell that you are in this situation because the reported "difference" between the bounds is very small compared to the bounds themselves.
To deal with this situation, explanation to come . . .
Return to the AMPL update page.