In order to say something about the quality of an approximate solution the concept of relaxation is important.Ĭonsider for example a mixed-integer optimization problem Even if the problem is only solved approximately, it is important to know how far the approximate solution is from an optimal one.
In practice this implies that the focus should be on computing a near-optimal solution quickly rather than on locating an optimal solution. The value of \(2^n\) is huge even for moderate values of \(n\). For instance, a problem with \(n\) binary variables, may require time proportional to \(2^n\). 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). Search: The optimal solution is located by branching on integer variables. Heuristics can be controlled by the parameter MSK_IPAR_MIO_HEURISTIC_LEVEL. Heuristic: Using heuristics the optimizer tries to guess a good feasible solution. The solution process can be split into these phases:Ĭut generation: Valid inequalities (cuts) are added to improve the lower bound. it can exploit multiple cores during the optimization. The mixed-integer optimizer is parallelized i.e. If a time limit is set then this may not be case since the time taken to solve a problem is not 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. Pure quadratic and quadratically constrained problems are automatically converted to conic form.īy default the mixed-integer optimizer is run-to-run deterministic. The mixed-integer optimizer is specialized for solving linear and conic optimization problems.
Problems, except for mixed-integer semidefinite problems. Quadratic and quadratically constrained, and 13.4.1 The Mixed-integer Optimizer Overview ¶ Readers unfamiliar with integer optimization are recommended to consult some relevant literature, e.g. 13.4 The Optimizer for Mixed-integer Problems ¶Ī problem is a mixed-integer optimization problem when one or more of the variables are constrained to be integer valued.