Central Library

Normal view MARC view ISBD view

Optimization of computer networks : modeling and algorithms : a hands-on approach / Pablo Pavon Marino.

By: Marino, Pablo Pavon [author.].
Contributor(s): IEEE Xplore (Online Service) [distributor.] | Wiley [publisher.].
Material type: materialTypeLabelBookPublisher: Southern Gate, Chichester, West Sussex, United Kingdom : Wiley ; 2016Distributor: [Piscataqay, New Jersey] : IEEE Xplore, [2016]Description: 1 PDF (xx, 375 pages) : illustrations.Content type: text Media type: electronic Carrier type: online resourceISBN: 9781119114840.Subject(s): Network performance (Telecommunication) -- Mathematical models | Computer networks -- Mathematical models | Computer algorithmsGenre/Form: Electronic books.DDC classification: 004.601 Online resources: Abstract with links to resource Also available in print.
Contents:
About the Author xv -- Preface xvii -- Acknowledgments xxi -- 1 Introduction 1 -- 1.1 What is a Communication Network? 1 -- 1.2 Capturing the Random User Behavior 4 -- 1.3 Queueing Theory and Optimization Theory 5 -- 1.4 The Rationale and Organization of this Book 6 -- 1.4.1 Part I: Modeling 6 -- 1.4.2 Part II: Algorithms 7 -- 1.4.3 Basic Optimization Requisites: Appendices I, II, and III 10 -- 1.4.4 Net2Plan Tool: Appendix IV 11 -- Part I MODELING -- 2 Definitions and Notation 15 -- 2.1 Notation for Sets, Vectors and Matrices 15 -- 2.1.1 Norm Basics 15 -- 2.1.2 Set Basics 16 -- 2.2 Network Topology 17 -- 2.3 Installed Capacities 19 -- 2.4 Traffic Demands 19 -- 2.4.1 Unicast, Anycast, and Multicast Demands 20 -- 2.4.2 Elastic versus Inelastic Demands 21 -- 2.5 Traffic Routing 21 -- References 22 -- 3 Performance Metrics in Networks 23 -- 3.1 Introduction 23 -- 3.2 Delay 23 -- 3.2.1 Link Delay 23 -- 3.2.2 End-to-End Delay 27 -- 3.2.3 Average Network Delay 27 -- 3.2.4 Convexity Properties 27 -- 3.3 Blocking Probability 28 -- 3.3.1 Link Blocking Probability 28 -- 3.3.2 Demand and Network Blocking Probability 30 -- 3.3.3 Other Blocking Estimations 31 -- 3.3.4 Convexity Properties 34 -- 3.4 Average Number of Hops 34 -- 3.5 Network Congestion 36 -- 3.6 Network Cost 36 -- 3.7 Network Resilience Metrics 37 -- 3.7.1 Shared Risk Groups 40 -- 3.7.2 Simplified Availability Calculations 41 -- 3.7.3 General Model 41 -- 3.8 Network Utility and Fairness in Resource Allocation 44 -- 3.8.1 Fairness in Resource Allocation 44 -- 3.8.2 Fairness and Utility Functions 45 -- 3.8.3 Convexity Properties 47 -- 3.9 Notes and Sources 47 -- 3.10 Exercises 49 -- References 51 -- 4 Routing Problems 53 -- 4.1 Introduction 53 -- 4.2 Flow-Path Formulation 54 -- 4.2.1 Optimality Analysis 55 -- 4.2.2 Candidate Path List Pre-Computation 58 -- 4.2.3 Ranking of Paths Elaboration 58 -- 4.2.4 Candidate Path List Augmentation (CPLA) 59 -- 4.3 Flow-Link Formulation 61 -- 4.3.1 Flow Conservation Constraints 62.
4.3.2 Obtaining the Routing from xde Variables 63 -- 4.3.3 Optimality Analysis 64 -- 4.4 Destination-Link Formulation 65 -- 4.4.1 Obtaining the Routing Tables from xte Variables 67 -- 4.4.2 Some Properties of the Routing Table Representation 67 -- 4.4.3 Comparing Flow-Based and Destination-Based Routing 71 -- 4.5 Convexity Properties of Performance Metrics 71 -- 4.6 Problem Variants 72 -- 4.6.1 Anycast Routing 72 -- 4.6.2 Multicast Routing 74 -- 4.6.3 Non-Bifurcated Routing 75 -- 4.6.4 Integral Routing 77 -- 4.6.5 Destination-Based Shortest Path Routing 77 -- 4.6.6 SRG-Disjoint 1+1 Dedicated Protection Routing 79 -- 4.6.7 Shared Restoration Routing 80 -- 4.6.8 Multi-Hour Routing 81 -- 4.7 Notes and Sources 83 -- 4.8 Exercises 83 -- References 86 -- 5 Capacity Assignment Problems 88 -- 5.1 Introduction 88 -- 5.2 Long-Term Capacity Planning Problem Variants 89 -- 5.2.1 Capacity Planning for Concave Costs 89 -- 5.2.2 Capacity Planning with Modular Capacities 94 -- 5.2.3 Multi-Period Capacity Planning 97 -- 5.3 Fast Capacity Allocation Problem Variants: Wireless Networks 98 -- 5.3.1 The Wireless Channel 99 -- 5.3.2 Wireless Networks 100 -- 5.3.3 Modeling Wireless Networks 101 -- 5.4 MAC Design in Hard-Interference Scenarios 104 -- 5.4.1 Optimization in Random Access Networks 105 -- 5.4.2 Optimization in Carrier-Sense Networks 109 -- 5.5 Transmission Power Optimization in Soft Interference Scenarios 113 -- 5.6 Notes and Sources 116 -- 5.7 Exercises 117 -- References 118 -- 6 Congestion Control Problems 120 -- 6.1 Introduction 120 -- 6.2 NUM Model 121 -- 6.2.1 Utility Functions for Elastic and Inelastic Traffic 121 -- 6.2.2 Fair Congestion Control 122 -- 6.2.3 Optimality Conditions 123 -- 6.3 Case Study: TCP 124 -- 6.3.1 Window-Based Flow Control 125 -- 6.3.2 TCP Reno 126 -- 6.3.3 TCP Vegas 131 -- 6.4 Active Queue Management (AQM) 134 -- 6.4.1 A Simplified Model of the TCP-AQM Interplay 135 -- 6.5 Notes and Sources 136 -- 6.6 Exercises 137 -- References 139 -- 7 Topology Design Problems 141.
7.1 Introduction 141 -- 7.2 Node Location Problems 142 -- 7.2.1 Problem Variants 143 -- 7.2.2 Results 144 -- 7.3 Full Topology Design Problems 146 -- 7.3.1 Problem Variants 148 -- 7.3.2 Results 150 -- 7.4 Multilayer Network Design 152 -- 7.5 Notes and Sources 154 -- 7.6 Exercises 154 -- References 157 -- Part II ALGORITHMS -- 8 Gradient Algorithms in Network Design 161 -- 8.1 Introduction 161 -- 8.2 Convergence Rates 163 -- 8.3 Projected Gradient Methods 164 -- 8.3.1 Basic Gradient Projection Algorithm 165 -- 8.3.2 Scaled Projected Gradient Method 165 -- 8.3.3 Singular and Ill-Conditioned Problems 168 -- 8.4 Asynchronous and Distributed Algorithm Implementations 169 -- 8.5 Non-Smooth Functions 172 -- 8.6 Stochastic Gradient Methods 174 -- 8.7 Stopping Criteria 176 -- 8.8 Algorithm Design Hints 177 -- 8.8.1 Dimensioning the Step Size 177 -- 8.8.2 Discrete Step Length 178 -- 8.8.3 Heavy-Ball Methods 179 -- 8.9 Notes and Sources 181 -- 8.10 Exercises 181 -- References 182 -- 9 Primal Gradient Algorithms 184 -- 9.1 Introduction 184 -- 9.2 Penalty Methods 185 -- 9.2.1 Interior Penalty Methods 185 -- 9.2.2 Exterior Penalty Methods 186 -- 9.3 Adaptive Bifurcated Routing 188 -- 9.3.1 Removing Equality Constraints 189 -- 9.3.2 Optimality and Stability 190 -- 9.3.3 Implementation Example 192 -- 9.4 Congestion Control using Barrier Functions 197 -- 9.4.1 Implementation Example 198 -- 9.4.2 Exterior Penalty 200 -- 9.5 Persistence Probability Adjustment in MAC Protocols 201 -- 9.5.1 Implementation Example 203 -- 9.6 Transmission Power Assignment in Wireless Networks 205 -- 9.6.1 Implementation Example 207 -- 9.7 Notes and Sources 210 -- 9.8 Exercises 211 -- References 213 -- 10 Dual Gradient Algorithms 214 -- 10.1 Introduction 214 -- 10.2 Adaptive Routing in Data Networks 217 -- 10.2.1 Optimality and Stability 219 -- 10.2.2 Implementation Example 219 -- 10.3 Backpressure (Center-Free) Routing 221 -- 10.3.1 Relation between and Average Queue Sizes, Qnd 224 -- 10.3.2 Implementation Example 225.
10.4 Congestion Control 228 -- 10.4.1 Optimality and Stability Conditions 229 -- 10.4.2 Implementation Example 230 -- 10.5 Decentralized Optimization of CSMA Window Sizes 231 -- 10.5.1 Implementation Example 234 -- 10.6 Notes and Sources 236 -- 10.7 Exercises 236 -- References 238 -- 11 Decomposition Techniques 240 -- 11.1 Introduction 240 -- 11.2 Theoretical Fundamentals 241 -- 11.2.1 Primal Decomposition 241 -- 11.2.2 Dual Decomposition 244 -- 11.2.3 Other Decompositions 246 -- 11.3 Cross-Layer Congestion Control and QoS Capacity Allocation 247 -- 11.3.1 Implementation Example 249 -- 11.4 Cross-Layer Congestion Control and Backpressure Routing 249 -- 11.4.1 Implementation Example 252 -- 11.5 Cross-Layer Congestion Control and Power Allocation 253 -- 11.5.1 Implementation Example 254 -- 11.6 Multidomain Routing 256 -- 11.6.1 Implementation Example 258 -- 11.7 Dual Decomposition in Non-Convex Problems 259 -- 11.7.1 Implementation Example 261 -- 11.8 Notes and Sources 261 -- 11.9 Exercises 263 -- References 265 -- 12 Heuristic Algorithms 266 -- 12.1 Introduction 266 -- 12.1.1 What Complexity Theory Tells us that We cannot Do 266 -- 12.1.2 Our Options 267 -- 12.1.3 Organization and Rationale of this Chapter 268 -- 12.2 Heuristic Design Keys 270 -- 12.2.1 Heuristic Types 270 -- 12.2.2 Intensification versus Diversification 271 -- 12.2.3 How to Assess the Solution Quality 271 -- 12.2.4 Stop Conditions 272 -- 12.2.5 Defining the Cost or Fitness Function 272 -- 12.2.6 Coding the Solution 273 -- 12.3 Local Search Algorithms 273 -- 12.3.1 Design Hints 274 -- 12.4 Simulated Annealing 276 -- 12.4.1 Design hints 277 -- 12.5 Tabu Search 278 -- 12.5.1 Design Hints 280 -- 12.6 Greedy Algorithms 281 -- 12.7 GRASP 282 -- 12.8 Ant Colony Optimization 283 -- 12.8.1 Design Hints 286 -- 12.9 Evolutionary Algorithms 288 -- 12.9.1 Design Hints 289 -- 12.10 Case Study: Greenfield Plan with Recovery Schemes Comparison 291 -- 12.10.1 Case Study Description 291 -- 12.10.2 Algorithm Description 293.
12.10.3 Combining Heuristics and ILPs 295 -- 12.10.4 Results 296 -- 12.11 Notes and Sources 297 -- 12.12 Exercises 297 -- References 299 -- A Convex Sets. Convex Functions 301 -- A.1 Convex Sets 301 -- A.2 Convex and Concave Functions 303 -- A.2.1 Convexity in Differentiable Functions 303 -- A.2.2 Strong Convexity/Concavity 306 -- A.2.3 Convexity in Non-Differentiable Functions 306 -- A.2.4 Determining the Curvature of a Function 307 -- A.2.5 Sub-level Sets 310 -- A.2.6 Epigraphs 311 -- A.3 Notes and Sources 311 -- Reference 312 -- B Mathematical Optimization Basics 313 -- B.1 Optimization Problems 313 -- B.2 A Classification of Optimization Problems 315 -- B.2.1 Linear Programming 315 -- B.2.2 Convex Programs 318 -- B.2.3 Nonlinear Programs 320 -- B.2.4 Integer Programs 321 -- B.3 Duality 324 -- B.3.1 Dual Function 324 -- B.4 Optimality Conditions 330 -- B.4.1 Optimality Conditions in Problems with Strong Duality 330 -- B.4.2 Graphical Interpretation of KKT Conditions 333 -- B.4.3 Optimality Conditions in Problems Without Strong Duality 336 -- B.5 Sensitivity Analysis 337 -- B.6 Notes and Sources 339 -- References 340 -- C Complexity Theory 341 -- C.1 Introduction 341 -- C.2 Deterministic Machines and Deterministic Algorithms 342 -- C.2.1 Complexity of a Deterministic Algorithm 342 -- C.2.2 Worst-Case Algorithm Complexity 343 -- C.2.3 Asymptotic Algorithm Complexity 343 -- C.2.4 Complexity is a Real Barrier 345 -- C.3 Non-Deterministic Machines and Non-Deterministic Algorithms 346 -- C.3.1 Complexity of a Non-Deterministic Algorithm 347 -- C.4 N and NP Complexity Classes 347 -- C.5 Polynomial Reductions 349 -- C.5.1 A Polynomial Time Reduction Example 350 -- C.6 NP-Completeness 351 -- C.6.1 An Example Proving NP-Completeness for a Problem 352 -- C.7 Optimization Problems and Approximation Schemes 352 -- C.7.1 The NP-�yClass 353 -- C.7.2 Approximation Algorithms 354 -- C.7.3 PTAS Reductions 356 -- C.7.4 NP Complete Problems 356 -- C.8 Complexity of Network Design Problems 357.
C.9 Notes and Sources 357 -- References 358 -- D Net2Plan 359 -- D.1 Net2Plan 359 -- D.2 On the Role of Net2Plan in this Book 360 -- Index 363.
    average rating: 0.0 (0 votes)
