13.4 The Optimizer for Mixedinteger Problems¶
A problem is a mixedinteger optimization problem when one or more of the variables are constrained to be integer valued. Readers unfamiliar with integer optimization are recommended to consult some relevant literature, e.g. the book [Wol98] by Wolsey.
13.4.1 The Mixedinteger Optimizer Overview¶
MOSEK can solve mixedinteger linear and conic problems, except for mixedinteger semidefinite problems.
By default the mixedinteger optimizer is runtorun deterministic. This means that if a problem is solved twice on the same computer with identical parameter settings and no time limit then the obtained solutions will be identical. If a time limit is set then this may not be case since the time taken to solve a problem is not deterministic. The mixedinteger optimizer is parallelized i.e. it can exploit multiple cores during the optimization.
The solution process can be split into these phases:
Presolve: See Sec. 13.1 (Presolve).
Cut generation: Valid inequalities (cuts) are added to improve the lower bound.
Heuristic: Using heuristics the optimizer tries to guess a good feasible solution. Heuristics can be controlled by the parameter
mioHeuristicLevel
.Search: The optimal solution is located by branching on integer variables.
13.4.2 Relaxations and bounds¶
It is important to understand that, in a worstcase scenario, the time required to solve integer optimization problems grows exponentially with the size of the problem (solving mixedinteger problems is NPhard). For instance, a problem with \(n\) binary variables, may require time proportional to \(2^n\) . The value of \(2^n\) is huge even for moderate values of \(n\).
In practice this implies that the focus should be on computing a nearoptimal solution quickly rather than on locating an optimal solution. Even if the problem is only solved approximately, it is important to know how far the approximate solution is from an optimal one. In order to say something about the quality of an approximate solution the concept of relaxation is important.
Consider for example a mixedinteger optimization problem
It has the continuous relaxation
obtained simply by ignoring the integrality restrictions. The relaxation is a continuous problem, and therefore much faster to solve to optimality with a linear (or, in the general case, conic) optimizer. We call the optimal value \(\underline{z}\) the objective bound. The objective bound \(\underline{z}\) normally increases during the solution search process when the continuous relaxation is gradually refined.
Moreover, if \(\hat{x}\) is any feasible solution to (13.12) and
then
These two inequalities allow us to estimate the quality of the integer solution: it is no further away from the optimum than \(\bar{z} \underline{z}\) in terms of the objective value. Whenever a mixedinteger problem is solved MOSEK reports this lower bound so that the quality of the reported solution can be evaluated.
13.4.3 Outer approximation for mixedinteger conic problems¶
The relaxations of mixed integer conic problems can be solved either as a nonlinear problem with the interior point algorithm (default) or with a linear outer approximation algorithm. The type of relaxation used can be set with mioConicOuterApproximation
. The best value for this option is highly problem dependent.
13.4.4 Randomization¶
A number of internal algorithms of the mixedinteger solver are dependend on random tiebreaking. The random tiebreaking can have a significant impact on the path taken by the algorithm and the optimal solution returned. The random seed can be set with the parameter
mioSeed
.
13.4.5 Termination Criterion¶
In general, it is time consuming to find an exact feasible and optimal solution to an integer optimization problem, though in many practical cases it may be possible to find a sufficiently good solution. The issue of terminating the mixedinteger optimizer is rather delicate and the user has numerous possibilities of influencing it with various parameters. The mixedinteger optimizer employs a relaxed feasibility and optimality criterion to determine when a satisfactory solution is located.
A candidate solution that is feasible for the continuous relaxation is said to be an integer feasible solution if the criterion
is satisfied, meaning that \(x_j\) is at most \(\delta_1\) from the nearest integer.
Whenever the integer optimizer locates an integer feasible solution it will check if the criterion
is satisfied. If this is the case, the integer optimizer terminates and reports the integer feasible solution as an optimal solution.
All the \(\delta\) tolerances discussed above can be adjusted using suitable parameters — see Table 13.3.
Tolerance 
Parameter name 

\(\delta_1\) 

\(\delta_2\) 

\(\delta_3\) 

\(\delta_4\) 
In Table 13.4 some other common parameters affecting the integer optimizer termination criterion are shown.
Parameter name 
Explanation 

Maximum number of branches allowed. 

Maximum number of relaxations allowed. 

