Skip to content

v2.25.0

Choose a tag to compare

@rcrida rcrida released this 26 Jun 14:43
· 11 commits to main since this release

What's new

dom/wdeg variable ordering + Luby restarts

The satisfaction terminal solver has been upgraded from plain backtracking (BacktrackingSearch with MRV) to DomWdegLubySearch, which combines two complementary techniques:

  • dom/wdeg variable ordering (Boussemart et al. 2004): each constraint carries a weight initialised to 1; when MAC inference causes a domain wipeout the weights of all active constraints on the failing variable are incremented. The variable selector picks argmin(domainSize / weightedDegree), steering search away from historically expensive regions.
  • Luby restarts: getSolution() applies restarts with per-restart failure budgets following the sequence 1, 1, 2, 1, 1, 2, 4, … (× DEFAULT_LUBY_UNIT = 100). Weights are preserved across restarts so accumulated failure knowledge guides every new attempt.

getSolutions() returns a complete lazy stream of all solutions with dom/wdeg ordering and weight accumulation (no restarts — equivalent to the old behaviour but with better variable ordering). BacktrackingSearch (with MRV) is retained for the BranchAndBound optimization chain.

Installation

```xml

io.github.rcrida
jcsp
2.25.0

```