The quadratic shortest path problem: Theory and computations

Hao Hu

Research output: ThesisDoctoral Thesis

9 Downloads (Pure)

Abstract

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
Supervisors/Advisors
  • Sotirov, Renata, Promotor
  • van Dam, Edwin, Promotor
Award date13 Sep 2019
Place of PublicationTilburg
Publisher
Print ISBNs978 90 5668 601 7
Publication statusPublished - 2019

Fingerprint

Shortest Path Problem
Linearization
Semidefinite Programming Relaxation
Binary
Method of multipliers
Alternating Direction Method
Quadratic Optimization
Directed Acyclic Graph
Semidefinite Programming
Linear programming
Polynomial time
Computational Complexity
Optimization Problem

Cite this

Hu, H. (2019). The quadratic shortest path problem: Theory and computations. Tilburg: CentER, Center for Economic Research.
Hu, Hao. / The quadratic shortest path problem : Theory and computations. Tilburg : CentER, Center for Economic Research, 2019. 111 p.
@phdthesis{2affb54fda41461b9782ddb3bf00442e,
title = "The quadratic shortest path problem: Theory and computations",
abstract = "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.",
author = "Hao Hu",
note = "CentER Dissertation Series Volume: 600",
year = "2019",
language = "English",
isbn = "978 90 5668 601 7",
volume = "600",
series = "CentER Dissertation Series",
publisher = "CentER, Center for Economic Research",
school = "Tilburg University",

}

Hu, H 2019, 'The quadratic shortest path problem: Theory and computations', Doctor of Philosophy, Tilburg University, Tilburg.

The quadratic shortest path problem : Theory and computations. / Hu, Hao.

Tilburg : CentER, Center for Economic Research, 2019. 111 p.

Research output: ThesisDoctoral 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 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.

AB - 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.

M3 - Doctoral Thesis

SN - 978 90 5668 601 7

VL - 600

T3 - CentER Dissertation Series

PB - CentER, Center for Economic Research

CY - Tilburg

ER -

Hu H. The quadratic shortest path problem: Theory and computations. Tilburg: CentER, Center for Economic Research, 2019. 111 p. (CentER Dissertation Series).