A polyhedral approach to an integer multicommodity flow problem

DOI10.1016/S0166-218X(99)00187-0MaRDI QIDQ1975361zbMATH OpenOpenAlexWikidataFDO

Authors Lorenzo Brunetta, Michele Conforti, Matteo Fischetti

Publication date 22 June 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(99)00187-0

zbMATH Keywords

transportationbranch-and-cut\({\mathcal N}{\mathcal P}\)-hard probleminteger multi-commodity flow problemVLSI design, and telecommunications

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10) Transportation, logistics and supply chain management (90B06)

Recommendations

• Integral polyhedra related to integer multicommodity flows on a cycle
• scientific article; zbMATH DE number 1086903
• Integer multicommodity flow problems
• Multi-commodity variable upper bound flow models
• Minimum cost capacity installation for multicommodity network flows

Cites work

• scientific article; zbMATH DE number 16298 (Why is no real title available?)
• scientific article; zbMATH DE number 3409134 (Why is no real title available?)
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Matroids and multicommodity flows
• Odd Minimum Cut-Sets and b-Matchings
• On the Computational Complexity of Combinatorial Problems
• On the cycle polytope of a binary matroid
• The Circuit Polytope: Facets

Cited in

(20)

• Tree metrics and edge-disjoint \(S\)-paths
• The projected pairwise multicommodity flow polyhedron
• The invisible‐hand heuristic for origin‐destination integer multicommodity network flows
• Multicommodity network flows: A survey. II: Solution methods
• Multicut Is FPT
• scientific article; zbMATH DE number 634022 (Why is no real title available?)
• Algorithms for an integer multicommodity network flow problem with node reliability considerations
• Heuristic approaches for the multiperiod location-transportation problem with reuse of vehicles in emergency logistics
• Minimal multicut and maximal integer multiflow: a survey
• Integer multicommodity flow problems
• On seeking efficient Pareto optimal points in multi-player minimum cost flow problems with application to transportation systems
• Routing and scheduling of network flows with deadlines and discrete capacity allocation
• Integral polyhedra related to integer multicommodity flows on a cycle
• The M{\texttt{CF}}-separator: Detecting and exploiting multi-commodity flow structures in MIPs
• A heuristic solution procedure for multicommodity integer flows
• Optimization in telecommunication networks
• Multicommodity disconnecting set problem
• scientific article; zbMATH DE number 833409 (Why is no real title available?)
• Multi-commodity variable upper bound flow models
• Multicommodity flow problems with a bounded number of paths: A flow deviation approach

Describes a project that uses

Uses Software

• CPLEX
• RelaxIV

This page was built for publication: A polyhedral approach to an integer multicommodity flow problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1975361)