[BUG] set_cover Python: integer focus overloads are unreachable, and a bool in_focus mask crashes GreedySolutionGenerator on a fresh invariant
- Dominant language
- C++
- Stars
- 14.1k
- Forks
- 2.5k
- Avg merge
- 8h 39m
- Merged PRs (30d)
- 72
Description
**Version:** `ortools` 9.15.6755 (PyPI wheel) · CPython 3.13.11 · macOS 26.5.2, arm64
Two independent problems with restricting a solve to a subset of the subsets. Happy to split this into two issues.
1. *Every* binding that takes the integer `focus` list is unreachable from Python: no `absl::Span` caster is registered, so those overloads can never be selected.
2. Passing a correctly sized bool `in_focus` mask to `GreedySolutionGenerator` on a freshly built invariant terminates the interpreter. The same call after a solve is fine, and the other generators are fine, so this one is narrow.
## Model used throughout
48 elements on a 6×8 grid; 24 subsets, one per other cell, each covering the cells within L1 distance 2; all costs 1.0. This is the shape of a depot-siting instance (`focus` is how you would restrict a solve to the sites a planner is actually allowed to open), but nothing here depends on that reading.
```python
from ortools.set_cover.python import set_cover
ROWS, COLS = 6, 8
model = set_cover.SetCoverModel()
for r in range(ROWS):
for c in range(COLS):
if (r + c) % 2:
continue
model.add_empty_subset(1.0)
for dr in range(-2, 3):
for dc in range(-2, 3):
nr, nc = r + dr, c + dc
if abs(dr) + abs(dc) <= 2 and 0 <= nr < ROWS and 0 <= nc < COLS:
model.add_element_to_last_subset(nr * COLS + nc)
inv = set_cover.SetCoverInvariant(model)
greedy = set_cover.GreedySolutionGenerator(inv)
```
Without a focus this is healthy: `greedy.next_solution()` returns `True` at cost 10.0, exit 0 on 5 of 5 runs.
## 1. No `absl::Span` caster, so the integer `focus` overloads are dead
```python
>>> inv.compute_coverage_in_focus([0, 1, 2])
TypeError: compute_coverage_in_focus(): incompatible function arguments. The following argument types are supported:
1. (self: ...SetCoverInvariant, focus: absl::lts_20250814::Span) -> list[int]
```
pybind11 falling back to the raw C++ type name in the signature is the tell: nothing is registered for `absl::Span`, so no Python object can satisfy the parameter. `set_cover.cc` includes `pybind11/stl.h` and `pybind11_protobuf/native_proto_caster.h`, neither of which provides abseil casters.
| Binding | Result, 5 runs |
|---|---|
| `SetCoverInvariant.compute_coverage_in_focus(focus)` | `TypeError` |
| `clear_random_subsets(focus, num_subsets, inv)` | `TypeError` |
| `clear_most_covered_elements(focus, num_subsets, inv)` | `TypeError` |
Consequence: `VectorIntToVectorSubsetIndex` is dead code from Python.
Where a `list[bool]` overload sits beside the `Span` one, the outcome is worse than a `TypeError`, because the id list appears to bind to the bool overload instead: a list of subset ids becomes a truthiness mask of the wrong length.
```python
greedy.next_solution([0, 2, 4]) # meant as "these three subsets"
```
SIGABRT on 5 of 5 runs, with `adjustable_k_ary_heap.h:108] Check failed: !IsEmpty()` on stderr. I have not instrumented what the C++ side receives, so the overload-selection part is inference; what is measured is that the three bindings above have no bool overload and raise, while this one does have and crashes.
## 2. A bool mask crashes greedy on a fresh invariant
Documented bool-mask form, correct length, every entry `True`:
```python
greedy.next_solution([True] * model.num_subsets)
```
| Sequence | Result, 5 runs |
|---|---|
| fresh invariant → mask | exit 139 (SIGSEGV) |
| `next_solution()` first, then mask | exit 0, returns `True`, cost 10.0 |
So the greedy masked call is only safe once the invariant already holds a solution. `SteepestSearch.next_solution(mask)` after a solve, and `TrivialSolutionGenerator.next_solution(mask)` on a fresh invariant, each completed without crashing (one run each; I did not check the solutions they returned). The other six focus-taking classes are untried.
## Suggested direction
For 1, either register abseil casters for this module, or type the `focus` parameters `const std::vector&`. The second needs no new dependency and matches what the file already does for the `in_focus` bool overloads. I am happy to send that PR with regression tests.
For 2, I have not traced past the `CHECK` and would rather not guess at the root cause in the heap code.
## Update 2026-09-05: re-checked on `main`
Re-run against `main` @ `5a1b660` (Linux, Bazel build), 5 runs per probe, next to the 9.15.6755 wheel above. On `main`, `GreedySolutionGenerator` is `GreedySolutionOptimizer` and `next_solution()` is `optimize()`; the probes are otherwise unchanged.
**Part 1 is unchanged on `main`.** `compute_coverage_in_focus([0, 1, 2])` raises the same `TypeError` (the signature now shows `absl::lts_20260817::Span`), and `optimize([0, 2, 4])` aborts 5 of 5 with the same `!IsEmpty()` check.
**Part 2 does not reproduce on `main`.** The bool mask on a fresh invariant returns `True` 5 of 5, and so does the mask after a solve. On the wheel it still crashes 5 of 5 on a fresh invariant, and also 3 of 5 after a solve, so on 9.15 it is less narrow than described above. I have not bisected what fixed it. Part 2 can be treated as fixed on `main` unless a backport to `stable` is wanted.
Related: my open PR #5121 proposes a fix for a separate defect in the same file, a `std::transform` into an empty vector that is what makes `SetCoverModel.all_subsets` segfault. It is still present on `main` @ `5a1b660` (SIGSEGV 5 of 5 runs there and on the wheel); the regression test in that PR fails on unpatched `main` and passes with the patch applied.
**Disclosure:** investigated with AI assistance (Claude). Every exit code and message above comes from a run I executed on the machine described, against the code exactly as shown.
Contributor guide
Research direction
Start with the set_cover.cc Python binding declarations and reproduce the integer-focus TypeError and masked optimize behavior on main versus the 9.15 wheel. Add regression coverage for the intended Python focus calls and verify the fresh-invariant bool-mask behavior; the integer focus bindings should be callable, while the wheel-only crash should be confirmed as fixed on main or narrowed to a stable backport.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp, python
- Domain
- api, backend
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100