Wikunia commented 3 years ago

This PR adds the functionality of element constraint for a 1D constant standard Julia Vector.

The user can therefore now write things like T[x] == y where x is a variable as long as T is a Vector{Int}.

Syntax example

This code will sort the elements in c

    m = Model(CS.Optimizer)
    c = rand(1:1000, 50)
    @variable(m, 1 <= idx[1:length(c)] <= length(c), Int)
    @variable(m, minimum(c) <= val[1:length(c)] <= maximum(c), Int)
    for i in 1:length(c)-1
        @constraint(m, val[i] <= val[i+1])
    end
    for i in 1:length(c)
        @constraint(m, c[idx[i]] == val[i])
    end
    @constraint(m, idx in CS.AllDifferentSet())
    optimize!(m)

Closes #196

[x] Implement is_constraint_violated
[x] Implement constraint XNOR to combine it when inside ActivatorConstraint or OrConstraint. #259
- the XNOR will then be a global constraint and && will continue to be the inner constraint
[ ] Indicator and reified when element constraint in AndConstraint
[ ] Indicator and reified when element constraint in OrConstraint
[ ] Element constraint in || outside of ActivatorConstraint
[ ] More test cases
- [ ] in indicator
- [ ] in reified
[x] nice JuMP syntax with z == T[y]
[ ] refactoring

codecov[bot] commented 3 years ago

Codecov Report

Merging #213 (718aa7f) into master (72f4c36) will increase coverage by 0.00%. The diff coverage is 96.96%.

@@           Coverage Diff            @@
##           master     #213    +/-   ##
========================================
  Coverage   97.62%   97.62%            
========================================
  Files          52       54     +2     
  Lines        4328     4547   +219     
========================================
+ Hits         4225     4439   +214     
- Misses        103      108     +5

Impacted Files	Coverage Δ
src/ConstraintSolver.jl	`99.11% <ø> (+0.58%)`	:arrow_up:
src/constraints/indicator.jl	`100.00% <ø> (ø)`
src/util.jl	`96.40% <66.66%> (-2.06%)`	:arrow_down:
src/MOI_wrapper/element.jl	`88.88% <88.88%> (ø)`
src/constraints/element1Dconst.jl	`97.47% <97.47%> (ø)`
src/MOI_wrapper/MOI_wrapper.jl	`95.00% <100.00%> (+0.06%)`	:arrow_up:
src/MOI_wrapper/constraints.jl	`99.61% <100.00%> (+<0.01%)`	:arrow_up:
src/MOI_wrapper/util.jl	`100.00% <100.00%> (ø)`
src/constraints.jl	`100.00% <100.00%> (ø)`
src/constraints/activator_constraints.jl	`100.00% <100.00%> (ø)`
... and 6 more

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 72f4c36...718aa7f. Read the comment docs.

Wikunia commented 3 years ago

This does currently not work inside reified or indicator constraints because the constraint itself gets added to the entire model. I think based on #205 it would be good to support that one indicator can have several inner constraints and possibly a && or || between them. Example:

b := { T[y] == x + 1}

would be translated to:

b := { T[y] == z && z == x+1}

If the variable z is only used inside an inner constraint it will get removed from the model and instead added to the list of inner constraints.

Wikunia commented 3 years ago

This is finally in a stage which might be usable. If you want to play around with it @hakank please give it a go! It will not be merged for quite a bit as it needs more thorough testing and some refactoring so check it out whenever you have time. That would be highly appreciated.

Wikunia commented 3 years ago

I hope I figured it out now ...

    c = collect(1:5)
    crev = reverse(c)
    @variable(m, b, Bin)
    @constraint(m, b < 0.5)
    @variable(m, 1 <= idx <= length(c), Int)
    @constraint(m, b := { c[idx] == crev[idx]})

should be transformed into:

    c = collect(1:5)
    crev = reverse(c)
    @variable(m, b, Bin)
    @constraint(m, b < 0.5)
    @variable(m, 1 <= idx <= length(c), Int)
    @variable(m, 1 <= y <= 5, Int)
    @variable(m, 1 <= z <= 5, Int)
    @constraint(m, b := {!(([y, idx] in CS.Element1DConst(c))   ⊻ (y == z))})
    @constraint(m, b := {!(([z, idx] in CS.Element1DConst(crev)) ⊻ (y == z))})
    @constraint(m, b := { y == z })

so the global element constraint needs to be deactivated but the activator constraint itself stays as it is. Additionally an activator constraint gets added which uses an xnor constraint such that when it's activated both needs to be fulfilled due to the @constraint(m, b := { y == z }) and if it's deactivated the element constraint needs to be still fulfilled which limits the number of possible solutions to the one the user expects.

Wikunia commented 2 years ago

Should check is_deactivated before calling functions like reverse_pruning_constraint! make it into two functions one internal for the constraints with _ in front and one which checks whether it should actually be called

Wikunia commented 2 years ago

Benchmark Report for ConstraintSolver

Job Properties

Time of benchmarks:
- Target: 6 Feb 2022 - 15:07
- Baseline: 6 Feb 2022 - 15:21
Package commits:
- Target: 0d915c
- Baseline: f6332b
Julia commits:
- Target: ac5cc9
- Baseline: ac5cc9
Julia command flags:
- Target: -O3
- Baseline: -O3
Environment variables:
- Target: None
- Baseline: None

