The quadratic shortest path problem: Theory and computations

Hao Hu

Research output: ThesisDoctoral Thesis

367 Downloads (Pure)


The quadratic shortest path problem (QSPP) has a lot of applications in real-life problems. This thesis consists of four essays about the QSPP concerning its theory and computation, where linear and semidefinite programming were used as a major tool for solving and understanding the problem. In the second chapter, we investigate the computational complexity of the problem as well as the polynomial-time solvable special cases. In the third and fourth chapters, we show that the linearization problem of the quadratic shortest path problem on directed acyclic graphs can be solved efficiently. By using the linearization problem of binary quadratic problems as a unifying tool, the dominance between the Generalized Gilmore-Lawler bound and the first level RLT bound is also established. We also propose a new class of relaxation for binary quadratic optimization problems based on its linearization problem. In the last chapter, we derive several semidefinite programming relaxations with increasing complexity for the quadratic shortest path problem. We implement the alternating direction method of multipliers to solve our strongest semidefinite programming relaxation, and the obtained bound is currently the best one solved in the literature.

Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Tilburg University
  • Sotirov, Renata, Promotor
  • van Dam, Edwin, Promotor
Award date13 Sep 2019
Place of PublicationTilburg
Print ISBNs978 90 5668 601 7
Publication statusPublished - 2019


Dive into the research topics of 'The quadratic shortest path problem: Theory and computations'. Together they form a unique fingerprint.

Cite this