Certain optimization problems in networks

该提案的目的是为运筹学、无线传感器网络和光WDM网络中某些众所周知的问题开发有效的算法。第一个项目处理经典的固定收费运输问题（FCTP）。在最近的过去，我们研究了纯固定电荷问题的理论结构，我们假设可变流量成本可以忽略不计。我们的第一个目标是利用我们过去的经验为FCTP开发额外的强有效不等式，并结合最近的发展来加速Bender分解方法在求解混合整数规划中的应用。我们的第二个目标是将这些思想扩展到一般固定收费有容量网络流问题的研究中。第二个项目涉及无线传感器网络的一般领域。在两层架构中，传感器节点构成下层。在上层，具有较高初始能量的几个簇头（特殊关键节点）接收分配给其簇头的传感器节点的数据，形成一个连接的网络，并与基站通信。除了将传感器节点分配给簇头之外，最重要的问题是连通性和将数据从簇头的上层网络路由到基站。我们的主要目标是首先利用无线网络的连接特性开发高效的路由算法，然后最优地研究创建集群和路由的联合问题。第三个项目涉及半透明光网络。在广域网中，如果信号的源端和目的端之间的距离超过了光的距离，就必须对信号进行再生，建立再生点。由于这些再生点价格昂贵且具有固有的波长转换能力，因此在这些网络中需要研究一些设计和路由问题。我们目前正在为这个难题开发一个分支和价格算法。

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.