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


  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.