A branch-and-cut algorithm for capacitated network design problems

DOI10.1007/S101070050077zbMath1015.90090OpenAlexW2010440802MaRDI QIDQ1806022

Oktay Günlük

Publication date: 1999

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

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

zbMATH Keywords

branch-and-cut algorithmmixed-integer programmingcapacitated network designnetwork loading problembi-directional edge capacitiescapacity expansion problemknapsack branchingpoint-to-point traffic demands

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10)

Related Items (31)

A genetic algorithm based on relaxation induced neighborhood search in a local branching framework for capacitated multicommodity network design ⋮ 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 ⋮ Robust Metric Inequalities for Network Loading Under Demand Uncertainty ⋮ Network loading problem: valid inequalities from 5- and higher partitions ⋮ 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 robust optimization model for distribution network design under a mixed integer set of scenarios ⋮ Multi-period traffic routing in satellite networks ⋮ A note on capacity models for network design ⋮ Separating tight metric inequalities by bilevel programming ⋮ Benders, metric and cutset inequalities for multicommodity capacitated network design ⋮ Solving survivable two-layer network design problems by metric inequalities ⋮ The Steiner connectivity problem ⋮ Network Models with Unsplittable Node Flows with Application to Unit Train Scheduling ⋮ MIP Neighborhood Search Heuristics for a Capacitated Fixed-Charge Network Design Problem ⋮ Partition inequalities for capacitated survivable network design based on directed \(p\)-cycles ⋮ Metric inequalities and the network loading problem ⋮ Lagrangean heuristic for primary routes assignment in survivable connection-oriented networks ⋮ Multi-commodity variable upper bound flow models ⋮ The M{\texttt{CF}}-separator: Detecting and exploiting multi-commodity flow structures in MIPs ⋮ Polyhedral structure of the 4-node network design problem ⋮ Branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design ⋮ An effective logarithmic formulation for piecewise linearization requiring no inequality constraint ⋮ On cut-based inequalities for capacitated network design polyhedra ⋮ 0-1 reformulations of the multicommodity capacitated network design problem ⋮ Branch-and-Cut Techniques for Solving Realistic Two-Layer Network Design Problems ⋮ A local branching heuristic for the capacitated fixed-charge network design problem ⋮ An exact approach for the multicommodity network optimization problem with a step cost function ⋮ Diversification strategies in local search for a nonbifurcated network loading problem

Uses Software

• Concorde

This page was built for publication: A branch-and-cut algorithm for capacitated network design problems