Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming

by Tawarmalani, Mohit; Sahinidis, Nikolaos V.

• ISBN13: 9781402010316
• ISBN10: 1402010311
• Format: Hardcover
• Copyright: 2003-02-01
• Publisher: Kluwer Academic Pub

Summary

This book provides an insightful and comprehensive treatment of convexification and global optimization of continuous and mixed-integer nonlinear programs. Developed for students, researchers, and practitioners, the book covers theory, algorithms, software, and applications. This thought-provoking book: develops a powerful and widely-applicable framework for constructing closed-form expressions of convex envelopes of nonlinear functions; presents a systematic treatment of branch-and-bound, while providing acceleration mechanisms and enhancements; unifies ideas at the interface between operations research and computer science, devising efficient algorithmic implementation for global optimization; offers students, modelers, and algorithm developers a rich collection of models, applications, and numerical examples; elucidates through geometric interpretations the concepts discussed throughout the book; shows how optimization theory can lead to breakthroughs in diverse application areas, including molecular design, process and product design, facility location, and supply chain design and operation; demonstrates that the BARON software developed by the authors can solve global optimization problems heretofore considered intractable, in an entirely automated manner on a personal computer. Audience: This book will be of interest to researchers in operations research, management science, applied mathematics, computer science, computational chemistry, and all branches of engineering. In addition, the book can be used in graduate level courses in nonlinear optimization, integer programming, global optimization, convex analysis, applied mathematics, and engineering design.

Author Biography

Mohit Tawarmalani: Purdue University, West Lafayette, IN, U.S.A. Nikolaos V. Sahinidis: University of Illinois, Urbana, IL, U.S.A.

Table of Contents

