Tag Archives: Julia

Indicator constraint + Benchmarks

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

The Logo

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…