• Tawarmalani, M. and N. V. Sahinidis, Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, 500 pages, Kluwer Academic Publishers, Boston MA, to appear in "Nonconvex Optimization And Its Applications" series in late October-early November 2002.

• Global Optimization of Mixed Integer Nonlinear Programs
  This work addresses the development of an efficient solution strategy for obtaining global optima of continuous, integer, and mixed integer nonlinear programs. Towards this end, we develop novel range reduction tests, relaxation schemes, and branching strategies which we incorporate into the prototypical branch and bound algorithm.

  We begin by developing a unifying theory of domain reduction strategies as a consequence of which we derive new as well as most range-reduction strategies currently used in nonlinear and integer linear programming. This reduction theory is based on conjugate/linear programming duality and leads to a learning heuristic that improves initial branching decisions by relaying data across siblings in a branch and bound tree. We then develop novel strategies for constructing linear relaxations of mixed integer nonlinear programs and prove that these relaxations enjoy quadratic convergence properties. Finally, we improve the standard branch and bound algorithm by allowing postponement of nodes and incorporating branching strategies that guarantee finiteness for certain classes of continuous global optimization problems.

  We describe our implementation, BARON, discussing, wherever appropriate, the use of suitable data-structures and associated algorithms. We present extensive computational experience with 435 test problems from various classes of global optimization problems, including indefinite quadratic programs, multiplicative programs, fractional 0-1 programs, and applications in pooling, engineering design, facility location and capacity expansion, fixed charge programming, power economies of scale, just-in-time manufacturing, and molecular design.

  • M. Tawarmalani and N. V. Sahinidis, Global Optimization of Mixed integer Nonlinear Programs: A Theoretical and Computational study, Mathematical Programming (submitted).
  • N. V. Sahinidis and M. Tawarmalani, Applications of Global Optimization to Process and Molecular Design, Computers and Chemical Engineering 24, 2157-2169, 2000.

• Convex Extensions
  We define a convex extension of a lower-semicontinuous function to be a convex function that is identical to the given function over a pre-specified subset of its domain. Convex extensions are not necessarily constructible or unique. We identify conditions under which a convex extension can be constructed. When multiple convex extensions exist, we characterize the tightest convex extension in a well-defined sense. Using the notion of a generating set, we establish conditions under which the tightest convex extension is the convex envelope. Then, we employ convex extensions to develop a constructive technique for deriving convex envelopes of nonlinear functions. Finally, using the theory of convex extensions we characterize the precise gaps exhibited by various underestimators of x/y over a rectangle and prove that the extensions theory provides convex relaxations that are much tighter than the relaxation provided by the classical outer-linearization of bilinear terms.
  • M. Tawarmalani and N. V. Sahinidis, Convex extensions and envelopes of lower semi-continous functions, Mathematical Programming (submitted).
  
  
• Convex Extensions as a Convexification Tool
  We present new techniques for constructing convex and concave envelopes of nonlinear functions using the theory of convex extensions. In particular, we develop the convex envelope and concave envelope of z=x/y over a hypercube. We show that the convex envelope is strictly tighter than previously known convex underestimators of x/y. We then propose a new relaxation technique for fractional programs which includes the derived envelopes. The resulting relaxation is shown to be a semidefinite program. Finally, we derive the convex envelope for a class of functions of the type f(x,y) over a hypercube under the assumption that f is concave in x and convex in y.
  • M. Tawarmalani and N. V. Sahinidis, Semidefinite Relaxations of Fractional Programs via Novel Convexification Techniques, Journal of Global Optimization (accepted).

• Hyperbolic Programming and p-choice Facility Location
  We develop 8 different mixed-integer convex programming reformulations of 0-1 hyperbolic programs. We obtain analytical results on the relative tightness of these formulations and propose a branch and bound algorithm for 0-1 hyperbolic programs. The main feature of the algorithm is that it reformulates the problem at every node of the search tree. We demonstrate that this algorithm has a superior convergence behavior than directly solving the relaxation derived at the root node. The algorithm is used to solve a discrete p-choice facility location problem for locating 10 restaurants in the city of Edmonton.
  • M. Tawarmalani, S. Ahmed and N.V. Sahinidis, Global Optimization of 0-1 Hyperbolic Programs, Journal of Global Optimization (submitted).

• Reformulations of Rational Functions
  We present mixed-integer linear programming reformulations of rational functions of 0-1 variables and analyze the tightness of the corresponding linear relaxations. In the process of doing so, we develop a number of new results. First, we consider the product of a single continuous variable and the sum of a number of continuous variables and show that "product disaggregation" (distributing the product over the sum) leads to tighter linear programming relaxations, much like variable disaggregation does in mixed-integer linear programming. Second, we derive closed-form expressions characterizing the exact region over which these relaxations improve when the bounds of participating variables are reduced. Third, we prove that the task of bounding general linear fractional functions of 0-1 variables is NP-hard.
  • M. Tawarmalani, S. Ahmed and N. V. Sahinidis, Reformulations of Rational Functions of 0-1 Variables, European Journal of Operational Research(submitted).

• Molecular Design
  The enumeration of large, combinatorial search spaces presents a central conceptual difficulty in molecular design. To address this difficulty, we develop a branch-and-bound algorithm which guarantees globally optimal solutions to a new mixed-integer nonlinear programming formulation for molecular design. We use this algorithm to identify several novel replacements of Freon 12. Some of the proposed alternatives possess thermodynamic properties which render them more efficient than Freon 12 in the context of a typical refrigeration cycle.
  • N. V. Sahinidis, M. Tawarmalani and M. Yu, Design of Alternative Refrigerants via Global Optimization, (in preparation)
  • N. V. Sahinidis and M. Tawarmalani, Applications of Global Optimization to Process and Molecular Design, Computers & Chemical Engineering 24(9-10), 2157-2169, 2000.

• Pooling Problems
  Pooling and blending problems 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. We present computational results on a set of 13 problems which includes 4 particularly difficult problems we constructed.
  • N. Adhya, M. Tawarmalani and N. V. Sahinidis, A Lagrangian Approach to Pooling Problems, Industrial & Engineering Chemistry, 38(5), 1956-1972, 1999 (copyright with journal).

• Stochastic Integer Programming
  This work addresses a general class of two-stage stochastic programs with integer recourse and discrete distributions. We exploit the structure of the value function of the second stage problem to develop a novel global optimization algorithm. The proposed scheme departs from those in the current literature in that it avoids explicit enumeration of the search space while guaranteeing finite termination. Our computational results indicate superior performance of the proposed algorithm in comparison to the existing literature.
  • S. Ahmed, M. Tawarmalani and N. V. Sahinidis, A Finite Algorithm for Two-stage Stochastic Integer Programs, Mathematical Programming (submitted).

Email Address: mtawarma@mgmt.purdue.edu
URL: http://web.ics.purdue.edu/~mtawarma/