Presidential Young Investigator Award: Parallel Algorithms for Integer and Mixed Integer Nonlinear Programs Arising in the Management and Design of Chemical Processes

化工过程工程中的许多问题，包括系统的工艺设计、改造设计、间歇调度、生产计划、设施布局和装置启动等，都可以自然地建模为混合整数非线性规划(MINLP)。虽然针对各种具体情况已有大量的模型问世，但由于传统的求解技术仅对有限大小的模型有效，因此MINLP方法的实际应用受到了限制。这一长期研究计划的一个重要目标是开发用于求解MINLP的高度并行算法。特别是，这项研究寻求能够使用数百个强大的处理器来大幅扩展MINLP的可处理性范围。解决方案能力的显著提高对于将多目标、逼真的物理、灵活性和稳健性纳入工程设计和运营模型至关重要。在开发有效的并行MINLP算法的过程中，必须解决的三个重要问题是：(1)问题结构的系统开发(2)处理机之间的工作量划分和(3)利用并发可用信息来提高算法性能。理解这些问题的核心是开发专用并行算法的性能。理解这些问题的核心是为高度结构的整数程序开发特殊目的的并行算法。研究将沿着两条互补的道路进行：(1)开发通用并行MINLP算法(2)开发用于高结构整数程序的专用并行算法。这两种途径的基本目标都是学习如何有效地使用大量并行，同时利用特定于问题的特性。

A broad range of chemical process engineering problems including systematic process design, retrofit design, batch scheduling, production planning, facility layout, and plant startup may be naturally modeled as mixed integer nonlinear programs (MINLP). Although a large number of models have been published for a variety of specific situations, practical application of MINLP methods has been limited because conventional solution techniques are effective only on models of limited size. An important goal of this long term research program is the development of highly parallel algorithms for solving MINLP. In particular, this research seeks to be able to use hundreds of powerful processors to substantially extend the range of tractability for MINLP. The dramatic increase in solution capability is critical in incorporating multiple objectives, realistic physics, flexibility, and robustness into engineering design and operation models. Three important issues that must be addressed in the course of developing effective parallel MINLP algorithms are: (1) the systematic exploitation of problem structure (2) the partitioning of the workload among processors and (3) the utilization of concurrently available information to improve algorithm performance. Central to understanding these issues is the development of special purpose parallel algorithm performance. Central to understanding these issues is the development of special purpose parallel algorithms for highly structured integer programs. Research will proceed along two complementary paths: (1) development of general purpose parallel MINLP algorithms (2) development of special purpose parallel algorithms for highly structured integer programs. The underlying goal of both paths is to learn how to effectively use massive amounts of parallelism while at the same time exploiting problem specific features.