7
$\begingroup$

I have found the following slides of talks:

I am looking for similar resource (slides, videos, articles, etc.) that treats issues and subjects (numerical issues, performance, architecture etc.) related to building a solver (no matter the techniques MIP, CP, Local-search based etc.)

$\endgroup$
2
  • 1
    $\begingroup$ Can you be more specific in your question? What exactly are you looking for? $\endgroup$
    – Richard
    Commented Feb 15, 2021 at 10:06
  • 1
    $\begingroup$ I want to build a solver for educational purpose. However, I think that there are subjects to treat other than the solving techniques themselves. $\endgroup$
    – Leo_Divrik
    Commented Feb 15, 2021 at 11:08

2 Answers 2

8
$\begingroup$

Unfortunately this is a very sparsely documented subject in optimisation literature. The only technical resource I am aware of in my field is this one. Tobias Achterberg's thesis is also a good resource for MILP solver development.

The problem is that the number of people who are proficient in solver development is so small that the probability of one of us taking the time to also write a book about it is, unfortunately, practically zero.

The one thing I will warn you about is to only read resources written by people who have actually implemented solvers that are good enough for people to use. I've found that most other resources are just full of misconceptions/mistakes.

In my opinion, the best resource by far is to try and understand the source code of a good open-source solver in your area of interest. Examples of good code include MINOTAUR (local MINLP), Couenne (Global MINLP), SCIP (for MILP & MINLP), and SoPlex (LP). There's also a bunch of other code bases like SHOT or Maingo, but those are implementations of more niche methods that are not very relevant to beginners. Do not attempt to read any CoinOR code (other than Couenne) as it's very hard to read even for professional solver developers like myself.

When it comes to understanding solver design, it is important to ask yourself (while reading source code), "why is this implemented the way it is". Many design choices in solver code appear odd at first glance, but there is always a reason (typically performance) if you dig deeper.

$\endgroup$
4
$\begingroup$

The most important thing when writing a floating point solver is to learn the fundamentals of numerical analysis, to include understanding the effects of roundoff error in finite precision numerical calculations. This is the building block on which all else rests.

For this purpose, I can suggest a book such as Accuracy and Stability of Numerical Algorithms, Second Edition by Nicholas J. Higham, SIAM, 2002.

This book also provides introductory material on numerical linear algebra, to include matrix factorizations. The book notably omits coverage of eigenvalues, eigenvectors, singular values, and singular vectors; so be aware. You may wish to proceed to more advanced numerical linear algebra and matrix factorization material at some point.

$\endgroup$
2
  • $\begingroup$ Hi Mark, thanks for your answer. Does this hold for any type of solver (Constraint Programming, Local-search based etc.) ? $\endgroup$
    – Leo_Divrik
    Commented Feb 16, 2021 at 14:03
  • $\begingroup$ @Leo_Divrik If there are floating point calculations, yes. If everything is done in exact or integer arithmetic, no. For what I think you have in mind, I beliieve the answer is yes. $\endgroup$ Commented Feb 16, 2021 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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