Repository: Wikunia/ConstraintSolver.jl (julia)

Issue:
Position of constant in a sum constraint matters (sometimes)
This is a magic square model where the position of `s` in the `sum` constraints give an `INFEASIBLE solution` if the first constraint (the rows constraint) in the `for` loop is stated as 
   `@constraint(model, sum(x[i,:]) == s) # INFEASIBLE`
but it works if it stated as 
  `@constraint(model, s == sum(x[i,:]))  # This works`

What I have understood there shouldn't be any restriction on the position of the `sum` in a constraints (i.e. LHS or RHS). 

For the second (column) constraint both ways work. 
It's the same problem with the first diagonal constraint where position of `s` matters, while the second diagonal constraint works either way.

Note that `s` is a constant (Int64). If `s` has been defined as a variable then there is no problem.

Also, I tested with a simple model with a single `sum` constraint, but then there's no problem where the `sum` is placed (LHS or RHS).

```
using ConstraintSolver, JuMP
const CS = ConstraintSolver

function magic_square(n=4,print_solutions=true,all_solutions=true)

    model = Model(optimizer_with_attributes(CS.Optimizer,   "all_solutions"=> all_solutions,
                                                            "logging"=>[],
                                                            "traverse_strategy"=>:BFS,
                                                            "branch_split"=>:InHalf,
                                                            "time_limit"=>3,                                        ))
                                        ))

    s = round(Int,n*(n^2 + 1) / 2) # The total for each row, column, and the two main diaginals
    @variable(model, 1 <= x[1:n,1:n] <= n^2, Int)
    @constraint(model, x[:] in CS.AllDifferentSet())

    for i in 1:n
        # Rows 
        # @constraint(model, s == sum(x[i,:]))  # This works
        @constraint(model, sum(x[i,:]) == s) # INFEASIBLE

        # Columns
        @constraint(model, sum(x[:,i]) == s) # This works
        # @constraint(model, s == sum(x[:,i])) # This works as well
    end

    # diagonals
    @constraint(model, s == sum([x[i,i] for i in 1:n])) # This works
    # @constraint(model, sum([x[i,i] for i in 1:n]) == s) # This yield INFEASIBLE solution

    @constraint(model, s == sum([x[i,n-i+1] for i in 1:n])) # This works
    # @constraint(model, sum([x[i,n-i+1] for i in 1:n]) == s) # This works as well

    optimize!(model)

    status = JuMP.termination_status(model)
    if status == MOI.OPTIMAL
        num_sols = MOI.get(model, MOI.ResultCount())
        println("num_sols:$num_sols\n")
        if print_solutions
            for sol in 1:num_sols
                println("solution #$sol")
                xx = convert.(Integer,JuMP.value.(x; result=sol))
                display(xx)
            end
        end
    else
        println("status:$status")
    end

    return status
end

print_solutions = true
all_solutions = false
@time magic_square(5,print_solutions,all_solutions)
```

Pull request description:
Fixes #226 

Fixes a bug in `simplify` which creates additional `==` constraints when both `==` and alldifferent are active.
In this case indices were used more than once to calculate the inner sum.

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 4a75c511..00a83f97 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,8 +1,9 @@
 # ConstrainSolver.jl - Changelog
 
 ## Unreleased 
+- **Dropped support for Julia v1.0 and v1.1**
 - Throw error if there is a dimension mismatch in a `TableSet`
-- Dropped support for Julia v1.0 and v1.1
+- Bugfix in `simplify!` check that one inner index isn't used more than once
 
 ## v0.5.3 (12th of December 2020)
 - Bugfix for optimization with reified and indicator constraints
diff --git a/Project.toml b/Project.toml
index e2972d28..c36e9be8 100644
--- a/Project.toml
+++ b/Project.toml
@@ -1,7 +1,7 @@
 name = "ConstraintSolver"
 uuid = "e0e52ebd-5523-408d-9ca3-7641f1cd1405"
 authors = ["Ole Kröger <o.kroeger@opensourc.es>"]
