Incremental network design with maximum flows

DOI10.1016/J.EJOR.2014.10.003zbMATH Open1341.90024arXiv1312.6447OpenAlexW2027517531WikidataQ57955342 ScholiaQ57955342MaRDI QIDQ726224FDOQ726224

Authors: Thomas Kalinowski, Dmytro Matsypura, Martin W. P. Savelsbergh 

Publication date: 8 July 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Abstract: We study an incremental network design problem, where in each time period of the planning horizon an arc can be added to the network and a maximum flow problem is solved, and where the objective is to maximize the cumulative flow over the entire planning horizon. After presenting two mixed integer programming (MIP) formulations for this NP-complete problem, we describe several heuristics and prove performance bounds for some special cases. In a series of computational experiments, we compare the performance of the MIP formulations as well as the heuristics.

Full work available at URL: https://arxiv.org/abs/1312.6447

Recommendations

• Incremental network design with shortest paths
• An incremental algorithm for the maximum flow problem
• The maximum flow in dynamic networks
• Incremental network optimization: theory and algorithms
• Multiperiod network design with incremental routing
• Maximum flows by incremental breadth-first search
• Algorithms for maximum network flow
• scientific article; zbMATH DE number 634019
• Incremental network design with minimum spanning trees
• Maximum network flows with concave gains

zbMATH Keywords

approximation algorithmsschedulingnetwork design

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Deterministic scheduling theory in operations research (90B35)

Cites Work

• Restoring infrastructure systems: an integrated network design and scheduling (INDS) problem
• Integrating restoration and scheduling decisions for disrupted interdependent infrastructure systems
• Incremental network design with shortest paths
• Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules

Cited In (28)

• Polynomial-time approximation schemes for a class of integrated network design and scheduling problems with parallel identical machines
• Incremental network optimization: theory and algorithms
• A quantitative approach for the long-term assessment of railway rapid transit network construction or expansion projects
• Dynamic resource allocation to support oil spill response planning for energy exploration in the Arctic
• Exact solution approaches for the multi-period degree constrained minimum spanning tree problem
• Incremental network design with shortest paths
• Scheduling maintenance jobs in networks
• Lateness minimization in pairwise connectivity restoration problems
• Interdependent integrated network design and scheduling problems with movement of machines
• Polynomial-time algorithms for single resource stochastic capacity expansion models with lost sales
• Interdependent network restoration: on the value of information-sharing
• Network construction problems with due dates
• Online scheduling problems with flexible release dates: applications to infrastructure restoration
• Designing and constructing networks under uncertainty in the construction stage: definition and exact algorithmic approach
• A critical survey on the network optimization algorithms for evacuation planning problems
• Scheduling arc shut downs in a network to maximize flow over time with a bounded number of jobs per time period
• Learn to decompose multiobjective optimization models for large‐scale networks
• Tree optimization based heuristics and metaheuristics in network construction problems
• The incremental connected facility location problem
• Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows
• Incremental network design with minimum spanning trees
• Approximation guarantees of algorithms for fractional optimization problems arising in dispatching rules for INDS problems
• Approximating incremental combinatorial optimization problems
• Quantitative models for infrastructure restoration after extreme events: network optimization meets scheduling
• Fractionally subadditive maximization under an incremental knapsack constraint
• Multiperiod network design with incremental routing
• Integrated reinforcement and repair of interdependent infrastructure networks under disaster-related uncertainties
• The post-disaster debris clearance problem under incomplete information

This page was built for publication: Incremental network design with maximum flows

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