Maximum number of feasible integer solutions allowed. 
13.4.6 Speeding Up the Solution Process¶
As mentioned previously, in many cases it is not possible to find an optimal solution to an integer optimization problem in a reasonable amount of time. Some suggestions to reduce the solution time are:
Relax the termination criterion: In case the run time is not acceptable, the first thing to do is to relax the termination criterion — see Sec. 13.4.5 (Termination Criterion) for details.
Specify a good initial solution: In many cases a good feasible solution is either known or easily computed using problemspecific knowledge. If a good feasible solution is known, it is usually worthwhile to use this as a starting point for the integer optimizer. See Sec. 7.6.2 (Specifying an initial solution).
Improve the formulation: A mixedinteger optimization problem may be impossible to solve in one form and quite easy in another form. However, it is beyond the scope of this manual to discuss good formulations for mixedinteger problems. For discussions on this topic see for example [Wol98].
13.4.7 Understanding Solution Quality¶
To determine the quality of the solution one should check the following:
The problem status and solution status returned by MOSEK, as well as constraint violations in case of suboptimal solutions.
The optimality gap defined as
\[\epsilon= \mbox{(objective value of feasible solution)}\mbox{(objective bound)} = \bar{z}\underline{z}.\]which measures how much the located solution can deviate from the optimal solution to the problem. The optimality gap can be retrieved through the information item
"mioObjAbsGap"
. Often it is more meaningful to look at the relative optimality gap normalized against the magnitude of the solution.\[\epsilon_{\textrm{rel}} = \frac{\bar{z}\underline{z}}{\max(\delta_4, \bar{z})}.\]The relative optimality gap is available in the information item
"mioObjRelGap"
.
13.4.8 The Mixedinteger Log¶
Below is a typical log output from the mixedinteger optimizer:
Presolved problem: 6573 variables, 35728 constraints, 101258 nonzeros
Presolved problem: 0 general integer, 4294 binary, 2279 continuous
Clique table size: 1636
BRANCHES RELAXS ACT_NDS DEPTH BEST_INT_OBJ BEST_RELAX_OBJ REL_GAP(%) TIME
0 1 0 0 NA 1.8218819866e+07 NA 1.6
0 1 0 0 1.8331557950e+07 1.8218819866e+07 0.61 3.5
0 1 0 0 1.8300507546e+07 1.8218819866e+07 0.45 4.3
Cut generation started.
0 2 0 0 1.8300507546e+07 1.8218819866e+07 0.45 5.3
Cut generation terminated. Time = 1.43
0 3 0 0 1.8286893047e+07 1.8231580587e+07 0.30 7.5
15 18 1 0 1.8286893047e+07 1.8231580587e+07 0.30 10.5
31 34 1 0 1.8286893047e+07 1.8231580587e+07 0.30 11.1
51 54 1 0 1.8286893047e+07 1.8231580587e+07 0.30 11.6
91 94 1 0 1.8286893047e+07 1.8231580587e+07 0.30 12.4
171 174 1 0 1.8286893047e+07 1.8231580587e+07 0.30 14.3
331 334 1 0 1.8286893047e+07 1.8231580587e+07 0.30 17.9
[ ... ]
Objective of best integer solution : 1.825846762609e+07
Best objective bound : 1.823311032986e+07
Construct solution objective : Not employed
Construct solution # roundings : 0
User objective cut value : 0
Number of cuts generated : 117
Number of Gomory cuts : 108
Number of CMIR cuts : 9
Number of branches : 4425
Number of relaxations solved : 4410
Number of interior point iterations: 25
Number of simplex iterations : 221131
The first lines contain a summary of the problem as seen by the optimizer. This is followed by the iteration log. The columns have the following meaning:
BRANCHES
: Number of branches generated.RELAXS
: Number of relaxations solved.ACT_NDS
: Number of active branch bound nodes.DEPTH
: Depth of the recently solved node.BEST_INT_OBJ
: The best integer objective value, \(\bar{z}\).BEST_RELAX_OBJ
: The best objective bound, \(\underline{z}\).REL_GAP(%)
: Relative optimality gap, \(100\%\cdot\epsilon_{\textrm{rel}}\)TIME
: Time (in seconds) from the start of optimization.
Following that a summary of the optimization process is printed.