[Scip] Design choices

Marco Lübbecke marco.luebbecke at rwth-aachen.de
Mon Jul 1 19:45:31 MEST 2013


2013/7/1 Timo Berthold <berthold at zib.de>

> I do not really get the point on B,C&P. It is possible in SCIP to
> generate rows and columns at one node, simultaneously. Maybe I'm missing
> out on some previous discussion about some specific features missing.
>


SCIP is a BCP (or as I would put it, a BPC) framework, and a good one.
However, column generation is not only "adding a pricer plugin" and even
more, branch-and-price is not only "solving the relaxation by CG". The
community spits out more and more details and techniques that put "special
needs" on B&P, which are not so prominent in "traditional" B&B, and B&C.
Stabilization is an example, branching another, and a big issue (in my
personal view, the BIGGEST) is in the small things: CG and B&P work in
practice ONLY because of tricks. ONLY. Period. An implementation of these
tricks, without much effort, would currently often require to change SCIP
core code. An example is to early terminate pricing when solving the master
problem because the Lagrangian bound and the master objective funciton
value are close enough (this would require changing the SCIP pricing loop,
in particular it would require to make SCIP aware of such a thing as
Lagrangian bound) -- I fought for this issue for a while, maybe we have it
in the SCIP core now, but again this is just one example. So, from my
"demand" perspective, as a B&P person, we see it everywhere that some
design choices were made when the B&P "algorithmic" was not as developed as
it is today. The GCG project tries to incorporate as much of this B&P need
as possible - I believe that one day this side project may merge back into
the main line, but we will see.

Anyway, keep on doing this good work. Don't discuss too much about C.

M.


<http://www.or.rwth-aachen.de/luebbecke>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20130701/5dcc5692/attachment.html


More information about the Scip mailing list