Bridging the Gap between Heuristics and Optimization in Process Synthesis and Operations
N. V. Sahinidis,* K. Furman, S. Ahmed
National Science Foundation, CTS 97-04643

Heuristics in process synthesis and operations offer fast solutions but no guarantee of optimality. Optimization approaches, on the other hand, offer rigor but suffer combinatorial explosion of computational requirements. We pursue analytical investigations to characterize the behavior of heuristics and optimization algorithms and produce a framework that combines the strengths of the two approaches while eliminating their weaknesses. We proved that process planning is NP-hard and that synthesis of heat exchanger networks is NP-hard in the strong sense. As the relaxation gap of integer programming formulations for these problems asymptotically diminishes, we develop relaxation-based heuristics that are optimal in expectation.

Combinatorial Problems in Computational Chemistry
N. V. Sahinidis,* A. Vaia, M. Yu
University of Illinois; National Science Foundation, BES 98-73586

The enumeration of large, combinatorial search spaces presents a central conceptual difficulty in many problems in combinatorial chemistry, chemometrics, and molecular design. We develop novel mathematical models and algorithms to address such combinatorial challenges. In one application area, we develop models and algorithms for interpreting FTIR spectra. In another application area, we develop a systematic methodology for the design of environmentally benign alternative refrigerants. This has led to the identification of several novel potential alternatives. We develop molecular design techniques with an emphasis on minimizing the environmental impact over the entire life-cycle of the new compounds.

Branch-and-Reduce Algorithms for Global Optimization
N. V. Sahinidis,* M. Tawarmalani, J. P. Shectman, H. S. Ryoo
National Science Foundation, DMI 94-14615, DMI 95-02722

Realistic treatments of physical and engineering systems frequently involve nonlinear models whose optimization requires escaping from local minima traps. This project develops global optimization methodologies. The algorithms solve sequences of convex underestimating subproblems obtained by evolutionary subdivision of the search region. Novel features include optimally- and feasibility-based range reduction, new branching rules, new bounding schemes, and efficient heuristics to accelerate convergence. The project addresses applications in engineering design, molecular structure determination, and economics. Special classes of problems are also considered: minimization of concave functions over convex sets, minimization of products of convex functions, bilinear programs, integer programs, and factorable programs.

Modeling and Optimization Techniques for Scheduling Continuous Chemical Processes
N. V. Sahinidis,* E. Kourpas, J. P. Shectman
TAPPI Foundation; National Science Foundation, DMI 95-02722

The goal of this project is to develop novel modeling and optimization techniques for improving energy efficiency and productivity in the process industry. Production of paper, dyes, and polymers are some examples. In particular, we address: (1) the development of novel formulations for short-term, reactive scheduling of continuous production facilities with resource constraints and sequence-dependent changeovers, (2) the development of efficient optimization algorithms for solving the above scheduling formulations, and (3) the potential of the developed techniques to reduce waste and minimize costs.

BARON-An All-Purpose Global Optimization Package
N. V. Sahinidis,* M. Tawarmalani
National Science Foundation, DMI 94-14615, DMI 95-02722

The area of global optimization software is so important yet so underdeveloped. This projects aims to develop BARON: an all-purpose, high-performance global optimization methodology to support engineering design and manufacturing. BARON (Branch-And-Reduce-Optimization-Navigator) executes a global optimization strategy by navigating its way through user-provided subroutines. Its optimization strategy integrates conventional branch-and-bound with a wide variety of range-reduction tests and branching schemes. Specialized modules have been developed for special problem classes including concave minimization over polyhedra, polynomial programs, mixed integer and quadratic programs, and factorable programs.

Separable Concave Minimization over Polyhedral Sets
N. V. Sahinidis,* J. P. Shectman
National Science Foundation, DMI 94-14615, DMI 95-02722

In addition to having many industrial applications, separable concave minimization over polyhedra constitutes the definitive global optimization test problem. We develop a branch-and-reduce approach to this problem. The algorithm solves a sequence of linear programs and terminates finitely with the global minimum. Our proof of finiteness solves a long-standing question in the area of concave minimization; previous similar algorithms are merely infinite. Further, the algorithm makes possible for the first time the solution of large-scale problems on conventional computers. Problems with 100 concave variables are solved to globality in minutes on a standard engineering workstation.

Planning in the Process Industry under Uncertainty
N. V. Sahinidis,* S. Ahmed
National Science Foundation, DMI 94-14615, DMI 95-02722

As the chemical industry is becoming increasingly competitive, tools to hedge against uncertainty become increasingly important. The project develops a two-stage stochastic optimization approach to the problem of planning in the process industries. We consider both discrete and continuous random parameters. In one research direction, we introduce the upper partial mean as a new measure of robustness and developed robust process planning algorithms under uncertainty. In another research direction, we develop approximation algorithms for two-stage stochastic integer programs. We provide proofs that these schemes are optimal in expectation as the problem size increases.

A Lagrangian Approach to the Pooling Problem
N. V. Sahinidis,* N. Adhya, M. Tawarmalani
National Science Foundation, DMI 95-02722; Mobil Technology Center

Pooling and blending occur frequently in the petrochemical industry where crude oils, procured from various sources, are mixed together to manufacture several end-products. Finding optimal solutions to pooling problems requires the solution of nonlinear optimization problems with multiple local minima. We introduce a new Lagrangian relaxation approach for developing lower bounds for the pooling problem. We prove that, for the multiple quality case, the Lagrangian approach provides tighter lower bounds than the standard linear programming relaxations used in global optimization algorithms.