12
$\begingroup$

As far as I know, implementing a branch-and-price algorithm is a task far from trivial. However, there are tools such as SCIP or the BCP framework of COIN-OR that help implement such algorithms.

I would like to ask you two questions in this regard:

  1. According to your experience, what is the best alternative to implement a branch-and-price algorithm: using SCIP, the BCP framework of COIN-OR, another tool I am not aware of, or maybe implementing an algorithm from scratch?
  2. Can you comment on the advantages and disadvantages of the alternative you recommend? e.g., learning curve, good/bad documentation, the possibility of parallel executions, or availability/lack of methods to improve performance such as dual variable stabilization.

Thank you very much.

$\endgroup$
  • 2
    $\begingroup$ You can also check out DipPy (optimization-online.org/DB_FILE/2011/02/2921.pdf), it is a powerful open-source tool that you can find on COIN-OR interfaced with PuLp. $\endgroup$ – Kuifje Dec 30 '19 at 8:46
  • $\begingroup$ There are many questions related to this topic. Would you see this, this and this links? $\endgroup$ – A.Omidi Dec 30 '19 at 9:01
  • 4
    $\begingroup$ SCIP has a extension called GCG that turns SCIP into a BPC solver, i.e., it manages an orignal and a reformulated model, thus can perform branching automatically, uses stabilization etc. It can be a good starting point, but documentation ATM is worse than SCIP's. $\endgroup$ – Marco Lübbecke Dec 30 '19 at 9:36
  • 1
    $\begingroup$ There is Coluna.jl package which implements Branch-and-Price: github.com/atoptima/Coluna.jl At the moment, this project is in active development, so the documentation is rudimentary. Dual stabilization and parallelization are in plans. $\endgroup$ – Ruslan Sadykov Jan 6 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.