Results

A ratio greater than 1.0 denotes a possible regression (marked with :x:), while a ratio less than 1.0 denotes a possible improvement (marked with :white_check_mark:). Only significant results - results that indicate possible regressions or improvements - are shown below (thus, an empty table means that all benchmark results remained invariant between builds).

ID	time ratio	memory ratio
`["eternity", "5x5_opt_ind"]`	0.94 (5%) :white_check_mark:	1.02 (1%) :x:
`["eternity", "5x5_opt_rei"]`	1.01 (5%)	1.02 (1%) :x:
`["graph_coloring", "queen7_7"]`	1.06 (5%) :x:	1.00 (1%)
`["scheduling", "all_different_except_0_len10"]`	1.08 (5%) :x:	1.17 (1%) :x:
`["scheduling", "all_different_except_0_len12"]`	1.06 (5%) :x:	1.18 (1%) :x:
`["scheduling", "organize_day"]`	0.95 (5%)	1.02 (1%) :x:
`["steiner", "steiner_7"]`	1.08 (5%) :x:	1.03 (1%) :x:

Benchmark Group List

Here's a list of all the benchmark groups executed by this job:

["eternity"]
["graph_coloring"]
["killer_sudoku"]
["lp"]
["scheduling"]
["steiner"]
["sudoku"]

Julia versioninfo

Target

Julia Version 1.7.1
Commit ac5cc99908 (2021-12-22 19:35 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  uname: Linux 5.15.13-arch1-1 #1 SMP PREEMPT Wed, 05 Jan 2022 16:20:59 +0000 x86_64 unknown
  CPU: AMD Ryzen 7 PRO 4750U with Radeon Graphics: 
                 speed         user         nice          sys         idle          irq
       #1-16  2065 MHz     404920 s       1406 s      99820 s    2375552 s          0 s

  Memory: 38.47813034057617 GB (7096.03125 MB free)
  Uptime: 326427.12 sec
  Load Avg:  1.54  1.82  1.64
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, znver2)

Baseline

Julia Version 1.7.1
Commit ac5cc99908 (2021-12-22 19:35 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  uname: Linux 5.15.13-arch1-1 #1 SMP PREEMPT Wed, 05 Jan 2022 16:20:59 +0000 x86_64 unknown
  CPU: AMD Ryzen 7 PRO 4750U with Radeon Graphics: 
                 speed         user         nice          sys         idle          irq
       #1-16  1400 MHz     417434 s       1407 s     101168 s    2494941 s          0 s

  Memory: 38.47813034057617 GB (7270.90625 MB free)
  Uptime: 327264.44 sec
  Load Avg:  1.81  1.89  1.8
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, znver2)

hakank commented 2 years ago

Is this model expected to work (tested with #master version)?

n = 4
@variable(model, 1 <= x[1:n] <= n, Int)
@variable(model, 1 <= y[1:n] <= n, Int)
@variable(model, 1 <= p[1:n] <= n, Int)
@constraint(model, p in CS.AllDifferent())

for i in 1:n
  @constraint(model, x[p[i]] == y[i])
end

optimize!(model)

status = JuMP.termination_status(model)

It throws this error:

ERROR: LoadError: ArgumentError: invalid index: p[1] of type VariableRef
Stacktrace:
  [1] to_index(i::VariableRef)
    @ Base ./indices.jl:300
  [2] to_index(A::Vector{VariableRef}, i::VariableRef)
    @ Base ./indices.jl:277
  [3] to_indices
    @ ./indices.jl:333 [inlined]
  [4] to_indices
    @ ./indices.jl:325 [inlined]
  [5] getindex
    @ ./abstractarray.jl:1218 [inlined]
  [6] macro expansion
    @ ~/.julia/packages/MutableArithmetics/0Y9ZS/src/rewrite.jl:279 [inlined]
  [7] macro expansion
    @ ~/.julia/packages/JuMP/klrjG/src/macros.jl:676 [inlined]
  [8] element_1d_const_test(n::Int64, print_solutions::Bool, all_solutions::Bool, timeout::Int64)
    @ Main ~/julia/constraints/element_1d_test3.jl:74
  [9] element_1d_const_test(n::Int64, print_solutions::Bool, all_solutions::Bool)
    @ Main ~/julia/constraints/element_1d_test3.jl:26
 [10] top-level scope
    @ ~/julia/constraints/element_1d_test3.jl:102
 [11] include
    @ ./client.jl:451 [inlined]
 [12] top-level scope
    @ ./timing.jl:220 [inlined]

Wikunia commented 2 years ago

No unfortunately it isn't supported yet currently the array has to be constant. Your request is tracked here: #198

hakank commented 2 years ago

OK. Thanks for the clarification.

I tested some variants with constant arrays and found no problems.

Wikunia commented 2 years ago

Perfect thanks a lot for testing!

Wikunia / ConstraintSolver.jl

Feature element 1D const #213

Syntax example

Codecov Report

Benchmark Report for ConstraintSolver

Job Properties

Results

Benchmark Group List

Julia versioninfo

Target

Baseline