Wikunia commented 3 years ago

First draft of #185

Info:

Maybe there is a fast way to actually remove the != constraints. Currently they are only deactivated which shouldn't be too bad I think.
- splice com.constraints and recalculating the subscription should be fine.
- splice doesn't seem to be the best idea if constraints somehow rely on the ids of others like with sub_constraint_idx
- resetting subscription should work though

Bugfixes needed:

[x] Let all_different fail if clique is bigger than number of colors More generally if no match can be found because of m > n
[x] One should us the lp solver also for single variable constraints to have good bounds
- This can slow down the search process maybe one can improve this by not solving the lp every time? :thinking:
[x] The best bound here should be the size of the maximum clique. For this one probably needs to combine the .>= constraint for the max color into a vector constraint and compute extra bounds for biggest value in smallest all different i.e when we have 4 out of 1-9: [1,2,3,4] => 4 and [6,7,8,9] => 6.
[x] Compat entry for LightGraphs
[x] Automatically combine >= constraints into a GeqSet.

Wikunia commented 3 years ago

Benchmark Report for ConstraintSolver

Job Properties

Time of benchmarks:
- Target: 23 Nov 2020 - 16:59
- Baseline: 23 Nov 2020 - 17:10
Package commits:
- Target: 33a0dc
- Baseline: e6114c
Julia commits:
- Target: 96786e
- Baseline: 96786e
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
`["graph_coloring", "US_50colors"]`	0.93 (5%) :white_check_mark:	1.03 (1%) :x:
`["graph_coloring", "US_50colors+equal"]`	0.93 (5%) :white_check_mark:	1.04 (1%) :x:
`["graph_coloring", "US_8+equal"]`	0.93 (5%) :white_check_mark:	1.03 (1%) :x:
`["graph_coloring", "le450_5d"]`	0.99 (5%)	8.76 (1%) :x:
`["graph_coloring", "queen7_7"]`	0.17 (5%) :white_check_mark:	0.59 (1%) :white_check_mark:
`["killer_sudoku", "niall_5500"]`	1.05 (5%) :x:	1.00 (1%)
`["lp", "issue_83"]`	0.97 (5%)	0.97 (1%) :white_check_mark:
`["sudoku", "top95_1"]`	1.07 (5%) :x:	1.00 (1%)
`["sudoku", "top95_11"]`	1.06 (5%) :x:	1.00 (1%)
`["sudoku", "top95_16"]`	1.06 (5%) :x:	1.00 (1%)
`["sudoku", "top95_21"]`	1.06 (5%) :x:	1.00 (1%)
`["sudoku", "top95_26"]`	1.06 (5%) :x:	1.00 (1%)
`["sudoku", "top95_31"]`	1.06 (5%) :x:	1.00 (1%)
`["sudoku", "top95_36"]`	1.07 (5%) :x:	1.00 (1%)
`["sudoku", "top95_41"]`	1.07 (5%) :x:	1.00 (1%)
`["sudoku", "top95_46"]`	1.06 (5%) :x:	1.00 (1%)
`["sudoku", "top95_51"]`	1.06 (5%) :x:	1.00 (1%)
`["sudoku", "top95_56"]`	1.06 (5%) :x:	1.00 (1%)
`["sudoku", "top95_6"]`	1.07 (5%) :x:	1.00 (1%)
`["sudoku", "top95_61"]`	1.06 (5%) :x:	1.00 (1%)
`["sudoku", "top95_71"]`	1.06 (5%) :x:	1.00 (1%)
`["sudoku", "top95_76"]`	1.06 (5%) :x:	1.00 (1%)
`["sudoku", "top95_81"]`	1.06 (5%) :x:	1.00 (1%)
`["sudoku", "top95_86"]`	1.06 (5%) :x:	1.00 (1%)
`["sudoku", "top95_91"]`	1.06 (5%) :x:	1.00 (1%)

