Tamsayı çoklu ağ tasarımı problemleri için algoritmalar

ABSTRACTALGORITHMS FOR THE INTEGERMULTICOMMODITY NETWORK DESIGN PROBLEMMustafa Rasim KılınşcM.S. in Industrial EngineeringSupervisor: Assist. Prof. Dr. Oya Ekin KaraşansJuly 2004In this thesis, we study the problem of logical network design in telecommunica-tion networks. Given a set of nodes and a set of commodities, we aim to locatelightpaths(links) between nodes and route the commodities over these lightpaths.The cost to be minimized is the number of lightpaths used. The problem has ca-pacity, degree and delay constraints. An important characteristic of our problemis that the commodities can not be split, therefore they must be routed on asingle path.We present two integer programming formulations of the problem and con-sider four sets of valid inequalities. Additionally, a relaxation of the problem ispresented to obtain a lower bound to the problem. Finally, we propose two algo-rithms of generating good feasible solutions to the problem. Our results prove tobe close to the lower bounds.Keywords: Network Topology Design, Integer Multicommodity Flow Problem,Tabu Search, Capacitated Network Design, Branch-and-Price Algorithm.iii