Certain optimization problems in networks

网络中的某些优化问题

• 批准号: 4138-2011
• 负责人: Aneja, Yash
• 金额: $ 1.38万
• 依托单位: University of Windsor
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=636690
• 关键词: Certain; optimization; problems; 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.

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