This page presents the semantics of the most common solver features; for a development
reference see HOWTO hook your solver to AMPL MP.
General features
Output level
All solvers print some information during the solution process. For the sake of clarity,
when using the solvers from AMPL the information is mostly ommitted, and only the solver message is
displayed, which describes the outcome of the optimization process.
The amount of information printed is controlled by the option outlev:
option <solver>_options 'outlev=1';
In case of repeated executions it is often desiderable to hide all solver output. The solver message
can be suppressed by setting the option solver_msg to 0. The solver banner is displayed anyway;
to suppress it a redirection is needed:
option solver_msg 0;
solve > NUL;
Option |
outlev
|
Applicability |
All models |
Values |
Values:
0 - No (default) 1 - Yes, print detailed execution log 2, 3, … - Solver-dependent values
|
Model export
Most solvers can export the model before solving. This is usually
controlled by the option writeprob:
option <solver>_options 'writeprob=/tmp/diet.lp';
The format is solver-dependent and determined by the file extension
(‘.lp’ in the example).
Option |
writeprob
|
Applicability |
All models |
Values |
Values:
|
Report solution time
All solvers can measure the execution times of the solution process;
by setting this option to 1, the solver will display and return via
problem suffixes this information.
The reported times are: time_solver (the time taken by the solver itself
to solve the model), time_setup (the time spent in the solver driver for
reading the model file, reformulating it and prepare all the memory structures)
and time (=time_solver+time_setup, the total time spent in the driver):
option <solver>_options 'report_times=1';
Option |
tech:reporttimes
|
Applicability |
All models |
Input |
None |
Output |
Suffixes (on problem):
time total time spent in the driver
time_setup time spent to read and reformulate the model
time_solver time spent solving the model
|
Values |
Values:
|
Example |
Use this model
Execute:
option <solver>_options "tech:reporttimes=1";
solve;
display Initial.time, Initial.time_setup, Initial.time_solver;
Output:
tech:reporttimes = 1
Setup time: 0.0113952s
Solution time: 0.0016453s
suffix time OUT;
suffix time_setup OUT;
suffix time_solver OUT;
Initial.time = 19.43
Initial.time_setup = 0.88
Initial.time_solver = 19.46
|
Warm start
Solution process can often benefit of a solution (a set of variable values) to start the algorithm.
This is passed to supporting solver automatically if the option is activated and variables in AMPL
have a value assigned. Note that, for LP problems, also the dual values can be passed.
This option controls whether to use incoming primal (and dual, for LP) variable values in
a warmstart.
Option |
alg:start
|
Applicability |
LP and MIP models |
Input |
Variable values |
Output |
None |
Values |
Sum of:
0 - No (default) 1 - Yes (for LP: if there is no incoming alg:basis) (default) 2 - Yes (for LP: ignoring the incoming alg:basis, if any)
|
Example |
Use this model
Execute:
option <solver>_options "alg:start=1";
let n:=250; # increase the size of the model to have noticeable solution times
solve;
printf "Solution without warm start took %fs\n", _solve_time;
# Now an optimal solution is already present, we pass it to the solver
# which would use to start the solution process
solve;
printf "Solution with warm start took %fs\n", _solve_time;
Output:
...
Solution without warm start took 2.89062s
...
Solution with warm start took 0.671875s
|
Feasibility Relaxation
The feasibility relaxation functionality enables the solver to find a feasible
solution even if the original model is unfeasible without explicitly adding
slack variables to the constraints.
In the feasibility relaxation problem,
Each variable \(x\) can violate its bounds (\(lb \leq x \leq ub\)):
Violation of lower bound \(lbv = max(0, lb-x)\)
Violation of upper bund \(ubv = max(0, x-ub)\)
Each constraint body \(c\) can violate its bounds also (\(c \leq rhs\))
The objective then becomes to minimize some function of the
violations (e.g. the number of violations, or their sum - possibly weighted by some
penalty values).
The penalty values (used in some kinds of feasibility relaxation problmes) can be
controlled with macro defaults (e.g. option alg:ubpen sets the penalty weight for
all upper buonds violations, and its default values is 1) or, with more granularity,
on each entity via suffix values (e.g. variable suffix ubpen on variables, default
value 0).
Penaly weights < 0 are treated as Infinity, allowing no violation.
Option |
alg:feasrelax
|
Applicability |
LP and MIP models |
Input |
Options
alg:lbpen: penalty for lower bound violations if suffix lbpen is not defined - default 1
alg:ubpen: penalty for upper bound violations if suffix ubpen is not defined - default 1
alg:rhspen: penalty for rhs violations if suffix rhspen is not defined - default 1
Suffixes
lbpen on variables - penalty for lower bound violations - default 0
ubpen on variables - penalty for upper bound violations - default 0
rhspen on constraints - penalty for rhs violations - default 0
|
Output |
None |
Values |
Sum of:
0 - No 1 - Yes, minimizing the weighted sum of violations 2 - Yes, minimizing the weighted sum of squared violations 3 - Yes, minimizing the weighted count of violations 3-6 - Same objective as 1-3, but also optimize the original objective, subject to the violation being minimized
|
Example |
Use this model
Solve the model changing the penalties to get different solutions:
options <solver>_options "alg:feasrelax=1";
option presolve 0; # otherwise the model could be oversimplified
solve; display x,y;
Gives:
Now we want to force all variable lower bounds to be respected:
options <solver>_options "alg:feasrelax=1 alg:lbpen=-1";
solve; display x,y;
Gives, as expected x=5 (it had a lower bound of 5):
Single violations can be controlled via suffixes; in this case we
want to control the constraints violations:
options <solver>_options "alg:feasrelax=1 alg:lbpen=1"; # allow lower bounds to be violated again
suffix rhspen IN;
let C1.rhspen := 1; # normal weight
let C2.rhspen := -1; # C2 can NOT be violated
let C3.rhspen := 10; # We'd rather not violate C3
solve;
display C1.slack, C2.slack, C3.slack;
Gives:
C1.slack = -3
C2.slack = 4
C3.slack = 0
C1 is violated - which makes sense as we specified that C2 cannot be violated
and we gave an higher avoidance weight to C2. If we want to violate C1 instead,
we can:
let C1.rhspen := 10; # We'd rather not violate C1
let C2.rhspen := 1; # C2 can be violated
let C3.rhspen := 1; # Normal weight
solve;
display C1.slack, C2.slack, C3.slack;
Which gives, as expected:
C1.slack = 18
C2.slack = 2
C3.slack = -1
|
Multiple solutions
More often than not, optimization problems have more than one optimal solution; moreover, during the
solution process, MIP solvers usually find sub-optimal solutions, which are normally discarded.
They can be however be kept, and in most cases there are solver-specific options to control how
the search for additional solutions is performed.
The main (and generic) options that controls the search are sol:stub amd sol:count, which
control respecitvely the base-name for the files where additional solution will be stored and
if to count additional solutions and return them in the nsol problem suffix.
Specifying a stub name automatically enables the solutions count; found solutions are written to
files [solutionstub1.sol', … solutionstub<nsol>.sol].
Option |
sol:stub
|
Applicability |
MIP models |
Input |
None |
Output |
Suffixes nsol and npool on problem |
Values |
The name used as base file name for the alternative solutions |
Example |
Use this model
Execute:
option gurobi_options "sol:stub=queentake";
solve;
printf "I have found %d solutions\n", Initial.nsol;
printf "Displaying solution 1";
solution queentake1.sol;
display X;
printf "Displaying solution 2";
solution queentake2.sol;
display X;
Output:
x-Gurobi 9.5.2: sol:stub=queentake
x-Gurobi 9.5.2: optimal solution; objective 10
355 simplex iterations
23 branching nodes
suffix nsol OUT;
suffix npool OUT;
I have found 10 solutions
Displaying solution 1
x-Gurobi 9.5.2: Alternative solution; objective 10
X [*,*]
: 1 2 3 4 5 6 7 8 9 10 :=
1 0 0 0 0 0 0 1 0 0 0
2 1 0 0 0 0 0 0 0 0 0
3 0 0 0 1 0 0 0 0 0 0
4 0 0 0 0 0 1 0 0 0 0
5 0 0 0 0 0 0 0 0 1 0
6 0 0 1 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 0 1
8 0 0 0 0 0 0 0 1 0 0
9 0 1 0 0 0 0 0 0 0 0
10 0 0 0 0 1 0 0 0 0 0;
Displaying solution 2
x-Gurobi 9.5.2: Alternative solution; objective 10
X [*,*]
: 1 2 3 4 5 6 7 8 9 10 :=
1 0 0 1 0 0 0 0 0 0 0
2 0 0 0 0 0 1 0 0 0 0
3 0 0 0 0 0 0 0 0 1 0
4 1 0 0 0 0 0 0 0 0 0
5 0 0 0 1 0 0 0 0 0 0
6 0 0 0 0 0 0 1 0 0 0
7 0 0 0 0 0 0 0 0 0 1
8 0 0 0 0 0 0 0 1 0 0
9 0 1 0 0 0 0 0 0 0 0
10 0 0 0 0 1 0 0 0 0 0
|
Sensitivity analysis
It is often useful to know the ranges of variables and constraint bodies for which the optimal basis
remains optimal. Solvers supporting this feature return such ranges in suffixes after solving to optimum.
This option controls whether to calculate these values and return them in the suffixes listed below.
Option |
alg:sens
|
Applicability |
LP and MIP models |
Input |
None |
Output |
Suffixes for variables only:
Suffixes for variables and constraints:
senslblo smallest variable/constraint lower bound
senslbhi greatest lower bound
sensublo smallest upper bound
sensubhi greatest upper bound
|
Values |
Sum of:
|
Example |
Use Multi objective diet model
Execute:
options <solver>_options "alg:sens=1";
option presolve 0; # disable model transformations in AMPL
solve;
Then the ranges for variables and constraints can be examined:
display Buy, Buy.sstatus, Buy.sensublo, Buy.sensubhi;
Which gives:
display Buy.sensublo, Buy.sensubhi, Buy.sstatus, Buy;
: Buy.sensublo Buy.sensubhi Buy.sstatus Buy :=
BEEF 2 1e+100 low 2
CHK 9.12987 10.9792 upp 10
FISH 2 1e+100 low 2
HAM 2 1e+100 low 2
MCH 2 1e+100 low 2
MTL 6.23596 1e+100 bas 6.23596
SPG 5.25843 1e+100 bas 5.25843
TUR 2 1e+100 low 2;
|
Kappa
Kappa is the condition number for the current LP basis matrix.
It is a measure of the stability of the current solution \(Ax=b\)
measuring the rate at which the solution \(x\) will change with respect to a
change in \(b\).
It is only available for basic solutions, therefore it is not available for barrier method
if crossover is not applied.
Option |
alg:kappa
|
Applicability |
LP and MIP models with optimal basis |
Input |
None |
Output |
Additional text in solve_message and suffix:
|
Values |
Sum of:
|
Example |
Use Multi objective diet model
Solve the model and report kappa:
options <solver>_options "alg:kappa=3";
solve;
display Initial.kappa, total_number.kappa;
Gives:
x-Gurobi 9.5.2: optimal solution; objective 30.92537313
kappa value: 53.5399
5 simplex iterations
suffix kappa OUT;
Initial.kappa = 53.5399
total_number.kappa = 53.5399
|
Unbounded rays
When a model is unbounded, a vector \(r\) (unbounded ray) can be found such that
when added to any feasible solution \(x\), the resulting vector is a feasible solution
with an improved objective value.
When a model is infeasible, the dual solution is unbounded and the same as above can be applied
to constraints.
This option controls whether to return suffix unbdd if the objective is unbounded
or suffix dunbdd if the constraints are infeasible.
Option |
alg:rays
|
Applicability |
Unbounded/unfeasible LP and MIP linear models |
Input |
None |
Output |
Suffixes:
|
Values |
Sum of:
|
Example |
Use this model
Solve the (infeasible) model and report the dunbdd rays:
options gurobi_options "alg:rays=3"; # it is default already
option presolve 0; # else the model could be oversimplified
solve;
display c1.dunbdd, c2.dunbdd, c3.dunbdd;
Output:
x-Gurobi 9.5.2: alg:rays=3
x-Gurobi 9.5.2: infeasible problem
suffix dunbdd OUT;
c1.dunbdd = 1
c2.dunbdd = 0
c3.dunbdd = 0
|
Multiple objectives
Many real world problems have multiple objectives; often this scenario is tackled by blending all the objectives
by linear combination when formulating the model, or by minimizing each unwanted objective deviations from a pre-specified
goal.
Many solvers can facilitate the formulation; the available functionalities are solver-specific; at MP level
they accessible via the main option obj:multi. Consult the solver documentation for the functionalities available
on your solver.
Option |
obj:multi
|
Applicability |
LP and MIP models |
Input |
None |
Output |
All objectives are reported in solve_message |
Values |
Values:
|
Example |
Use Multi objective diet model
Execute:
options <solver>_options "obj:multi=1";
solve;
Output:
x-Gurobi 9.5.1: obj:multi=1
x-Gurobi 9.5.1: optimal solution; objective 74.27382022
Individual objective values:
_sobj[1] = 74.27382022
_sobj[2] = 75.01966292
_sobj[3] = 79.59719101
_sobj[4] = 31.49438202
|
Irreducible Inconsistent Subset (IIS)
Given an infeasible model, it is useful to know where the infeasibility comes from, that is, which
bounds and/or constraints are incompatible.
An IIS is a subset of constraints and variables that is still infeasible and where if a member is removed
the subsystem becaomes feasible. Note that an infeasible model can have more than one IIS.
This options controls whether to perform the additional computational steps required to find an IIS.
Option |
alg:iisfind, iisfind, iis
|
Applicability |
LP and MIP models |
Input |
None |
Output |
Suffix iis on variables and constraints |
Values |
Values:
|
Example |
Use this model
Execute:
option <solver>_options "iisfind=1";
option presolve 0; # else the model could be oversimplified
solve;
display c1.iis, c2.iis, c3.iis;
Output:
x-Gurobi 9.5.2: alg:iisfind=1
x-Gurobi 9.5.2: infeasible problem
2 simplex iterations
suffix iis symbolic OUT;
suffix dunbdd OUT;
c1.iis = mem
c2.iis = mem
c3.iis = mem
|
MIP-only features
Return MIP gap
The MIP gap describes how far the reported solution for the MIP model is from the
best bound found. It is defined as:
\(absgap = | objective - bestbound |\)
\(relmipgap = absgap / | objective |\)
It gives a measure of how far the current solution is from the
theoretical optimum.
The AMPL option controls whether to return mipgap suffixes or include mipgap values
in the solve_message. Returned suffix values are +Infinity if no integer-feasible
solution has been found, in which case no mipgap values are reported in the solve_message.
Option |
mip:return_gap
|
Applicability |
MIP models |
Input |
None |
Output |
Additional text in solve_message and suffixes:
|
Values |
Sum of:
0 - Do not report gaps 1 - Return .relmipgap suffix (relative to |obj|) 2 - Return .absmipgap suffix (absolute mipgap) 4 - Suppress mipgap values in solve_message
|
Example |
Use this model
Execute:
# 3 = return both absolute and relative MIP gap, and also report them
# in the solve_message
option <solver>_options "return_mipgap=3";
solve;
display max_queens.relmipgap, max_queens.absmipgap;
display Initial.relmipgap, Initial.absmipgap;
Output:
x-Gurobi 9.5.2: mip:return_gap=3
x-Gurobi 9.5.2: optimal solution; objective 10
suffix absmipgap OUT;
max_queens.relmipgap = 0
max_queens.absmipgap = 0
Initial.relmipgap = 0
Initial.absmipgap = 0
|
Return best dual bound
The best dual bound (on the objective) represents what is the currently
proven best value that the objective value can assume. Usually solvers terminate
when the current solution is close enough to the best bound.
This option controls whether to return suffix .bestbound for the best known MIP dual
bound on the objective value. The returned value is -Infinity for minimization
problems and +Infinity for maximization problems if there are no integer
variables or if a dual bound is not available.
Option |
mip:bestbound
|
Applicability |
MIP models |
Input |
None |
Output |
Suffix:
|
Values |
Sum of:
|
Example |
Use this model
Execute:
option <solver>_options "mip:bestbound=3";
solve;
display max_queens.bestbound, Initial.bestbound;
Output:
x-Gurobi 9.5.2: mip:bestbound=1
x-Gurobi 9.5.2: optimal solution; objective 10
max_queens.bestbound = 10
Initial.bestbound = 10
|
Lazy constraints and user cuts
The solution process of a MIP model can be helped by further specifying its structure.
Specifically, constraints can be marked as lazy or as user cuts.
Such constraints are not included initially, then:
Lazy constraints are pulled in when a feasible solution is found; if the solution violates
them, it is cut off. They are integral part of the model, as they can cut off integer-feasible
solutions.
User cuts are pulled in also, but they can only cut off relaxation solutions; they are
consider redundant in terms of specifying integer feasibility.
This option controls whether to recognize the suffx lazy on constraints, which should then be
positive to denote a lazy constraint and negative to mark a contraint as a user cut.
Option |
mip:lazy
|
Applicability |
MIP models |
Input |
Suffix:
|
Output |
None |
Values |
Sum of:
0 - No 1 - Accept >0 values to denote lazy constraints 2 - Accept <0 values to denote user cuts 3 - Accept both (default)
|
Example |
Following ampl model
end of code block
option presolve 0; # disable model transformations in AMPL
suffix lazy IN;
let c1.lazy := 1; # lazy constraint
let c2.lazy := -1; # user cut, must be redundant as it might never be pulled in
solve;
# TODO SHOW OUTPUT
|
Variable priorities
Solution of MIP models via branch and bound can often be helped by providing
preferences on which variables to branch on. Those can be specified in AMPL via the suffix
priority.
This option controls whether to read those values and use them in the solution process.
Option |
mip:priorities
|
Applicability |
MIP models |
Input |
Suffix:
|
Output |
None |
Values |
Values:
|
Example |
Following AMPL model
end of code block
option presolve 0; # disable model transformations in AMPL
let x.priority := 1;
let y.priority := 5;
solve;
# TODO SHOW OUTPUT
|
Fixed model (return basis for MIP)
At the end of the solution process for a MIP model, a continuous relaxation of the model
with all the integer variables fixed at their integer-optimum value. Some continuous variables
can also be fixed to satisfy SOS or general constraints.
The model can therefore be solved without these types of restrictions to calculate a basis,
dual values or sensitivity information that wouldn’t normally be available for MIP problems.
This option controls if to generate and solve the fixed model after solving the integer problem.
Option |
mip:basis
|
Applicability |
MIP models |
Input |
None |
Output |
Suffixes:
|
Values |
Values
|
Example |
Following ampl model
end of code block
option <solver>_options "mip:basis=1";
# TODO SHOW OUTPUT
|