search

Wikunia / ConstraintSolver.jl

ConstraintSolver in Julia: Blog posts ->
https://opensourc.es/blog/constraint-solver-1
MIT License
136 stars 13 forks source link

Feature xor + xnor #264

Closed Wikunia closed 3 years ago

Wikunia commented 3 years ago

This will be needed to make the element constraint work in activator constraints. #213 Implements #259

Possible new constraints

@constraint(m, !(x <= 2))
@constraint(m, !((x <= 2) ⊻ (y >= 4)))
@constraint(m, b := {!(x <= 2 && y >= 4)})

Needs a good interface to get the anti constraint of boolean functions. Either via (x || y) -> (!x && !y) or via (x \xor y) -> (x \xnor y) such that the anti set of xor is xnor but the anti set of || is not existing. Nevertheless the anti_constraint can still be constructed. I'll think about naming those things accordingly :smile: and will think about a good structure to implement this. I might call && <-> || the demorgancomplement and the other the complement and in general change from `antitocomplement`

This includes

codecov[bot] commented 3 years ago

Codecov Report

Merging #264 (55e5fa5) into master (1a8b397) will increase coverage by 0.13%. The diff coverage is 97.75%.

Impacted file tree graph

@@            Coverage Diff             @@
##           master     #264      +/-   ##
==========================================
+ Coverage   97.34%   97.47%   +0.13%     
==========================================
  Files          48       53       +5     
  Lines        4136     4389     +253     
==========================================
+ Hits         4026     4278     +252     
- Misses        110      111       +1
Impacted Files Coverage Δ
src/ConstraintSolver.jl 98.57% <ø> (-0.57%) :arrow_down:
src/constraints/equal_set.jl 95.87% <ø> (ø)
src/constraints/activator_constraints.jl 89.79% <44.44%> (ø)
src/MOI_wrapper/complement.jl 91.66% <91.66%> (ø)
src/util.jl 97.45% <95.45%> (-0.66%) :arrow_down:
src/MOI_wrapper/Bridges/complement.jl 97.05% <97.05%> (ø)
src/constraints/xnor.jl 97.26% <97.26%> (ø)
src/MOI_wrapper/constraints.jl 99.55% <98.66%> (+<0.01%) :arrow_up:
src/MOI_wrapper/Bridges/bool.jl 100.00% <100.00%> (+2.67%) :arrow_up:
src/MOI_wrapper/Bridges/indicator.jl 100.00% <100.00%> (ø)
... and 31 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 1a8b397...55e5fa5. Read the comment docs.

Wikunia commented 3 years ago

Benchmark Report for ConstraintSolver

Job Properties

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%)
["graph_coloring", "US_50colors"] 1.10 (5%) :x: 1.03 (1%) :x:
["graph_coloring", "US_50colors+equal"] 1.04 (5%) 1.03 (1%) :x:
["graph_coloring", "US_8+equal"] 1.09 (5%) :x: 1.03 (1%) :x:
["lp", "issue_83"] 1.15 (5%) :x: 1.07 (1%) :x:
["scheduling", "all_different_except_0_len10"] 0.25 (5%) :white_check_mark: 0.26 (1%) :white_check_mark:
["scheduling", "all_different_except_0_len12"] 0.31 (5%) :white_check_mark: 0.32 (1%) :white_check_mark:
["scheduling", "furniture_moving"] 0.59 (5%) :white_check_mark: 0.48 (1%) :white_check_mark:
["scheduling", "organize_day"] 1.24 (5%) :x: 1.11 (1%) :x:
["steiner", "steiner_7"] 1.03 (5%) 0.96 (1%) :white_check_mark:
["sudoku", "top95_1"] 1.29 (5%) :x: 1.14 (1%) :x:
["sudoku", "top95_11"] 1.18 (5%) :x: 1.07 (1%) :x:
["sudoku", "top95_16"] 1.19 (5%) :x: 1.07 (1%) :x:
["sudoku", "top95_21"] 1.30 (5%) :x: 1.13 (1%) :x:
["sudoku", "top95_26"] 1.31 (5%) :x: 1.13 (1%) :x:
["sudoku", "top95_31"] 1.13 (5%) :x: 1.07 (1%) :x:
["sudoku", "top95_36"] 1.35 (5%) :x: 1.14 (1%) :x:
["sudoku", "top95_41"] 1.26 (5%) :x: 1.11 (1%) :x:
["sudoku", "top95_46"] 1.32 (5%) :x: 1.11 (1%) :x:
["sudoku", "top95_51"] 1.25 (5%) :x: 1.09 (1%) :x:
["sudoku", "top95_56"] 1.15 (5%) :x: 1.06 (1%) :x:
["sudoku", "top95_6"] 1.39 (5%) :x: 1.14 (1%) :x:
["sudoku", "top95_61"] 1.29 (5%) :x: 1.11 (1%) :x:
["sudoku", "top95_66"] 1.10 (5%) :x: 1.04 (1%) :x:
["sudoku", "top95_71"] 1.22 (5%) :x: 1.11 (1%) :x:
["sudoku", "top95_76"] 1.25 (5%) :x: 1.11 (1%) :x:
["sudoku", "top95_81"] 1.32 (5%) :x: 1.12 (1%) :x:
["sudoku", "top95_86"] 1.25 (5%) :x: 1.11 (1%) :x:
["sudoku", "top95_91"] 1.21 (5%) :x: 1.09 (1%) :x:

Benchmark Group List

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

Julia versioninfo

Target

Julia Version 1.6.1
Commit 6aaedecc44 (2021-04-23 05:59 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  uname: Linux 5.12.5-arch1-1 #1 SMP PREEMPT Wed, 19 May 2021 10:32:40 +0000 x86_64 unknown
  CPU: AMD Ryzen 7 PRO 4750U with Radeon Graphics: 
                 speed         user         nice          sys         idle          irq
       #1-16  1700 MHz    1175322 s        842 s     505313 s    5741354 s          0 s

  Memory: 38.4824333190918 GB (1964.1015625 MB free)
  Uptime: 204538.0 sec
  Load Avg:  2.22  1.95  2.0
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, znver2)

Baseline

Julia Version 1.6.1
Commit 6aaedecc44 (2021-04-23 05:59 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  uname: Linux 5.12.5-arch1-1 #1 SMP PREEMPT Wed, 19 May 2021 10:32:40 +0000 x86_64 unknown
  CPU: AMD Ryzen 7 PRO 4750U with Radeon Graphics: 
                 speed         user         nice          sys         idle          irq
       #1-16  1400 MHz    1186280 s        843 s     507660 s    5860782 s          0 s

  Memory: 38.4824333190918 GB (2127.75 MB free)
  Uptime: 205372.0 sec
  Load Avg:  2.34  2.09  2.06
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, znver2)
Wikunia commented 3 years ago

Currently the bool bridge only supports two bridges (so not the complement bridge). I think I have to just apply them one after the other though in a bridge chain. The benchmarks look good as I haven't changed something for alldifferent so the Sudoku ones are probably just because I didn't run them on a dedicated benchmark machine.

Wikunia commented 3 years ago

Bridge chain for boolean constraints work now but I think something similar is needed for the complement bridge as well.

Wikunia commented 3 years ago

Things like this:

@constraint(m, b := {(!((!(sum(x) > 3)) ⊻ (sum(x) >= 2))) && (x[1]+2x[2] <= 5)})

Currently don't work as there are too many levels of the complement and bool bridge. Not sure yet how to fix this so I'll make another issue for that.