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 [17] by Wolsey is a good introduction to integer optimization.
In general, an integer optimization problem has the form
![]() |
(9.1.1) |
where is an index set specifying which variables are integer-constrained. Frequently we talk about the continuous relaxation of an integer optimization problem defined as
![]() |
(9.1.2) |
i.e. we ignore the constraint
![]() |
Moreover, let be any feasible solution to (9.1.1) and define
![]() |
It should be obvious that
![]() |
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 , which implies that the obtained solution is no further away from the optimum than
.
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 . It is a simple exercise to verify that
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.
The process of solving an integer optimization problem can be split in three phases:
In this phase the optimizer tries to reduce the size of the problem using preprocessing techniques. Moreover, it strengthens the continuous relaxation, if possible.
Using heuristics the optimizer tries to guess a good feasible solution.
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.
In the preprocessing stage redundant variables and constraints are removed. The presolve stage can be turned off using the Env.iparam.mio_presolve_use parameter.
Initially, the integer optimizer tries to guess a good feasible solution using different heuristics:
The following parameters can be used to control the effort made by the integer optimizer to find an initial feasible solution.
This phase solves the problem using the branch and cut algorithm.
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 (9.1.2), is said to be an integer feasible solution if the criterion
![]() |
is satisfied. Hence, such a solution is defined as a feasible solution to (9.1.1).
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. Please note that is a valid lower bound determined by the integer optimizer during the solution process, i.e.
![]() |
The lower bound normally increases during the solution process.
The tolerances can are specified using parameters — see Table 9.1.
|
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 Env.dparam.mio_disable_term_time parameter on solving the problem, it will check whether the criterion
![]() |
is satisfied. If it is satisfied, the optimizer will report that the candidate solution is near optimal and then terminate. All tolerances can be adjusted using suitable parameters — see Table 9.1.
|
In Table 9.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 Env.dparam.mio_disable_term_time parameter.
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:
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
![]() |
The objective value of the solution is guarentted to be within of the optimal solution.
The optimality gap can be retrived through the solution item Env.dinfitem.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 Env.dinfitem.mio_obj_rel_gap.
The function Task.solutionsummary prints the most important solution information to the screen.
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 , 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.
Information about the solution quality may be retrieved in the API with the help of the following functions: