search

coin-or / Clp

COIN-OR Linear Programming Solver
Other
392 stars 82 forks source link

Which simplex method does CLP actually use? #263

Closed dxyzx0 closed 1 year ago

dxyzx0 commented 1 year ago

In the doc and source code, it says CLP uses a one phase method.

Can you give some reference about this method? Is it a composite simplex method?

jjhforrest commented 1 year ago

Run clp and then

primalweight?? or dualbound??

to get a brief description

dxyzx0 commented 1 year ago

@jjhforrest Thanks. I can understand the primal simplex, it's a composite simplex method. But I'm confused with the description in the dual simplex method.

If a problem has both upper and lower bounds then it is trivial to get dual feasible by setting non basic variables to correct bound. If the gap between the upper and lower bounds of a variable is more than the value of dualBound Clp introduces fake bounds so that it can make the problem dual feasible. This has the same effect as a composite objective function in the primal algorithm.

  1. Why does a problem with bother upper and lower bounds(i.e. the lp is bounded), then it is trivial to get dual feasible? How?
  2. What's the role of the parameter dualbound?
jjhforrest commented 1 year ago
  1. A problem is dual feasible if basic variables have zero reduced cost - which they will with a non singular basis and all variables at lower bound have non-negative reduced costs and variables at upper bound have non-positive reduced costs. So you just look at reduced cost and set variable to correct bound.
  2. If a variable just has a lower bound and a negative reduced cost then you pretend it has an upper bound of lower+dualbound.