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!
