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)

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

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)