chocoteam / chocoteam/choco-solver
[BUG] LCG reports UNSAT on a satisfiable model when the value selector picks a pruned value
- Dominant language
- Java
- Stars
- 779
- Forks
- 159
- Avg merge
- 6d 9h
- Merged PRs (30d)
- 10
Description
**Describe the bug**
With lazy clause generation enabled, the solver can report UNSAT on a satisfiable model. It
happens when a value selector instantiates a variable to a value no longer in its domain.
IntDomainMiddle does this readily, since it returns min + (max - min) / 2 without checking the
value is still present. That enqueues an already-false literal with no reason (a C_Fail
conflict), and conflict analysis reads its level off the {0, 0} sentinel clause, gets 0, and
backjumps above the root, concluding UNSAT.
**To Reproduce**
Run this:
Model model = new Model(new SettingsBuilder().setLCG(true).build());
IntVar x = model.intVar("x", 0, 4);
model.arithm(x, "!=", 2).post(); // remove the midpoint value
Solver solver = model.getSolver();
solver.setSearch(Search.intVarSearch(
new InputOrder<>(model), new IntDomainMiddle(true),
DecisionOperatorFactory.makeIntEq(), x));
System.out.println(solver.solve()); // prints false
A larger, real-world trigger (a de Bruijn sequence under first_fail / indomain_split) is in
the minimal repro repository: https://github.com/rasros/choco-lcg-false-unsat
**Expected behavior**
The model is satisfiable (x can be 0, 1, 3 or 4), so the solver should never report UNSAT.
Disabling LCG, or using the default search, correctly returns SAT.
**Possible solution**
I have a PR ready.
**Environment (please complete the following information):**
- Choco-solver version: 6.0.1 (also reproduces on master)
- JRE: 21
Contributor guide
Assessment
This issue has not been assessed yet.