No physical items for this record

Includes bibliographical references and index.

About the Author xv -- Preface xvii -- Acknowledgments xxi -- 1 Introduction 1 -- 1.1 What is a Communication Network? 1 -- 1.2 Capturing the Random User Behavior 4 -- 1.3 Queueing Theory and Optimization Theory 5 -- 1.4 The Rationale and Organization of this Book 6 -- 1.4.1 Part I: Modeling 6 -- 1.4.2 Part II: Algorithms 7 -- 1.4.3 Basic Optimization Requisites: Appendices I, II, and III 10 -- 1.4.4 Net2Plan Tool: Appendix IV 11 -- Part I MODELING -- 2 Definitions and Notation 15 -- 2.1 Notation for Sets, Vectors and Matrices 15 -- 2.1.1 Norm Basics 15 -- 2.1.2 Set Basics 16 -- 2.2 Network Topology 17 -- 2.3 Installed Capacities 19 -- 2.4 Traffic Demands 19 -- 2.4.1 Unicast, Anycast, and Multicast Demands 20 -- 2.4.2 Elastic versus Inelastic Demands 21 -- 2.5 Traffic Routing 21 -- References 22 -- 3 Performance Metrics in Networks 23 -- 3.1 Introduction 23 -- 3.2 Delay 23 -- 3.2.1 Link Delay 23 -- 3.2.2 End-to-End Delay 27 -- 3.2.3 Average Network Delay 27 -- 3.2.4 Convexity Properties 27 -- 3.3 Blocking Probability 28 -- 3.3.1 Link Blocking Probability 28 -- 3.3.2 Demand and Network Blocking Probability 30 -- 3.3.3 Other Blocking Estimations 31 -- 3.3.4 Convexity Properties 34 -- 3.4 Average Number of Hops 34 -- 3.5 Network Congestion 36 -- 3.6 Network Cost 36 -- 3.7 Network Resilience Metrics 37 -- 3.7.1 Shared Risk Groups 40 -- 3.7.2 Simplified Availability Calculations 41 -- 3.7.3 General Model 41 -- 3.8 Network Utility and Fairness in Resource Allocation 44 -- 3.8.1 Fairness in Resource Allocation 44 -- 3.8.2 Fairness and Utility Functions 45 -- 3.8.3 Convexity Properties 47 -- 3.9 Notes and Sources 47 -- 3.10 Exercises 49 -- References 51 -- 4 Routing Problems 53 -- 4.1 Introduction 53 -- 4.2 Flow-Path Formulation 54 -- 4.2.1 Optimality Analysis 55 -- 4.2.2 Candidate Path List Pre-Computation 58 -- 4.2.3 Ranking of Paths Elaboration 58 -- 4.2.4 Candidate Path List Augmentation (CPLA) 59 -- 4.3 Flow-Link Formulation 61 -- 4.3.1 Flow Conservation Constraints 62.

