## Wednesday, April 20, 2011

### In need of a optimal basis improvement procedure in linear programming.

One of our MOSEK customers is solving an LP with the primal simplex optimizer. Next she does a sensitivity analysis but that fails because the optimal basis is singular. This should not happen in ideal world but can happen for at least three reasons:
• A bug may cause the optimal basis to be singular.
• The primal simplex optimizer works on a presolved and scaled problem. Whereas the sensitivity analysis is performed on the original problems. The basis might be well-conditioned in the presolved and scaled "space" and not the original space.
• The simplex optimizer usually starts with a nicely conditioned basis. In each iteration an LU representation of the basis is updated using rank 1 updates. If the rank 1 update signals that the basis is ill-conditioned then the iterations is continued. Using an idea by John Tomlin it is possible in some cases to discover that the basis becomes ill-conditioned during the rank-1 update. Hence, it might very well be that an ill-conditioned basis is not discovered. Particularly if it becomes ill-conditioned in the last simplex iteration.
Since most real world LPs have multiple optimal basic solutions then looking for the best conditioned (near) optimal basis might be very useful before doing sensitivity analysis or even hotstart. Finding the best conditioned optimal basis is most likely not computationally feasible but maybe it can done in approximate way.

At ISMP 2009 I saw a talk about the cutting plane methods. There was some relation between the quality of the cuts generated and the conditioning of the basis.

Btw. the John Tomlin article I am referring to is "An Accuracy Test for Updating Triangular Factors", Mathematical Programming Study 4, pp. 142-145 (1975).

#### 2 comments:

1. Erling, one approach would be to take
advantage of dual degeneracy in the
final solution (or any other along the
way). If B is the current basis and S
is the set of nonbasic columns that have
zero reduced costs, we could form the
matrix C = [B S] and do a rectangular LU
factorization to select a better B.
Most LU routines keep L well-conditioned
for stability, so we really need to
factorize C(transpose) = LU, and then
the first m pivot rows will point to a
good B.

This is the "basis repair" that we do
with LUSOL inside MINOS and SNOPT. See
section 5.3 of our paper in SIAM Review
47:1 (2005), pp 99-131.

Note that Tomlin's paper is about the
Forrest-Tomlin method for updating the
current LU factors. The test decides
whether the next FT update will be
sufficiently stable, or whether it would
be safer to factorize B from scratch.

This is different from deciding that B
is ill-conditioned. (We can *always*
apply the Bartels-Golub update safely,
whether B is ill-conditioned or not.)

2. Thanks. I should reread your SIREV paper :-).

In some places I use the condition estimate of Bill Hager. If that shows problems I do something along the lines you suggest. In BI
(aka. cross over) we also need to crash an initial stable basis among the potential basis variables.

I was hoping to avoid the factorization and maybe just pivot few of dual degenerate variables into the basis.

Note: Only a member of this blog may post a comment.