11
$\begingroup$

I want to learn more about solvers by reading the code of some open-source projects such as MINOTAUR, Optaplanner and OR-Tools.

However, I am struggling. I don't know where to start from there are a lot of repositories and files with no high-level overview. I don't know if I need to start with smaller solvers (in this case feel free to suggest one or more) or I need to learn how to approach open-source projects in general (any references for that?).

I would be grateful if someone could provide some guidance.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ A good start can be to try and use the code successfully. Once you are confortable as a user, you can open the hood and try to understand which procedure/method achieves which feature, step by step $\endgroup$ – Kuifje Sep 11 '20 at 21:25
14
$\begingroup$

I read through the code of several solvers before developing Tulip.jl. To be honest, unless you are yourself developing a solver/interface, or need to reproduce an author's implementation, there is probably a better use of your time than reading solvers' source code. Reading the user guide or, when applicable, the paper(s) that describe the software's algorithmic components should definitely be your starting point. In addition, as Kuifje mentions in their comment, begin familiar with a solver's interface makes it easier to understand its inner workings.

That being said, I have found that, at least for linear programming, most of the algorithmic components are, overall, fairly similar. Differences stem from particular choices of data structures and how modular the code is.

To me, the most important part is knowing what you are looking for in the code. Is it to understand an algorithm's implementation? Specific data structures? How solvers parameters are handled? This will help focus your work and not get lost.

Here are another few factors I would take into account (I guess several are not specific to optimization software) when choosing which solvers to look at:

  1. Documentation. Just don't expect to get much from un-documented source code.

  2. Is the solver maintained? If a solver is maintained by several people, then those people will have looked at the code. That's a good indication that the source is readable, at least enough so that others have been able to modify it.

  3. Programming language. It may sound obvious, but reading a language you're familiar with makes the task way easier. Most solvers are written in C or C++, some old ones are in Fortran, and I know a few in Julia. Similar paradigms may result in completely different implementations in different languages, though the basic ideas will most likely remain the same.

  4. Which problems are supported? Data structures (and algorithms) vary widely between a linear programming solver and a non-linear programming one. The former only needs matrices and vectors, the latter will likely include automatic differentiation tools, appropriate data structures for gradient and hessian computations. Mixed-integer solvers add a layer of complexity with branching trees, etc... Constraint Programming are another category altogether. Thus, know what you're searching for.

As for whether some solvers are more "readable" than others, my experience here is limited to (mixed-integer) linear programming, and a little of conic optimization. I have found GLPK to be well-written and easy to follow. SCIP and Ipopt have good and extensive documentations, which to me is a requirement. I would not go near Clp's or Cbc's codebase unless you know what you are doing. For conic optimization, ECOS is a light-weight interior-point solver in C. HiGHS is a modern simplex solver for linear programming under active development. Solvers written in higher-level languages such as Julia or Matlab may be easier to follow: Tulip's entire codebase is only ~4000 lines of code (Clp is ~180k, Ipopt ~75k, HiGHS ~50k).

In most solvers' source code, you will find a src/ directory: this is where the source code will be. I generally proceed as follows:

  1. Identify which specific component I want to understand, e.g., how parameters are handled internally
  2. Make a quick search through the docs. Many times that is enough
  3. If not, peek at the code that's pointed to by the documentation. I generally start by looking at header files, and rarely look at source files directly.
  4. If there's anything I don't understand, e.g., some class or I don't know or function whose role is unclear, search where it is defined.
  5. Repeat.
Improve this answer
$\endgroup$
3
  • $\begingroup$ Tulip.jl looks really good. May I ask why you made the choice of Julia rather than say C++ ? Do you think Julia is the future (or at least, it should be preferred over C++) ? $\endgroup$ – Kuifje Sep 15 '20 at 6:59
  • $\begingroup$ Thanks :) At the time I wanted to evaluate performance improvements of a column-generation algorithm by solving the master problem with a specialized IPM algorithm. That meant I had to implement (and interface): 1) a column-generation code, 2) an IPM solver with 3) specialized linear algebra, and 4) other LP solvers for baseline. The Julia ecosystem was the best way to achieve that with minimum effort (and virtually no performance trade-off) $\endgroup$ – mtanneau Sep 16 '20 at 14:04
  • $\begingroup$ As for whether Julia is the future, this question can be an entire topic by itself. It certainly is my present. $\endgroup$ – mtanneau Sep 16 '20 at 14:06
5
$\begingroup$

There are software tools (typically language-specific, I think) that will ingest a software project and excrete a map of dependencies (basically, which methods / classes / files invoke something from which other methods / classes / files). If you pick an open-source project and run it through such a tool, you should be able to sort all the files etc. into a hierarchy. Then you can start with the top-level piece, read the code there and just make a note of what calls to other pieces are doing in general terms ("solves the model", "exports an MPS file", "checks data for consistency" ...) without getting into too much detail. Then work your way down the hierarchy as far as you care to go.

