Are you new to this series? You might want to check out the start of the series: Creating a constraint solver from scratch

I know it’s a lot to read so you might want to just check out the solver itself ConstraintSolver.jl

This was my next up from last time and it feels like I should actually follow my plans one day…

• How about those unit tests?
• Being able to hot start
  • So provide a partial solution to find a feasible solution faster
  • If the partial solution is wrong or optimality should be reached then backtrack all the way back
• Oh yeah I need to decide on the logo. Please help! Logo issue

At least I did some of it. I talked about the logo in the last post: Housekeeping May 2020

Unit tests

I actually added some unit tests and got some nice improvements out of it. If you want to get details check out PR #162

It includes several bug fixes non feature to feature conversions:

• To feature conversion:
  • in equal constraint, if the synching the equal constraint fails
  • I forgot to return false if that happens :/
  • In the less than constraint I computed a worse safe_threshold such that a bit more pruning is possible
• Feature: Better pruning of eq_sum when changing some variables it is reasonable to test the other ones again

One can hopefully see some of the changes in the benchmark section below 😉

Indicator constraint

Before we go to the benchmark section I also want to introduce a new constraint type which doesn’t have a benchmark test yet so if you have some ideas:
Reach out 🙂

This constraint is partially supported in PR #167. Will be available in v0.1.8 hopefully soon.

JuMP supports the following syntax for indicator constraints:

@constraint(m, b => {x + y >= 0})

Where the constraint in {} has to be an affine constraint at the moment which means that I don’t support an inner alldifferent or table constraint just yet but working on it.

Okay what does that constraint mean?

b is a binary variable and if b = 1 then the constraint must be satisfied otherwise that constraint is not relevant.

The implementation is relatively straightforward I would say and probably gives another good example of how to add a constraint to the solver.

We start with adding a new type in src/types.jl:

mutable struct IndicatorConstraint <: Constraint
    std::ConstraintInternals
    activate_on::MOI.ActivationCondition
    inner_constraint::Constraint
end

We of course need std::ConstraintInternals as in all other constraints to save the indices it uses for pruning and the id of the constraint and other useful information.

The activation_on field is of type: MOI.ActivationCondition and holds information on whether we have b => or !b => so whether we activate the inner constraint on a positive or a negative value.

help?> MOI.ActivationCondition
  ActivationCondition

  Activation condition for an indicator constraint. The enum value is used as first type parameter of IndicatorSet{A,S}.

As you can see it’s an @enum which we haven’t discussed…

This was my next up from last time and it feels like I should actually follow my plans one day…

• How about those unit tests?
• Being able to hot start
  • So provide a partial solution to find a feasible solution faster
  • If the partial solution is wrong or optimality should be reached then backtrack all the way back
• Oh yeah I need to decide on the logo. Please help! Logo issue

At least I did some of it.

I have to say that in this times I really don’t have a timetable and just do what I want which sometimes is not that much 😀

Sorry for not posting consistently. In this post I try to bring you to the current stage of what I’m doing.

Logo

I finally decided on a logo for the constraint solver which took a very long time but I’m finally happy with a design that is mostly inspired from @owiecc and @pdimens on this issue.

Thanks everyone who supported me on that decision and gave me tips over Twitter and GitHub as well as friends over WhatsApp.

I’m happy to present my solver with that logo next year at the JuMP-dev 2021 conference 🙂

Exercism

You see that this is one of those posts that have too many topics in it as I wasn’t able to write down smaller ones in between. Hope it is still a useful one and doesn’t read like a boring diary 😀

Two awesome guys in the julia community, namely Jacob Zelko and Miguel Raz Guzmán, pointed out exercism which is an awesome website to learn a bunch of programming languages including julia. I feel like my code is not too bad but one can always improve, right? Especially in those areas I normally don’t really use like strings, chars and similar concepts which don’t occur often in mathematical programming. I mean I study computer science and I have the general knowledge, hopefully, but every language is different so it’s always good to learn. Anyway I decided to solve some problems on that website which works normally in the following way.

You

• download a problem
• solve it locally
• check the test cases
• submit your code
• get feedback from a mentor
• iterate

I normally know websites which use the first 4 steps but normally I don’t get real feedback about code style or performance.
The “problem” is that you have to wait for mentoring as it’s not done by computers (yet). Because I’m in central Europe I had to wait quite some time before I got feedback to a solution I submitted when the folks from America are normally sleeping, I actually signed up for being a mentor myself.

I got sucked in immediately after an awesome mentor worked through my submissions quite fast and I mentored students in solutions I got mentored it already.
Mentored quite a lot of people and got some positive feedback but most importantly for my egoistic self I learned a lot by…