Network flows with conflict constraints

Abstract

It is a commonly used approach to model real life problems as network flow 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 flow problems with conflict constraints that prevent the simul taneous usage of some arc pairs to send flow. We particularly concentrate on four of them: the minimum cost noncrossing flow problem on layered networks, the minimum cost flow problem with conflicts, the maximum flow problem with conflicts and the assignment problem with conflicts. The minimum cost noncrossing flow 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 flow problem with conflicts on general networks are also pro vided. Moreover, polynomially solvable special cases for the minimum cost noncrossing flow problem on layered networks and the assignment problem with conflicts, 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 flow problem with conflicts and the maximum flow problem with conflicts taking ad vantage of the conflict graph representation. Alternative mathematical representations for these problems are developed. Pre-optimization procedures to reduce the problem size and to find an initial feasible solution are defined. 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.