For each variable whose integrality you want to relax, assign a positive
value to variable-name.relax. For example, if your model has
var X {1..n} integer >= 0;
var Y {1..m} integer >= 0;
then to relax the integrality of only the Y variables, you can use
the command
let {i in 1..m} Y[i].relax := 1;
To remove a relaxation specified in this way, assign a nonpositive value to
variable-name.relax.
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.
The "break" signal (Ctrl-C for many computers) stops the solver and returns
control to AMPL, but does not necessarily return any solution from the solver.
Some solvers may make provision to "catch" the break signal and return the best
solution found so far; consult the solver
directive instructions to see if this is the case for the solver that you
are using.
Various solver directives can stop a run and return the current incumbent
optimal solution, but they must be given before the run begins. Available
stopping criteria may include number of branch-and-bound nodes, number of
integer solutions, and total time. Directives are different for each solver, so
consult AMPL's solver directive instructions for details.
Special ordered sets of type 2 (SOS2s) are used automatically by some solvers
(including CPLEX and OSL) to handle piecewise-linear functions as described in
Chapter 14 of the AMPL book.
Special ordered sets of type 1 and 3 are most useful for handling variables
that are restricted to a finite but not regularly-spaced series of values. For
example, a variable Cap[j] standing for capacity of warehouse
j might be required to take one of the values 0, 15, 25 or 30. AMPL
doesn't currently have any convenient way to express such restrictions. (CPLEX's
sosscan directive invokes a preprocessor that can automatically
identify constraints that have a SOS3 interpretation. However, AMPL does not
usually supply enough information about these constraints to afford any
significant efficiency in the branch-and-bound process.)
|
