Network flows with conflict constraints

Abstract

Telekomünikasyon, kablosuz ağlar, taşımacılık, tıp ve sağlık hizmetleri, çizelgelemegibi alanlarda karşımıza çıkan birçok problemi ağ akış problemleri olarak modellemekyaygın bir yaklaşımdır. Bu tez bağlamında odaklanılan ise, ağ akış problemlerinin belirli okların aynı anda akış taşımasını engelleyen çatışma kısıtlı uzantısıdır. Ele alınanproblemlerin bazıları daha önceden yazında var olan, bazıları da ilk defa bu tezdeçalışılmış katmanlı ağlarda en küçük maliyetli kesişmeyen akış problemi, çatışma kısıtlıen küçük maliyetli akış problemi, çatışma kısıtlı en büyük akış problemi ve çatışmakısıtlı atama problemidir. Konteyner limanlarında kıyı vinci çizelgeleme probleminimodellemek için ortaya çıkan katmanlı ağlarda en küçük maliyetli kesişmeyen akışprobleminin NP-zor olduğu kanıtlanmıştır. Çatışma kısıtlı en küçük maliyetli akışprobleminin güçlü NP-zorluğu ve polinom zamanlı yakınlaştırma algoritmasının bulunmazlığı gibi karma¸sıklık çözümleme sonuçlarına da ulaşılmıştır. Ayrıca, katmanlıağlarda en küçük maliyetli kesişmeyen akış problemi ve çatışma kısıtlı atama problemiiçin polinom zamanda çözülebilen özel durumlar açıklanmıştır. Benzer şekilde, çatışmakısıtlı en küçük maliyetli akış problemi ve çatışma kısıtlı en büyük akış problemi içinolurlu çözüm sayısını polinom bir sayıyla sınırlayan durumlar çatışma çizgesinden faydalanılarak işaret edilmiştir. Tüm problemler için çeşitli matematiksel gösterimlerelde edilmiştir. Hızlı bir biçimde problem boyutunu küçülten ve olurlu bir çözümbulan eniyileme öncesi işlemler önerilmiştir. Eldeki problemin özel yapısını kullananetkili alt yordamlarla zenginleştirilmiş dal-sınır algoritması, yenilikçi yaklaşımlarla iyileştirilmiş matruşka araması ve güçlü kesiler kullanan Benders ayrıştırması gibi kesinçözüm yöntemleri geliştirilmiştir. Algoritmalar geniş bir örnek problem kümesi üzerindedenenmiş ve başarımlarının matematiksel gösterimlerini bir ticari eniyileme yazılımı ileçözmekten daha iyi olduğu sonucuna varılmıştır.

It is a commonly used approach to model real life problems as network flow problems and they appear in a wide range of areas including telecommunication, wirelessnetworks, transportation, healthcare and scheduling. Our focus in this thesis is on anextension of network flow problems with conflict constraints that prevent the simultaneous usage of some arc pairs to send flow. We particularly concentrate on four ofthem: the minimum cost noncrossing flow problem on layered networks, the minimumcost flow problem with conflicts, the maximum flow problem with conflicts and theassignment problem with conflicts. The minimum cost noncrossing flow problem onlayered networks, which emerges from the quay crane scheduling problem in containerterminals, is proven to be NP-hard. Further complexity results including the strongNP-hardness and the non-existence of polynomial time approximation algorithm forthe the minimum cost flow problem with conflicts on general networks are also provided. Moreover, polynomially solvable special cases for the minimum cost noncrossingflow problem on layered networks and the assignment problem with conflicts, which isknown to be NP-hard, are explored. Similarly, the conditions which limit the numberof feasible solutions with a polynomial number are indicated for the minimum costflow problem with conflicts and the maximum flow problem with conflicts taking advantage of the conflict graph representation. Alternative mathematical representationsfor these problems are developed. Pre-optimization procedures to reduce the problemsize and to find an initial feasible solution are defined. Exact solution algorithms including a branch-and-bound algorithm enriched with the subroutines that exploit thespecial structure of the considered problem, an improved Russian doll search algorithmand a Benders decomposition with strengthened cuts are proposed. The methods aretested on a large set of test instances and they are shown to be superior than solvingthe underlying mathematical formulations with a commercial optimization solver.