A Unifying Study of the Capacitated Fixed-Charge Network Flow Polyhedron

容量固定电荷网络流多面体的统一研究

• 批准号: 0970180
• 负责人: Alper Atamturk
• 金额: $ 28.5万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-06-01 至 2015-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0970180&HistoricalAwards=false
• 关键词: Unifying; Study; Capacitated; Fixed; Charge

The objective of the research proposal is to derive new strong valid inequalities for capacitated fixed-charge networks and build computational methods for their large-scale solution. The proposal suggests an innovative approach for investigating the polyhedral structure of capacitated fixed-charge network flow (CFNF). In particular, strong valid inequalities that exploit detailed network substructures will be developed based on an effective use of the submodularity of flows and the max flow-min cut theorem. This new approach unifies previous work done on CFNF through a systematic study, which is more generally applicable. Moreover, it allows the derivation of much stronger valid inequalities than known to date, as it uses crucial structural information that has not been exploited yet.If successful, the fundamental development and solution methods that will result from this project will improve the solvability of large-scale instances of a broad class of logistics, supply chain, telecom applications that contain fixed-charge network flow substructure. One of the immediate outcomes of the project is the development of stronger cutting planes for mixed integer programming software systems that utilize fixed-charge network substructures. These new, strong inequalities can immediately replace the weak ones currently in use to improve the performance of these software systems.

研究的目的是推导出容量限制的固定电荷网络的新的强有效不等式，并建立其大规模解决方案的计算方法。该建议提出了一种创新的方法来研究容量限制的固定电荷网络流（CFNF）的多面体结构。特别是，强大的有效的不等式，利用详细的网络子结构将开发的基础上，有效地利用子模块的流量和最大流量最小割定理。这种新的方法统一了以前的工作CFNF通过系统的研究，这是更普遍适用。此外，它允许推导出比迄今已知的更强的有效不等式，因为它使用了尚未被利用的关键结构信息。如果成功的话，该项目的基本开发和解决方法将提高包含固定费用网络流子结构的大规模物流，供应链和电信应用实例的可解性。该项目的直接成果之一是为利用固定电荷网络子结构的混合整数规划软件系统开发更强大的切割平面。这些新的强不等式可以立即取代目前使用的弱不等式，以提高这些软件系统的性能。