[Clp] Branch and price implementation / documentation / example projects

[Jesse Jaanila]

Hi everyone,

Can someone point to any resource/example of a branch-and-price algorithm
implemented CLP (and maybe with additional coin-OR projects)

Things I would like to control / overload are:
1. Generating negative reduced cost columns until termination criteria are
met. (duh!)
2. If root node RMP does not yield integer solution, branch fractional
variable into N branches. => would be nice to implement own branching scheme
3. Define/store node data that is used to update variable bounds/pricing
problem structure for each node that we process next.
4. Priority queue for non-root nodes. I want to do a depth-first search
first to find any integer solution and then start using the best node first
(lowest node bound) to prove optimality.
5. Control what nodes to prune and the change optimality condition(s)
(integrality gap, etc.,).

So in the API, I’d like to see “generateColums,” “startBrancing,”
“storeNode,” “restoreNode,” “chooseNode” style functions that I could
overload. Is there anything close to this available?

I have been for years trying to get into using coin-OR libraries, but I
think the threshold is quite high. I’m willing to contribute and write
clear documentation for the steps needed to build and run
from scratch, for example, a B&B solver for generalized assignment problem,
if I’m able to create it myself first :-D

I think a detailed step-by-step guide would be handy and would bring more
people into using coin-OR libraries. And I see column generation, and B&B
is usually the next method to try after the standard process of "just plug
the IP model to a solver and hope it solves it" fails.

Any comments or thoughts are welcome! And as this is my first post to this
mailing list, Hello Coiners (what do you call yourselves;-)?). If this is
the wrong board, sorry!
Br, Jesse
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20181107/691da7cf/attachment.html>