-version = "0.5.3"
+version = "0.6.0"
 
 [deps]
 DataStructures = "864edb3b-99cc-5e75-8d2d-829cb0a9cfe8"
diff --git a/src/simplify.jl b/src/simplify.jl
index ffb26d81..c992370d 100644
--- a/src/simplify.jl
+++ b/src/simplify.jl
@@ -240,6 +240,10 @@ This function checks all sum constraints which are completely inside of the alld
 function simplify_all_different_inner_equal_to(com, constraint::AllDifferentConstraint)
     @assert length(constraint.indices) == length(constraint.pvals)
     added_constraint_idxs = Int[]
+    # make sure that we don't use an index more than once
+    used_indices = falses(length(com.search_space))
+    # we don't try to maximize the sum here so one might be able to use
+    # a different constraint to start with to get a better sum.
     all_diff_sum = sum(constraint.pvals)
     in_sum = 0
     found_possible_constraint = false
@@ -251,11 +255,16 @@ function simplify_all_different_inner_equal_to(com, constraint::AllDifferentCons
         if isa(sub_constraint.fct, SAF) && isa(sub_constraint.set, MOI.EqualTo)
             # the coefficients must be all 1
             if all(t.coefficient == 1 for t in sub_constraint.fct.terms)
-                # compute sum inside all sum constraints
-                found_possible_constraint = true
-                in_sum += sub_constraint.set.value - sub_constraint.fct.constant
-                # for sum which are in alldifferent but not in sum constraints
-                outside_indices = setdiff(outside_indices, sub_constraint.indices)
+                # only use constraint if none of the indices was already used for
+                # computing the inner sum
+                if !any(used_indices[sub_constraint.indices])
+                    used_indices[sub_constraint.indices] .= true
+                    # compute sum inside all sum constraints
+                    found_possible_constraint = true
+                    in_sum += sub_constraint.set.value - sub_constraint.fct.constant
+                    # for sum which are in alldifferent but not in sum constraints
+                    outside_indices = setdiff(outside_indices, sub_constraint.indices)
+                end
             end
         end
     end


Test patch:
diff --git a/test/small_special.jl b/test/small_special.jl
index 41d4c9d4..4ef61ead 100644
--- a/test/small_special.jl
+++ b/test/small_special.jl
@@ -531,4 +531,44 @@
         @test JuMP.value(b) ≈ 0
     end
 
+    @testset "Magic Square 5x5" begin
+        n = 5
+        model = Model(optimizer_with_attributes(CS.Optimizer,
+                "traverse_strategy"=>:BFS,
+                "logging" => [],
+                "branch_split"=>:InHalf,
+                "time_limit"=>3,
+            )
+        )
+
+
+        # The total for each row, column, and the two main diaginals
+        s = round(Int,n*(n^2 + 1) / 2)
+        @variable(model, 1 <= x[1:n,1:n] <= n^2, Int)
+        @constraint(model, x[:] in CS.AllDifferentSet())
+
+        for i in 1:n
+            # Rows
+            @constraint(model, sum(x[i,:]) == s)
+
+            # Columns
+            @constraint(model, sum(x[:,i]) == s)
+        end
+
+        # diagonals
+        @constraint(model, sum([x[i,i] for i in 1:n]) == s)
+        @constraint(model, s == sum([x[i,n-i+1] for i in 1:n]))
+
+        optimize!(model)
+        status = JuMP.termination_status(model)
+        @test status == MOI.OPTIMAL
+        sol = convert.(Int,JuMP.value.(x))
+        for i=1:n
+            @test sum(sol[i,:]) == 65
+            @test sum(sol[:,i]) == 65
+        end
+        @test sum([sol[i,i] for i in 1:n]) == 65
+        @test sum([sol[i,n-i+1] for i in 1:n]) == 65
+        @test allunique(sol)
+    end
 end