Is there a better way to combine all different with the linear combination constraint?
i.e sum([1:6,1:6,1:6]) == 8 when alldifferent can remove the 6 which is currently not done.

Currently for each possibility a new branch is created.
Instead create branches like

• List of possibilities <= pivot
• The other half >= pivot+1
  First just the middle of the current range can be chosen.
  The problem with the current solution is that a lot of branches are created if the number of possible values is high but this is often not necessary.

export functions which are used by the user like:
add_constraint! and solve!

Trying to construct an MWE for #82 , I ran into this. A small problem, which I imagine ConstraintSolver should be able to enumerate and solve in it's entirety (smaller than sudoku) seems to take very long and consume all my RAM.

To reproduce:

using JuMP
using ConstraintSolver
using Cbc # for testing

model = Model()


# Variables
@variable(model, 0 <= inclusion[h = 1:3] <= 1, Int);
@variable(model, 0 <= allocations[h = 1:3, a = 1:3] <= 1, Int);
@variable(model, 0 <= days[h = 1:3, a = 1:3] <= 5, Int);

# Constraints
@constraint(model, must_include[h = 1:3],
    sum(allocations[h,a] for a in 1:3) <= inclusion[h]
);
# at least n
@constraint(model, min_hospitals,
    sum(inclusion[h] for h in 1:3) >= 3
);
# every h must be allocated at most one a
@constraint(model, must_visit[h = 1:3],
    sum(allocations[h,a] for a in 1:3) <= 1
);
# every allocated h must have fewer than 5 days of visits per week
@constraint(model, max_visits[h = 1:3],
    sum(days[h, a] for a in 1:3) <= 5 * inclusion[h]
);

benefit = @expression(model,
    sum(days[h,a] * 5
    for h in 1:3, a in 1:3));


@objective(model, Max, benefit);
set_optimizer(model, with_optimizer(Cbc.Optimizer))
optimize!(model) # working
set_optimizer(model, with_optimizer(ConstraintSolver.Optimizer))
optimize!(model) # consumes all RAM without finishing

Status:

pkg> status
    Status `C:\Users\username\Documents\Projects\projectname\Project.toml`
  [336ed68f] CSV v0.5.23
  [9961bab8] Cbc v0.6.6
  [e0e52ebd] ConstraintSolver v0.1.0 #master (https://github.com/Wikunia/ConstraintSolver.jl)
  [a93c6f00] DataFrames v0.20.0
  [4076af6c] JuMP v0.20.1
  [fdbf4ff8] XLSX v0.5.8

Support a+b != c

Currently you need to define a variable using @variable(m, 1 <= x <= 10, Int) but it also should be possible to define it like @variable(m, x in CS.IntegerSet(1:10)) or
@variable(m, x in CS.IntegerSet([1,2,4,5,9]))

• Depth first search
• Best first search
• First depth until feasible solution

Currently only best first search is implemented

The maximum stable set of the following should be 2.7.

matrix = [
        0  1  0  1  0  0  1  0  0  1
        1  0  1  0  1  0  0  0  0  0
        0  1  0  1  0  0  0  0  1  0
        1  0  1  0  1  1  0  0  0  0
        0  1  0  1  0  1  1  1  0  0
        0  0  0  1  1  0  1  0  0  0
        1  0  0  0  1  1  0  1  0  0
        0  0  0  0  1  0  1  0  1  0
        0  0  1  0  0  0  0  1  0  1
        1  0  0  0  0  0  0  0  1  0
    ]
    n = 10
    m = Model(CS.Optimizer)
    @variable(m, x[1:n], Bin)
    for i = 1:n, j = i+1:n
        if matrix[i, j] == 1
            @constraint(m, x[i] + x[j] <= 1)
        end
    end
    w = [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0]
    @objective(m, Max, dot(w, x))
    optimize!(m)
    @assert MOI.get(m, MOI.ObjectiveValue()) ≈ 2.7

It produces this output:

 #Open      #Closed         Incumbent             Best Bound        Time [s]  
================================================================================
     1           1                -                    3.70             1.50    
     3           3               0.90                  3.70             1.93    
     26          28              1.80                  1.70             1.99    

The incumbent should never be better than the best bound.

At the moment :Solved is only returned if the first solution found is optimal.

• Need a checkout_from_to!

In Killer sudokus it's much faster to split the tree into #value branches instead of 2 by choosing a middle element.
Maybe trying out to split it into two parts one with a single element and one representing the rest is more valuable. This reduces the overhead when having a large number of possibilities but reduces the number of stupid propagation steps which don't do anything useful.

At the moment it isn't possible to have more values than indices in all_different

Being able to use it as a JuMP solver

• Explain all options of the solver
• List of all constraint and objective types

• doc strings for every funtion
• use Documenter

Print out information of the current state as a table for problems that need longer to solve.

Currently the next variable is chosen based on number of possible values and how often it failed at that point (bt_infeasible)

• ABS
• Weighted degree heuristic (wdeg)
• dom / wdeg
• Impact based search

