Constraint Solver: Support for linear objectives

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:

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...