Mixed-Integer Optimization for Multi-Item Multi-Echelon Production and Distribution Planning

本研究的目标是(1)建立可能存在情景不确定性的复杂多物品多梯级生产与配送计划问题的固定费用网络流(FCNF)模型；(2)对FCNF的多面体结构进行严格的研究；(3)开发和实现FCNF的有效算法；(4)应用这些算法来解决上述问题。这笔拨款为在一般网络上开发FCNF的统一割平面理论提供资金，而不对子图的结构做出任何假设。所提出的开发割平面的方法将利用底层网络流信息。由此产生的不平等的显性和组合性将使人们能够描述在哪些条件下不平等是强的。它们还将使开发有效的分离算法成为可能。此外，针对确定性生产和配送计划问题提出的不等式将适用于其随机对应的问题，以解决需求和供应模式的不稳定性质。如果成功，所开发的求解方法将非常有效地解决工业中具有挑战性的生产和配送计划问题，以及定义在网络上的一大类混合整数规划，如电信网络设计和紧急医疗服务部署。开发的强大切割平面还可以集成到现有的商业或开源混合整数规划解算器中，这些解算器越来越多地用于最先进的计划和调度软件。研究活动将与研究生和本科生的教学和咨询紧密结合。研究成果将通过出版物和会议报告进一步传播。

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.