NVIDIA / NVIDIA/cuopt

[BUG] Initial solution ‘accepted’ index updated incorrectly in generate_initial() (Routing solver)

Open
#338 2 comments 0 reactions 1 assignee View on GitHub

Nobody has claimed this yet.

bug
Dominant language
Cuda
Stars
1k
Forks
233
Avg merge
4d 4h
Merged PRs (30d)
95

Description

When at least one initial solution has a route count greater than target_vehicles_, the code assigns an incorrect value to next_injection. For simplicity, let me consider example with a single initial solution by inspecting the first injection iteration. However, the same indexing mismatch can occur with multiple initial solutions whenever the route-count filter’s while-loop is entered.
https://github.com/NVIDIA/cuopt/blob/c76c186124bfde26409d52f9d5377fdd423ae1d3/cpp/src/routing/diversity/diverse_solver.hpp#L863-L873

  • At line 865, temp_pair.first is set from injection_info.solutions[0].
  • Entering the while-loop at lines 868–871, temp_pair.first is reassigned (still to injection_info.solutions[0] in this example), but the iterator is incremented and, at the end, next_injection is set to 1.

As a result, later in the function:
https://github.com/NVIDIA/cuopt/blob/c76c186124bfde26409d52f9d5377fdd423ae1d3/cpp/src/routing/diversity/diverse_solver.hpp#L896-L900

  • At line 897, the solver injects temp_pair.first (which still refers to solution index 0),
  • But at line 900, it updates injection_info.accepted[next_injection++] using index 1.

This is incorrect and, when there is only one initial solution (n_sol == 1), it also causes an out-of-bounds write.

Additionally, at the end of the solve, you can get the acceptance flags for initial solutions with assignment_t::get_accepted() (see assignment.cu (L187–L191)). Due to the indexing mismatch described above, the injected solution can be evaluated and inserted, yet the corresponding accepted entry (e.g., accepted[0]) may remain -1 (“not evaluated”) instead of 1 or 0 (“accepted” or "not accepted"). This is misleading for users and downstream tooling (including the Python API), since it suggests the initial solution wasn’t considered when it actually was.

I will create PR with fix.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.