Skip to content

MIP heuristics: replace the process-wide seed_generator with per-worker RNGs #1749

Description

@ramakrishnap-nv

#1717 gives routing a per-problem seed generator, so routing and the MIP heuristics no longer share one process-wide counter. The heuristics still draw from cuopt::seed_generator, whose state is a single static int64_t handed out by a plain seed_++.

That is a data race under the solver's OpenMP thread pool, and the order in which concurrent callers receive values is not fixed, so seed assignment is not reproducible across runs.

Proposal

Use the pattern branch and bound already uses, at cpp/src/branch_and_bound/worker.hpp:110:

rng(settings.random_seed + pcgenerator_t::default_seed + rng_offset + worker_id,
    pcgenerator_t::default_stream ^ (worker_id + rng_offset))

Each worker owns its RNG, seeded from the user's random_seed and its own id, so no state is shared and the sequence a worker sees does not depend on how it interleaves with the others.

Scope

32 call sites across 16 files under cpp/src/mip_heuristics. The work is not a mechanical substitution: none of those files has a worker id in scope today.

  • mip_solver_context_t is constructed once, at cpp/src/mip_heuristics/solver.cuh:28
  • the single OpenMP region, cpp/src/mip_heuristics/solve.cu:850, exists to create a thread pool shared across the solver, with the solve itself running under #pragma omp masked

So the heuristics have no notion of worker identity. Establishing it is the substance of this issue; updating the call sites afterwards is the easy half.

Once this lands, cpp/src/utilities/seed_generator.{cuh,cu} has no remaining users and can be deleted.

Metadata

Metadata

Assignees

Labels

awaiting responseThis expects a response from maintainer or contributor depending on who requested in last comment.

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions