14

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.
SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
vulpith
  • 383
  • 1
  • 5
  • 2
    You can also check out DipPy (http://www.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. – Kuifje Dec 30 '19 at 08:46
  • There are many questions related to this topic. Would you see this, this and this links? – A.Omidi Dec 30 '19 at 09:01
  • 6
    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. – Marco Lübbecke Dec 30 '19 at 09:36
  • 3
    There is Coluna.jl package which implements Branch-and-Price: https://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.

     – Ruslan Sadykov Jan 06 '20 at 13:22

1 Answers1

3

You can check out the MINOTAUR codebase, it's pretty well written and designed for people to create their own algorithms.

Last time I checked (a few years ago), it wasn't very well documented, but the code itself is very readable and very well designed.

The fastest way to get started is to check out their examples of how to create new algorithms (e.g. this QG algorithm), and basically modify those files to suit your needs.

The code itself is fairly high performant and already has plug-and-play interfaces to a bunch of things like IPOPT and CBC so you won't have to write them yourself. It also has an ASL interface.

The reason I would recommend this over SCIP is the readability of the code - even though SCIP does come with a lot of documentation it's very hard to understand its codebase, and even harder to edit it.

Nikos Kazazakis
  • 12,121
  • 17
  • 59