Benchmark Group List

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

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

Julia versioninfo

Target

Julia Version 1.5.0
Commit 96786e22cc (2020-08-01 23:44 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
      "Arch Linux"
  uname: Linux 5.9.9-arch1-1 #1 SMP PREEMPT Wed, 18 Nov 2020 19:52:04 +0000 x86_64 unknown
  CPU: Intel(R) Xeon(R) CPU E5-1650 0 @ 3.20GHz: 
                 speed         user         nice          sys         idle          irq
       #1-12  2924 MHz     228754 s         47 s      11209 s    6029657 s        892 s

  Memory: 46.98863983154297 GB (45873.34375 MB free)
  Uptime: 5227.0 sec
  Load Avg:  1.0  1.00927734375  0.93359375
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, sandybridge)

Baseline

Julia Version 1.5.0
Commit 96786e22cc (2020-08-01 23:44 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
      "Arch Linux"
  uname: Linux 5.9.9-arch1-1 #1 SMP PREEMPT Wed, 18 Nov 2020 19:52:04 +0000 x86_64 unknown
  CPU: Intel(R) Xeon(R) CPU E5-1650 0 @ 3.20GHz: 
                 speed         user         nice          sys         idle          irq
       #1-12  1558 MHz     294760 s         47 s      13434 s    6769415 s       1034 s

  Memory: 46.98863983154297 GB (45922.67578125 MB free)
  Uptime: 5901.0 sec
  Load Avg:  1.27978515625  1.10888671875  1.0263671875
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, sandybridge)

Wikunia commented 3 years ago

Benchmark Report for ConstraintSolver

Job Properties

Time of benchmarks:
- Target: 24 Nov 2020 - 17:44
- Baseline: 24 Nov 2020 - 17:55
Package commits:
- Target: a36008
- Baseline: 4e14d3
Julia commits:
- Target: 96786e
- Baseline: 96786e
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
`["graph_coloring", "US_50colors"]`	1.04 (5%)	1.10 (1%) :x:
`["graph_coloring", "US_50colors+equal"]`	0.97 (5%)	1.01 (1%) :x:
`["graph_coloring", "US_8+equal"]`	0.99 (5%)	1.16 (1%) :x:
`["graph_coloring", "le450_5d"]`	1.01 (5%)	10.90 (1%) :x:
`["graph_coloring", "queen7_7"]`	0.06 (5%) :white_check_mark:	0.22 (1%) :white_check_mark:
`["killer_sudoku", "niall_5500"]`	1.08 (5%) :x:	1.00 (1%)
`["killer_sudoku", "niall_5500_special"]`	1.05 (5%) :x:	1.00 (1%)
`["killer_sudoku", "niall_5501"]`	1.07 (5%) :x:	1.00 (1%)
`["killer_sudoku", "niall_5501_special"]`	1.06 (5%) :x:	1.00 (1%)
`["lp", "issue_83"]`	1.00 (5%)	0.98 (1%) :white_check_mark:
`["sudoku", "top95_1"]`	1.14 (5%) :x:	1.03 (1%) :x:
`["sudoku", "top95_11"]`	1.10 (5%) :x:	1.01 (1%) :x:
`["sudoku", "top95_16"]`	1.10 (5%) :x:	1.01 (1%) :x:
`["sudoku", "top95_21"]`	1.13 (5%) :x:	1.03 (1%) :x:
`["sudoku", "top95_26"]`	1.13 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_31"]`	1.10 (5%) :x:	1.01 (1%) :x:
`["sudoku", "top95_36"]`	1.14 (5%) :x:	1.03 (1%) :x:
`["sudoku", "top95_41"]`	1.12 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_46"]`	1.12 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_51"]`	1.11 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_56"]`	1.10 (5%) :x:	1.01 (1%) :x:
`["sudoku", "top95_6"]`	1.14 (5%) :x:	1.03 (1%) :x:
`["sudoku", "top95_61"]`	1.12 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_66"]`	1.09 (5%) :x:	1.01 (1%)
`["sudoku", "top95_71"]`	1.12 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_76"]`	1.12 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_81"]`	1.12 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_86"]`	1.12 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_91"]`	1.11 (5%) :x:	1.02 (1%) :x:

