Feature priority queue

[Wikunia]

Implementation of #194 + removing further pruning for the following reasons:

A node that was stopped because of further pruning still creates two children even though it might be infeasible. Additionally pruning has to be done at a later step in both children which potentially increases running time.

[codecov[bot]]

Codecov Report

Merging #199 (c804c6b) into master (59134e4) will decrease coverage by 0.11%. The diff coverage is 91.54%.

@@            Coverage Diff             @@
##           master     #199      +/-   ##
==========================================
- Coverage   96.71%   96.59%   -0.12%     
==========================================
  Files          36       36              
  Lines        3072     3113      +41     
==========================================
+ Hits         2971     3007      +36     
- Misses        101      106       +5     

Impacted Files	Coverage Δ
src/type_inits.jl	94.44% <ø> (ø)
src/traversing.jl	92.77% <85.18%> (-4.53%)	:arrow_down:
src/types.jl	97.40% <90.90%> (-2.60%)	:arrow_down:
src/ConstraintSolver.jl	98.72% <100.00%> (+0.03%)	:arrow_up:
src/options.jl	100.00% <100.00%> (ø)
src/simplify.jl	98.70% <0.00%> (+0.64%)	:arrow_up:

---

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 59134e4...c804c6b. Read the comment docs.

[Wikunia]

Benchmark Report for ConstraintSolver

Job Properties

• Time of benchmarks:
  • Target: 7 Dec 2020 - 19:52
  • Baseline: 7 Dec 2020 - 20:04
• Package commits:
  • Target: e23085
  • Baseline: 38b19a
• 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
["eternity", "5x5_opt_ind"]	1.11 (5%) :x:	1.14 (1%) :x:
["eternity", "6x5"]	0.85 (5%) :white_check_mark:	1.00 (1%)
["killer_sudoku", "niall_5501_special"]	0.73 (5%) :white_check_mark:	1.01 (1%)
["lp", "issue_83"]	1.06 (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.12-arch1-1 #1 SMP PREEMPT Wed, 02 Dec 2020 16:14:56 +0000 x86_64 unknown
  CPU: Intel(R) Xeon(R) CPU E5-1650 0 @ 3.20GHz: 
                 speed         user         nice          sys         idle          irq
       #1-12  1638 MHz    1751053 s       1675 s     350231 s   12994296 s     105967 s

  Memory: 46.9886360168457 GB (37999.91015625 MB free)
  Uptime: 12723.0 sec
  Load Avg:  1.84130859375  1.78759765625  1.5029296875
  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.12-arch1-1 #1 SMP PREEMPT Wed, 02 Dec 2020 16:14:56 +0000 x86_64 unknown
  CPU: Intel(R) Xeon(R) CPU E5-1650 0 @ 3.20GHz: 
                 speed         user         nice          sys         idle          irq
       #1-12  2720 MHz    1854244 s       1684 s     364896 s   13766856 s     110181 s

  Memory: 46.9886360168457 GB (37953.77734375 MB free)
  Uptime: 13462.0 sec
  Load Avg:  1.88916015625  1.8134765625  1.68017578125
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, sandybridge)

[Wikunia]

To make this actually calling the same order as before the Priority structs should contain the backtrack idx for the last check in the isless function.

[Wikunia]

Does not seem to be slower or faster but the tests are all relatively small. Will make a benchmark set of eternity puzzles similar to the graph color ones. There the constraints should be faster and more backtrack objects are created.

[Wikunia]

Is indeed much better for bigger eternity puzzles with around ~300,000 closed nodes.