Draft Writeup of April 16, 1995

PRESOLVE TOLERANCES

Because computers work in finite-precision arithmetic, AMPL must employ a variety of tolerances to cope with small inaccuracies. For example, rounding to finite precision often leads solvers to return numbers that differ from zero by an insignificant amount:

	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.


Determining that no feasible solution exists

If presolve determines that any variable's lower bound is greater than its upper bound, then there can be no solution satisfying all the bounds and other constraints, and an error message is printed accordingly. For example, here's what would happen if you changed market["bands"] to 500 when you meant 5000:

	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.00214
If 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 iterations
Here 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.


Rounding bounds on integer variables

When AMPL's presolve phase determines that a variable declared integer has a fractional lower (or upper) bound, it rounds the bound up to the next highest integer (or down to the next lowest integer). Due to inaccuracies of finite-precision computation, however, a bound may be calculated to have a value that is just slightly different from an integer. An upper bound that should be 7, for example, might be calculated as 6.99999999998, in which case you would not want the bound to be rounded down to 6!

To deal with this situation, explanation to come . . .


Computing dual values on presolved constraints

[[to come]]


Determining when a constraint can be dropped by presolve

[[to come]]



Comments or questions?
Write to info@ampl.com or use our comment form.

Return to the AMPL update page.

Return to the AMPL home page.


LAST MODIFIED 19 JANUARY 1996 BY 4er.