Network Optimization

Name: Network Optimization | 5th International Conference, INOC 2011, Hamburg, Germany, June 13-16, 2011, Proceedings
Brand: Springer
Price: 96.29 EUR
Availability: OnlineOnly

5th International Conference, INOC 2011, Hamburg, Germany, June 13-16, 2011, Proceedings

Julia Pahl Torsten Reiners Stefan Voß(Editor)

Springer (Publisher)

Published on 15. September 2011

XIV, 670 pages

E-Book

PDF with digital watermarking

System requirements

978-3-642-21527-8 (ISBN)

€96.29incl. 7% vat

System requirements

for PDF with digital watermarking

E-Book Single Licence

Available for download

Description

More details

Other editions

Content

Title
Preface
Organization
Table of Contents
Part I: Theoretical Problems / Uncertainty / Graph Theory / Network Design
On the Design of Optical OFDM-Based Networks
Introduction
The Optical Multi-Band Networks Design Problem
General Statement
Node-Arcs ILP Formulation
Arcs-Paths ILP Formulation
The Column Generation Procedure
Conclusion
References
An Exact Algorithm for Robust Network Design
Introduction
Problem Formulation
Preprocessing
Primal Heuristics
Separation of Target Cuts
Choice of the Projection
Cut Generation
Computational Results on Realistic Instances
References
SRG-Disjoint Design with Dedicated and Shared Protection
Introduction and Problem Statement
Proposed Approaches: Models and Heuristic
Computational Results
References
Improved Formulations for the Ring Spur Assignment Problem
Introduction
Survivable Network Design Problems
The Ring Spur Assignment Problem
A Formulation Based on Ring Representatives
An Extended Formulation
Comparison of the Formulations
Computational Results
Conclusion
References
A Chance-Constrained Model and Cutting Planes for Fixed Broadband Wireless Networks
Introduction
Mathematical Formulation
Valid Inequalities
Computational Results
Concluding Remarks
References
Formulations and Branch-and-Cut Algorithm for the K-rooted Mini-Max Spanning Forest Problem
Introduction
Integer Programming Formulations
A Branch-and-Cut Algorithm Based on the Undirected Formulation
Preliminary Computational Results and Conclusions
References
Negative Cycle Separation in Wireless Network Design
Introduction
A Pure 0-1 Linear Programming Formulation for the WND
Preliminary Computational Results
References
A Node Splitting Technique for Two Level Network Design Problems with Transition Nodes
Introduction
MIP Formulations for the Two Level Network Design Problem
Modeling the TLND Problem
Modeling Facility Opening Costs
The Node-Splitting Model
Computational Study
The Branch-and-Cut Algorithm
Instances
Results
Conclusions
References
The Two Level Network Design Problem with Secondary Hop Constraints
Introduction
MIP Models
Layered Graph Models for TLNDSH
Solving the TLNDSH as a Steiner Arborescence Problem with Facility and Node-Degree Constraints
Generalized Cut-Jump Inequalities
References
Spanning Trees with Generalized Degree Constraints Arising in the Design of Wireless Networks
Introduction
Description and Motivation of the Problem
Formulations
Model (P$_1$)
Model (P$_2$)
References
Reformulation by Intersection Method on the MST Problem with Lower Bound on the Number of Leaves
Introduction
The Directed Model and the Reformulation by Intersection
The Iterative Procedure
Phase 1: Adding Violated SECs
Phase 2: Adding Violated Leaf Linking Constraints
Computational Results
References
A Polyhedral Approach for Solving Two Facility Network Design Problem
Introduction and Problem Formulation
Solution Approach and Strategy
Shrinking the Original NDP Graph
Enumeration of the Extreme Points of the Subproblem Polyhedron
Computation of Facets of the Subproblem
Computational Study
Conclusion
References
FTTH Network Design under OA&M Constraints
Introduction
Mathematical Modelling
K-Level PON Network Design
PON Network Design under OA&M Constraints
Numerical Tests
Numerical Results
Impact of OA&M Constraints
Conclusions
References
Introducing the Virtual Network Mapping Problem with Delay, Routing and Location Constraints
Introduction
Related Work
The Model
Generating the Benchmark-Instances
Substrate Network
Slices
VNMP-DRL Instance
Computational Results
Created Benchmark-Set
Solving the VNMP-DRL
Conclusion and Future Work
References
Cutset Inequalities for Robust Network Design
Introduction
G-Robust Network Design
Valid Inequalities
Computations
Concluding Remarks
References
Stabilized Branch-and-Price for the Rooted Delay-Constrained Steiner Tree Problem
Introduction
Previous and Related Work
Branch-and-Price
The Pricing Subproblem
Column Generation Stabilization
Alternative Dual-Optimal Solutions
Piecewise Linear Stabilization
Computational Results
Conclusions and Future Work
References
A Heuristic Algorithm for a Prize-Collecting Local Access Network Design Problem
Introduction
Problem Definition
Heuristic
Results
References
The Two Layer Network Design Problem
Introduction and Motivation
Formulation of the Problem
The Polyhedron
References
Affine Recourse for the Robust Network Design Problem: Between Static and Dynamic Routing
Introduction
Robust Network Design with Recourse
Affine Routings
References
On the Weight-Constrained Minimum Spanning Tree Problem
Introduction
Formulations
Valid Inequalities
Computational Experiments
References
The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm
Introduction
Integer Programming Formulation
Branch-and-Cut Algorithm
Preliminary Computational Results
Conclusions
References
Multilayer Survivable Optical Network Design
Introduction
Notations
Complexity
Path Formulation
Pricing Problem
Preliminary Results
Conclusion
References
Hop-Level Flow Formulation for the Hop Constrained Survivable Network Design Problem
Introduction
Hop Multi-Commodity Flow Formulation (Hop-MCF)
Hop-Level Multi-Commodity Flow Formulation (HL-MCF)
Computational Experiments
References
Part II: Network Flow
Maximum Delay Computation under Traffic Matrix Uncertainty and Its Application to Interdomain Path Selection
Introduction
Problem Statement
Assumptions and Notations
Modelling Traffic Uncertainty
Mathematical Formulation
Finding the Solution
Simulations
The Abilene Network
The GÉANT Network
Conclusion and Future Work
References
The Spatially Equitable Multicommodity Capacitated Network Flow Problem
Introduction
The Spatially Equitable Multicommodity Network Flow Problem
Computational Results on a Real Traffic Network
Evaluating the Spatial Concentration of the Flows
A Bi-objective Approach Balancing Spatial Equity and Total Routing Costs
Conclusions and Further Research
References
Approximating Minimum Cut with Bounded Size
Introduction
The Randomized Algorithm
The Bi-criteria Algorithm
References
Lexicographical Minimization of Routing Hops in Telecommunication Networks
Introduction
The Iterative Approach
The MCF(H*) Model
The HOP(H*) Model
Comparing the LP Relaxations of MCF(H*) and HOP(H*)
The Single Model Approach
Computational Results
Conclusions and Future Work
References
A Method for Obtaining the Maximum (d ,?)-Balanced Flow in a Network
Introduction
Preliminaries
Flow Network
Definition of Flow
Cut-Flow
(d ,?)-Balanced FLOW
(d ,?)-Balanced Flow
(d ,?)-Capacity of a Mixed Cut
Evaluation of (d ,?)-Capacity of a Mixed Cut
Max-Flow Min-Cut Theorem of (d ,?)-Balanced Flow
How to Obtain the Maximum (d ,?)-Balanced Flow
Example
References
Quickest Cluster Flow Problems on Tree Networks
Introduction
Preliminaries and Notation
Quickest Cluster Flow Problems
Quickest Cluster Problems with Divisible Cluster Sizes
Assumption
Examples
Conclusions
References
Strong Duality for the Maximum Borel Flow Problem
Introduction
The Maximum Borel Flow Problem
Dual Formulation and Strong Duality
References
Modeling the Gateway Location Problem for Multicommodity Flow Rerouting
Introduction
Formalizing the Gateway Location Problem
A Bilevel Multicommodity Flow Model
A Path Based Model
A k-Median Like Model
Comparing the Three Models
Computational Results
Conclusions and Ongoing Work
References
Affine Decision Rules for Tractable Approximations to Robust Capacity Planning in Telecommunications
Introduction
Affine Decision Rules
Tractable Approximations
References
Optimal Download Time in a Cloud-Assisted Peer-to-Peer Video on Demand Service
Introduction
Video-on-Demand Fluid Model
Model Optimization Based on GRASP
Numerical Results and Discussion
References
The Maximum Flow Problem with Conflict and Forcing Conditions
Introduction
MFCG Is Strongly NP-Hard
MFFG with Integer Flow Values
MFFG with Arbitrary Flow Values
References
Algebraic Methods for Stochastic Minimum Cut and Maximum Flow Problems
Introduction
Formulation
Algebraic Operations and Properties
The and Operations
Properties of and
Exact Calculation
Bounding Distributions
Modified Path Enumeration
Acyclic Networks
Bounds on Expected Capacity
Fulkerson Bound
Numerical Results
References
Reliable and Restricted Quickest Path Problems
Introduction
Problem Definition
Algorithms
Conclusion
References
Modeling and Optimization of Production and Distribution of Drinking Water at VMW
Introduction
Description of the Model
Discrete Time Setting
System Components and Restrictions
Goal Function
Testing and Results
Conclusion
References
Part III: Routing and Transportation
On the Hazmat Transport Network Design Problem
Introduction
Problem Description
Computational Complexity
A Mixed Integer Linear Programming Formulation
Computational Experiments
Instance Testbed
Comparison with Previous Exact and Heuristic Methods
Concluding Remarks
References
Complexity of Inverse Shortest Path Routing
Introduction
The Inverse Shortest Path Routing Problems
Mathematical Formulations of ISPR Problems
Incompatible and Unrealizable SP-Graphs
Complexity of ISPR Problems
Conclusion
References
The Skill Vehicle Routing Problem
The Skill Vehicle Routing Problem
ILP Models for the Skill VRP
The Aggregated Formulation
The Destination Disaggregated Model
Some Valid Inequalities
The Destination-Technician Disaggregated Model
The Computational Experience
The Instances
Computational Results
Conclusions
References
The Biobjective Inventory Routing Problem - Problem Solution and Decision Support
Introduction
Description of the Investigated IRP
Solution Representation and Heuristic Search
Solution Encoding
Heuristic Search
Experimental Investigation
Proposition of Benchmark Data
Implementation of a Decision Support System
Results
The Decision Maker's Point of View
Conclusions
References
Problem Transformations for Vehicle Routing and Scheduling in the European Union
Introduction
Problem Transformation
Conclusions
References
New Models for and Numerical Tests of the Hamiltonian p-Median Problem
Introduction
MILP Models
Notation
Subtour Elimination Constraints
Formulations Based on Connectivity Concepts
Symmetry Breaking and Valid Inequalities
Computational Study
Branch-and-Cut Framework
Instances
Results
Conclusions
References
Solving Variants of the Vehicle Routing Problem with a Simple Parallel Iterated Tabu Search
Introduction
Short Description of the Iterated Tabu Search Heuristic
Computational Results
References
The Multi-Commodity One-to-One Pickup-and-Delivery Traveling Salesman Problem: A Matheuristic
Introduction
The Heuristic Algorithm
Computational Results
References
An Adaptive Large Neighborhood Search Heuristic for a Snow Plowing Problem with Synchronized Routes
Introduction
Problem Description
Mathematical Model
Summary of the Adaptive Large Neighborhood Search Heuristic
Initial Solutions Generator
Improvement Phase
Preliminary Computational Results
Conclusions
References
A Novel Column Generation Algorithm for the Vehicle Routing Problem with Cross-Docking
Introduction
Column Generation Formulation
Column Generation Subproblem
Branch-and-Cut Algorithm
Heuristic Algorithm
Branch-and-Price Algorithm
Computational Results
Concluding Remarks
References
Impacts of Imprecise Demand Forecasts in Network Capacity Control: An Online Analysis
Introduction
Decision Situation
Literature
Dynamic Decision Problem
Model-Based Determination of Quotas and Bid-Prices
Capacity Control System
Outline of the System
Resource (Re-)Allocation
Control Policies
Computational Experiments
Metrics for Evaluation
Results
Conclusions
References
A Branch-and-Price Algorithm for the Risk-Equity Constrained Routing Problem
Introduction
Description of the Problem
Multiple Objective Functions
An Optimization Model
Column Generation Formulation
Handling One Objective Only
Risk on Trucks
Branch-and-Price for Single Objective Problems
Preliminary Experiments and Perspectives
Conclusion
References
A Matheuristic for the Dial-a-Ride Problem
Introduction
TheProblem
The Granular Search Approach
Applying Granular Search to DARP
The Proposed Granular Tabu Search
Computational Study and Conclusions
References
Part IV: Further Optimization Problems and Applications
A MILP-Based Heuristic for Energy-Aware Traffic Engineering with Shortest Path Routing
Introduction
Related Work
Mixed Integer Programming Formulation
Heuristic Algorithms
Greedy Algorithm with Dual Weights Initialization (GA-DW)
Two-Stage Algorithm with Dual Weights Initialization (TA-DW)
MILP-Based Algorithm
Computational Experiments
Network Topologies and Traffic Matrices
Results
Concluding Remarks
References
Designing AC Power Grids Using Integer Linear Programming
Introduction
The General Model
Linear Approximations of the Power Flow Functions
The DC Power Flow
Approximation of the AC Power Flow
Linearization of the Network Design Model
Computational Experience and Further Remarks
References
Energy Saving in Fixed Wireless Broadband Networks
Introduction
Problem Modeling and Linear Formulation
Hybrid Algorithm
Sparse Cuts-Based Algorithm
Simulation Results
Conclusion
References
MIP Modeling of Incremental Connected Facility Location
Introduction
MIP Modeling
Valid Inequalities
Separation Algorithms
Separation of Cut-Set Inequalities
Separation of Cover and Cut-Set-Cover Inequalities
Experiments
Branch and Cut Implementation
Results
Conclusions
References
A Computational Study of the Pseudo-Boolean Approach to the p-Median Problem Applied to Cell Formation
Introduction
The Mixed Boolean Pseudo-Boolean Model (MBpBM)
Reduction Tests for the p-Median Problem
Computational Results for Benchmark Instances
Application to Cell Formation
Additional Constraints
Summary and Future Research Directions
References
Cache Location in Tree Networks: Preliminary Results
Introduction
Problem Statement
A Mixed Integer Programming Model
A Dynamic Programming (DP) Approach
Computational Experiments
Conclusion
References
The Multi Terminal q-FlowLoc Problem: A Heuristic
Introduction and Notations
Heuristic
Comparison of the Cost Functions
Conclusion
References
Optimal Bandwidth Allocation in Mesh-Based Peer-to-Peer Streaming Networks
Introduction
Mathematical Model
A Polytime Resolution and Its Generalization
Empirical Results
Conclusions
References
Hub Location Problems with Choice of Different Hub Capacities and Vehicle Types
Introduction
Formulations
Notations
Multiple Allocation Formulation
Single Allocation Formulation
Further Modifications
Computational Experiments
Test Data
Computational Results
Summary and Outlook
References
A Stochastic Optimization Model for Positioning Disaster Response Facilities for Large Scale Emergencies
Introduction
The Stochastic Distance Dependent Model
Computational Results
Conclusion
References
Efficient Robust Linear Optimization for Large Repositioning Problems
Introduction
Integer Programming Models
The Nominal Model
Robustness
A Constraint Generation Linear Programming Approach
Conclusion
References
Robust Supply Vessel Planning
Introduction
Mathematical Model
The Weather Impact
Robustness Approaches
Adding Slack to the Voyages and Schedule
An Optimization and Simulation Framework for Robust Schedules
Computational Study
Description of Problem Instances
Numerical Results
Concluding Remarks
References
A Liner Shipping Network Design - Routing and Scheduling Impacted by Environmental Influences
Introduction
Literature Review and Problem Statement
Solution Approach
References
A VND-ILS Heuristic to Solve the RWA Problem
Introduction
Related Work
Variable Neighborhood Descent
Iterated Local Search
Results
Conclusions
References
Recoverable Robust Knapsacks: G -Scenarios
Introduction
Recoverable Robust Knapsack Problem
A Compact ILP Formulation
Computational Experiments
Concluding Remarks
References
A Tabu Search Heuristic Based on k-Diamonds for the Weighted Feedback Vertex Set Problem
Introduction
Definitions and Notation
The Class of k-Diamond Graphs
The Neighborhood Structures and the Iterative Tabu Search
The k-Diamond Neighborhood
The 2-Exchange Neighborhood and the Double-Insert Operator
The Tabu List
The Diversification Phase
Computational Results
Conclusions
References
Cuts, c-Cuts, and c-Complexes over the n-Cube
Introduction
Terminologies
References
Exact and Metaheuristic Approaches to Extend Lifetime and Maintain Connectivity in Wireless Sensors Networks
Introduction
Notation and Problem Definition
Column Generation Approach
Greedy and GRASP Algorithms
Computational Results
Conclusions
References
Computing Upper Bounds for a LBPP with and without Probabilistic Constraints
Introduction
Problem Formulation and the Jacobsen Construction Method
The Iterative Min-Max Algorithm
Numerical Results
Conclusions
References
Mixed Integer Programming Model for Pricing in Telecommunication
Introduction
Pricing Problem in Voice Telecommunication Networks
MIP Formulation
Notation
General Problem Formulation
Linear Demand and Load Model
Experimentation and Numerical Results
Conclusion and Future Research Work
References
UL RSSI as a Design Consideration for Distributed Antenna Systems, Using a Radial Basis Function Model for UL RSSI
Introduction
WCDMA Network Theory
WCDMA Network Architecture Overview
Discussion on HSUPA/EUL
Theory on Uplink Noise
Introduction to RBF Neural Networks
Modelling Uplink Noise
Uplink Noise Floor
Current RoT Model
New Proposed Model for RoT
Design Model for DAS System
Design Results
Conclusion
References
Handling Rest Requirements and Preassigned Activities in Airline Crew Pairing Optimization
Introduction
Related Work
Crew Pairing Optimization
Crew Rostering
Integration in Crew Scheduling
Modeling and Solution Approach
Network Construction
Basic Model
Weekly and Monthly Rests
Availability Blocks
Solution Approach
Computational Results
Conclusions and Outlook
References
On the Cover Scheduling Problem inWireless Sensor Networks
Introduction
Introductory Example
Problem Definition and Notations
Organization of the Paper
Complexity Analysis
The Cover Scheduling Problem in a Particular Case
WSN-CSP Is NP-Hard in the Strong Sense
A Lower Bound for WSN-CSP
A MILP Formulation of WSN-CSP
A Greedy Heuristic Approach to WSN-CSP
A Genetic Algorithm Based Approach to WSN-CSP
Computational Results
Conclusions and Perspectives
References
Author Index

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Network Optimization

Description

More details

Other editions

Additional editions

Content

System requirements