search

scipopt / soplex

Sequential object-oriented simPlex
Other
59 stars 18 forks source link

Basis recovery #2

Open chrhansk opened 3 years ago

chrhansk commented 3 years ago

As I mentioned in #1: SoPlex is highly pessimistic regarding changes in the objective function and the bounds of the variables / linear constraints. Essentially, the Basis is discarded entirely.

I think it would be more efficient to recompute the reduced costs / primal solution and decide whether the changes preserve primal / dual feasibility. If this is the case, the primal / dual simplex can be warm started based on the Basis. Since the Basis matrix stays regular, this hopefully only requires some triangular substitutions.

This may cause problems in combination with presolving though, so maybe the recovery is not as straightforward if presolving is enabled...

ambros-gleixner commented 3 years ago

Yes, presolving definitely must be disabled for basis warmstarts.