# 9 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.

## 9.1 The Mixed-integer Optimizer Overview¶

**MOSEK** can solve mixed-integer

- linear,
- quadratic and quadratically constrained, and
- conic quadratic

problems, at least as long as they do not contain both quadratic objective or constraints and conic constraints at the same time. 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:

**Presolve:**See Sec. 8.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`MSK_IPAR_MIO_HEURISTIC_LEVEL`

.**Search:**The optimal solution is located by branching on integer variables.

## 9.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

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 (1) 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 mixed-integer problem is solved **MOSEK** reports this lower bound so that the quality of the reported solution can be evaluated.

## 9.3 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

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. If an optimal solution cannot be located after the time specified by the parameter `MSK_DPAR_MIO_DISABLE_TERM_TIME`

(in seconds), it may be advantageous to relax the termination criteria, and they become replaced with

Any solution satisfying those will now be reported as **near optimal** and the solver will be terminated (note that since this criterion depends on timing, the optimizer will not be run to run deterministic).

All the \(\delta\) tolerances discussed above can be adjusted using suitable parameters — see Table 6.

Tolerance | Parameter name |
---|---|

\(\delta_1\) | `MSK_DPAR_MIO_TOL_ABS_RELAX_INT` |

\(\delta_2\) | `MSK_DPAR_MIO_TOL_ABS_GAP` |

\(\delta_3\) | `MSK_DPAR_MIO_TOL_REL_GAP` |

\(\delta_4\) | `MSK_DPAR_MIO_NEAR_TOL_ABS_GAP` |

\(\delta_5\) | `MSK_DPAR_MIO_NEAR_TOL_REL_GAP` |

In Table 7 some other common parameters affecting the integer optimizer termination criterion are shown. Please note that if the effect of a parameter is delayed, the associated termination criterion is applied only after some time, specified by the `MSK_DPAR_MIO_DISABLE_TERM_TIME`

parameter.

Parameter name | Delayed | Explanation |
---|---|---|

`MSK_IPAR_MIO_MAX_NUM_BRANCHES` |
Yes | Maximum number of branches allowed. |

`MSK_IPAR_MIO_MAX_NUM_RELAXS` |
Yes | Maximum number of relaxations allowed. |

`MSK_IPAR_MIO_MAX_NUM_SOLUTIONS` |
Yes | Maximum number of feasible integer solutions allowed. |

## 9.4 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. 9.3 (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.
- 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].

## 9.5 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

`MSK_DINF_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(10^{-10}, |\bar{z}|)}.\]The relative optimality gap is available in

`MSK_DINF_MIO_OBJ_REL_GAP`

.

## 9.6 The Optimizer 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.