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:

  1. Presolve: See Sec. 8.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 MSK_IPAR_MIO_HEURISTIC_LEVEL.
  4. 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

(1)\[\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

(2)\[\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 (1) 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.

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

\[\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 (10^{-10},|\bar{z}|))\]

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

\[\bar{z} - \underline{z} \leq \max (\delta_4,\delta_5 \max (10^{-10},|\bar{z}|)).\]

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.

Table 6 Tolerances for the mixed-integer optimizer.
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.

Table 7 Other parameters affecting the integer optimizer termination criterion.
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.