4.3.2 Obtaining the Routing from xde Variables 63 -- 4.3.3 Optimality Analysis 64 -- 4.4 Destination-Link Formulation 65 -- 4.4.1 Obtaining the Routing Tables from xte Variables 67 -- 4.4.2 Some Properties of the Routing Table Representation 67 -- 4.4.3 Comparing Flow-Based and Destination-Based Routing 71 -- 4.5 Convexity Properties of Performance Metrics 71 -- 4.6 Problem Variants 72 -- 4.6.1 Anycast Routing 72 -- 4.6.2 Multicast Routing 74 -- 4.6.3 Non-Bifurcated Routing 75 -- 4.6.4 Integral Routing 77 -- 4.6.5 Destination-Based Shortest Path Routing 77 -- 4.6.6 SRG-Disjoint 1+1 Dedicated Protection Routing 79 -- 4.6.7 Shared Restoration Routing 80 -- 4.6.8 Multi-Hour Routing 81 -- 4.7 Notes and Sources 83 -- 4.8 Exercises 83 -- References 86 -- 5 Capacity Assignment Problems 88 -- 5.1 Introduction 88 -- 5.2 Long-Term Capacity Planning Problem Variants 89 -- 5.2.1 Capacity Planning for Concave Costs 89 -- 5.2.2 Capacity Planning with Modular Capacities 94 -- 5.2.3 Multi-Period Capacity Planning 97 -- 5.3 Fast Capacity Allocation Problem Variants: Wireless Networks 98 -- 5.3.1 The Wireless Channel 99 -- 5.3.2 Wireless Networks 100 -- 5.3.3 Modeling Wireless Networks 101 -- 5.4 MAC Design in Hard-Interference Scenarios 104 -- 5.4.1 Optimization in Random Access Networks 105 -- 5.4.2 Optimization in Carrier-Sense Networks 109 -- 5.5 Transmission Power Optimization in Soft Interference Scenarios 113 -- 5.6 Notes and Sources 116 -- 5.7 Exercises 117 -- References 118 -- 6 Congestion Control Problems 120 -- 6.1 Introduction 120 -- 6.2 NUM Model 121 -- 6.2.1 Utility Functions for Elastic and Inelastic Traffic 121 -- 6.2.2 Fair Congestion Control 122 -- 6.2.3 Optimality Conditions 123 -- 6.3 Case Study: TCP 124 -- 6.3.1 Window-Based Flow Control 125 -- 6.3.2 TCP Reno 126 -- 6.3.3 TCP Vegas 131 -- 6.4 Active Queue Management (AQM) 134 -- 6.4.1 A Simplified Model of the TCP-AQM Interplay 135 -- 6.5 Notes and Sources 136 -- 6.6 Exercises 137 -- References 139 -- 7 Topology Design Problems 141.

