13.6 Basis Identification

An interior-point optimizer does not return an optimal basic solution unless the problem has a unique primal and dual optimal solution. Therefore, the interior-point optimizer has an optional post-processing step that computes an optimal basic solution starting from the optimal interior-point solution. More information about the basis identification procedure may be found in [AY96]. In the following we provide an overall idea of the procedure.

There are some cases in which a basic solution could be more valuable:

• a basic solution is often more accurate than an interior-point solution,

• a basic solution can be used to warm-start the simplex algorithm in case of reoptimization,

• a basic solution is in general more sparse, i.e. more variables are fixed to zero. This is particularly appealing when solving continuous relaxations of mixed integer problems, as well as in all applications in which sparser solutions are preferred.

To illustrate how the basis identification routine works, we use the following trivial example:

\[\begin{split}\begin{array}{lcll} \mbox{minimize} & x + y & & \\ \mbox{subject to} & x + y & = & 1, \\ & x,y\geq 0. & & \end{array}\end{split}\]

It is easy to see that all feasible solutions are also optimal. In particular, there are two basic solutions, namely

\[\begin{split}\begin{array}{lcll} (x_1^*,y_1^*) & = & (1,0), & \\ (x_2^*,y_2^*) & = & (0,1). & \end{array}\end{split}\]

The interior point algorithm will actually converge to the center of the optimal set, i.e. to \((x^*,y^*)=(1/2,1/2)\) (to see this in MOSEK deactivate presolve).

In practice, when the algorithm gets close to the optimal solution, it is possible to construct in polynomial time an initial basis for the simplex algorithm from the current interior point solution. This basis is used to warm-start the simplex algorithm that will provide the optimal basic solution. In most cases the constructed basis is optimal, or very few iterations are required by the simplex algorithm to make it optimal and hence the final clean-up phase be short. However, for some cases of ill-conditioned problems the additional simplex clean up phase may take of lot a time.

By default MOSEK performs a basis identification. However, if a basic solution is not needed, the basis identification procedure can be turned off. The parameter iparam.intpnt_basis controls when basis identification is performed.

Finally, it should be mentioned that there is no guarantee on which basic solution will be returned.