arxiv: 2604.03452 · v1 · submitted 2026-04-03 · 🧮 math.OC

Recognition: 2 theorem links

· Lean Theorem

SDP Approach to Quadratic Vertex-Disjoint Paths Problem

Mingming Xu , Hao Hu

Authors on Pith no claims yet

Pith reviewed 2026-05-13 18:37 UTC · model grok-4.3

classification 🧮 math.OC

keywords quadratic vertex-disjoint pathssemidefinite programmingbranch-and-boundalternating direction method of multipliersgraph reductionbinary quadratic programdirected graphsnetwork optimization

0 comments

The pith

An SDP relaxation solved inside branch-and-bound with ADMM finds optimal solutions for more quadratic vertex-disjoint paths instances than Gurobi.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper casts the quadratic k-vertex-disjoint paths problem as a binary quadratic program on a directed graph. A systematic graph reduction shrinks the model, after which the subtour-elimination constraints are dropped to produce a semidefinite programming relaxation. This relaxed model supplies bounds that are computed efficiently by a tailored alternating direction method of multipliers and are used inside a branch-and-bound tree. On benchmark sets the resulting solver closes more instances to proven optimality than the commercial solver Gurobi, with the largest gains on big graphs. If the bounds remain effective at scale, exact solutions become available for larger network-design and routing tasks whose costs are quadratic.

Core claim

The authors formulate the quadratic k-vertex-disjoint paths problem as a binary quadratic program, reduce the graph to control size, drop subtour-elimination constraints to obtain an SDP relaxation, and embed the relaxation inside branch-and-bound where bounds are obtained via a custom ADMM routine; computational tests show this procedure solves more instances to optimality than Gurobi, especially on large-scale instances.

What carries the argument

The SDP relaxation obtained by dropping subtour-elimination constraints from the binary quadratic program, with bounds computed by ADMM inside branch-and-bound.

If this is right

More quadratic k-vertex-disjoint paths instances become solvable to proven optimality in practical time.
The graph-reduction preprocessing step lowers dimensionality before the relaxation is formed.
ADMM supplies the SDP bounds quickly enough to keep the overall branch-and-bound tractable.
Performance gains are largest precisely on the challenging large-scale instances.
The method works on directed graphs with nonconvex quadratic objectives.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same pattern of dropping subtour constraints and recovering feasibility by branching may transfer to other quadratic routing problems on graphs.
If the relaxation remains reasonably tight, vertex-disjointness can be enforced mainly through branching rather than inside the continuous relaxation.
The approach suggests that semidefinite bounds could replace linear or convex quadratic bounds in other network-design solvers when the objective is quadratic.
Computational success on directed graphs raises the question of whether an analogous reduction and relaxation works for undirected versions of the same problem.

Load-bearing premise

The SDP relaxation produces bounds tight enough for branch-and-bound to prune the search tree effectively on the tested instances.

What would settle it

A collection of large instances on which the SDP branch-and-bound procedure solves strictly fewer problems to optimality than Gurobi within the same time limit.

Figures

Figures reproduced from arXiv: 2604.03452 by Hao Hu, Mingming Xu.

**Figure 1.** Figure 1: Directed planar graph G with source–target pairs (1, 2) and (3, 4) as described in Example 5.1. This instance, consisting of six nodes and eight arcs, is used to illustrate the failure of Slater’s condition in the SDP relaxation. 1 1 2 1 3 1 4 1 5 1 6 1 1 2 2 2 3 2 4 2 5 2 6 2 [PITH_FULL_IMAGE:figures/full_fig_p015_1.png] view at source ↗

