Segfault with use_combined_no_overlap due to uninitialized FixedCapacityVector in CombinedDisjunctive
- 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
Assessment
This issue has not been assessed yet.