Tag Archives: julia,constraint-programming,optimization,video

Constraint Solver Part 10: Graph Coloring Part 1

Series: Constraint Solver in Julia

This is part 10 of the series about: How to build a Constraint Programming solver?

In this post I’ll first make a small update to the sum constraint as it should simplify things like 2x+3x to 5x
and also 2x-3y+5 == z by moving the 5 to the rhs and the z to the left.

In the second part of this post we create the not equal constraint and use it for graph coloring as I’m missing some visualizations in this series.

Sum Constraint

This time I want to do test driven development that means we define the tests first.

Inside test/small_special_tests.jl:

@testset "Reordering sum constraint" begin
    com = CS.init()

    x = CS.addVar!(com, 0, 9)
    y = CS.addVar!(com, 0, 9)
    z = CS.addVar!(com, 0, 9)

    CS.add_constraint!(com, 2x+3x == 5)
    CS.add_constraint!(com, 2x-3y+6+x == z)
    CS.add_constraint!(com, x+2 == z)
    CS.add_constraint!(com, z-2 == x)
    CS.add_constraint!(com, 2x+x == z+3y-6)

    status = CS.solve!(com)
    @test status == :Solved 
    @test CS.isfixed(x) && CS.value(x) == 1
    @test 2*CS.value(x)-3*CS.value(y)+6+CS.value(x) == CS.value(z)
    @test CS.value(x)+2 == CS.value(z)
end

It’s important that we test for + and - and single variables as well as LinearVariables and a bit more on the rhs.

then we can run ] test ConstraintSolver

  • MethodError: no method matching +(::ConstraintSolver.LinearVariables, ::Int64)

That is part of the second constraint as the first one can actually be solved currently but is not converted to a simplified form.

I want that 2x+3x == 5 actually creates the same as 5x == 5.

Therefore I add:

@test length(c1.indices) == 1
@test c1.indices[1] == 1
@test c1.coeffs[1] == 5
@test c1.rhs == 5

to the test case which fails.

Now we can simplify it because we have the same variable index inside the constraint indices or linear variables indices.

At which step do we want to simplify?

We could simplify in + when we build the linear variables object or in == when we actually construct the constraint. I’m going for the latter one as this has overhead only once.

The idea is to sort the indices and if two indices are the same then we add up the coefficients.

This will be done in src/eq_sum.jl but we want to do it later also for <= and >= therefore the function of simplification will be in src/linearcombination.jl.

The new == function:

function Base.:(==)(x::LinearVariables, y::Int)
    lc = LinearConstraint()
    indices, coeffs = simplify(x)
    lc.fct = eq_sum
    lc.indices = indices
    lc.coeffs = coeffs
    lc.operator = :(==)
    lc.rhs = y
    return lc
end

The simplify function:

function simplify(x::LinearVariables)
    set_indices = Set(x.indices)
    # if unique
    if length(set_indices) == length(x.indices)
        return x.indices, x.coeffs
    end

    perm = sortperm(x.indices)
    x.indices = x.indices[perm]
    x.coeffs = x.coeffs[perm]
    indices = Int[x.indices[1]]
    coeffs = Int[x.coeffs[1]]

    last_idx = x.indices[1]
    for i=2:length(x.indices)
        if x.indices[i] == last_idx
            coeffs[end] += x.coeffs[i]...

Constraint Solver Part 9: Recap video

Series: Constraint Solver in Julia

This is part 9 of the series about: How to build a Constraint Programming solver?

We did a lot already in very small steps sometimes and maybe not all of you read everything. Special thanks to those who did!

If you’re interested in this project but don’t have time to read through all of it: Bookmark the website and return back later 😉

In this post I mostly mention the video I made about this series:

The main goal of this video is to show you the overall structure of the code which might be hard to follow in the blog version.

Additionally in the last couple of minutes I also give a coding session on how to integrate your own constraint. In the post it’s the very simple equal constraint.

I don’t explain the constraints in the video so if you want to read that again I would suggest:

Part Four: Alldifferent constraint and Part Eight: UI Refactoring. In the latter I gave a simple explanation of the sum constraint which I failed to give before.

If you wonder about the Variable Type which isn’t explained in the video you should check out:

Part Five: Better data structure

Unfortunately the quality of the video/microphone isn’t that good but I hope it’s still watchable and reasonable. If you’re interested in more stuff like this and maybe live coding of a constraint or something please comment. Comment as well if you think I should just keep blogging 😉

Stay tuned 😉

And as always:

Thanks for reading and special thanks to my first three patrons!

List of patrons paying more than 2$ per month:

  • Site Wang

If you want to have early access to the next posts as well and enjoy the blog in general please consider a donation via Patreon to keep this project running.

For a donation of a single dollar per month you get early access to the posts. Try it out for a the last two weeks of October for free and if you don’t enjoy it just cancel your subscription.

If you have any questions, comments or improvements on the way I code or write please comment here and or write me a mail o.kroeger@opensourc.es and for code feel free to open a PR on GitHub ConstraintSolver.jl

I’ll keep you updated on Twitter OpenSourcES as well as my more personal one:
Twitter Wikunia_de