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

多项目多梯次生产和配送计划的混合整数优化

• 批准号: 0917952
• 负责人: Simge Kucukyavuz
• 金额: $ 23.61万
• 依托单位: Ohio State University Research Foundation -DO NOT USE
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-12-22 至 2012-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0917952&HistoricalAwards=false
• 关键词: Mixed; Integer; Optimization; Multi; Item

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.

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