This is part 17 of the series about: How to build a Constraint Programming solver?
In this series I’m building a constraint solver from scratch in Julia.
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
- Part 16: Dealing with real objectives
but that is a long list so I’ll make a short post again for Part 20. Explaining what I’ve programmed so far and what is still missing.
I’m doing this in my free time but would like to spend more and more time programming this project as well as blogging about it. If you want to support this project and the blog in general I would be amazed if you become 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 exists until the 10th of February.
Implementing support for linear objectives
If you want to just keep reading -> Here you go 😉
Since the last part the solver supports real coefficients but it only supports to minimize/maximize a single variable the next reasonable step is to support linear objective functions in general. As you might remember all the variables are discrete which means we can’t minimize something like \(0.5x+7.2y\) as of now.
Feel free to check out all the code changes needed to make this possible on GitHub PR #61.
This post explains the needed changes to make it work. At first it seems like an easy problem again as we only need to change the get_best_bound
functionality. We only had single_variable_objective
here.
Now we add a function called linear_combination_objective
into the same file src/objective.jl
.
Where we use the fact that we have a linear combination so the maximum sum is adding the maximum terms together which consist of the maximum value for each variable times the coefficient, if the coefficient is positive and otherwise take the minimum value.
In code on Github
function linear_combination_objective(com::CS.CoM, var_idx::Int, val::Int)
objective = com.objective
indices = objective.lc.indices
coeffs = objective.lc.coeffs
objval = objective.constant
if com.sense...