google / google/or-tools

CP-SAT: `sufficient_assumptions_for_infeasibility()` returns a literal that is not in the assumption list (presolve only)

Open
#5,141 4 comments 0 reactions 1 assignee Claimed by @lperron View on GitHub
Bug Solver: CP-SAT Solver
Dominant language
C++
Stars
14.1k
Forks
2.5k
Avg merge
8h 39m
Merged PRs (30d)
72

Description

**What version of OR-Tools and what language are you using?**
Version: `main` @ commit `79e340fd50e1cae499bd6c9035486cf06c8261a5` (built from source). Also reproduces on stable `v9.15.6755` (PyPI) and `v9.14.6206` (PyPI).
Language: Python

**Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)**
CP-SAT

**What operating system (Linux, Windows, ...) and version?**
Linux. Reproduced on Ubuntu 24.04 with the stable PyPI wheel, and inside `python:3.13-bookworm` Docker for the master build.

**What did you do?**

`CpSolver.sufficient_assumptions_for_infeasibility()` is documented to return "a subset of the model assumptions that are sufficient to ensure infeasibility" (an MUS). With the default `cp_model_presolve=True`, it returns a literal index that was never passed to `CpModel.add_assumptions(...)`. Disabling presolve returns a correct subset.

Minimal repro — run this script:

```python
"""Minimal reproducer for an OR-Tools CP-SAT bug:

CpSolver.sufficient_assumptions_for_infeasibility() is documented to return
a subset of the model assumptions. With the default cp_model_presolve=True,
the returned list contains a literal that is NOT in the assumption list.
Disabling presolve returns the correct subset.
"""
from ortools.sat.python import cp_model

def build_model():
"""Tiny model with:
- assumption literal `y` (the only assumption)
- a constraint `y == 0` that makes `y=1` infeasible
- a circuit constraint whose only arc into an otherwise isolated node is
a self-loop gated on NOT(v), which forces v = 0
- v is NEVER added to the assumption list
The correct MUS is [y]; the bug returns [v] when presolve is enabled.
"""
m = cp_model.CpModel()

# v — forced to 0 by the circuit, never assumed.
v = m.new_bool_var("v")
# y — the assumption; `y == 0` makes `y=1` infeasible.
y = m.new_bool_var("y")
m.add(y == 0)

# Two further bools used as circuit-node self-loop literals.
a = m.new_bool_var("a")
b = m.new_bool_var("b")

# Tour over {0, 1, 2} plus an isolated node 99 whose only arc is a
# self-loop gated on NOT(v). The circuit must pick that self-loop, so
# v is forced to 0.
arcs = [
(0, 1, m.new_bool_var("arc_0_1")),
(1, 0, m.new_bool_var("arc_1_0")),
(0, 2, m.new_bool_var("arc_0_2")),
(2, 0, m.new_bool_var("arc_2_0")),
(1, 1, a.Not()), # node 1 self-loop (optional)
(2, 2, b.Not()), # node 2 self-loop (optional)
(99, 99, v.Not()), # forces v = 0
]
m.add_circuit(arcs)
return m, v, y

def solve(model, presolve):
s = cp_model.CpSolver()
s.parameters.cp_model_presolve = presolve
s.parameters.num_workers = 1
status = s.solve(model)
return s.status_name(status), list(s.sufficient_assumptions_for_infeasibility())

model, v, y = build_model()
model.add_assumptions([y])
assumptions = [y.index]

print(f"v.index = {v.index} (NOT in assumptions)")
print(f"y.index = {y.index} (the only assumption)")
print(f"assumptions = {assumptions}")
print()
for presolve in (True, False):
m, v2, y2 = build_model()
m.add_assumptions([y2])
status, core = solve(m, presolve=presolve)
bad = [c for c in core if c != y2.index]
tag = "BUG" if bad else "OK"
print(f"presolve={presolve!s:5} status={status} core={core} "
f"literals_not_in_assumptions={bad} [{tag}]")
```

**What did you expect to see**

Both runs should return `[y.index]` (= `[1]`). The documented contract is that the returned list is a subset of the literals passed to `add_assumptions(...)`.

**What did you see instead?**

```
v.index = 0 (NOT in assumptions)
y.index = 1 (the only assumption)
assumptions = [1]

presolve=True status=INFEASIBLE core=[0] literals_not_in_assumptions=[0] [BUG]
presolve=False status=INFEASIBLE core=[1] literals_not_in_assumptions=[] [OK]
```

With presolve enabled, the core is `[0]` — that is `v`'s literal index, which was never added via `add_assumptions`. With presolve disabled, the core is `[1]` = `y.index`, the correct result.

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.