Nonlinear Integer Programming

by Li, Duan; Sun, Xiaoling

• ISBN13: 9780387295039
• ISBN10: 0387295038
• Format: Hardcover
• Copyright: 2006-06-15
• Publisher: Springer-Verlag New York Inc

Summary

The methodological development of integer programming has grown by leaps and bounds in the past four decades, with its main focus on linear integer programming. However, the past few years have also witnessed certain promising theoretical and methodological achievements in nonlinear integer programming. These recent developments have produced applications of nonlinear (mixed) integer programming across a variety of various areas of scientific computing, engineering, management science and operations research. Its prominent applications include, for examples, portfolio selection, capital budgeting, production planning, resource allocation, computer networks, reliability networks and chemical engineering. In recognition of nonlinearity's academic significance in optimization and its importance in real world applications, NONLINEAR INTEGER PROGRAMMING is a comprehensive and systematic treatment of the methodology. The book's goal is to bring the state-of-the-art of the theoretical foundation and solution methods for nonlinear integer programming to students and researchers in optimization, operations research, and computer science. This book systemically investigates theory and solution methodologies for general nonlinear integer programming, and at the same time, provides a timely and comprehensive summary of the theoretical and algorithmic development in the last 30 years on this topic. The following are some features of the book: Duality theory for nonlinear integer programming is thoroughly discussed. Convergent Lagrangian and cutting methods for separable nonlinear integer programming are explained and demonstrated. Convexification scheme and the relation between the monotonicity and convexity is explored and illustrated. A solution framework is provided using global descent. Computational implementations for large-scale nonlinear integer programming problems are demonstrated for several efficient solution algorithms presented in the book.

Table of Contents

