Abstract
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  13 Sep 2019 
Place of Publication  Tilburg 
Publisher  
Print ISBNs  978 90 5668 601 7 
Publication status  Published  2019 
Fingerprint
Cite this
}
The quadratic shortest path problem : Theory and computations. / Hu, Hao.
Tilburg : CentER, Center for Economic Research, 2019. 111 p.Research output: Thesis › Doctoral Thesis
TY  THES
T1  The quadratic shortest path problem
T2  Theory and computations
AU  Hu, Hao
N1  CentER Dissertation Series Volume: 600
PY  2019
Y1  2019
N2  The quadratic shortest path problem (QSPP) has a lot of applications in reallife 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 polynomialtime 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 GilmoreLawler 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.
AB  The quadratic shortest path problem (QSPP) has a lot of applications in reallife 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 polynomialtime 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 GilmoreLawler 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.
M3  Doctoral Thesis
SN  978 90 5668 601 7
VL  600
T3  CentER Dissertation Series
PB  CentER, Center for Economic Research
CY  Tilburg
ER 