Skip to content

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

@SomovMike

Description

@SomovMike

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.

} else if (injection_info.has_info() && next_injection < injection_info.n_sol) {
injection_state = true;
temp_pair.first = injection_info.solutions[next_injection];
if (!p->has_vehicle_fixed_costs()) {
auto injection_it = next_injection;
while (injection_it < injection_info.n_sol &&
temp_pair.first.sol.get_n_routes() > target_vehicles_) {
temp_pair.first = injection_info.solutions[injection_it++];
}
next_injection = injection_it;
}

  • 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:

if (injection_info.has_info() && injection_state) {
auto ret = a.add_solution(timer.elapsed_time(), temp_pair.first);
injection_state = false;
auto accepted = ret < 0 ? 0 : 1;
injection_info.accepted[next_injection++] = accepted;

  • 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.

Metadata

Metadata

Assignees

Labels

bugSomething isn't working

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions