Wikunia commented 3 years ago

First part of #205 but only for the right hand side.

Currently this does only parsing stuff and creating the AndConstraint. It also obviously only implements && for now and not ||. Todo:

[x] Implement the usual constraint functions
[x] Somehow understand why two or more && seem to create extra variables
[x] Bridge to support >= and >
- [X] LHS
- [X] RHS
- [x] Both LHS and RHS (figure out why this doesn't work atm)
- Probably do all in a single run for a certain subbridge to avoid creating too many subsubsubbridges or some kind of recursion
- [x] For several && constraints
[x] test cases
- [X] Unit tests for reified
- [x] Unit tests inside indicator
- [x] Small real test case
- [x] Test with several && in one constraint
- [x] Test with brackets around several &&
[x] Documentation changes?
[x] Changelog
[x] Check if active in init_constraint!

I'll most likely create other PRs to support more of #205 in the future. This PR might already be enough for #213 though

codecov[bot] commented 3 years ago

Codecov Report

Merging #244 (0e6d1ef) into master (d5e7753) will increase coverage by 0.16%. The diff coverage is 97.94%.

@@            Coverage Diff             @@
##           master     #244      +/-   ##
==========================================
+ Coverage   96.51%   96.67%   +0.16%     
==========================================
  Files          39       48       +9     
  Lines        3439     3761     +322     
==========================================
+ Hits         3319     3636     +317     
- Misses        120      125       +5

Impacted Files	Coverage Δ
src/MOI_wrapper/Bridges/strictly_greater_than.jl	`66.66% <ø> (ø)`
src/constraints/all_different.jl	`100.00% <ø> (ø)`
src/constraints/equal_set.jl	`95.60% <ø> (ø)`
src/constraints/geqset.jl	`100.00% <ø> (ø)`
src/constraints/linear_constraints.jl	`96.98% <ø> (ø)`
src/constraints/table.jl	`99.23% <ø> (ø)`
src/MOI_wrapper/or.jl	`89.47% <89.47%> (ø)`
src/MOI_wrapper/and.jl	`90.47% <90.47%> (ø)`
src/MOI_wrapper/Bridges/bool.jl	`96.66% <96.66%> (ø)`
src/constraints/or.jl	`97.72% <97.72%> (ø)`
... and 24 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 d5e7753...0e6d1ef. Read the comment docs.

Wikunia commented 3 years ago

Hi @hakank,

this PR is ready for your tests :smile:

It implements && inside reified and indicator constraints but only on the right hand side of the => or :=.

One example is your alldifferent except 0 from #202 which can be done by using a reified constraint instead of directly having the && at the left hand side.

m = Model(CS.Optimizer)
@variable(m, 0 <= x[1:5] <= 3, Int)
len = length(x)
for i in 2:len, j in 1:i-1
    b = @variable(m, binary=true)
    @constraint(m, b := {x[i] != 0 && x[j] != 0})
    @constraint(m, b => {x[i] != x[j]} ) 
end
@objective(m, Max, sum(x))
optimize!(m)

I only implement <= and < directly and >= and > are transformed. That was the most challenging part of this PR so that would benefit most from testing.

I'll of course test this further in the next couple of days but I think it's ready for your review.

Thanks in advance!

hakank commented 3 years ago

I have now checked all my models (http://hakank.org/julia/constraints/ ), and changed the following to use && instead:

http://hakank.org/julia/constraints/a_round_of_golf.jl http://hakank.org/julia/constraints/breaking_news.jl http://hakank.org/julia/constraints/monks_and_doors.jl http://hakank.org/julia/constraints/tourist_site_competition.jl

http://hakank.org/julia/constraints/constraints_utils.jl (changed all_different_except_c) and is tested by http://hakank.org/julia/constraints/all_different_except_0.jl

I couldn't see any performance changes in these models.

There was, however one model that was much slower with && for some reason: http://hakank.org/julia/constraints/steiner_and.jl (compared with the original http://hakank.org/julia/constraints/steiner.jl Here is the diff:

23a24,26
>   This version use && instead of a couple of Bin variables, but it's 
>   very slow. Why?
> 
85,86c88,89
<             b1 = @variable(model, [1:n], Bin)
<             b2 = @variable(model, [1:n], Bin)
---
>             # b1 = @variable(model, [1:n], Bin)
>             # b2 = @variable(model, [1:n], Bin)
89,92c92,95
<                 @constraint(model, b1[k] := {x[i,k] == 1})
<                 @constraint(model, b2[k] := {x[j,k] == 1})
<                 @constraint(model, b[k] := { b1[k] + b2[k] == 2 })
<                 # @constraint(model, b[k] := { x[i,k] == 1 && x[j,k] == 1 })
---
>                 # @constraint(model, b1[k] := {x[i,k] == 1})
>                 # @constraint(model, b2[k] := {x[j,k] == 1})
>                 # @constraint(model, b[k] := { b1[k] + b2[k] == 2 })
>                 @constraint(model, b[k] := { x[i,k] == 1 && x[j,k] == 1 })

The original model (steiner.jl) solved n=[3,7,9] in 0.25s, 0.04s, 0.21s respectively. The && variant solved n=3 in 0.19s but timed out (>16s) on n=7.

Wikunia commented 3 years ago

Regarding your test case which is slower. I mentioned it in our chat but to have it here as well: This is due to the fact that I haven't implement the "anti" constraint yet but that should be easy to add after #245 is tested and merged after this. :wink: Thanks again a lot for testing!

Wikunia commented 3 years ago

Benchmark Report for ConstraintSolver

Job Properties

Time of benchmarks:
- Target: 12 Feb 2021 - 16:55
- Baseline: 12 Feb 2021 - 17:10
Package commits:
- Target: cd744a
- Baseline: c97c28
Julia commits:
- Target: 788b2c
- Baseline: 788b2c
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_all"]`	1.05 (5%) :x:	1.00 (1%)
`["eternity", "5x5_opt"]`	0.82 (5%) :white_check_mark:	1.00 (1%)
`["eternity", "5x5_opt_ind"]`	1.06 (5%) :x:	1.00 (1%)
`["eternity", "5x5_opt_rei"]`	1.07 (5%) :x:	1.00 (1%)
`["eternity", "6x5"]`	1.07 (5%) :x:	1.00 (1%)
`["eternity", "6x5_ABS"]`	0.82 (5%) :white_check_mark:	1.00 (1%)
`["graph_coloring", "US_50colors+equal"]`	1.05 (5%) :x:	1.01 (1%)
`["graph_coloring", "US_50colors+equal_ABS"]`	0.94 (5%) :white_check_mark:	1.00 (1%)
`["graph_coloring", "US_8+equal"]`	0.85 (5%) :white_check_mark:	1.01 (1%)
`["graph_coloring", "US_8+equal_ABS"]`	0.93 (5%) :white_check_mark:	1.00 (1%)
`["graph_coloring", "le450_5d"]`	1.11 (5%) :x:	1.00 (1%)
`["graph_coloring", "queen7_7"]`	1.11 (5%) :x:	1.00 (1%)
`["killer_sudoku", "niall_5501_special"]`	0.88 (5%) :white_check_mark:	1.00 (1%)
`["lp", "issue_83"]`	1.01 (5%)	1.01 (1%) :x:
`["scheduling", "all_different_except_0_len12"]`	0.93 (5%) :white_check_mark:	1.00 (1%)
`["scheduling", "furniture_moving"]`	0.93 (5%) :white_check_mark:	1.00 (1%)
`["scheduling", "organize_day"]`	1.03 (5%)	1.02 (1%) :x:
`["sudoku", "top95_1"]`	1.12 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_11"]`	1.17 (5%) :x:	1.01 (1%)
`["sudoku", "top95_16"]`	0.95 (5%) :white_check_mark:	1.01 (1%)
`["sudoku", "top95_21"]`	1.06 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_26"]`	0.94 (5%) :white_check_mark:	1.02 (1%) :x:
`["sudoku", "top95_31"]`	1.22 (5%) :x:	1.01 (1%)
`["sudoku", "top95_36"]`	1.08 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_41"]`	1.01 (5%)	1.01 (1%) :x:
`["sudoku", "top95_46"]`	1.13 (5%) :x:	1.01 (1%) :x:
`["sudoku", "top95_51"]`	1.05 (5%)	1.01 (1%) :x:
`["sudoku", "top95_56"]`	1.05 (5%) :x:	1.01 (1%)
`["sudoku", "top95_6"]`	1.01 (5%)	1.02 (1%) :x:
`["sudoku", "top95_61"]`	0.86 (5%) :white_check_mark:	1.01 (1%) :x:
`["sudoku", "top95_66"]`	0.91 (5%) :white_check_mark:	1.01 (1%)
`["sudoku", "top95_71"]`	1.06 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_76"]`	1.09 (5%) :x:	1.01 (1%) :x:
`["sudoku", "top95_81"]`	1.10 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_86"]`	1.03 (5%)	1.01 (1%) :x:
`["sudoku", "top95_91"]`	1.10 (5%) :x:	1.01 (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"]
["sudoku"]

Julia versioninfo

Target

Julia Version 1.5.3
Commit 788b2c77c1 (2020-11-09 13:37 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  uname: Linux 5.10.13-arch1-2 #1 SMP PREEMPT Sat, 06 Feb 2021 11:07:29 +0000 x86_64 unknown
  CPU: AMD Ryzen 7 PRO 4750U with Radeon Graphics: 
                 speed         user         nice          sys         idle          irq
       #1-16  1397 MHz    1851575 s    1584148 s     661709 s   27648504 s          0 s

  Memory: 38.482669830322266 GB (1459.4375 MB free)
  Uptime: 67071.0 sec
  Load Avg:  2.72998046875  2.5009765625  2.7802734375
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, znver2)

Baseline

Julia Version 1.5.3
Commit 788b2c77c1 (2020-11-09 13:37 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  uname: Linux 5.10.13-arch1-2 #1 SMP PREEMPT Sat, 06 Feb 2021 11:07:29 +0000 x86_64 unknown
  CPU: AMD Ryzen 7 PRO 4750U with Radeon Graphics: 
                 speed         user         nice          sys         idle          irq
       #1-16  1397 MHz    1962785 s    1649652 s     684176 s   28867718 s          0 s

  Memory: 38.482669830322266 GB (1306.19140625 MB free)
  Uptime: 67961.0 sec
  Load Avg:  2.1474609375  2.68505859375  2.8154296875
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, znver2)

Wikunia / ConstraintSolver.jl

Feature "And" constraint #244

Codecov Report

Benchmark Report for ConstraintSolver

Job Properties

Results

Benchmark Group List

Julia versioninfo

Target

Baseline