Relaxation and decomposition methods for mixed integer nonlinear programming / Ivo Nowak.

Por: Nowak, IvoTipo de material: TextoTextoEditor: Basel ; Boston, Suiza : Birkhäuser, c2005. Descripción: xvi, 213 p. : il. ; 24 cmISBN: 0817672389 ; 3764372389 ; 3764373741 ; 9783764372385 Tema(s): PROGRAMACIÓN NO CONVEXAS | PROGRAMACIÓN INTEGRAL | PROGRAMACIÓN LINEALClasificación CDD: 519.77 Recursos en línea: Tabla de contenido
Contenidos:
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
Etiquetas de esta biblioteca: No hay etiquetas de esta biblioteca para este título. Ingresar para agregar etiquetas.
    Valoración media: 0.0 (0 votos)
Tipo de ítem Ubicación actual Colección Signatura Info Vol Copia número Estado Fecha de vencimiento Código de barras Reserva de ítems
LIBRO - MATERIAL GENERAL LIBRO - MATERIAL GENERAL Bodega
Fondo general
Colección / Fondo / Acervo / Resguardo 519.77 N946r (Navegar estantería) EJ. 1 1 Disponible 023415
Total de reservas: 0

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

Amazon-444444001 Compra 22/09/2014 OC19722 $175.500

No hay comentarios en este titulo.

para colocar un comentario.

Haga clic en una imagen para verla en el visor de imágenes