Certain optimization problems in networks

点击翻译按钮获取中文摘要

The objective of the proposal is to develop efficient algorithms for certain well know problems in Operations Research, Wireless Sensor Networks and Optical WDM Networks. The first project deals with the classical Fixed-Charge Transportation Problem (FCTP). We have, in the recent past, studied the theoretical structure of the pure fixed charge problem where we assume that the variable flow costs are negligible. Our first objective is to develop additional strong valid inequalities for the FCTP using our past experience, and incorporate recent developments for accelerating Bender's decomposition approach in solving Mixed Integer Programs. Our second objective is to extend these ideas to the study of the general fixed-charge capacitated network flow problem. The second project deals with the general area of Wireless Sensor Networks. In a two-tier architecture, sensor nodes constitute the lower-tier. For upper layer, several cluster heads, special critical nodes equipped with higher initial energy, receive data from sensor nodes assigned to their cluster heads, form a connected network, and communicate with the base-station. Apart from assigning sensor nodes to cluster heads, the most important issues are that of connectivity and of routing data from the upper layer network of cluster heads to the base-station. Our main objective is to first develop efficient routing algorithms by making use of the special features of connectivity in wireless networks, and then study the joint problem of creating clusters and routing, optimally. Third project deals with translucent optical networks. In wide area networks, signals have to be regenerated if the distance between the source and destination exceeds the optical reach, setting up of regeneration points. Several design and routing issues need to be researched in these networks, since these regeneration points are expensive and have inherent wavelength conversion capabilities. We are currently developing a branch-and-price algorithm for this hard problem.