Preface	xiii
Acknowledgments	xvii
List of Figures	xix
List of Tables	xxiii
Introduction	1	(24)
The Mixed-Integer Nonlinear Program	5	(1)
Branch-and-Bound	6	(2)
Illustrative Example	8	(10)
A Separable Relaxation	9	(3)
Tighter Relaxation	12	(1)
Optimality-Based Range Reduction	12	(4)
Drawing Inferences from Constraints	16	(1)
Branching on the Incumbent	17	(1)
Outline of this Book	18	(7)
Convex Extensions	25	(46)
Introduction	26	(3)
Convex Extensions of 1.s.c. Functions	29	(11)
Multilinear Functions	40	(3)
Analysis of Convex Underestimators of x / y	43	(19)
Convex Envelope of x / y	44	(1)
Closed-Form Expression of Convex Envelope	45	(2)
Theoretical Comparison of Underestimators	47	(5)
Numerical Example	52	(4)
Concave Envelope of x / y	56	(1)
Relaxing the Positivity Requirement	57	(3)
Semidefinite Relaxation of x / y	60	(2)
Generalizations and Applications	62	(9)
Envelopes of (ax + by) / (cx + dy)	64	(1)
Convex Envelope of f(x)y2	65	(4)
Convex Envelope of f(x)/y	69	(1)
Summation of Functions	69	(2)
Product Disaggregation	71	(54)
Introduction	72	(3)
Preliminaries	75	(2)
Reformulations of a Rational Function	77	(4)
Tightness of the Reformulation Scheme	81	(10)
Special Instances of the Reformulation	91	(2)
Examples of the Reformulation Scheme	93	(7)
Example 1: Hock & Schittkowski (1981)	94	(1)
Example 2: Nuclear Reactor Reload Pattern Design	95	(2)
Example 3: Catalyst Mixing for Packed Bed Reactor	97	(3)
Reformulations of Hyperbolic Programs	100	(5)
Upper Bounding of 0--1 Hyperbolic Programs	105	(3)
A Branch-and-Bound Algorithm	108	(2)
Cardinality Constrained Hyperbolic Programs	110	(1)
Computational Results for CCH Programs	111	(14)
Comparison of Bounds	112	(1)
Performance of the Proposed Algorithm	112	(3)
p-Choice Facility Location	115	(10)
Relaxations of Factorable Programs	125	(22)
Nonlinear Relaxation Construction	125	(7)
Concavoconvex Functions	130	(2)
Polyhedral Outer-Approximation	132	(15)
Domain Reduction	147	(42)
Preliminaries	147	(6)
Legendre-Fenchel Transform	148	(4)
Lagrangian Relaxation	152	(1)
An Iterative Algorithm for Domain Reduction	153	(1)
Theoretical Framework: Abstract Minimization	154	(6)
Application to Traditional Models	160	(3)
Geometric Intuition	163	(1)
Domain Reduction Problem: Motivation	163	(1)
Relation to Earlier Works	164	(17)
Bounds Via Monotone Complementarity	177	(1)
Tightening using Reduced Costs	178	(1)
Linearity-based Tightening	179	(2)
Probing	181	(2)
Learning Reduction Procedure	183	(6)
Node Partitioning	189	(24)
Introduction	189	(1)
Partitioning Factorable Programs	190	(6)
Branching Variable Selection	190	(4)
Branching Point Selection	194	(2)
Finiteness Issues	196	(17)
Stochastic Integer Programs	197	(1)
The Question of Finiteness	198	(1)
Key to Finiteness	199	(1)
Lower Bounding Problem	200	(2)
Upper Bounding	202	(1)
Branching Scheme	203	(2)
Finiteness Proof	205	(1)
Enhancements	205	(2)
Extension to Mixed-Integer Recourse	207	(1)
Computational Results for Stochastic Programs	207	(6)
Implementation	213	(16)
Design Philosophy	213	(2)
Programming Languages and Portability	215	(1)
Supported Optimization Solvers	216	(1)
Data Storage and Associated Algorithms	216	(3)
Management of Work-Array	216	(1)
List of Open Nodes	217	(1)
Module Storage: Factorable Programming	218	(1)
Evaluating Derivatives	219	(2)
Algorithmic Enhancements	221	(3)
Multiple Solutions	221	(1)
Local Upper Bounds	222	(1)
Postponement	222	(1)
Finite Branching Schemes	223	(1)
Debugging Facilities	224	(1)
BARON Interface	224	(5)
Refrigerant Design Problem	229	(24)
Introduction	229	(1)
Problem Statement	230	(1)
Previous Work	231	(1)
Optimization Formulation	232	(17)
Modeling Physical Properties	235	(4)
Modeling Structural Constraints	239	(10)
Multiple Solutions	249	(1)
Computational Results	249	(4)
The Pooling Problem	253	(32)
Introduction	254	(2)
The p- and q-Formulations	256	(8)
The p-Formulation	256	(5)
The q-Formulation	261	(3)
The pq-Formulation	264	(12)
Properties of the pq-Formulation	266	(7)
Lagrangian Relaxations	273	(3)
Global Optimization of the Pooling Problem	276	(9)
Branching Strategy	278	(1)
Computational Experience	279	(6)
Miscellaneous Problems	285	(28)
Separable Concave Quadratic Programs	285	(4)
Indefinite Quadratic Programs	289	(4)
Linear Multiplicative Programs	293	(4)
Generalized Linear Multiplicative Programs	297	(1)
Univariate Polynomial Programs	298	(1)
Miscellaneous Benchmark Problems	298	(7)
Selected Mixed-Integer Nonlinear Programs	305	(8)
Design of Just-in-Time Flowshops	305	(6)
The Gupta-Ravindran Benchmarks	311	(2)
GAMS/BARON: A Tutorial	313	(90)
Introduction	314	(1)
Types of Problems GAMS/BARON Can Solve	315	(5)
Factorable Nonlinear Programming: MIP, NLP, and MINLP	315	(1)
Special Cases of BARON's Factorable Nonlinear Programming Solver	316	(4)
Software and Hardware Requirements	320	(1)
Model Requirements	320	(1)
Variable and Expression Bounds	320	(1)
Allowable Nonlinear Functions	321	(1)
How to Run GAMS/BARON	321	(1)
System Output	322	(3)
System Log	322	(2)
Termination Messages, Model and Solver Status	324	(1)
Algorithmic and System Options	325	(1)
Application to Multiplicative Programs	325	(31)
LMPs of Type 1	326	(3)
Controlling Local Search Requirements	329	(2)
Reducing Memory Requirements via Branching Options	331	(2)
Controlling Memory Requirements via Probing	333	(1)
Effects of Reformulation	334	(1)
LMPs of Type 2	335	(4)
Controlling Time Spent on Preprocessing LPs	339	(3)
LMPs of Type 3	342	(5)
Comparison with Local Search	347	(9)
Application to Pooling Problems	356	(20)
Controlling Time Spent in Preprocessing	364	(4)
Reducing Memory Requirements	368	(1)
Controlling the Size of the Search Tree	368	(3)
Controlling Local Search Time During Navigation	371	(1)
Reduced Branching Space	371	(1)
Pooling Problem Computations	372	(4)
Problems from globallib and minlplib	376	(4)
Local Landscape Analyzer	380	(3)
Finding the K Best or All Feasible Solutions	383	(20)
Motivation and Alternative Approaches	383	(2)
Finding All Solutions to Combinatorial Optimization Problems	385	(6)
Refrigerant Design Problem	391	(3)
Finding All Solutions to Systems of Nonlinear Equations	394	(9)
A GAMS Models for Pooling Problems	403	(32)
Problems Adhya 1, 2, 3, and 4	403	(8)
Problems Bental 4 and 5	411	(5)
Problems Foulds 2, 3, 4, and 5	416	(12)
Problems Haverly 1, 2, and 3	428	(3)
Problem RT 2	431	(4)
Bibliography	435	(28)
Index	463	(6)
Author Index	469