google / google/or-tools

[BUG] set_cover Python: integer focus overloads are unreachable, and a bool in_focus mask crashes GreedySolutionGenerator on a fresh invariant

Open
#5,278 0 comments 0 reactions 0 assignees View on GitHub
Lang: Python
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.