TRY NOW!
AMPL > >Integer Programming > >Why does my solver’s relax directive sometimes give a higher objective value than AMPL’s relax_integrality option?

These two ways of relaxing integrality can give different results because they interact differently with AMPL’s presolve phase.

Under option relax_integrality 1, all integer variables are changed to continuous before AMPL’s presolve. Thus presolve works on the “true” relaxation, and the reduced LP that comes out of presolve has the same objective value as the true relaxation.

Under option relax_integrality 0, all integer variables remain integer through AMPL’s presolve phase. Presolve may take advantage of this integrality to further tighten bounds and reduce the problem size. If the solver’s relax directive is subsequently set, then it will solve the relaxation of the presolved integer program, which may not have the same objective value as the true relaxation. (Specifically, its value may be higher for a minimization, or lower for a maximization.)

As a simple example, imagine a minimization model in which there are integer variables X[t] constrained by sum {t in 1..T} X[t] <= 7.5. If relax_integrality is set to 1, then the variables are made continuous, but otherwise the constraint remains the same. If relax_integrality is instead left at 0, then presolve will tighten 7.5 to 7 before sending the integer program to the solver. This has no effect on the integer optimum, but by tightening the constraint it may cause the solver’s relaxation to have a higher value than AMPL’s relaxation.

For purposes of solving the problem, the solver’s higher relaxation value is normally to be preferred. In some iterative schemes that solve a series of relaxations, however, only the lower true relaxation value makes sense. To ensure that you get the optimum of the true relaxation, either set option relax_integrality 1 or set option presolve 0 and turn on the solver’s relax directive.

Posted in: Integer Programming