google / google/or-tools

Segfault with use_combined_no_overlap due to uninitialized FixedCapacityVector in CombinedDisjunctive

Open
#5,135 0 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: v9.15
Language: Python 3.13

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

**What operating system (Linux, Windows, ...) and version?**
macOS 15 (arm64)

**What did you do?**

Set `solver.parameters.use_combined_no_overlap = True` on a model with a `NoOverlap` constraint containing 3 or more intervals.

```python
from ortools.sat.python import cp_model

model = cp_model.CpModel()
starts = [model.new_int_var(0, 100, f"s_{i}") for i in range(3)]
intervals = [model.new_fixed_size_interval_var(starts[i], 10, f"iv_{i}") for i in range(3)]
model.add_no_overlap(intervals)

solver = cp_model.CpSolver()
solver.parameters.use_combined_no_overlap = True
status = solver.solve(model)
```

**What did you expect to see**

A solved model (OPTIMAL or FEASIBLE status).

**What did you see instead?**

Segmentation fault during `solve()`.

```
Fatal Python error: Segmentation fault

Thread 0x0000000208402240 (most recent call first):
File ".../ortools/sat/python/cp_model.py", line 1771 in solve
```

Models with 2 or fewer intervals work fine (the `CombinedDisjunctive` code path requires `intervals.size() > 2` in `AddDisjunctive`). Also reproduces with optional intervals (`new_optional_fixed_size_interval_var`).

**Anything else we should know about your project / environment**

The bug is a null pointer write in `CombinedDisjunctive::AddNoOverlap` (`ortools/sat/disjunctive.cc`, line 341). The `FixedCapacityVector` backing a `TaskSet` is default-constructed with `data_ = nullptr`, and `ClearAndReserve()` is never called. During `Propagate()`, `TaskSet::AddEntry()` calls `push_back()` which writes to the null pointer.

Suggested fix — allocate storage before constructing the `TaskSet`:

```diff
template
void CombinedDisjunctive::AddNoOverlap(
absl::Span vars) {
const int index = task_sets_.size();
- task_sets_.emplace_back(task_set_storage_.emplace_back());
+ auto& storage = task_set_storage_.emplace_back();
+ storage.ClearAndReserve(vars.size());
+ task_sets_.emplace_back(storage);
end_mins_.push_back(kMinIntegerValue);
for (const IntervalVariable var : vars) {
task_to_disjunctives_[var.value()].push_back(index);
}
}
```

Verified fix locally by building from source.

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.