Constrained Shortest Path Eval

constrained-shortest-path-eval

Constrained Shortest Path Search with Graph Convolutional Neural Networks — Osanlou et al. (2021) (arXiv:2108.00978, 2021)

What this evaluates

Evaluates a graph convolutional neural network's ability to predict optimal next-node preferences for constrained shortest path problems with mandatory waypoints, to accelerate constraint programming solvers.

Datasets

• Maneuver benchmark — total 1008; splits: test (1008)
• Exploration benchmark — total 2208; splits: test (2208)

Metrics

• Number of instances resolved with proof of optimality (primary) — range: other
  • Count of problem instances for which the solver finds a mathematically optimal path within a strict 3-second time limit.
• Average solving time for optimality — range: other
  • Mean wall-clock time (seconds) taken by the solver to prove optimality across all successfully resolved instances.
• Average number of backtracks for optimality — range: other
  • Mean number of search tree backtracking operations performed by the solver before proving optimality.

Input / output format

Input: Graph adjacency matrix with edge costs, node features, and mandatory waypoint locations, encoded as a vector x.

Output: Preference ordering vector y_hat over all graph nodes, produced via a softmax layer, indicating the probability/rank of the next node to visit from the start node.

Scoring recipe

def evaluate_solver(nn_predictions, instances, timeout=3.0):
    solved_count = 0
    total_time = 0.0
    total_backtracks = 0
    for inst in instances:
        solver = CP_Solver()
        solver.set_root_node_ordering(nn_predictions[inst])
        solver.set_time_limit(timeout)
        result = solver.solve()
        if result.status == OPTIMAL:
            solved_count += 1
            total_time += result.wall_time
            total_backtracks += result.backtracks
    avg_time = total_time / solved_count if solved_count > 0 else 0
    avg_bt = total_backtracks / solved_count if solved_count > 0 else 0
    return solved_count, avg_time, avg_bt

Common pitfalls

• The neural network is only queried once at the root of the search tree, not at every choice point, to avoid computational overhead.
• Only instances solved to mathematical optimality are counted; near-misses or timeouts are excluded from the main metric.
• Benchmarks are synthetically generated with 0-10 mandatory waypoints, not real-world terrain data.

Evidence (verbatim from paper)

We generate instances for two benchmarks, a maneuver benchmark, associated with graph G1, and an exploration benchmark, associated with graph G2. The first benchmark comprises 1008 instances, the second one 2208 instances. ... We solve those instances using our original model-based planning solver without neural network support to obtain reference performance. Then, we evaluate solving performance on the same instances using a modified version of the solver based on neural network probing, that was trained over data provided in § 5. In both cases, we only keep results where the proof of optimality could be achieved. Results are reported in table 2, showing stable improvements on all datasets of instances. Table 2: Number of instances resolved with proof of optimality. Comparison between the reference version and the neural network probing one (under 3 seconds 'time out').

Citation

@misc{osanlou2021constrained,
  title={Constrained Shortest Path Search with Graph Convolutional Neural Networks},
  author={Osanlou et al. (2021)},
  year={2021},
  note={arXiv:2108.00978}
}

• arXiv: 2108.00978