[Cbc] Using LP solvers other than CLP

[Ted Ralphs]

Iain,

If what you are interested in is having a platform to plug your LP
solver into and do some testing, then there are a few other options.
It would be easy to do this in SYMPHONY
(https://projects.coin-or.org/SYMPHONY), which has no Clp dependency
and accesses the LP solver through OSI. The performance will not be as
good as Cbc because it lacks some of the bells and whistles, but it is
still one of the better open source MIP solvers out there and has most
of the components that are in current state-of-the-art solvers. It is
also very well documented. If you want a simple MIP solver with just
the bare bones of branch and cut, but whose implementation and
connections to the LP solver might be a little easier to dissect,
there is also BLIS (https://projects.coin-or.org/CHiPPS). It is a
basic MIP solver built with the CHiPPS parallel search framework. I
would recommend taking a look at SYMPHONY first. I can help you with
any modifications to the configuration files or build scripts needed
to hook it up to your solver.

As far as Cbc, there is a tradeoff between performance of the solver
itself and agnosticism with respect to the LP solver. The more tightly
coupled the MIP solver is to its LP solver, the better performance you
will get. Part of the performance advantage Cbc has over SYMPHONY
comes from this tight coupling. Over the years, the development of Cbc
has favored performance over solver agnosticism, which was probably
the right choice overall, given that it is being used by IBM and
others in a commercial environment. We are in the process of thinking
about how to make Cbc also function well as a research tool and to
make individual components of it useful for experimentation and
research. It is not clear what will come out of that, but we'll keep
you posted.

Cheers,

Ted

On Tue, Jan 25, 2011 at 5:21 PM, Lou Hafer <lou at cs.sfu.ca> wrote:
> Iain,
>
>          I agree; it's a shame that cbc ended up so tightly tied to clp.
> That's not to say it needs to be that way.  One of my longer-term goals is to
> break this tie, but it's not trivial and there's a lot of side work to be done
> along the way.  Cbc is not the only piece of COIN with this problem.  Up until
> about four years ago, I was able to maintain an ability to use libCbc with a
> generic OSI solver (cbc-generic, files with prefix CbcGen), but eventually could
> no longer keep up with the repairs.  A bunch of observations, in no particular
> order:
>
>  * To appreciate the scope of the problem, try the following on Cbc/src:
>
>      find . -name .svn -prune -o -exec grep -l ClpSimplex {} \;
>
>    Every file name that prints contains code that's specific to clp.  There are
>    about 30 such files in the cbc source.  For some of these, the fix is
>    relatively simple; indeed, some of them date to the period when cbc-generic
>    still worked and generic code is already in place as an alternative.  For
>    others, the fix will be difficult.
>
>    For at least a few, I suspect that equivalent functionality is simply not
>    possible within the existing OSI API. A fix will require extensions to OSI
>    or a rethink of the cbc code. This is the core reason why cbc is tied to
>    clp --- there was no feasible alternative at the time.
>
>  * There's another batch of code, not quite so easy to identify, which depends
>    on the OsiSimplex API or equivalent for access to the simplex tableau
>    (several of the cutting plane generators, for example).  This is a largely
>    unimplemented subset of OSI; currently only clp and, relatively recently,
>    dylp, provide this capability.  Most of the other OsiXXX could be upgraded,
>    but someone has to take the time to do it.
>
>  * LibCbc is a separate thing from libCbcSolver; libCbcSolver is built on top
>    of libCbc. LibCbc is less tightly tied to clp than libCbcSolver, but
>    libCbcSolver contains much of the heuristic intelligence that's applied at
>    startup.
>
>  * Your best chance, if you want to try this, is to edit Cbc/src/Makefile.am
>    (or do something equivalent) so that you build only libCbc.  Undefine
>    COIN_HAS_CLP and see what breaks.
>
> I'm certainly interested in the results, and can provide advice and guidance,
> but I'm not really in a position to give hands-on coding help.  (I'm
> overcommitted as it is, and currently deep in one of the bits of side work I
> mentioned at the start.)
>
>                                                        Lou
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/cbc
>



-- 
Dr. Ted Ralphs
Associate Professor, Lehigh University
(610) 628-1280
ted 'at' lehigh 'dot' edu
coral.ie.lehigh.edu/~ted