Incremental network design with maximum flows

DOI10.1016/J.EJOR.2014.10.003MaRDI QIDQ726224zbMATH OpenOpenAlexWikidataFDO

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)

Full work available at URL https://arxiv.org/abs/1312.6447, http://hdl.handle.net/1959.13/1332466

zbMATH Keywords

approximation algorithmsschedulingnetwork design

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(27)

• Incremental network optimization: theory and algorithms
• Polynomial-time approximation schemes for a class of integrated network design and scheduling problems with parallel identical machines
• 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
• Lateness minimization in pairwise connectivity restoration problems
• Interdependent integrated network design and scheduling problems with movement of machines
• Interdependent network restoration: on the value of information-sharing
• Network construction problems with due dates
• Polynomial-time algorithms for single resource stochastic capacity expansion models with lost sales
• 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
• Scheduling arc shut downs in a network to maximize flow over time with a bounded number of jobs per time period
• Tree optimization based heuristics and metaheuristics in network construction problems
• A critical survey on the network optimization algorithms for evacuation planning problems
• Learn to decompose multiobjective optimization models for large‐scale networks
• 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
• The post-disaster debris clearance problem under incomplete information
• Integrated reinforcement and repair of interdependent infrastructure networks under disaster-related uncertainties

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)