Network flows with conflict constraints - Şuvak, Zeynep. (Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2019., 2019)
It is a commonly used approach to model real life problems as network ﬂow prob lems and they appear in a wide range of areas including telecommunication, wireless networks, transportation, healthcare and scheduling. Our focus in this thesis is on an extension of network ﬂow problems with conﬂict constraints that prevent the simul taneous usage of some arc pairs to send ﬂow. We particularly concentrate on four of them: the minimum cost noncrossing ﬂow problem on layered networks, the minimum cost ﬂow problem with conﬂicts, the maximum ﬂow problem with conﬂicts and the assignment problem with conﬂicts. The minimum cost noncrossing ﬂow problem on layered networks, which emerges from the quay crane scheduling problem in container terminals, is proven to be NP-hard. Further complexity results including the strong NP-hardness and the non-existence of polynomial time approximation algorithm for the the minimum cost ﬂow problem with conﬂicts on general networks are also pro vided. Moreover, polynomially solvable special cases for the minimum cost noncrossing ﬂow problem on layered networks and the assignment problem with conﬂicts, which is known to be NP-hard, are explored. Similarly, the conditions which limit the number of feasible solutions with a polynomial number are indicated for the minimum cost ﬂow problem with conﬂicts and the maximum ﬂow problem with conﬂicts taking ad vantage of the conﬂict graph representation. Alternative mathematical representations for these problems are developed. Pre-optimization procedures to reduce the problem size and to ﬁnd an initial feasible solution are deﬁned. Exact solution algorithms in cluding a branch-and-bound algorithm enriched with the subroutines that exploit the special structure of the considered problem, an improved Russian doll search algorithm and a Benders decomposition with strengthened cuts are proposed. The methods are tested on a large set of test instances and they are shown to be superior than solving the underlying mathematical formulations with a commercial optimization solver.
Keywords: Network analysis (Planning); Mathematical optimization.