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…