Vista normal Vista MARC Vista ISBD

Nowak, Ivo.

Relaxation and decomposition methods for mixed integer nonlinear programming / Ivo Nowak. - Basel ; Boston, Suiza : Birkhäuser, c2005. - xvi, 213 p. : il. ; 24 cm.

Incluye Bibliografía e indices

I Basic Concepts 1
1 Introduction 3
1.1 The structured nonconvex mixed integer nonlinear program .. . 3
1.2 Applications ...... ..... ................. 4
1.3 Outline of the solution approach . . ............... . 5
1.4 An illustrative example ... ...... . .... 6
2 Problem Formulations 9
2.1 The condensed formulation ....... .. .. . . 9
2.2 Smooth and disjunctive reformulations . . . . .. . . 10
2.2.1 Integrality constraints . .. . . . . 10
2.2.2 Disjunctive constraints . .... . .... . . . . . . . 10
2.2.3 Big-M constraints ..... .. . ......... .... 11
2.2.4 The smooth binary formulation . . .. . .. . .
2. Block-separabilit . . . . . . . ........... . . 12
2.3 Block-separable splitting-schemes . . I. ... . . . . . . . 12
2.3.1 The sparsity graph . ... ....... ..... . . 12
2.3.2 MINLP splitting-schemes . . . . . . . . . . . 12
2.33 IQQP splitting-schemes . . . ......... . . . 14
2.4 Separable reformulation of factorable programs . . .. . . . . 15
2.5 Extended block-separable reformulation . . . . . . 17
2.6 Other frmulations , . ..., .. . . . 18
3 Convex and Lagrangian Relaxations 21
3.1 Convexification of sets and functions . . . .. .. . . . . . 21
3.2 Convex underestimating-relaxations ..... . . . 23
3.3 Lagrangian relaxation ........ . . . . . . . . 24
3.4 Dual-equivalent convex relaxations . . . . . . . . . 25
3.5 Reducing the duality gap . ....... ... ... . . . 28
3.6 Augmented Lagrangians ... . . . . . . 31
4 Decomposition Methods 33
4.1 Lagrangian decomposition -- dual methods . . . . . . . 33
4.1.1 Subgradient methods . .. . ... . . 35
4.1.2 Dual cutting-plane methods . ......... . . . . . 36
4.1.3 Proximal bundle methods . . . . .. . . 38
4.2 Primal cutting-plane methods ..... . . . . . 39
4.3 Column generation ... . . . ....... . . . 12
4.3.1 A simple column generation method . . . 42
4.3.2 Initializing the RMP . .. . .... ... . . . .. 45
4.3.3 An improved column generation method . . . . . 49
4.4 Benders decomposition . ......... ..... . . . 52
5 Semidefinite Relaxations 55
5.1 Semidefinite and Lagrangian relaxations . ..... . . . . . . 55
5.2 Block-separable reformulation . . . . . . . . . . . . .. . . . . 58
5.3 Eigenvalue representation of the dual function . . . . . . . . . 59
5.4 Duality results and convex relaxation ..... . . 60
5.4.1 The trust region problem . . . . . . . 60
5.4.2 Dual-equivaence . ..... ............ . . . 61
5.4.3 Modifications ... ................... 63
5.4.4 Influence of decomposition on the dual function . . . . .. 64
5.5 Solving the Lagrangian dual problem (D) .... . .. 65
5.6 Numerical results. . . . . . . . . . . 66
5.6.1 Block structure . . ............... . . . 66
5.6.2 Network structure . . . . . .67
5.7 Computing relaxations of mixed linear quadratic programs . .. 69
6 Convex Underestimators 73
6.1 Interval arithmetic . . . . . . .......... 73
6.2 Bezier polynomials . . . . . . 75
6.3 o:-underestimators .. . . . ..... . 77
6.4 CCU-underestimators .................... . 78
6.5 Convexified polynomial underestimators . . . . . . . . 78
6.5.1 Rigorous underestimators . . . . . . . . . . . 80
6.5.2 Restricted sampling . . . . . . . . . . . . . . . . . 80
7 Cuts, Lower Bounds and Box Reduction 83
7.1 V alid cuts . . . . . . . . . . . . . . . . . . . . . . .. . . ... 83
7.1.1 Linearization cuts ........... .... ...... 84
7.1.2 Knapsack cuts ........ 84
7.1.3 Interval-gradient uts . .. ........ . 85
.1.4 Lagrangian cuts . . . . . . . . .. . . 86
.1.5 Level cuts . . . . . . . . ... .. . 87
7.1.6 Othervalid cuts ... . . . . ..... 87
7.2 Initialization of polyhedral relaxations . . .... 88
7.3 Lower bounds .... ... ... ... . ........ . . . . 88
7.3. NLP-bounds ......... ..... 89
73.2 MINLP-bounds .. . . . . . . . ..... . 90
7.33 Dual bounds ........ 90
7.3. LP-bounds . ....... .......... 90
7.4 Box reduction . . . . . . . . . . . . . . . . . . . . . . . .. . .. . 91
7.5 Numeerical results ...... .... 92
8 Local and Global Optimality Criteria 99
1 Local optimality conditions . . . . . . . . 99
8.2 Local strong duality of nonconvex QQPs .. . . . .. 101
8.3 Global optliaality cuts ............... ...... 105
8.4 Some global optiality critria for QQPs . . . . . . 106
8.5 Global optimality via interval-gradient cuts . . . .. ..... 110
9 Adaptive Discretization of Infinite Dimensional MINLPs 113
9.1 Aggregated discretizations ......... . 113
9.1.1 Multistage stochastic programs . . .. . . . 113
9.1.2 Optinal control problems ......... . 115
9.1.3 Abstract formulation ....... 116
9.2 Optimai mesh and scenario refinement . . . 116
9.3 Updating and solving relaxations ..... . 117
II Algorithms 119
10 Overview of Global Optimization Methods 121
10.1 Sampling heuristics ... .. . .. . . . . . . . i.123
10.2 ranch-and-bond methods . ....... . . . . . . . . 12
10.3 Successive approximation methods . . . . . . .. .126
10.4 Relaxation-based heuristics ......... 127
11 Deformation Heuristics 129
11.1 The algorithm of Mor6 and Wu ... ..... ........ . . 29
11.2 A MaxCut deformation heuristic . . . . . . . . . . .... 130
11.2.1 Problem formulation .. . .. . . . . .. . . 130
11 2.2 A M axCut algorithm . ................. . .... 132
11.2.3 Sam pling ...... . .... . ..... ..... 134
1 .12.4 Numerical results .. . . . . . .......... 135
11.3 Generalization to MINLP .......... 138
11.3.1 Parametric problem formulation . . . . . . . . . . . . . 138
11.3.2 A MINLP deformation algorithm . .. . . . . . . .. 139
11.3.3 Numerical results. . . .. . . . . .. . .. . . . 140
12 Rounding, Partitioning and Lagrangian Heuristics 143
12.1 A rounding heuristic ........ .............. . 143
12.2 A partitioning heuristic that uses central cuts . . ...... . . 145
12.3 Numerical results ................ . . . . . . . . 147
12.4 A Lagrangian heuristic .. . .. . . .. . 153
13 Branch-Cut-and-Price Algorithms 155
13.1 Branch.-and-bound algorithms . . . . . . . . ..... 155
13.1.1 Preliminaries ... . . ............ . 155
13.1.2 A generic branch-and-bound algorithm . . . . . .. 106
13.2 Convergence and finiteness . . ....... . .. ... . . 156
3.2.2 Finiteness . . . . . . . . . . . . . . . . . . . . . . . 157
13.2.1 Convergence..... . . 156
13.3 Consistent bounding operations .... . . . . ... . . .. 159
13.3.1 NLP-bounds . .. . .. . . . ...... . 159
1 ,3.32 LP-bounds . . . . . . .. . .... ... . ... . 160
13.3.3 Dual bounds ...... . ... .. .. 161
13.4 Branching ................. .. . 1 62
13.4.1 Rectangular subdivision rules ... . . . . . . . . . . . 162
13.4.2 Updating lower bounds . . . . ..... ... ...... . 163
13.5 Numerical results . . . . . . . ...... . 163
13.5.1 Network MaxCut experiments ...... 164
13.5.2 MINLP experiments .. ......... .. .... 169
13.5.3 Cost-efficient design of energy conversion systems . . .. . 175
13.6 Nonconvex polyhedral inner and outer approximations . . . . 176
14 LaGO --- An Object-Oriented Library for Solving MINLPs 181
14.1 Design philosophy .............. . . .. . 181
14.2 Related work .. .......... . . . . . .. 182
14.3 Structure . .. . . .. .... .. ... . . 183
14.4 The modules . . . . . ..... . . ... . .183
1 .441 Reformulation .. . . . . . . . . 183
14.4.2 Relaxation . .. . . 85
14.4.3 Solvers. . .. .... . 186


ISBN: 0817672389 3764372389 3764373741 9783764372385

Subjects--Topical Terms:
PROGRAMACIÓN NO CONVEXAS
PROGRAMACIÓN INTEGRAL
PROGRAMACIÓN LINEAL

Dewey Class. No.: 519.77 / N946r