I'm thinking about renaming the package as it would sound like it's THE package for constraint programming if it gets an actual julia package. Some of you might know that I'm terrible at naming things... And yes currently there is no other constraint solver julia package but nevertheless it should be up for discussion here.
Based on previous help: Do you have some ideas @ccoffrin @shibumi ?
Current ideas:

• CPS.jl
• CoPS.jl
• CoPra.jl
• ConstraintProgramming.jl by @rschwarz

Measure solving time internally to be able to get the solve time via JuMP and MOI.

For the following problem:

# Variables
@variable(model, 1 <= x[1:10] <= 15, Int)

# Constraints
@constraint(model, sum(x[1:5]) >= 10)
@constraint(model, sum(x[6:10]) <= 15)
@constraint(model, x in CS.AllDifferentSet())

@objective(model, Max, sum(x))
optimize!(model)

The AllDifferentSet() only restricts sum(x) <= 105 but it could restrict sum(x[1:5]) to 65.

I assume that there can be a huge speed up if the constraints are ordered before pruning starts.
The ordering should depend on the function (all_different is slower than sum but might prune more). Fewer unfixed values are normally preferred (i.e smaller graph in all_different)

How many binary variables, integer variables
How many:

• Equality
• Inequality
• NotEqual
• Alldifferent
  constraints?

A variable can only be fixed by removing all other possibilities but not directly.
This is the case because we have the first_ptr which doesn't change in reverse_pruning. We need to have two pruning vectors to be able to handle that.

Try to get a feasible solution as fast as possible and only later try to optimize it.

Currently only == is supported and a >= b but not a+b+c >= d

Break out of backtracking after a defined time limit

The memory can be allocated once for each alldifferent constraint and then simply reused i.e in bipartite_cardinality_matching.

It might be due to the solver being tested first on Sudoku instances. When testing the solver on problems with non-integer coefficients, some errors occur, which can be fixed by widening the types.

However, in some places of the code, the value and index spaces are mixed up. An example with the has function:

function has(v::CS.Variable, x::Int)
    if x > v.max || x < v.min
        return false
    end
    ind = v.indices[x + v.offset]
    return v.first_ptr <= ind <= v.last_ptr
end

In the first part, x is used as a value, checking if the variable is between min and max. But in the second part, it is used as an index as x + v.offset. Using values and indices interchangeably will lead to bugs later (what if you have infinite, if you have float coefficients, etc).

Currently only x != y is supported but not x != 2.

I have a JuMP model where all variables are bounded and type Int (I had some Bin variables, and changed them to be Int with 0 lower bound and 1 upper bound, but that does not help).

If I run v = JuMP.all_variables(model) on my model then v has length 15272.

So the following error message is very strange:

julia> optimize!(model)
ERROR: Each variable must be an integer and bounded. Currently the variable index 15273 doesn't fulfill this requirements.
Stacktrace:
 [1] check_var_bounds at C:\Users\username\.julia\packages\ConstraintSolver\qrqj1\src\MOI_wrapper\variables.jl:23 [inlined]
 [2] optimize!(::ConstraintSolver.Optimizer) at C:\Users\username\.julia\packages\ConstraintSolver\qrqj1\src\MOI_wrapper\MOI_wrapper.jl:79
 [3] optimize!(::MathOptInterface.Bridges.LazyBridgeOptimizer{ConstraintSolver.Optimizer}) at C:\Users\username\.julia\packages\MathOptInterface\izyVf\src\Bridges\bridge_optimizer.jl:239
 [4] optimize!(::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.AbstractOptimizer,MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}) at C:\Users\username\.julia\packages\MathOptInterface\izyVf\src\Utilities\cachingoptimizer.jl:189
 [5] #optimize!#78(::Bool, ::Bool, ::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}, ::Function, ::Model, ::Nothing) at C:\Users\username\.julia\packages\JuMP\MsUSY\src\optimizer_interface.jl:141
 [6] optimize! at C:\Users\colin37\.julia\packages\JuMP\MsUSY\src\optimizer_interface.jl:111 [inlined] (repeats 2 times)
 [7] top-level scope at none:0

I don't understand what I might be doing wrong, so I'm logging this in the hope that my mistake is obvious to someone else.

My proposal for the package logo.

You might want to implement the ability to read FlatZinc models. This would open up a large library of MiniZinc models for testing.

Instead of returning just the first solution it would be nice to get all of them.
Maybe one by one such that one can call solve again to get the next possible or a different function name.

Maybe be able to save more logs of how things got pruned step by step which can be implemented in the visual tree representation. Need to be careful that this doesn't slow things down but will be handy for finding out where it can be improved or does something wrong.

• add_var! instead of addVar!
  and maybe others?

In general larger test cases would be helpful such that overhead on JuMP or simple measurement errors (some other task on the machine) are reduced.
Probably there are some NxN sudoku test cases out there...

Currently it splits into smallest value and rest by default.
A better strategy for optimization problems would be to make this dependent on the coefficient of the particular variable and whether it's minimizing or maximizing.
i.e positive coefficient in a maximization problem => branch split on :Biggest

