Relaxation And Decomposition Methods for Mixed Integer Nonlinear Programming

by Nowak, Ivo

• ISBN13: 9783764372385
• ISBN10: 3764372389
• Format: Hardcover
• Copyright: 2005-12-30
• Publisher: Birkhauser

Summary

This book presents a comprehensive description of theory, algorithms and software for solving nonconvex mixed integer nonlinear programs (MINLP). The main focus is on deterministic global optimization methods, which play a very important role in integer linear programming, and are used only recently in MINLP.The presented material consists of two parts. The first part describes basic optimization tools, such as block-separable reformulations, convex and Lagrangian relaxations, decomposition methods and global optimality criteria. Some of these results are presented here for the first time.The second part is devoted to algorithms. Starting with a short overview on existing methods, deformation, rounding, partitioning and Lagrangian heuristics, and a branch-cut-and-price algorithm are presented. The algorithms are implemented as part of an object-oriented library, called LaGO. Numerical results on several mixed integer nonlinear programs are reported to show abilities and limits of the proposed solution methods.The book contains many illustrations and an up-to-date bibliography. Because of the emphasis on practical methods, as well as the introduction into the basic theory, it is accessible to a wide audience and can be used both as a research as well as a graduate text.

Table of Contents

Preface	xi
Acknowledgments	xiv
Notation	xv
I. Basic Concepts	1	(118)
Introduction	3	(6)
The structured nonconvex mixed integer nonlinear program	3	(1)
Applications	4	(1)
Outline of the solution approach	5	(1)
An illustrative example	6	(3)
Problem Formulations	9	(12)
The condensed formulation	9	(1)
Smooth and disjunctive reformulations	10	(2)
Integrality constraints	10	(1)
Disjunctive constraints	10	(1)
Big-M constraints	11	(1)
The smooth binary formulation	11	(1)
Block-separability	12	(1)
Block-separable splitting-schemes	12	(3)
The sparsity graph	12	(1)
MINLP splitting-schemes	12	(2)
MIQQP splitting-schemes	14	(1)
Separable reformulation of factorable programs	15	(2)
Extended block-separable reformulation	17	(1)
Other formulations	18	(3)
Convex and Lagrangian Relaxations	21	(12)
Convexification of sets and functions	21	(2)
Convex underestimating-relaxations	23	(1)
Lagrangian relaxation	24	(1)
Dual-equivalent convex relaxations	25	(3)
Reducing the duality gap	28	(3)
Augmented Lagrangians	31	(2)
Decomposition Methods	33	(22)
Lagrangian decomposition --- dual methods	33	(6)
Subgradient methods	35	(1)
Dual cutting-plane methods	36	(2)
Proximal bundle methods	38	(1)
Primal cutting-plane methods	39	(3)
Column generation	42	(10)
A simple column generation method	42	(3)
Initializing the RMP	45	(4)
An improved column generation method	49	(3)
Benders decomposition	52	(3)
Semidefinite Relaxations	55	(18)
Semidefinite and Lagrangian relaxations	55	(3)
Block-separable reformulation	58	(1)
Eigenvalue representation of the dual function	59	(1)
Duality results and convex relaxation	60	(5)
The trust region problem	60	(1)
Dual-equivalence	61	(2)
Modifications	63	(1)
Influence of decomposition on the dual function	64	(1)
Solving the Lagrangian dual problem (D)	65	(1)
Numerical results	66	(3)
Block structure	66	(1)
Network structure	67	(2)
Computing relaxations of mixed linear quadratic programs	69	(4)
Convex Underestimators	73	(10)
Interval arithmetic	73	(2)
Bezier polynomials	75	(2)
α-underestimators	77	(1)
CGU-underestimators	78	(1)
Convexified polynomial underestimators	78	(5)
Rigorous underestimators	80	(1)
Restricted sampling	80	(3)
Cuts, Lower Bounds and Box Reduction	83	(16)
Valid cuts	83	(5)
Linearization cuts	84	(1)
Knapsack cuts	84	(1)
Interval-gradient cuts	85	(1)
Lagrangian cuts	86	(1)
Level cuts	87	(1)
Other valid cuts	87	(1)
Initialization of polyhedral relaxations	88	(1)
Lower bounds	88	(3)
NLP-bounds	89	(1)
MINLP-bounds	90	(1)
Dual bounds	90	(1)
LP-bounds	90	(1)
Box reduction	91	(1)
Numerical results	92	(7)
Local and Global Optimality Criteria	99	(14)
Local optimality conditions	99	(2)
Local strong duality of nonconvex QQPs	101	(4)
Global optimality cuts	105	(1)
Some global optimality criteria for QQPs	106	(4)
Global optimality via interval-gradient cuts	110	(3)
Adaptive Discretization of Infinite Dimensional MINLPs	113	(6)
Aggregated discretizations	113	(3)
Multistage stochastic programs	113	(2)
Optimal control problems	115	(1)
Abstract formulation	116	(1)
Optimal mesh and scenario refinement	116	(1)
Updating and solving relaxations	117	(2)
II. Algorithms	119	(70)
Overview of Global Optimization Methods	121	(8)
Sampling heuristics	123	(2)
Branch-and-bound methods	125	(1)
Successive approximation methods	126	(1)
Relaxation-based heuristics	127	(2)
Deformation Heuristics	129	(14)
The algorithm of More and Wu	129	(1)
A MaxCut deformation heuristic	130	(8)
Problem formulation	130	(2)
A MaxCut algorithm	132	(2)
Sampling	134	(1)
Numerical results	135	(3)
Generalization to MINLP	138	(5)
Parametric problem formulation	138	(1)
A MINLP deformation algorithm	139	(1)
Numerical results	140	(3)
Rounding, Partitioning and Lagrangian Heuristics	143	(12)
A rounding heuristic	143	(2)
A partitioning heuristic that uses central cuts	145	(2)
Numerical results	147	(6)
A Lagrangian heuristic	153	(2)
Branch-Cut-and-Price Algorithms	155	(26)
Branch-and-bound algorithms	155	(1)
Preliminaries	155	(1)
A generic branch-and-bound algorithm	156	(1)
Convergence and finiteness	156	(3)
Convergence	156	(1)
Finiteness	157	(2)
Consistent bounding operations	159	(3)
NLP-bounds	159	(1)
LP-bounds	160	(1)
Dual bounds	161	(1)
Branching	162	(1)
Rectangular subdivision rules	162	(1)
Updating lower bounds	163	(1)
Numerical results	163	(13)
Network MaxCut experiments	164	(5)
MINLP experiments	169	(6)
Cost-efficient design of energy conversion systems	175	(1)
Nonconvex polyhedral inner and outer approximations	176	(5)
LaGO --- An Object-Oriented Library for Solving MINLPs	181	(8)
Design philosophy	181	(1)
Related work	182	(1)
Structure	183	(1)
The modules	183	(6)
Reformulation	183	(2)
Relaxation	185	(1)
Solvers	186	(3)
Appendix	189	(6)
A. Future Perspectives	189	(2)
B. MINLP Problems	191	(4)
B.1 Instances from the MINLPLib	191	(2)
B.2 Random MIQQP problems	193	(2)
Bibliography	195	(16)
Index	211