- 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.

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).

Erling, one approach would be to take

ReplyDeleteadvantage 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.)

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

ReplyDeleteIn 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.