7.1 Introduction 141 -- 7.2 Node Location Problems 142 -- 7.2.1 Problem Variants 143 -- 7.2.2 Results 144 -- 7.3 Full Topology Design Problems 146 -- 7.3.1 Problem Variants 148 -- 7.3.2 Results 150 -- 7.4 Multilayer Network Design 152 -- 7.5 Notes and Sources 154 -- 7.6 Exercises 154 -- References 157 -- Part II ALGORITHMS -- 8 Gradient Algorithms in Network Design 161 -- 8.1 Introduction 161 -- 8.2 Convergence Rates 163 -- 8.3 Projected Gradient Methods 164 -- 8.3.1 Basic Gradient Projection Algorithm 165 -- 8.3.2 Scaled Projected Gradient Method 165 -- 8.3.3 Singular and Ill-Conditioned Problems 168 -- 8.4 Asynchronous and Distributed Algorithm Implementations 169 -- 8.5 Non-Smooth Functions 172 -- 8.6 Stochastic Gradient Methods 174 -- 8.7 Stopping Criteria 176 -- 8.8 Algorithm Design Hints 177 -- 8.8.1 Dimensioning the Step Size 177 -- 8.8.2 Discrete Step Length 178 -- 8.8.3 Heavy-Ball Methods 179 -- 8.9 Notes and Sources 181 -- 8.10 Exercises 181 -- References 182 -- 9 Primal Gradient Algorithms 184 -- 9.1 Introduction 184 -- 9.2 Penalty Methods 185 -- 9.2.1 Interior Penalty Methods 185 -- 9.2.2 Exterior Penalty Methods 186 -- 9.3 Adaptive Bifurcated Routing 188 -- 9.3.1 Removing Equality Constraints 189 -- 9.3.2 Optimality and Stability 190 -- 9.3.3 Implementation Example 192 -- 9.4 Congestion Control using Barrier Functions 197 -- 9.4.1 Implementation Example 198 -- 9.4.2 Exterior Penalty 200 -- 9.5 Persistence Probability Adjustment in MAC Protocols 201 -- 9.5.1 Implementation Example 203 -- 9.6 Transmission Power Assignment in Wireless Networks 205 -- 9.6.1 Implementation Example 207 -- 9.7 Notes and Sources 210 -- 9.8 Exercises 211 -- References 213 -- 10 Dual Gradient Algorithms 214 -- 10.1 Introduction 214 -- 10.2 Adaptive Routing in Data Networks 217 -- 10.2.1 Optimality and Stability 219 -- 10.2.2 Implementation Example 219 -- 10.3 Backpressure (Center-Free) Routing 221 -- 10.3.1 Relation between and Average Queue Sizes, Qnd 224 -- 10.3.2 Implementation Example 225.

