chocoteam / chocoteam/choco-solver

[BUG] LCG reports UNSAT on a satisfiable model when the value selector picks a pruned value

Open
#1,210 2 comments 0 reactions 0 assignees View on GitHub
bug
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.