GOALI: Large Scale Dynamic Programming for Optimizing the Design and Operation of Complex Systems with Applications to Production Line Design

动态规划是描述和解决非线性离散优化问题的一个非常通用的框架。它允许明确地结合非此即彼的决策，以及可能存在于被建模系统中的潜在不确定性的影响。它的主要缺点是公式的底层状态空间相对于系统的大小有爆炸式增长的趋势。这笔赠款为制定程序提供资金，以便将需要考虑的国家空间的增长限制在可管理的比例内。这将通过两种方式来完成：(1)通过分层状态聚合来实现模型简化；(2)通过状态剪枝来加速求解。前一种方法可能会引入误差，通过计算近似结果误差的界限来控制误差。开发的模型和算法将与位于密歇根州沃伦的通用汽车研发中心的研究人员合作，在生产线设计的大规模问题上进行实施和验证。如果这项研究工作取得成功，由此产生的利用易于实施的动态规划技术对大规模复杂系统进行近似建模和优化的能力将极大地扩大制造业和服务业中适合分析的设计和操作问题的类别。

Dynamic programming is an extremely general framework for the formulation and solution of nonlinear discrete optimization problems. It allows for the explicit incorporation of either-or decisions as well as the effects of underlying uncertainty that may be present in the system being modeled. Its principal drawback is the tendency for the underlying state space of the formulation to grow explosively with respect to the size of the system. This grant provides funding for the development of procedures to limit to manageable proportions the growth of the state space that needs to be considered. This will be accomplished in two ways: (1) Model Simplification though hierarchical state aggregation; and (2) Solution Acceleration through state pruning. The former approach can introduce errors which will be controlled through the ability to compute bounds on the resulting error of the approximation. The models and algorithms developed will be implemented and validated on a large scale problem in production line design in cooperation with research staff at the General Motors R&D Center at Warren, Michigan. If this research effort is successful, the resulting ability to approximately model and optimize large scale complex systems with easily implemented dynamic programming techniques will greatly expand the class of design and operational problems in manufacturing and service sectors that are amenable to analysis.