**Figure 2.** Figure 2: Disjoint union graph G 1 ⊔ G2 , constructed from two isomorphic copies of the base graph G in [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗

**Figure 3.** Figure 3: Reduced graph G after removing fixed arcs in the disjoint union graph in [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The SDP method with graph reduction and ADMM beats Gurobi on the tested instances for quadratic k-VDP, but the dropped subtour constraints leave bound tightness unproven.

read the letter

The main thing to know is that this paper turns the quadratic k-vertex-disjoint paths problem into a binary quadratic program, reduces the graph to control size, drops the subtour constraints to get an SDP relaxation, and solves the bounds with a custom ADMM inside branch-and-bound. On their instances it solves more cases to optimality than Gurobi, especially the larger ones. That is the practical result worth checking. The graph reduction step is a straightforward but useful engineering move that keeps the lifted SDP from blowing up. The tailored ADMM for the relaxed model is also a reasonable choice for getting bounds quickly. The overall pipeline is complete and directly addresses a nonconvex quadratic objective on directed graphs, which is not the most common setting in the path literature. The computational claim is the part that stands out: if the experiments hold up, the method gives a workable alternative to off-the-shelf MIQP solvers for this structure. The soft spot is the relaxation itself. Dropping all subtour-elimination constraints removes the enforcement of path structure beyond flow conservation, and the paper gives no a-priori guarantee that the resulting bounds stay tight enough for reliable pruning on general nonconvex quadratics. The stress-test concern lands here; without a comparison to a version that retains even a few cuts or an analysis of when the relaxation is strong, the outperformance could be instance-specific. The abstract mentions large-scale wins, but the strength of the evidence depends on how the instances were generated and how gaps were measured. Minor point: more baselines beyond Gurobi would help put the gains in context. This is for people working on network optimization or quadratic combinatorial problems who need a concrete SDP-based solver. A reader already familiar with SDP relaxations for paths will see the extension clearly and might try the reduction plus ADMM on related problems. It deserves a serious referee because the method is fully described and the empirical results are positive enough to check in detail. I would send it for review and ask the referees to look closely at bound quality and experimental setup.

Referee Report

2 major / 0 minor

Summary. The paper studies the quadratic k-vertex-disjoint paths problem (Q-k-VDP) on directed graphs. It formulates the problem as a binary quadratic program, applies a graph reduction, drops subtour-elimination constraints to derive an SDP relaxation, and solves the relaxation via a tailored ADMM solver inside a branch-and-bound framework. Computational experiments are reported to show that the method solves more instances to optimality than Gurobi, especially on large-scale instances.

Significance. If the SDP relaxation produces sufficiently tight bounds for effective pruning and the reported outperformance is reproducible, the work would provide a practical new bounding technique for nonconvex quadratic path problems. The combination of graph reduction with ADMM-based SDP bounding inside B&B is a standard but here newly applied approach that could extend to related network design problems with quadratic objectives.

major comments (2)

[Computational results] Computational results section: the central claim that the method 'consistently outperforms Gurobi by solving more instances to optimality, especially on challenging large-scale instances' is unsupported by any reported details on the number of instances, their sizes, runtimes, optimality-gap measurement protocol, or hardware. Without these data the computational superiority cannot be assessed.
[SDP relaxation formulation] SDP relaxation (after dropping subtour-elimination constraints): no a-priori bound-quality guarantee, no comparison against a formulation that retains even a subset of subtour cuts, and no analysis of how the tailored ADMM affects dual-bound accuracy are provided for the nonconvex quadratic objective on directed graphs. These omissions leave the load-bearing assumption that the relaxation is tight enough for effective branch-and-bound pruning unverified.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address each of the major comments below and outline the revisions we plan to make to strengthen the paper.

read point-by-point responses

Referee: [Computational results] Computational results section: the central claim that the method 'consistently outperforms Gurobi by solving more instances to optimality, especially on challenging large-scale instances' is unsupported by any reported details on the number of instances, their sizes, runtimes, optimality-gap measurement protocol, or hardware. Without these data the computational superiority cannot be assessed.

Authors: We agree that more details are needed to support the claims. In the revised version, we will expand the computational results section to include: the total number of test instances and their generation procedure, the range of graph sizes (number of vertices and arcs), hardware specifications (CPU, memory), time limits, and the exact protocol for measuring optimality gaps. We will present detailed tables comparing the number of instances solved to optimality, average and maximum runtimes, and final gaps for our method versus Gurobi. revision: yes
Referee: [SDP relaxation formulation] SDP relaxation (after dropping subtour-elimination constraints): no a-priori bound-quality guarantee, no comparison against a formulation that retains even a subset of subtour cuts, and no analysis of how the tailored ADMM affects dual-bound accuracy are provided for the nonconvex quadratic objective on directed graphs. These omissions leave the load-bearing assumption that the relaxation is tight enough for effective branch-and-bound pruning unverified.

Authors: We acknowledge that the manuscript does not provide theoretical a-priori guarantees on bound quality, which is challenging for this nonconvex quadratic setting. However, the empirical results indicate effective pruning. To address this, we will add a new subsection in the computational results that: (i) compares the SDP bounds to those obtained from a formulation retaining a subset of subtour-elimination cuts on smaller instances where the full model is solvable, (ii) reports the duality gaps achieved by the tailored ADMM solver, and (iii) analyzes the tightness of the bounds in the context of the branch-and-bound tree. We maintain that dropping the subtour constraints is necessary for tractability, as including them would render the SDP computationally prohibitive. revision: partial

Circularity Check

0 steps flagged

No circularity: standard SDP relaxation and empirical comparison are self-contained

full rationale

The derivation proceeds from a standard binary quadratic formulation of the Q-k-VDP, applies a graph reduction, drops subtour-elimination constraints to obtain an SDP relaxation, and solves the relaxation via a tailored ADMM inside branch-and-bound. Computational outperformance over Gurobi is reported as an empirical result on test instances. No equation reduces to a self-definition, no fitted parameter is relabeled as a prediction, and no load-bearing step relies on a self-citation chain whose validity is presupposed by the present work. The approach is therefore independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The approach rests on standard convex relaxation assumptions and a graph reduction step whose validity is asserted without independent proof in the abstract.

axioms (2)

domain assumption The systematic graph reduction preserves the optimal value of the original quadratic program.
Invoked to manage dimensionality before forming the SDP.
standard math Dropping subtour-elimination constraints produces a valid lower bound for the integer program.
Standard integer programming relaxation technique.

pith-pipeline@v0.9.0 · 5412 in / 1225 out tokens · 52155 ms · 2026-05-13T18:37:58.597418+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

To obtain a tractable bounding model, we drop the subtour-elimination constraints and derive a semidefinite programming (SDP) relaxation... tailored alternating direction method of multipliers
IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We formulate the Q-k-VDP as a binary quadratic program... SDP relaxation of the subtour-relaxed BQP

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

[1]

On the Computational Complexity of Combinatorial Problems

Richard M. Karp. “On the Computational Complexity of Combinatorial Problems”. In:Networks5.1 (1975), pp. 45–68.doi:10.1002/net.1975.5.1.45

work page doi:10.1002/net.1975.5.1.45 1975
[2]

The directed subgraph home- omorphism problem

Steven Fortune, John Hopcroft, and James Wyllie. “The directed subgraph home- omorphism problem”. In:Theoretical Computer Science10.2 (1980), pp. 111–121

work page 1980
[3]

Disjoint paths in graphs

Paul D Seymour. “Disjoint paths in graphs”. In:Discrete mathematics29.3 (1980), pp. 293–309

work page 1980
[4]

A polynomial solution to the undirected two paths problem

Yossi Shiloach. “A polynomial solution to the undirected two paths problem”. In: Journal of the ACM (JACM)27.3 (1980), pp. 445–456. 24

work page 1980
[5]

2-linked graphs

Carsten Thomassen. “2-linked graphs”. In:European Journal of Combinatorics1.4 (1980), pp. 371–378

work page 1980
[6]

The two disjoint path problem and wire routing design

Tatsuo Ohtsuki. “The two disjoint path problem and wire routing design”. In:Graph Theory and Algorithms: 17th Symposium of Research Institute of Electrical Com- munication, Tohoku University Sendai, Japan, October 24–25, 1980 Proceedings. Springer. 1981, pp. 207–216

work page 1980
[7]

Neil H. E. Weste and Kamran Eshraghian.Principles of CMOS VLSI Design: A Systems Perspective. 2nd ed. Addison-Wesley, 1993

work page 1993
[8]

Finding k disjoint paths in a directed planar graph

Alexander Schrijver. “Finding k disjoint paths in a directed planar graph”. In: SIAM Journal on Computing23.4 (1994), pp. 780–788

work page 1994
[9]

Graph minors. XIII. The disjoint paths problem

Neil Robertson and Paul D Seymour. “Graph minors. XIII. The disjoint paths problem”. In:Journal of combinatorial theory, Series B63.1 (1995), pp. 65–110

work page 1995
[10]

The disjoint shortest paths problem

Tali Eilam-Tzoreff. “The disjoint shortest paths problem”. In:Discrete applied mathematics85.2 (1998), pp. 113–138

work page 1998
[11]

Node-disjoint paths on the mesh and a new trade-off in VLSI layout

Alok Aggarwal, Jon Kleinberg, and David P Williamson. “Node-disjoint paths on the mesh and a new trade-off in VLSI layout”. In:SIAM Journal on Computing 29.4 (2000), pp. 1321–1333

work page 2000
[12]

Distributed algo- rithms for computing shortest pairs of disjoint paths

Richard G Ogier, Vladislav Rutenburg, and Nachum Shacham. “Distributed algo- rithms for computing shortest pairs of disjoint paths”. In:IEEE transactions on information theory39.2 (2002), pp. 443–455

work page 2002
[13]

Pearson Education, 2002

Jan M Rabaey, Anantha Chandrakasan, and Borivoje Nikolic.Digital Integrated Circuits. Pearson Education, 2002

work page 2002
[14]

Fast Integer Linear Programming Based Models for VLSI Global Routing

Laleh Behjat and A. Chiang. “Fast Integer Linear Programming Based Models for VLSI Global Routing”. In:Proceedings of the 2005 IEEE International Symposium on Circuits and Systems. IEEE, 2005, pp. 6238–6243.doi:10.1109/ISCAS.2005. 1466066

work page doi:10.1109/iscas.2005 2005
[15]

Finding minimum energy disjoint paths in wireless ad-hoc networks

Anand Srinivas and Eytan Modiano. “Finding minimum energy disjoint paths in wireless ad-hoc networks”. In:Wireless Networks11.4 (2005), pp. 401–417. 25

work page 2005
[16]

Integer Linear Program- ming Models for Global Routing

Laleh Behjat, Anthony Vannelli, and William Rosehart. “Integer Linear Program- ming Models for Global Routing”. In:INFORMS Journal on Computing18.2 (2006), pp. 137–150.doi:10.1287/ijoc.1040.0127

work page doi:10.1287/ijoc.1040.0127 2006
[17]

Alternating direction augmented Lagrangian methods for semidefinite programming

Zaiwen Wen, Donald Goldfarb, and Wotao Yin. “Alternating direction augmented Lagrangian methods for semidefinite programming”. In:Mathematical Program- ming Computation2.3 (2010), pp. 203–230

work page 2010
[18]

Combinatorial optimization in VLSI design

Stephan Held et al. “Combinatorial optimization in VLSI design”. In:Combinatorial Optimization(2011), pp. 33–96

work page 2011
[19]

GRIP: Global Routing via Integer Programming

Tai-Hsuan Wu, Azadeh Davoodi, and Jeffrey T. Linderoth. “GRIP: Global Routing via Integer Programming”. In:IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems30.1 (2011), pp. 72–84.doi:10.1109/TCAD.2010. 2066030

work page doi:10.1109/tcad.2010 2011
[20]

The disjoint paths problem in quadratic time

Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce Reed. “The disjoint paths problem in quadratic time”. In:Journal of Combinatorial Theory, Series B102.2 (2012), pp. 424–435

work page 2012
[21]

The directed disjoint shortest paths prob- lem

Krist´ of B´ erczi and Yusuke Kobayashi. “The directed disjoint shortest paths prob- lem”. In:25th Annual European Symposium on Algorithms (ESA 2017). Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik. 2017

work page 2017
[22]

The many faces of degeneracy in conic optimization

Dmitriy Drusvyatskiy, Henry Wolkowicz, et al. “The many faces of degeneracy in conic optimization”. In:Foundations and Trends®in Optimization3.2 (2017), pp. 77–170

work page 2017
[23]

ADMM for the SDP relaxation of the QAP

Danilo Elias Oliveira, Henry Wolkowicz, and Yangyang Xu. “ADMM for the SDP relaxation of the QAP”. In:Mathematical Programming Computation10.4 (2018), pp. 631–658

work page 2018
[24]

Two disjoint shortest paths problem with non- negative edge length

Yusuke Kobayashi and Ryo Sako. “Two disjoint shortest paths problem with non- negative edge length”. In:Operations Research Letters47.1 (2019), pp. 66–69

work page 2019
[25]

A polynomial time algorithm for the k-disjoint shortest paths problem

Willian Lochet. “A polynomial time algorithm for the k-disjoint shortest paths problem”. In:Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algo- rithms (SODA). SIAM. 2021, pp. 169–178. 26

work page 2021
[26]

2026.url:https: //www.gurobi.com

Gurobi Optimization, LLC.Gurobi Optimizer Reference Manual. 2026.url:https: //www.gurobi.com. A Detailed Reduction Statistics Table 2: Average arc counts before (k|E|) and after the reduction procedure (|E|), to- gether with the average computational time in seconds required per configuration. Pairs Grid size Initial arcs Remaining arcs Time k m v k|E| |E...

work page 2026