Dedication	v
List of Figures	xiii
List of Tables	xvi
Preface	xix
Acknowledgments	xxii
Introduction	1	(12)
Classification of Nonlinear Integer Programming Formulations	2	(2)
Examples of Applications	4	(4)
Resource allocation in production planning	4	(1)
Portfolio selection	4	(2)
Redundancy optimization in reliability networks	6	(1)
Chemical engineering	7	(1)
Difficulties and Challenges	8	(2)
Organization of the Book	10	(1)
Notes	11	(2)
Optimality, Relaxation and General Solution Procedures	13	(32)
Optimality Condition via Bounds	14	(1)
Partial Enumeration	14	(10)
Outline of the general branch-and-bound method	15	(2)
The back-track scheme	17	(7)
Continuous Relaxation and Lagrangian Relaxation	24	(4)
Continuous relaxation	24	(1)
Lagrangian relaxation	25	(1)
Continuous bound versus Lagrangian bound	26	(2)
Proximity between Continuous Solution and Integer Solution	28	(9)
Linear integer program	29	(2)
Linearly constrained separable convex integer program	31	(1)
Unconstrained convex integer program	32	(5)
Penalty Function Approach	37	(1)
Optimality Conditions for Unconstrained Binary Quadratic Problems	38	(6)
General case	38	(4)
Convex case	42	(2)
Notes	44	(1)
Lagrangian Duality Theory	45	(52)
Lagrangian Relaxation and Dual Formulation	45	(7)
Dual Search Methods	52	(18)
Subgradient method	52	(5)
Outer Lagrangian linearization method	57	(11)
Bundle method	68	(2)
Perturbation Function	70	(7)
Optimal Generating Multiplier and Optimal Primal-Dual Pair	77	(6)
Solution Properties of the Dual Problem	83	(5)
Lagrangian Decomposition via Copying Constraints	88	(7)
General Lagrangian decomposition schemes	88	(3)
0-1 quadratic case	91	(4)
Notes	95	(2)
Surrogate Duality Theory	97	(16)
Conventional Surrogate Dual Method	97	(7)
Surrogate dual and its properties	97	(2)
Surrogate dual search	99	(5)
Nonlinear Surrogate Dual Method	104	(8)
Notes	112	(1)
Nonlinear Lagrangian and Strong Duality	113	(36)
Convexification and Nonlinear Support: p-th power Nonlinear Lagrangian Formulation	113	(5)
Nonlinear Lagrangian Theory Using Equivalent Reformulation	118	(9)
Nonlinear Lagrangian Theory Using Logarithmic-Exponential Dual Formulation	127	(10)
Generalized Nonlinear Lagrangian Theory for Singly-Constrained Nonlinear Integer Programming Problems	137	(11)
Notes	148	(1)
Nonlinear Knapsack Problems	149	(60)
Continuous-Relaxation-Based Branch-and-Bound Methods	150	(9)
Multiplier search method	151	(6)
Pegging method	157	(2)
0-1 Linearization Method	159	(5)
0-1 linearization	159	(2)
Algorithms for 0-1 linear knapsack problem	161	(3)
Convergent Lagrangian and Domain Cut Algorithm	164	(17)
Derivation of the algorithm	165	(5)
Domain cut	170	(3)
The main algorithm	173	(3)
Multi-dimensional nonlinear knapsack problems	176	(5)
Concave Nonlinear Knapsack Problems	181	(7)
Linear approximation	181	(3)
Domain cut and linear approximation method	184	(4)
Reliability Optimization in Series-Parallel Reliability Networks	188	(7)
Maximal decreasing property	190	(5)
Implementation and Computational Results	195	(11)
Test problems	196	(2)
Heuristics for feasible solutions	198	(1)
Numerical results of Algorithm 6.2 for singly constrained cases	199	(2)
Numerical results of Algorithm 6.2 for multiply constrained cases	201	(1)
Numerical results of Algorithm 6.3	202	(1)
Comparison results	203	(3)
Notes	206	(3)
Separable Integer Programming	209	(32)
Dynamic Programming Method	209	(8)
Backward dynamic programming	210	(1)
Forward dynamic programming	211	(4)
Singly constrained case	215	(2)
Hybrid Method	217	(7)
Dynamic programming procedure	218	(1)
Incorporation of elimination procedure	219	(2)
Relaxation of (RSPk)	221	(3)
Convergent Lagrangian and Objective Level Cut Method	224	(14)
Motivation	224	(3)
Algorithm description	227	(6)
Implementation of dynamic programming	233	(3)
Computational experiment	236	(2)
Notes	238	(3)
Nonlinear Integer Programming with a Quadratic Objective Function	241	(24)
Quadratic Contour Cut	241	(4)
Ellipse of quadratic contour	242	(1)
Contour cuts of quadratic function	243	(2)
Convergent Lagrangian and Objective Contour Cut Method	245	(5)
Extension to Problems with Multiple Constraints	250	(4)
Extension to Problems with Indefinite q	254	(3)
Computational Results	257	(7)
Test problems	258	(2)
Computational results	260	(2)
Comparison with other methods	262	(2)
Note	264	(1)
Nonseparable Integer Programming	265	(28)
Branch-and-Bound Method based on Continuous Relaxation	265	(3)
Branching variables	267	(1)
Branching nodes	268	(1)
Lagrangian Decomposition Method	268	(4)
Monotone Integer Programming	272	(18)
Discrete polyblock method for (MIP)	273	(4)
Convexity and monotonicity	277	(4)
Equivalent transformation using convexification	281	(3)
Polyblock and convexification method for (MIP)	284	(2)
Computational results	286	(4)
Notes	290	(3)
Unconstrained Polynomial 0-1 Optimization	293	(22)
Roof Duality	293	(7)
Basic concepts	294	(3)
Relation to other linearization formulations	297	(2)
Quadratic case	299	(1)
Local Search	300	(1)
Basic Algorithm	301	(3)
Continuous Relaxation and its Convexification	304	(2)
Unconstrained Quadratic 0-1 Optimization	306	(7)
A polynomially solvable case	307	(1)
Equivalence to maximum-cut problem	308	(1)
Variable fixation	309	(4)
Notes	313	(2)
Constrained Polynomial 0-1 Programming	315	(34)
Reduction to Unconstrained Problem	315	(2)
Linearization Methods	317	(2)
Branch-and-Bound Method	319	(2)
Upper bounds and penalties	319	(1)
Branch-and-bound method	320	(1)
Cutting Plane Methods	321	(7)
Generalized covering relaxation	321	(3)
Lower bounding linear function	324	(2)
Linearization of polynomial inequality	326	(2)
Quadratic 0-1 Knapsack Problems	328	(20)
Lagrangian dual of (QKP)	328	(7)
Heuristics for finding feasible solutions	335	(4)
Branch-and-bound method	339	(2)
Alternative upper bounds	341	(7)
Notes	348	(1)
Two Level Methods for Constrained Polynomial 0-1 Programming	349	(24)
Revised Taha's Method	349	(11)
Definitions and notations	350	(2)
Fathoming, consistency and augmentation	352	(5)
Solution algorithm	357	(3)
Two-Level Method for p-Norm Surrogate Constraint Formulation	360	(8)
Convergent Lagrangian Method Using Objective Level Cut	368	(2)
Computational Results	370	(1)
Notes	371	(2)
Mixed-Integer Nonlinear Programming	373	(24)
Introduction	373	(2)
Branch-and-Bound Method	375	(2)
Generalized Benders Decomposition	377	(5)
Outer Approximation Method	382	(7)
Nonconvex Mixed-Integer Programming	389	(5)
Convex relaxation	390	(3)
Convexification method	393	(1)
Notes	394	(3)
Global Descent Methods	397	(22)
Local Search and Global Descent	398	(2)
Local minima and local search	398	(2)
Identification of global minimum from among local minima	400	(1)
A Class of Discrete Global Descent Functions	400	(10)
Condition (D1)	403	(1)
Condition (D2)	403	(2)
Condition (D3)	405	(5)
The Discrete Global Descent Method	410	(2)
Computational Results	412	(4)
Notes	416	(3)
References	419	(14)
Index	433