google / google/or-tools

SetCoverLagrangian: stale ThreePhase() declaration, and ComputeLowerBound() segfaults if UseNumThreads() was not called

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

Description

Two small things in `ortools/set_cover/set_cover_lagrangian.h`, found while writing #5122.
Neither comes from that PR. Checked on `main` @5a1b660. `set_cover_lagrangian.cc` is
identical on `stable`, so both apply to the released wheels too.

### 1. `ThreePhase()` is declared but has no definition

`set_cover_lagrangian.h:135` declares `void ThreePhase(Cost upper_bound);`. Nothing defines
it in `ortools/set_cover`. The three-phase procedure now lives in `set_cover_cft.cc` as
`RunThreePhase`, so this looks like a leftover from before CFT moved to its own file.

It is harmless in C++ until someone calls it (link error). Through pybind11 it is worse:
`&SetCoverLagrangian::ThreePhase` compiles, and the failure only shows up at module import
as `undefined symbol: _ZN19operations_research18SetCoverLagrangian10ThreePhaseEd`, which takes down the whole `set_cover` extension.

Suggest deleting the declaration.

### 2. `ComputeLowerBound()` needs `UseNumThreads()` first but has undocumented condition

`thread_pool_` is `nullptr` until `UseNumThreads()` runs (`set_cover_lagrangian.h:60`,
`:64`). `ComputeLowerBound()` calls the `Parallel*` methods unconditionally, and they do
`thread_pool_->Schedule(...)`. `set_cover_solve.cc:335` calls `UseNumThreads()` first, so the
solver binary is fine. A fresh `SetCoverLagrangian` however results in:

```python
lag = set_cover.SetCoverLagrangian(inv)
lag.compute_lower_bound(model.subset_costs, upper_bound) # SIGSEGV
lag.use_num_threads(1) # fine if called first
```

The header does not mention the precondition. One could: i) Either default `thread_pool_` to one thread in the constructor, or ii) `CHECK(thread_pool_ != nullptr) with a message naming
`UseNumThreads()`, or iii) a comment on `ComputeLowerBound()`.

Drafted with Claude; reproduced and verified by me.

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.