ConstraintSolver.jl Refactoring

About a month ago I started this PR #178 and wanted to do some simple refactoring. I did some of it on my Twitch stream which was more complicated than I thought and I already imagined it to be complicated. Running test cases is taking too much time but I might have a way how I can speed that up now 😃 and the project is just very big.

Refactoring also means: Jumping around in the code base a lot. My unstructured comments probably also didn't help... Anyway I might think about that again in the future but it's important nonetheless to have a blog post about it for you and me to have a searchable and structured way. Furthermore, one can read this in 10 minutes and doesn't have to watch 10 hours of stream 😄

Most of the refactoring work was pretty boring as well so I can skip over the "renaming stuff" part here I guess.

Oh yeah for everyone who is new to this series... Let me check the counter...

It's part 26 of the long long series (and kind of never ending journey) of writing a constraint solver from scratch in Julia

You might want to start with Part 1: Setup and backtracking

And after a couple of weeks of reading feel free to come back to this post 😉 It's okay you can jump over my errors and read only the important parts. This post is probably interesting for two kinds of people out there: Those who follow me for nearly a year on this journey. You're awesome btw!

Additionally some of the parts discussed here can be relevant for other projects. Check out the first section and or the table of contents to decide whether it's worth your time.

What I wanted

Let's start with some things that I wanted. I achieved at least part of it:

• Removing low level interface as I don't mentally support it for a while anyway. Everything can be done with MOI and JuMP now.

• Having more consistency with naming variables

• Moving some functions to different folders

• ...

and the two main points:

• Don't rely on hashing constraints anymore for ordering and just rely on the now deterministically ordered constraints given by MOI.

• Have access to the ConstraintInternals like indices with .indices instead of using .std.indices. <- the most interesting part of this post

Renaming stuff and moving things over to different functions

Come one nobody want to read this...

Hashing constraints

I shall shortly explain why I did this as well as why it failed and then why I don't need this anymore 😉

The user gives some kinds of constraints like:

@constraint(m, sum(x) <= 12)
@constraint(m, x in CS.AllDifferentSet())
@constraint(m, y in CS.AllDifferentSet())

and probably 10th more (yeah that is the order of magnitude I currently work with :D). One day you might be able to have a fast solution with a lot of constraints 😄

You can also write this as:

@constraint(m, y in CS.AllDifferentSet())
@constraint(m, sum(x) <= 12)
@constraint(m, x in CS.AllDifferentSet())

now the question is: Shall this run exactly the same way as the one above? The more important thing is: If I run one of the versions twice I kinda expect that the solver does the exact same thing.

The problem was that JuMP and MOI used a Dict for this which is unordered. They used a dict only for the set constraints like in CS.AllDifferentSet() such that nobody seemed to notice that before. Our assumption of running the same version twice and everything should be deterministic failed. I didn't know how to fix that error at first so I went with the goal that in both cases the solver should do exactly the same thing.

