SDP Approach to Quadratic Vertex-Disjoint Paths Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918427652784128 |
|---|---|
| author | Xu, Mingming Hu, Hao |
| author_facet | Xu, Mingming Hu, Hao |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_03452 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | SDP Approach to Quadratic Vertex-Disjoint Paths Problem Xu, Mingming Hu, Hao Optimization and Control 90C22, 90C27, 90C35 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. |
| title | SDP Approach to Quadratic Vertex-Disjoint Paths Problem |
| topic | Optimization and Control 90C22, 90C27, 90C35 |
| url | https://arxiv.org/abs/2604.03452 |