6
$\begingroup$

I heard once that the branch and price (B&P) algorithm is among the hardest ones in OR, but if it's implemented well, it could be very efficient. Aare there other algorithms that are also that tricky?

I want to implement B&P on a problem. So how do I choose a problem that is not too complex? Feel free to suggest more than one problem if you think that it has an impact on the way the algorithm is implemented, i.e. if I will learn different principles from different problems.

I also need some guidance. How to start? What are the pitfalls to avoid? Any resource that has an open-source code that is well documented would be appreciated as well. I want to choose python or C++.

$\endgroup$
11
$\begingroup$

Before starting implementation, I would make sure I am comfortable with all the theoretical aspects, which are somewhat tricky as well. This is quite an advanced topic in OR and requires some experience. Are you comfortable with branch-and-bound, with the simplex algorithm, with Dantzig-Wolfe decomposition, column generation, etc ?

You are hesitating between Python and C++. Is there a reason for that ? Python is much much simpler, but C++ will be faster. So is this for academia or for industry ?

You can also checkout DipPy, which is an extension of ​PuLP (so its Python) that allows users to specify decompositions and customize the branching, cut generation, and column generation of DIP, from within a PuLP model. Everything is open source.

$\endgroup$
2
  • $\begingroup$ Any resources to be comfortable with the theoretical aspects? I am comfortable with branch-and-bound, with the simplex algorithm, with Dantzig-Wolfe decomposition, column generation. $\endgroup$ – Best_fit Oct 3 '20 at 9:59
  • 1
    $\begingroup$ the column generation bible : link.springer.com/book/10.1007/b135457 $\endgroup$ – Kuifje Oct 9 '20 at 16:20
5
$\begingroup$

Using a framework like SCIP may be a good idea for starting. By doing so, you can quickly implement your formulation. It has interfaces on both C++ and Python. The documentation contains examples of branch-and-price, I suggest you to take a look at them. For any problem at hand, you can use Dantzig-Wolfe decomposition method to generate branch-and-price scheme.

$\endgroup$
5
$\begingroup$

Nah. Building an ASL interface is hard, BnP is OK. Assuming you are familiar with its building blocks (just like with any other algorithm), the challenge lies in the implementation details.

There are a few things to be aware of for BnB in general, and for BnP specifically:

BnB

  • Acceleration heuristics: BnB algorithms only work well if combined with certain acceleration heuristics such as domain reduction (e.g. constraint propagation), or good branching strategies (e.g. pseudocosts).
  • For large problems you need good & scalable data structures to avoid the algorithm slowing down to a crawl, especially if your problems are large enough to require column generation.
  • Pure Python will be 1,000-10,000 times slower than C++ for any problem of decent size. The proper way of doing this is to code C++ libraries for the high performance calculations and import them as Python objects using Python->C++ APIs such as boost Python. This can get you to 100x slower than C++.
  • For the two reasons above, Python has its limits due to the limited bandwidth in transferring data between different parts of your code. In particular, many Python->C++ APIs unavoidably trigger C++ copy constructors which can be a big problem if your data structures are large. Memory can also become an issue.
  • Since we're on the subject, even if you really know what you're doing in C++, the best you can do with hybrid code is 100x slower than C++. However, if you're in that level of knowing what you're doing, you might as well do the entire thing in C++.
  • MINOTAUR is the most well written C++ open-source BnB code I've seen so far (although not very well documented as of a few years ago).
  • One thing that most people neglect in the beginning is that you need a way to get the math in your code. Think about how you will do this early on as it will affect many of your architecture decisions.

BnP

  • An important implementation consideration here is that you are required to add columns to the relaxation as the solution procedure progresses. This can be a very costly operation, especially with large matrices, so you will need to research the fastest way that your linear solver supports to add new columns. Rebuilding the matrix is the simplest way of course and is actually ok-ish for many algorithms, but it's a no-no for column generation.

From your description it sounds like your goal is to learn new stuff, so either Python or C++ are fine for that purpose. If you want to use your code for something "real", using C++ to some extent will be unavoidable, so it's up to you to decide what you want to learn programming-wise. Be mindful though that migrating hybrid code to C++ can be quite painful, so if you see that you have to go with C++ better to do it early on in development.

Either way, mentally prepare yourself for a big time investment, and have fun!

$\endgroup$
2
  • $\begingroup$ Some questions related to your answer. 1. What do you mean by ASL interface? 2. Any examples of scalable data structure and why they are scalable ? 3. What did you mean by "getting the math in the code? $\endgroup$ – Best_fit Oct 3 '20 at 10:07
  • $\begingroup$ 1. ASL is the most widely used interface to represent math in solver format 2. E.g., a vector vs an unordered map, you can look up the complexity for various operations. 3. Human-readable math and solver formats are different (e.g., the AMPL language vs the ASL). Once you start thinking about how you can read math from somewhere and get that into a data structure that you can manipulate in your code you will see what I mean. $\endgroup$ – Nikos Kazazakis Oct 3 '20 at 10:47
4
$\begingroup$

If you want to look at C++ source code, there are some COIN-OR projects that provide frameworks for "branch price and cut" or "branch cut and price" as it's sometimes known. Two that come to mind are BCP and Symphony.

$\endgroup$
2
$\begingroup$

One of the main ideas behind our decomposition solver GCG (gcg.or.rwth-aachen.de/dev) is to save you the time experimenting with your own B&P code only to find out that B&P is not the right approach to your problem. One other main idea of our solver is that once you found out that B&P is a good approach then you can just use GCG to do the job for you. Give it a try, it hopefully saves you some hours. Download with SCIP at scipopt.org.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.