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.