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…