Network Optimization

by Pahl, Julia; Reiners, Torsten; Voss, Stefan

• ISBN13: 9783642215261
• ISBN10: 3642215262
• Format: Paperback
• Copyright: 2011-07-20
• Publisher: Springer-Verlag New York Inc

Summary

This book constitutes the refereed proceedings of the 5th International Conference on Network Optimization, INOC 2011, held in Hamburg, Germany, in June 2011. The 65 revised full papers presented were carefully reviewed and selected from numerous submissions. The papers highlight recent developments in network optimization and are organized in the following topical sections: theoretical problems, uncertainty, graph theory and network design; network flows; routing and transportation; and further optimization problems and applications (energy oriented network design, telecom applications, location, maritime shipping, and graph theory).

Table of Contents

Theoretical Problems / Uncertainty / Graph Theory / Network Design
On the Design of Optical Ofdm-Based Networks	p. 1
An Exact Algorithm for Robust Network Design	p. 7
SRG-Disjoint Design with Dedicated and Shared Protection	p. 18
Improved Formulations for the Ring Spur Assignment Problem	p. 24
A Chance-Constrained Model and Cutting Planes for Fixed Broadband Wireless Networks	p. 37
Formulations and Branch-and-Cut Algorithm for the K-rooted Mini-Max Spanning Forest Problem	p. 43
Negative Cycle Separation in Wireless Network Design	p. 51
A Node Splitting Technique for Two Level Network Design Problems with Transition Nodes	p. 57
The Two Level Network Design Problem with Secondary Hop Constraints	p. 71
Spanning Trees with Generalized Degree Constraints Arising in the Design of Wireless Networks	p. 77
Reformulation by Intersection Method on the Mst Problem With Lower Bound on the Number of Leaves	p. 83
A Polyhedral Approach for Solving Two Facility Network Design Problem	p. 92
Ftth Network Design under Oa&m Constraints	p. 98
Introducing the Virtual Network Mapping Problem with Delay, Routing and Location Constraints	p. 105
Cutset Inequalities for Robust Network Design	p. 118
Stabilized Branch-and-Price for the Rooted Delay-Constrained Steiner Tree Problem	p. 124
A Heuristic Algorithm for a Prize-Collecting Local Access Network Design Problem	p. 139
The Two Layer Network Design Problem	p. 145
Affine Recourse for the Robust Network Design Problem: Between Static and Dynamic Routing	p. 150
On the Weight-Constrained Minimum Spanning Tree Problem	p. 156
The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm	p. 162
Multilayer Survivable Optical Network Design	p. 170
Hop-Level Flow Formulation for the Hop constrained Survivable Network Design Problem	p. 176
Network Flow
Maximum Delay Computation under Traffic Matrix Uncertainty and Its Application to Interdomain Path Selection	p. 182
The Spatially Equitable Multicommodity Capacitated Network Flow Problem	p. 196
Approximating Minimum Cut with Bounded Size	p. 210
Lexicographical Minimization of Routing Hops in Telecommunication Networks	p. 216
A Method for Obtaining the Maximum (¿, ¿)-Balanced Flow in a Network	p. 230
Quickest Cluster Flow Problems on Tree Networks	p. 243
Strong Duality for the Maximum Borel Flow Problem	p. 256
Modeling the Gateway Location Problem for Multicommodity Flow Rerouting	p. 262
Affine Decision Rules for Tractable Approximations to Robust Capacity Planning in Telecommunications	p. 277
Optimal Download Time in a Cloud-Assisted Peer-to-Peer Video on Demand Service	p. 283
The Maximum Flow Problem with Conflict and Forcing Conditions	p. 289
Algebraic Methods for Stochastic Minimum Cut and Maximum Flow Problems	p. 295
Reliable and Restricted Quickest Path Problems	p. 309
Modeling and Optimization of Production and Distribution of Drinking Water at Vmc	p. 315
Routing and Transportation
On the Hazmat Transport Network Design Problem	p. 327
Complexity of Inverse Shortest Path Routing	p. 339
The Skill Vehicle Routing Problem	p. 354
The Bio ejective Inventory Routing Problem-Problem Solution and Decision Support	p. 365
Problem Transformations for Vehicle Routing and Scheduling in the European Union	p. 379
New Models for and Numerical Tests of the Hamiltonian p-Median Problem	p. 385
Solving Variants of the Vehicle Routing Problem with a Simple Parallel Iterated Tabu Search	p. 395
The Multi-Commodity One-to-One Pickup-and-Delivery Traveling Salesman Problem: A Matheuristic	p. 401
An Adaptive Large Neighborhood Search Heuristic for a Snow Plowing Problem with Synchronized Routes	p. 406
A Novel Column Generation Algorithm for the Vehicle Routing Problem with Cross-Docking	p. 412
Impacts of Imprecise Demand Forecasts in Network Capacity Control: An Online Analysis	p. 426
A Branch-and-Price Algorithm for the Risk-Equity Constrained Routing Problem	p. 439
A Matheuristic for the Dial-a-Ride Problem	p. 450
Further Optimization Problems and Applications
A Milp-Based Heuristic for Energy-Aware Traffic Engineering with Shortest Path Routing	p. 464
Designing Ac Power Grids Using Integer Linear Programming	p. 478
Energy Saving in Fixed Wireless Broadband Networks	p. 484
Mip Modeling of Incremental Connected Facility Location	p. 490
A Computational Study of the Pseudo-Boolean Approach to the p-Median Problem Applied to Cell Formation	p. 503
Cache Location in Tree Networks: Preliminary Results	p. 517
The Multi Terminal q-FlowLoc Problem: A Heuristic	p. 523
Optimal Bandwidth Allocation in Mesh-Based Peer-to-Peer Streaming Networks	p. 529
Hub Location Problems with Choice of Different Hub Capacities and Vehicle Types	p. 535
A Stochastic Optimization Model for Positioning Disaster Response Facilities for Large Scale Emergencies	p. 547
Efficient Robust Linear Optimization for Large Repositioning Problems	p. 553
Robust Supply Vessel Planning	p. 559
A Liner Shipping Network Design-Routing and Scheduling Impacted by Environmental Influences	p. 574
A Vnd-Ils Heuristic to Solve the Rwa Problem	p. 577
Recoverable Robust Knapsacks: T-Scenarios	p. 583
A Tabu Search Heuristic Based on k-Diamonds for the Weighted Feedback Vertex Set Problem	p. 589
Cuts, c-Cuts, and c-Complexes over the n-Cube	p. 603
Exact and Metaheuristic Approaches to Extend Lifetime and Maintain Connectivity in Wireless Sensors Networks	p. 607
Computing Upper Bounds for a Lbpp With and Without Probabilistic Constraints	p. 620
Mixed Integer Programming Model for Pricing in Telecommunication	p. 626
Ul Rssi as a Design Consideration for Distributed Antenna Systems, Using a Radial Basis Function Model for Ul Rssi	p. 631
Handling Rest Requirements and Preassigned Activities in Airline Crew Pairing Optimization	p. 643
On the Cover Scheduling Problem in Wireless Sensor Networks	p. 657
Author Index	p. 669
Table of Contents provided by Ingram. All Rights Reserved.