The objectives of this research are (1) to develop fixed-charge network flow (FCNF) models for complex multi-item multi-echelon production and distribution planning problems under possible scenario uncertainty, (2) to provide a rigorous study of the polyhedral structure of FCNF, (3) to develop and implement effective algorithms for FCNF, (4) to apply these algorithms to solve the aforementioned problems. This grant provides funding for the development of a unified theory of cutting planes for FCNF on a general network, without making any assumptions on the structure of the subgraphs. The proposed method for developing cutting planes will exploit the underlying network flow information. The explicit and combinatorial nature of the resulting inequalities will enable the characterization of the conditions under which the inequalities are strong. They will also enable the development of effective separation algorithms. Furthermore, the inequalities proposed for the deterministic production and distribution planning problems will be adapted to their stochastic counterparts to address the volatile nature of the demand and supply patterns.
If successful, the solution methods developed will be very effective in solving not only challenging production and distribution planning problems in industry, but also a large class of mixed-integer programs defined on networks, such as telecommunications network design and emergency medical services deployment. The strong cutting planes developed can also be integrated into existing commercial or open-source mixed-integer programming solvers, which are increasingly used in state-of-the-art planning and scheduling software. The research activities will be closely integrated with the teaching and advising of graduate and undergraduate students. The research results will be further disseminated through publications and conference presentations.