SDP Approach to Quadratic Vertex-Disjoint Paths Problem

Abstract

We study the quadratic $k$-vertex-disjoint paths problem (Q-$k$-VDP), which seeks $k$ vertex-disjoint paths in a directed graph that minimize a nonconvex quadratic objective function. We formulate the problem as a binary quadratic program and apply a systematic graph reduction to manage its dimensionality. To obtain a tractable bounding model, we drop the subtour-elimination constraints and derive a semidefinite programming (SDP) relaxation. We then solve this relaxed model within a branch-and-bound framework, where the bounds are computed from the SDP relaxation using a tailored alternating direction method of multipliers. Computational results show that our proposed method consistently outperforms Gurobi by solving more instances to optimality, especially on challenging large-scale instances.

29 pages, 3 figures, 2 tables