My solution was to use hash on the indices such that when defining @variable(m, y before @variable(m, x this would make a difference but I'm okay with that. The hash also uses the constraint type and some other parameters when needed.

During the refactoring I forgot to add a hash for some of the constraints and the benchmarks were not comparable anymore. I fixed that issue but had the glorious idea of having tests for it, such that a test case fails if the hashes differ from a reference of precomputed hashes.

A few days later Julia v1.5 was released and the test cases failed...

I was like what the heck!

julia v1.1> hash([1,2,3])
0xecc5186e7be222c6

julia v1.5> hash([1,2,3])
0xd22721a98cab7f9d

I guess you see the problem.

Maybe I should say that I find that unexpected somehow but yeah my use case of hashes i maybe also not the most normal one.

It is normally used to check if two things are equal and therefore only need to be consistent in one Julia version. I assume that it got some kind of speedup with the new hash, but I didn't dive into that hole of checking the source code to figure it out.

At that point I remembered that I fixed the the ordering issue in MOI so I might not need this anymore. And it seems like I don't ;) I still have test cases that solving the same problem twice should have the same deterministic solving process so I guess I'm safe.

It also removed some extra code of hashing and checking if a hash is bigger than another hash etc. (I could have sorted them once ...)

Playing around with getindex

This is probably the more interesting part, which can be useful in other projects. BTW please comment on what you're working on. I'm seeing some stats like 100 people read my blog post today. I would like to know who you're and what you're working on 😉

While you write a comment at the end of the post, I'll shortly explain why I have the weird constraint.std.indices syntax instead of constraint.indices. As this might be confusing in the first place.

Let's dive a bit into the struct and abstract type section of Julia.

abstract type Constraint end

In Julia abstract types can't store any fields. They are just there for dispatch reasons. This means I can have:

mutable struct BasicConstraint <: Constraint
    std::ConstraintInternals
end

mutable struct EqualConstraint <: Constraint
    std::ConstraintInternals
    first_ptrs::Vector{Int} # for faster apply_changes!
end

and then write

function set_impl_init!(constraint::Constraint)
    c_type = typeof(constraint)
    c_fct_type = typeof(constraint.fct)
    c_set_type = typeof(constraint.set)
    if hasmethod(init_constraint!, (CS.CoM, c_type, c_fct_type, c_set_type))
        constraint.impl.init = true
    end
end

so use the abstract type for the method.

The point now is that each constraint needs some information like an index and the variable indices as the solver knows when to call the constraint methods.

Therefore I have this:

mutable struct ConstraintInternals{
        FCT <: Union{MOI.AbstractScalarFunction, MOI.AbstractVectorFunction},
        SET <: Union{MOI.AbstractScalarSet, MOI.AbstractVectorSet}
    }
    idx::Int
    fct::FCT
    set::SET
    indices::Vector{Int}
    pvals::Vector{Int}
    impl :: ImplementedConstraintFunctions
    is_initialized :: Bool
    bound_rhs::Union{Nothing, Vector{BoundRhsVariable}} # should be set if `update_best_bound` is true
end

The problem now is that I always have to type constraint.std.indices to get the indices. It would be more developer friendly to write constraint.indices.

I just wrote "user friendly" and realized that they never use it => don't care about it. Nevertheless, in your project they might 😉

BTW did you finish your comment? Great!

Okay so how can we do that? We need some kind of our own getproperty method.

I failed a little bit at first to make this fast but now everything is working very smoothly and I don't want that you have a slow implementation.

Let's check the help mode:

help?> getproperty
search: getproperty

  getproperty(value, name::Symbol)

  The syntax a.b calls getproperty(a, :b).

okay so constraint.indices calls getproperty(constraint, :indices).

function Base.getproperty(c::Constraint, s::Symbol)

and this example from the help mode looks promising:

function Base.getproperty(obj::MyType, sym::Symbol)
    if sym === :special
        return obj.x + 1
    else # fallback to getfield
        return getfield(obj, sym)
    end
end

unfortunately using it like this will give us:

function Base.getproperty(c::Constraint, sym::Symbol)
    if sym === :indices
        return c.std.indices
    else # fallback to getfield
        return getfield(c, sym)
    end
end

which in itself looks a bit recursive and is doomed to be slow. The problem is that return c.std.indices calls getproperty(c, std).

I found out about Core.getproperty and now I have the relatively readable and same speed as c.std.indices solution:

@inline function Base.getproperty(c::Constraint, s::Symbol) 
    if s in (:idx, :indices, :fct, :set, :pvals, :impl, :is_initialized, :bound_rhs)
        Core.getproperty(Core.getproperty(c, :std), s)
    else
        getfield(c, s)
    end
end

That makes me very happy!

What's next?

I'm currently working mostly on Javis.jl to release v0.1.0 as soon as possible. Then I want to implement better branching strategies for the constraint solver and I'm currently failing to implement: Activity-Based Search mostly because I don't really understand why it doesn't use the same branching variable over and over again and that seems slow. I might search for other strategies or papers and blogs (which are rare) to figure things out.

Okay I have to leave now and start my stream... If you don't follow me on twitch yet: Why not? 😉

Twitch stream

And as always:

Thanks for reading and special thanks to my 10 patrons!

List of patrons paying more than 4$ per month:

• Site Wang

• Gurvesh Sanghera

• Szymon Bęczkowski

• Logan Kilpatrick

Currently I get more than 20$ per month using Patreon and PayPal.

For a donation of a single dollar per month you get early access to the posts.

I'll keep you updated on Twitter OpenSourcES.

Want to be updated? Consider subscribing and receiving a mail whenever a new post comes out.

Enter your email

Powered by Buttondown.