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