12. 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 integers. The integer optimizer available in MOSEK can solve integer optimization problems involving

constraints. However, a problem is not allowed to have both conic constraints and quadratic objective or constraints.

Readers unfamiliar with integer optimization are strongly recommended to consult some relevant literature, e.g. the book [18] by Wolsey is a good introduction to integer optimization.

12.1. Some notation

In general, an integer optimization problem has the form

\begin{math}\nonumber{}\begin{array}{rclccccl}\nonumber{}z^{*} & = & \mbox{minimize} &  &  & c^{T}x &  & \\\nonumber{} &  & \mbox{subject to} & l^{c} & \leq{} & Ax & \leq{} & u^{c},\\\nonumber{} &  &  & l^{x} & \leq{} & x & \leq{} & u^{x},\\\nonumber{} &  &  &  &  & x_{j}\in{}\mathcal{Z}, &  & \forall j\in{}\mathcal{J},\end{array}\end{math} (12.1.1)

where [[MathCmd 174]] is an index set specifying which variables are integer-constrained. Frequently we talk about the continuous relaxation of an integer optimization problem defined as

\begin{math}\nonumber{}\begin{array}{rclccccl}\nonumber{}\underline{z} & = & \mbox{minimize} &  &  & c^{T}x &  & \\\nonumber{} &  & \mbox{subject to} & l^{c} & \leq{} & Ax & \leq{} & u^{c},\\\nonumber{} &  &  & l^{x} & \leq{} & x & \leq{} & u^{x}\end{array}\end{math} (12.1.2)

i.e. we ignore the constraint

\begin{displaymath}\nonumber{}x_{j}\in{}\mathcal{Z},~\forall j\in{}\mathcal{J}.\end{displaymath}

Moreover, let [[MathCmd 715]] be any feasible solution to (12.1.1) and define

\begin{displaymath}\nonumber{}\overline{z}:=c^{T}\hat{x}.\end{displaymath}

It should be obvious that

\begin{displaymath}\nonumber{}\underline{z}\leq{}z^{*}\leq{}\overline{z}\end{displaymath}

holds. This is an important observation since if we assume that it is not possible to solve the mixed-integer optimization problem within a reasonable time frame, but that a feasible solution can be found, then the natural question is: How far is the obtained solution from the optimal solution? The answer is that no feasible solution can have an objective value smaller than [[MathCmd 718]], which implies that the obtained solution is no further away from the optimum than [[MathCmd 719]].

12.2. An important fact about integer optimization problems

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. For instance, assume that a problem contains n binary variables, then the time required to solve the problem in the worst case may be proportional to [[MathCmd 720]]. It is a simple exercise to verify that [[MathCmd 720]] 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 at locating an optimal solution.

12.3. How the integer optimizer works

The process of solving an integer optimization problem can be split in three phases:

Presolve:

In this phase the optimizer tries to reduce the size of the problem using preprocessing techniques. Moreover, it strengthens the continuous relaxation, if possible.

Heuristic:

Using heuristics the optimizer tries to guess a good feasible solution.

Optimization:

The optimal solution is located using a variant of the branch-and-cut method.

In some cases the integer optimizer may locate an optimal solution in the preprocessing stage or conclude that the problem is infeasible. Therefore, the heuristic and optimization stages may never be performed.

12.3.1. Presolve

In the preprocessing stage redundant variables and constraints are removed. The presolve stage can be turned off using the MSK_IPAR_MIO_PRESOLVE_USE parameter.

12.3.2. Heuristic

Initially, the integer optimizer tries to guess a good feasible solution using different heuristics:

  • First a very simple rounding heuristic is employed.
  • Next, if deemed worthwhile, the feasibility pump heuristic is used.
  • Finally, if the two previous stages did not produce a good initial solution, more sophisticated heuristics are used.

The following parameters can be used to control the effort made by the integer optimizer to find an initial feasible solution.

12.3.3. The optimization phase

This phase solves the problem using the branch and cut algorithm.

12.4. Termination criterion

