Minimum cost capacity installation for multicommodity network flows

DOI10.1007/BF01581104zbMath0922.90064OpenAlexW2051290577MaRDI QIDQ1290614

Oktay Günlük, Sunil Chopra, Chih-Yang Tsai, Bienstock, Daniel

Publication date: 18 October 1999

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01581104

zbMATH Keywords

directed graphnetwork designmetric inequalitiesaggregated multicommodity flow formulationminimum cost installation of capacity

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Deterministic network models in operations research (90B10)

Related Items

The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design ⋮ Exact approaches to the single-source network loading problem ⋮ Routing of uncertain traffic demands ⋮ Single-commodity robust network design with finite and hose demand sets ⋮ Single-commodity robust network design problem: complexity, instances and heuristic solutions ⋮ The robust network loading problem with dynamic routing ⋮ Near optimal design of wavelength routed optical networks ⋮ Approximation Algorithms for Buy-at-Bulk Geometric Network Design ⋮ Approximation algorithms for general one-warehouse multi-retailer systems ⋮ Costly circuits, submodular schedules and approximate Carathéodory theorems ⋮ Unsplittable non-additive capacitated network design using set functions polyhedra ⋮ Network loading problem: valid inequalities from 5- and higher partitions ⋮ A partitioning algorithm for the network loading problem ⋮ Robust network design: Formulations, valid inequalities, and computations ⋮ Benders decomposition approach for the robust network design problem with flow bifurcations ⋮ A polyhedral study of the capacity formulation of the multilayer network design problem ⋮ A mixed-integer approach to Core-Edge design of storage area networks ⋮ Chance-Constrained Optimization of Reliable Fixed Broadband Wireless Networks ⋮ Source sink flows with capacity installation in batches ⋮ New partial aggregations for multicommodity network flow problems: an application to the fixed-charge network design problem ⋮ A note on capacity models for network design ⋮ Separating tight metric inequalities by bilevel programming ⋮ Fixed charge multicommodity network design using \(p\)-partition facets ⋮ Solving survivable two-layer network design problems by metric inequalities ⋮ Bidirected and unidirected capacity installation in telecommunication networks. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Network Models with Unsplittable Node Flows with Application to Unit Train Scheduling ⋮ Convexification of generalized network flow problem ⋮ New Valid Inequalities for the Optimal Communication Spanning Tree Problem ⋮ A comparison of different routing schemes for the robust network loading problem: polyhedral results and computation ⋮ Algorithms and extended formulations for one and two facility network design ⋮ Metric inequalities and the network loading problem ⋮ Using mixed-integer programming to solve power grid blackout problems ⋮ Multi-commodity variable upper bound flow models ⋮ Cutting planes in integer and mixed integer programming ⋮ The M{\texttt{CF}}-separator: Detecting and exploiting multi-commodity flow structures in MIPs ⋮ Encoding binary arithmetic operations in integer programming formulations ⋮ Algorithms for the non-bifurcated network design problem ⋮ Polyhedral structure of the 4-node network design problem ⋮ Branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design ⋮ Optimal solution of the discrete cost multicommodity network design problem ⋮ On the problem of minimizing the cost with optical devices in Wavelength Division Multiplexing optical networks: complexity analysis, mathematical formulation and improved heuristics ⋮ Capacitated multi-layer network design with unsplittable demands: polyhedra and branch-and-cut ⋮ On cut-based inequalities for capacitated network design polyhedra ⋮ 0-1 reformulations of the multicommodity capacitated network design problem ⋮ Graphs and Algorithms in Communication Networks on Seven League Boots ⋮ Branch-and-Cut Techniques for Solving Realistic Two-Layer Network Design Problems ⋮ Benders Decomposition for Capacitated Network Design ⋮ Directed fixed charge multicommodity network design: a cutting plane approach using polar duality ⋮ Minimum cost capacity installation for multicommodity network flows ⋮ An exact approach for the multicommodity network optimization problem with a step cost function ⋮ A dynamic programming algorithm for the local access telecommunication network expansion problem

Cites Work

• Unnamed Item
• Minimum cost capacity installation for multicommodity network flows
• Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems
• A polyhedral approach to multicommodity survivable network design
• Computational experience with a difficult mixed-integer multicommodity flow problem
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut
• Solving Airline Crew Scheduling Problems by Branch-and-Cut
• Modeling and Solving the Two-Facility Capacitated Network Loading Problem
• Network Design Using Cut Inequalities
• Capacitated Network Design—Polyhedral Structure and Computation