AMPL > >Faqs

Integer Programming

How do I relax the integrality of only some of a model’s integer variables?

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.

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.

How can I “break” a run of an integer programming solver and get back the best integer solution found so far?

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.

How can I use the solver’s “special ordered sets” feature?

There are two kinds of formulations that cause special ordered sets to be set up by AMPL and used by your solver automatically. For other situations you can explicitly identify special ordered sets of types 1 and 2 using certain suffixes on variables. The first kind of formulation involves variables that are restricted to a finite but not regularly-spaced series of values. For example, each variable Cap[j] standing for the capacity of warehouse j might be required to take one of the values in a given set S by use of a declaration like this:

var Cap {i in WHSE} in S;

(For example, S might contain only 0, 15, 25, and 30.) Special ordered sets of type 1 are automatically generated to help the solver branch efficiently on the possibilities in this case. The second kind of formulation is used to handle separable piecewise-linear functions written as described in Chapter 17 of the AMPL book. As an example, a 3-part shipment cost to be minimized may be written as

minimize Total_Cost:
   sum {i in ORIG, j in DEST}
        rate1[i,j], rate2[i,j], rate3[i,j] >> Trans[i,j];

using AMPL’s <<>> notation for writing piecewise-linear functions in terms of their breakpoints and slopes. In special cases there is an equivalent linear formulation; but in all other cases, special ordered sets of type 2 are automatically generated to help the solver search the possibilities. To identify special ordered sets explicitly, the following statements must first be used to create two suffixes for providing extra information on each variable:

suffix sosno integer IN;
suffix ref integer IN;

For our type 1 example above, auxiliary binary variables Lambda[i,j] could be defined to express the Cap[i] variables as sums that can only take on the possible values in S:

param nWhse integer > 0;
set WHSE = 1..nWhse;
var Lambda {i in WHSE, j in S} binary;
var Cap {i in WHSE} = sum {j in S} j * Lambda[i,j];
subject to ChooseOne {i in WHSE}:
  sum {j in S} Lambda[i,j] = 1;

The special ordered sets for this formulation could be defined by assigning values to the suffixes as follows:

let {i in WHSE, j in S} Lambda[i,j].sosno := i;
let {i in WHSE, j in S} Lambda[i,j].ref := j;

The variables in each special ordered set must be given the same unique .sosno value, positive for sets of type 1 or negative for sets of type 2. The .ref values guide branching within the solver’s branch-and-bound scheme, and are generally the coefficients in a sum like sum {j in S} j * Lambda[i,j] that appears in the definition of some variable. The details vary with the situation being modeled, and some advanced study of relevant papers may be necessary to get them right.