10.4 Congestion Control 228 -- 10.4.1 Optimality and Stability Conditions 229 -- 10.4.2 Implementation Example 230 -- 10.5 Decentralized Optimization of CSMA Window Sizes 231 -- 10.5.1 Implementation Example 234 -- 10.6 Notes and Sources 236 -- 10.7 Exercises 236 -- References 238 -- 11 Decomposition Techniques 240 -- 11.1 Introduction 240 -- 11.2 Theoretical Fundamentals 241 -- 11.2.1 Primal Decomposition 241 -- 11.2.2 Dual Decomposition 244 -- 11.2.3 Other Decompositions 246 -- 11.3 Cross-Layer Congestion Control and QoS Capacity Allocation 247 -- 11.3.1 Implementation Example 249 -- 11.4 Cross-Layer Congestion Control and Backpressure Routing 249 -- 11.4.1 Implementation Example 252 -- 11.5 Cross-Layer Congestion Control and Power Allocation 253 -- 11.5.1 Implementation Example 254 -- 11.6 Multidomain Routing 256 -- 11.6.1 Implementation Example 258 -- 11.7 Dual Decomposition in Non-Convex Problems 259 -- 11.7.1 Implementation Example 261 -- 11.8 Notes and Sources 261 -- 11.9 Exercises 263 -- References 265 -- 12 Heuristic Algorithms 266 -- 12.1 Introduction 266 -- 12.1.1 What Complexity Theory Tells us that We cannot Do 266 -- 12.1.2 Our Options 267 -- 12.1.3 Organization and Rationale of this Chapter 268 -- 12.2 Heuristic Design Keys 270 -- 12.2.1 Heuristic Types 270 -- 12.2.2 Intensification versus Diversification 271 -- 12.2.3 How to Assess the Solution Quality 271 -- 12.2.4 Stop Conditions 272 -- 12.2.5 Defining the Cost or Fitness Function 272 -- 12.2.6 Coding the Solution 273 -- 12.3 Local Search Algorithms 273 -- 12.3.1 Design Hints 274 -- 12.4 Simulated Annealing 276 -- 12.4.1 Design hints 277 -- 12.5 Tabu Search 278 -- 12.5.1 Design Hints 280 -- 12.6 Greedy Algorithms 281 -- 12.7 GRASP 282 -- 12.8 Ant Colony Optimization 283 -- 12.8.1 Design Hints 286 -- 12.9 Evolutionary Algorithms 288 -- 12.9.1 Design Hints 289 -- 12.10 Case Study: Greenfield Plan with Recovery Schemes Comparison 291 -- 12.10.1 Case Study Description 291 -- 12.10.2 Algorithm Description 293.