Benchmark Group List

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

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

Julia versioninfo

Target

Julia Version 1.5.0
Commit 96786e22cc (2020-08-01 23:44 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
      "Arch Linux"
  uname: Linux 5.9.9-arch1-1 #1 SMP PREEMPT Wed, 18 Nov 2020 19:52:04 +0000 x86_64 unknown
  CPU: Intel(R) Xeon(R) CPU E5-1650 0 @ 3.20GHz: 
                 speed         user         nice          sys         idle          irq
       #1-12  1678 MHz     131891 s    4586801 s     159971 s   27811085 s      20351 s

  Memory: 46.98863983154297 GB (45103.375 MB free)
  Uptime: 27272.0 sec
  Load Avg:  1.04296875  1.09619140625  0.77294921875
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, sandybridge)

Baseline

Julia Version 1.5.0
Commit 96786e22cc (2020-08-01 23:44 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
      "Arch Linux"
  uname: Linux 5.9.9-arch1-1 #1 SMP PREEMPT Wed, 18 Nov 2020 19:52:04 +0000 x86_64 unknown
  CPU: Intel(R) Xeon(R) CPU E5-1650 0 @ 3.20GHz: 
                 speed         user         nice          sys         idle          irq
       #1-12  1629 MHz     198255 s    4586801 s     162204 s   28552474 s      20500 s

  Memory: 46.98863983154297 GB (45036.19921875 MB free)
  Uptime: 27948.0 sec
  Load Avg:  1.279296875  1.12841796875  0.98388671875
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, sandybridge)

codecov[bot] commented 3 years ago

Codecov Report

Merging #188 (87412bf) into master (23f8ce3) will increase coverage by 0.00%. The diff coverage is 98.55%.

@@           Coverage Diff            @@
##           master     #188    +/-   ##
========================================
  Coverage   96.66%   96.67%            
========================================
  Files          34       35     +1     
  Lines        2851     3006   +155     
========================================
+ Hits         2756     2906   +150     
- Misses         95      100     +5

Impacted Files	Coverage Δ
src/lp_model.jl	`92.00% <0.00%> (ø)`
src/type_inits.jl	`94.28% <ø> (ø)`
src/simplify.jl	`98.06% <98.75%> (+0.73%)`	:arrow_up:
src/ConstraintSolver.jl	`98.68% <100.00%> (-0.98%)`	:arrow_down:
src/MOI_wrapper/constraints.jl	`100.00% <100.00%> (ø)`
src/constraints/all_different.jl	`100.00% <100.00%> (ø)`
src/constraints/geqset.jl	`100.00% <100.00%> (ø)`
src/objective.jl	`96.20% <100.00%> (-0.10%)`	:arrow_down:
src/options.jl	`100.00% <100.00%> (ø)`
src/pruning.jl	`100.00% <100.00%> (ø)`
... and 5 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 23f8ce3...87412bf. Read the comment docs.

Wikunia commented 3 years ago

Add some docstrings before merging

Wikunia commented 3 years ago

Benchmark Report for ConstraintSolver

Job Properties

