This is kind of part 16 of the series about: How to build a Constraint Programming solver?
Even if you are not deep into constraint programming this post tries to show you what kind of problems occur when you deal with floating point numbers.
If you are new to this blog and are interested in constraint programming, there are several posts already waiting for you:
- Part 1: Setup and backtracking
- Part 2: Pruning
- Part 3: Pruning+Benchmarking
- Part 4: Alldifferent constraint
- Part 5: Better data structure
- Part 6: Sum constraint first part
- Part 7: Sum constraint speed-up
- Part 8: UI Refactoring
- Part 9: Recap video
- Part 10: First part of graph coloring
- Part 11: MIP graph coloring and optimization
- Part 12: Documentation and latest benchmarking
- Part 13: Profiling
- Part 14: Bipartite Matching
- Part 15: Now it’s a JuMP Solver
I’m a student and do this blog during my free time but would like to spend more and more time programming this project as well as blogging about it. If you have a very generous day you might want to go over the top and finance a bit of my dream 🙂 You can do so by becoming a patron. If you do I will create a better/faster blog experience and you will get posts like this two days in advance! Everything will be free forever but if you have some cash to spare -> This might be an option 😉
Special limited offer only for X days… I either just lost your attention or I have it now 😀
I decided to offer a 1:1 (binary) talk where you can ask me about my work and just chat with me if you’re willing to join the Patron 4$ club. 😉 This offer is until the 10th of February.
Start of the story
If you want to just keep reading -> Here you go 😉
After merging the JuMP part, Mathieu Besançon had a deeper look into the codebase and found out that I don’t support real number constraints like:
\[
0.2x+0.1y = 0.3z\]
At first I thought: Oh yeah I just have to change the type of some structs to support it. Well I forgot the problems using floating point numbers…
You might have seen it before
\[
0.2+0.1 \neq 0.3\]
Yes we are living in a new decade but we still need to deal with the problems that computers can’t calculate even though it’s kind of the thing everyone thinks they are much better than we humans…
There are way better posts and explanations out there why computers don’t sum up \(0.2+0.1\) to \(0.3\) but instead to something like \(0.30000000000000004\).
Have a look at StackOverflow for an answer on this question or search for “How floating point numbers work” on Google -> LMGTFY.
It might be obvious how this applies to the problem in this constraint solver project but maybe a short look back on how these equality constraints are tackled is helpful:
\[
0.2x+0.1y = 0.3z\]…