In general, it is impossible to find an exact feasible and optimal solution to an integer optimization problem in a reasonable amount of time, though in many practical cases it may be possible. Therefore, the integer optimizer employs a relaxed feasibility and optimality criterion to determine when a satisfactory solution is located.

A candidate solution, i.e. a solution to (12.1.2), is said to be an integer feasible solution if the criterion

\begin{displaymath}\nonumber{}\min (|x_{j}|-\lfloor x_{j}\rfloor ,\lceil x_{j}\rceil -|x_{j}|)\leq{}\max (\delta _{1},\delta _{2}|x_{j}|)~\forall j\in{}\mathcal{J}\end{displaymath}

is satisfied. Hence, such a solution is defined as a feasible solution to (12.1.1).

Whenever the integer optimizer locates an integer feasible solution it will check if the criterion

\begin{displaymath}\nonumber{}\overline{z}-\underline{z}\leq{}\max (\delta _{3},\delta _{4}\max (1,\left|\overline{z}\right|))\end{displaymath}

is satisfied. If this is the case, the integer optimizer terminates and reports the integer feasible solution as an optimal solution. Please note that [[MathCmd 718]] is a valid lower bound determined by the integer optimizer during the solution process, i.e.

\begin{displaymath}\nonumber{}\underline{z}\leq{}z^{*}.\end{displaymath}

The lower bound [[MathCmd 718]] normally increases during the solution process.

The [[MathCmd 727]] tolerances can are specified using parameters — see Table 12.1.

Table 12.1: Integer optimizer tolerances.

If an optimal solution cannot be located within a reasonable time, it may be advantageous to employ a relaxed termination criterion after some time. Whenever the integer optimizer locates an integer feasible solution and has spent at least the number of seconds defined by the MSK_DPAR_MIO_DISABLE_TERM_TIME parameter on solving the problem, it will check whether the criterion

\begin{displaymath}\nonumber{}\overline{z}-\underline{z}\leq{}\max (\delta _{5},\delta _{6}\max (1,\left|\overline{z}\right|))\end{displaymath}

is satisfied. If it is satisfied, the optimizer will report that the candidate solution is near optimal and then terminate. All [[MathCmd 727]] tolerances can be adjusted using suitable parameters — see Table 12.1.

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.
Table 12.2: Parameters affecting the termination of the integer optimizer.

In Table 12.2 some other 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.

12.5. How to speed 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:

12.6. Understanding solution quality

To determine the quality of the solution one should check the following:

The optimality gap is a measure for how close the solution is to the optimal solution. The optimality gap is given by

\begin{displaymath}\nonumber{}\epsilon =|\mbox{(objective value of feasible solution)}-\mbox{(objective bound)}|.\end{displaymath}

The objective value of the solution is guarentted to be within [[MathCmd 737]] of the optimal solution.

The optimality gap can be retrived through the solution item MSK_DINF_MIO_OBJ_ABS_GAP. Often it is more meaningful to look at the optimality gap normalized with the magnitude of the solution. The relative optimality gap is available in MSK_DINF_MIO_OBJ_REL_GAP.

12.6.1. Solutionsummary

After a call to the optimizer the solution summary might look like this:

Problem status  : PRIMAL_FEASIBLE
Solution status : INTEGER_OPTIMAL
Primal - objective: 1.2015000000e+06   eq. infeas.: 0.00e+00 max bound infeas.: 0.00e+00
cone infeas.: 0.00e+00 integer infeas.: 0.00e+00

The second line contains the solution status key. This shows how MOSEK classified the solution. In this case it is [[MathCmd 738]], meaning that the solution is considered to be optimal within the selected tolerances.

The third line contains information relating to the solution. The first number is the primal objective function. The second and third number is the maximum infeasibility in the equality constraints and bounds respectfully. The fourth and fifth number is the maximum infeasibility in the conic and integral contraints. All the numbers relating to the feasibility of the solution should be small for the solution to be valid.

Wed Feb 29 16:16:55 2012