Improve this answer
$\endgroup$
5
$\begingroup$

Funny you should mention MINOTAUR, I actually learned C++ by modifying MINOTAUR's source code for my PhD.

In my opinion, virtually no solver has documentation that helps understand how the code itself works and why it's put together the way it is.

The reason is that the overall algorithms are straightforward, you can learn those in a couple of days. Solver magic lies in the data structures, and how information is formatted and passed efficiently for iterative calculations.

The best way to understand the code is to try and modify it to do something different, but be warned that this can take many months.

Here's a few tips I can give you:

  • Get a good IDE such as CLion. This will help you easily navigate the code, look up method usages, and so on.

  • Don't use Eclipse, you'll regret it. If you want a good free option, use VSCode.

  • Don't assume that all code is well written. I learned how CGraphs and AD work by modifying MINOTAUR's code. When we implemented that from scratch for Octeract Engine, our code for the CGraph was ~50 times smaller, and faster.

  • Many design choices are deliberate, even if, for the life of you, you can't fathom the motivation. The why becomes clear years later, when you run into the same bottlenecks the original developers did. Solvers use many tricks such as caching, vectorisation of calculations, and , unfortunately, global variables because it's really not obvious how to put together high performance code and keep it maintainable at the same time.

  • If the solver is not designed using object-oriented programming don't waste your time reading the code. It will take forever and you will learn very little because you shouldn't code a solver that way nowadays.

  • For C++ try to replace pointer arguments to pass by value instead. This will force you to implement copy and move constructors, which will in turn help you understand the fundamental data structures.

  • Keep in mind that old-school solvers were written without modern compilers. Back in the day having one massive function instead of 100 small ones actually boosted performance. This is no longer true.

  • Try to break large functions into smaller ones.

  • Write tests for the solver so that you know that your modifications produced the same results. Ideally, use a CI platform like Jenkins.

  • Use Git, and use it a lot.

Improve this answer
$\endgroup$
4
  • $\begingroup$ When you say "high performance" code, are you referring to "high performance computing (HPC)" as a field ? $\endgroup$ – Best_fit Sep 13 '20 at 9:26
  • $\begingroup$ @Patrick K. Somewhat but not exclusively, in my view "high performance" code is code that is designed to scale well as problems become larger/more difficult. $\endgroup$ – Nikos Kazazakis Sep 13 '20 at 12:29
  • $\begingroup$ On the other hand, is "HPC", as a field, widely used in OR ? Any papers/resources on that? $\endgroup$ – Best_fit Sep 13 '20 at 12:31
  • $\begingroup$ @Patrick K. Not really, but we're trying to change that. AFAIK our solver is the first serious attempt to exploit HPC resources for hard problems. $\endgroup$ – Nikos Kazazakis Sep 13 '20 at 15:34
4
$\begingroup$

For the last few releases of the SCIP Optimization Suite there have been technical papers covering the new features and improvements - basically a very detailed CHANGELOG.

This might be a possible starting point as the source code is quite complex - which is true for just about any solver.

Improve this answer
$\endgroup$
4
$\begingroup$

The most important things have been said already but I want to add that in my opinion the best way to read code is to read it while stepping through a relatively easy test case in the debugger. When looking at an LP or MILP solver I would start by stepping through a tiny instance to get an idea of the program flow, do that multiple times, and stepping into major functions as needed and inspecting the data structures. Then I would try larger or different kinds of problems to see more of the code or better understand its intricacies. By the way, in my experience the best way to learn a code really well is trying to fix bugs in it...

Improve this answer
$\endgroup$
4
$\begingroup$

For OptaPlanner, start by understanding the CloudBalancing example as explained in docs chapter 2. Enable DEBUG and TRACE logging to see what happens during a run. Then run that it a java debugger and start adding breakpoints to figure out what's going on.

A quick run through of some of the important classes:

  • SolutionDescriptor, EntityDescriptor, GenuineVariableDescriptor: translates annotations on the user's domain classes into a queryable metamodel.
  • ScoreDirector calculates the score for a given solution
  • DefaultSolver: the actual solver implementation
  • DefaultLocalSearchPhase: the actual local search implementation. Start here if you want to see the algorithms at work. This holds the "step iteration" and delegates finding the winning the step to ...
  • LocalSearchDecider, this has the "move evaluation iteration": it selects a move from the MoveSeletor, does the move, asks ScoreDirector to calculate the score, accepts it with an Acceptor, undoes the move. Until it picks a move as the winning step.
  • TabuSearchAccepter, SimulatedAnnealingAccepter, etc: the local search variant implementations.

TLDR: Turn on TRACE logging and put a breakpoint in DefaultLocalSearchPhase.solve()

Improve this answer
$\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.