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.
