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]...