# 13.4 The Optimizer for Mixed-integer Problems¶

A problem is a mixed-integer 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 Mixed-integer Optimizer Overview¶

MOSEK can solve mixed-integer

• linear,
• conic

problems, except for mixed-integer semidefinite problems. The mixed-integer optimizer is specialized for solving linear and conic optimization problems. Pure quadratic and quadratically constrained problems are automatically converted to conic form.

By default the mixed-integer optimizer is run-to-run 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 mixed-integer optimizer is parallelized i.e. it can exploit multiple cores during the optimization.

The solution process can be split into these phases:

1. Presolve: See Sec. 13.1 (Presolve).
2. Cut generation: Valid inequalities (cuts) are added to improve the lower bound.
3. Heuristic: Using heuristics the optimizer tries to guess a good feasible solution. Heuristics can be controlled by the parameter iparam.mio_heuristic_level.
4. 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 worst-case scenario, the time required to solve integer optimization problems grows exponentially with the size of the problem (solving mixed-integer problems is NP-hard). 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 near-optimal 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 mixed-integer optimization problem

(13.12)$\begin{split}\begin{array}{rccccl} z^* & = & \mbox{minimize} & c^T x & & \\ & & \mbox{subject to} & A x & = & b, \\ & & & x \geq 0 & & \\ & & & x_j \in \integral, & & \forall j \in \mathcal{J}. \end{array}\end{split}$

It has the continuous relaxation

(13.13)$\begin{split}\begin{array}{rclcccl} \underline{z} & = & \mbox{minimize} & c^T x & & \\ & & \mbox{subject to} & A x & = & b,\\ & & & x \geq 0 & & \end{array}\end{split}$

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

$\bar{z} := c^T \hat{x}$

then

$\underline{z} \leq z^* \leq \bar{z}.$

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 mixed-integer 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 mixed-integer 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 iparam.mio_conic_outer_approximation. The best value for this option is highly problem dependent.

## 13.4.4 Randomization¶

A number of internal algorithms of the mixed-integer solver are dependend on random tie-breaking. The random tie-breaking 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 iparam.mio_seed.

## 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 mixed-integer optimizer is rather delicate and the user has numerous possibilities of influencing it with various parameters. The mixed-integer 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

$\min (x_j-\lfloor x_j \rfloor,\lceil x_j \rceil - x_j) \leq \delta_1 \quad \forall j \in \mathcal{J}$

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

$\bar{z} - \underline{z} \leq \max (\delta_2, \delta_3 \max (\delta_4,|\bar{z}|))$

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.

Table 13.3 Tolerances for the mixed-integer optimizer.
Tolerance Parameter name
$$\delta_1$$ dparam.mio_tol_abs_relax_int
$$\delta_2$$ dparam.mio_tol_abs_gap
$$\delta_3$$ dparam.mio_tol_rel_gap
$$\delta_4$$ dparam.mio_rel_gap_const

In Table 13.4 some other common parameters affecting the integer optimizer termination criterion are shown.

Table 13.4 Other parameters affecting the integer optimizer termination criterion.
Parameter name Explanation
iparam.mio_max_num_branches Maximum number of branches allowed.
iparam.mio_max_num_relaxs Maximum number of relaxations allowed.
iparam.mio_max_num_solutions 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 problem-specific 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. 6.7.2 (Specifying an initial solution).
• Improve the formulation: A mixed-integer 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 mixed-integer 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 dinfitem.mio_obj_abs_gap. 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 dinfitem.mio_obj_rel_gap.

## 13.4.8 The Mixed-integer Log¶

Below is a typical log output from the mixed-integer optimizer:

Presolved problem: 6573 variables, 35728 constraints, 101258 non-zeros
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.