000			10431cam a2200265za04500
001			18374
003			CoBo-ECI
005			20160719104756.0
008			050627s2005 sz eng d
020			_a0817672389 _a3764372389 _a3764373741 _a9783764372385
040			_aDLC _cDLC _dOHX _dBAKER _dGZM _dDLC
082	0	0	_a519.77 _bN946r
100	1		_aNowak, Ivo. _989
245	1	0	_aRelaxation and decomposition methods for mixed integer nonlinear programming / _cIvo Nowak.
260			_aBasel ; _aBoston, Suiza : _bBirkhäuser, _bc2005.
300			_axvi, 213 p. : _bil. ; _c24 cm.
504			_aIncluye Bibliografía e indices
505			_aI 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
541			_aAmazon-444444001 _cCompra _d22/09/2014 _eOC19722 _h$175.500
650		0	_aPROGRAMACIÓN NO CONVEXAS _992
650		0	_aPROGRAMACIÓN INTEGRAL _990
650		0	_987 _aPROGRAMACIÓN LINEAL
856	4	1	_uhttp://www.loc.gov/catdir/toc/fy0701/2005053009.html _yTabla de contenido _qTOC
942			_2ddc _cBK
999			_c17147 _d17147