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

研究方案的目的是推导出容量受限固定收费网络的新的强有效不等式，并建立其大规模解的计算方法。提出了一种研究容量约束固定电荷网络流(CFNF)多面体结构的创新方法。特别地，基于流的子模性和最大流-最小割集定理的有效利用，将得到利用详细网络子结构的强有效的不等式。这一新方法通过系统的研究统一了以往关于CFNF的工作，具有更广泛的适用性。此外，它允许推导出比目前已知的更强的有效不等式，因为它使用了尚未被利用的关键结构信息。如果成功，该项目将产生的基本开发和解决方法将提高包含固定费用网络流子结构的广泛类别的物流、供应链、电信应用的大规模实例的可解性。该项目的直接成果之一是为利用固定费用网络子结构的混合整数编程软件系统开发更强大的切割平面。这些新的、强的不平等可以立即取代目前正在使用的弱不平等，以提高这些软件系统的性能。

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.