Time of benchmarks:
- Target: 27 Nov 2020 - 18:15
- Baseline: 27 Nov 2020 - 18:26
Package commits:
- Target: 87412b
- Baseline: 23f8ce
Julia commits:
- Target: 96786e
- Baseline: 96786e
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
`["graph_coloring", "US_50colors"]`	1.02 (5%)	1.10 (1%) :x:
`["graph_coloring", "US_50colors+equal"]`	0.95 (5%)	1.01 (1%) :x:
`["graph_coloring", "US_8+equal"]`	0.96 (5%)	1.16 (1%) :x:
`["graph_coloring", "le450_5d"]`	0.88 (5%) :white_check_mark:	10.85 (1%) :x:
`["graph_coloring", "queen7_7"]`	0.05 (5%) :white_check_mark:	0.22 (1%) :white_check_mark:
`["killer_sudoku", "niall_5500"]`	1.06 (5%) :x:	1.00 (1%)
`["killer_sudoku", "niall_5501"]`	1.05 (5%) :x:	1.00 (1%)
`["sudoku", "top95_1"]`	1.12 (5%) :x:	1.03 (1%) :x:
`["sudoku", "top95_11"]`	1.08 (5%) :x:	1.01 (1%) :x:
`["sudoku", "top95_16"]`	1.09 (5%) :x:	1.01 (1%) :x:
`["sudoku", "top95_21"]`	1.12 (5%) :x:	1.03 (1%) :x:
`["sudoku", "top95_26"]`	1.11 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_31"]`	1.08 (5%) :x:	1.01 (1%) :x:
`["sudoku", "top95_36"]`	1.12 (5%) :x:	1.03 (1%) :x:
`["sudoku", "top95_41"]`	1.10 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_46"]`	1.10 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_51"]`	1.09 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_56"]`	1.08 (5%) :x:	1.01 (1%) :x:
`["sudoku", "top95_6"]`	1.12 (5%) :x:	1.03 (1%) :x:
`["sudoku", "top95_61"]`	1.10 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_66"]`	1.07 (5%) :x:	1.01 (1%)
`["sudoku", "top95_71"]`	1.10 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_76"]`	1.10 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_81"]`	1.10 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_86"]`	1.10 (5%) :x:	1.02 (1%) :x:
`["sudoku", "top95_91"]`	1.09 (5%) :x:	1.02 (1%) :x:

Benchmark Group List

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

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

Julia versioninfo

Target

Julia Version 1.5.0
Commit 96786e22cc (2020-08-01 23:44 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
      "Arch Linux"
  uname: Linux 5.9.10-arch1-1 #1 SMP PREEMPT Sun, 22 Nov 2020 14:16:59 +0000 x86_64 unknown
  CPU: Intel(R) Xeon(R) CPU E5-1650 0 @ 3.20GHz: 
                 speed         user         nice          sys         idle          irq
       #1-12  1448 MHz     373429 s        749 s      27982 s   18792629 s       3156 s

  Memory: 46.98863983154297 GB (42331.08984375 MB free)
  Uptime: 16007.0 sec
  Load Avg:  1.06005859375  1.0390625  0.890625
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, sandybridge)

Baseline

Julia Version 1.5.0
Commit 96786e22cc (2020-08-01 23:44 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
      "Arch Linux"
  uname: Linux 5.9.10-arch1-1 #1 SMP PREEMPT Sun, 22 Nov 2020 14:16:59 +0000 x86_64 unknown
  CPU: Intel(R) Xeon(R) CPU E5-1650 0 @ 3.20GHz: 
                 speed         user         nice          sys         idle          irq
       #1-12  1695 MHz     439213 s        749 s      30110 s   19527288 s       3325 s

  Memory: 46.98863983154297 GB (43496.234375 MB free)
  Uptime: 16677.0 sec
  Load Avg:  1.1455078125  1.15966796875  1.05322265625
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, sandybridge)

Wikunia / ConstraintSolver.jl

Use cliques for != #188

Benchmark Report for ConstraintSolver

Job Properties

Results

Benchmark Group List

Julia versioninfo

Target

Baseline

Benchmark Report for ConstraintSolver

Job Properties

Results

Benchmark Group List

Julia versioninfo

Target

Baseline

Codecov Report

Benchmark Report for ConstraintSolver

Job Properties

Results

Benchmark Group List

Julia versioninfo

Target

Baseline