12.10.3 Combining Heuristics and ILPs 295 -- 12.10.4 Results 296 -- 12.11 Notes and Sources 297 -- 12.12 Exercises 297 -- References 299 -- A Convex Sets. Convex Functions 301 -- A.1 Convex Sets 301 -- A.2 Convex and Concave Functions 303 -- A.2.1 Convexity in Differentiable Functions 303 -- A.2.2 Strong Convexity/Concavity 306 -- A.2.3 Convexity in Non-Differentiable Functions 306 -- A.2.4 Determining the Curvature of a Function 307 -- A.2.5 Sub-level Sets 310 -- A.2.6 Epigraphs 311 -- A.3 Notes and Sources 311 -- Reference 312 -- B Mathematical Optimization Basics 313 -- B.1 Optimization Problems 313 -- B.2 A Classification of Optimization Problems 315 -- B.2.1 Linear Programming 315 -- B.2.2 Convex Programs 318 -- B.2.3 Nonlinear Programs 320 -- B.2.4 Integer Programs 321 -- B.3 Duality 324 -- B.3.1 Dual Function 324 -- B.4 Optimality Conditions 330 -- B.4.1 Optimality Conditions in Problems with Strong Duality 330 -- B.4.2 Graphical Interpretation of KKT Conditions 333 -- B.4.3 Optimality Conditions in Problems Without Strong Duality 336 -- B.5 Sensitivity Analysis 337 -- B.6 Notes and Sources 339 -- References 340 -- C Complexity Theory 341 -- C.1 Introduction 341 -- C.2 Deterministic Machines and Deterministic Algorithms 342 -- C.2.1 Complexity of a Deterministic Algorithm 342 -- C.2.2 Worst-Case Algorithm Complexity 343 -- C.2.3 Asymptotic Algorithm Complexity 343 -- C.2.4 Complexity is a Real Barrier 345 -- C.3 Non-Deterministic Machines and Non-Deterministic Algorithms 346 -- C.3.1 Complexity of a Non-Deterministic Algorithm 347 -- C.4 N and NP Complexity Classes 347 -- C.5 Polynomial Reductions 349 -- C.5.1 A Polynomial Time Reduction Example 350 -- C.6 NP-Completeness 351 -- C.6.1 An Example Proving NP-Completeness for a Problem 352 -- C.7 Optimization Problems and Approximation Schemes 352 -- C.7.1 The NP-�yClass 353 -- C.7.2 Approximation Algorithms 354 -- C.7.3 PTAS Reductions 356 -- C.7.4 NP Complete Problems 356 -- C.8 Complexity of Network Design Problems 357.

C.9 Notes and Sources 357 -- References 358 -- D Net2Plan 359 -- D.1 Net2Plan 359 -- D.2 On the Role of Net2Plan in this Book 360 -- Index 363.

Restricted to subscribers or individual electronic text purchasers.

Also available in print.

Mode of access: World Wide Web

Description based on PDF viewed 10/24/2017.

There are no comments for this item.

Log in to your account to post a comment.