EURO 2025 Leeds
Abstract Submission

2910. A stable set based branch and bound algorithm for the shortest path problem with conflicts

Invited abstract in session MD-20: Problems on graphs, stream Combinatorial Optimization.

Monday, 14:30-16:00
Room: Esther Simpson 2.11

Authors (first author is the speaker)

1. BAHADIR PAMUK
2. I. Kuban Altinel
Industrial Engineering Dept., Bogaziçi University
3. Temel Öncan
Industrial Engineering, Galatasaray University

Abstract

Combinatorial optimization problems with conflicts, mirroring real-world scenarios in transportation and network design, have gained significant interest. The Shortest Path Problem with Conflicts (SPC) builds upon the classic One-to-many Shortest Path Problem (SP) by introducing conflict constraints, forbidding simultaneous inclusion of specific arc pairs. This renders SPC NP-hard, demanding efficient methodologies. SPC aims to identify a conflict-free Shortest Path Tree, a spanning outtree rooted at a source vertex. Notably, SPC is a specialized instance of the Minimum Cost Flow with Conflicts (MCFC), suggesting that efficient SPC solutions could pave the way for advancements in MCFC.
A branch-and-bound approach based on stable sets of the conflict graph addresses SPC, transforming maximal stable sets of a conflict graph into spanning outtrees of original network. The algorithm constructs an extended conflict graph, using conflict relations inherent to SP, to reduce the number of stable sets and feasible solution space. Feasibility branching increases stable set size towards |V(N)|-1 arcs, while optimality branching refines cost by incorporating negative reduced-cost arcs. Circuit prevention is integrated. Lower bounds are computed using Dijkstra's algorithm. A greedy heuristic generates initial stable sets at each search node. A fast infeasibility test with a connectivity check improves solution times. Single-threaded runs are compared with multi-threaded Gurobi solver.

Keywords

Status: accepted

Back to the list of papers