Include an easy example in the readme and move Blog posts to the bottom.
Making it ready for v0.1.0 ;)

@JuliaRegistrator register()

The best bound can be way too optimistic if we have <= constraints.
I.e

    m = Model(with_optimizer(CS.Optimizer))
    @variable(m, 1 <= x[1:10] <= 9, Int)
    @constraint(m, sum(x) <= 25)
    @constraint(m, sum(x) >= 20)
    weights = [1,2,3,4,5,6,7,8,9,10]
    @objective(m, Max, sum(weights .* x))
    optimize!(m)

The objective is currently only considering one change but by limiting the sum to 25 this can be reduced by looking at the constraints when calculating the best bound.
Otherwise this will take forever...

Follow up to #83

I extended the example slightly - adding new constraints to make the search space smaller.
Unfortunately it makes it too small - Cbc is able to find the optimal solution, while ConstraintSolver claims the problem is infeasible. They can't both be right.

Updated code:

using JuMP
using ConstraintSolver
using Cbc # for testing

model = Model()


# Variables
@variable(model, 0 <= inclusion[h = 1:3] <= 1, Int);
@variable(model, 0 <= allocations[h = 1:3, a = 1:3] <= 1, Int);
@variable(model, 0 <= days[h = 1:3, a = 1:3] <= 5, Int);

# Constraints
@constraint(model, must_include[h = 1:3],
    sum(allocations[h,a] for a in 1:3) <= inclusion[h]
);
# at least n
@constraint(model, min_hospitals,
    sum(inclusion[h] for h in 1:3) >= 3
);
# every h must be allocated at most one a
@constraint(model, must_visit[h = 1:3],
    sum(allocations[h,a] for a in 1:3) <= 1
);
# every allocated h must have fewer than 5 days of visits per week
@constraint(model, max_visits[h = 1:3],
    sum(days[h, a] for a in 1:3) <= 5 * inclusion[h]
);
@constraint(model, min_visits[h = 1:3],
    2 * inclusion[h] <= sum(days[h, a] for a in 1:3)
);
# for each a, only have days if allocated
@constraint(model, alloc_days[h = 1:3, a = 1:3],
    days[h,a] <= 5*allocations[h,a]
);
# every aa must be allocated to at most 2 h
@constraint(model, max_allocs[a = 1:3],
    sum(allocations[h,a] for h in 1:3) <= 2
);

benefit = @expression(model,
    sum(days[h,a] * 5
    for h in 1:3, a in 1:3));


@objective(model, Max, benefit);
set_optimizer(model, with_optimizer(Cbc.Optimizer))
optimize!(model) # working
termination_status(model) # OPTIMAL::TerminationStatusCode = 1
set_optimizer(model, with_optimizer(ConstraintSolver.Optimizer))
optimize!(model) # consumes all RAM without finishing
termination_status(model) # INFEASIBLE::TerminationStatusCode = 2

Package status:

pkg> status
    Status `C:\Users\colin37\Documents\Projects\IBS HBS Hospital Allocation\Project.toml`
  [336ed68f] CSV v0.5.23
  [9961bab8] Cbc v0.6.6
  [e0e52ebd] ConstraintSolver v0.1.0 #master (https://github.com/Wikunia/ConstraintSolver.jl)
  [a93c6f00] DataFrames v0.20.0
  [4076af6c] JuMP v0.20.1
  [fdbf4ff8] XLSX v0.5.8

Support for:

• 2x+x+y == 5 => 3x+y == 5
• 2x+y == z => 2x+y-z == 0

At the moment it's not really possible to add constraints. This would need to delete all previously feasible but now infeasible solutions. If a prev feasible solution is still feasible it can be returned otherwise a new search needs to be created but prev infeasible solutions are infeasible therefore they can be ignored.

Related to #56

I had a problem with floating coefficients, which were [1.0, 2.0, 3.0], they get converted to Int silently, which only errors if the coefficient is non-integral

Check if everything is deterministic by comparing logs for example.

Currently bounds are only really computed if we have positive coefficients in the objective and in the constraint.

As mentioned by @matbesancon it isn't a good idea to have the type Function in constraints like:

mutable struct LinearConstraint{T <: Real} <: Constraint
    idx                 :: Int
    fct                 :: Function
...

because of dynamic dispatching this will be slower. The idea is to have a similar structure to MOI instead such that new constraints provide two functions:
prune_constraint(com, v::MOI.VectorOfVariables, set) for example or
prune_constraint(com, func:MOI.ScalarAffineFunction, set). As well as a
still_feasible(com,func,set, value, index) function in contrast to the current functions:

function all_different(com::CS.CoM, constraint::BasicConstraint; logs = true)
function all_different(com::CoM, constraint::Constraint, value::Int, index::Int)

The MatrixNetworks.jl bipartite matching is a weighted bipartite matching which is more complicated than our actual goal.

Get only the open node that needs to be processed by filtering and minimum or maximum or simply iterating over it once. More memory and time efficient than a full sort. Should be noticeable in graph coloring when more than enough colors are available.

• maximization problem
• linear objective function