Minimum concave-cost network flow problems: Applications, complexity, and algorithms
From MaRDI portal
Publication:2277131
The paper is an overview of applications of minimum-cost network flow problems (MCNFP) economic problems and algorithms, a summary of known results in the complexity of the problem and some new results in the complexity area. At the end of the paper 108 references are given. Some of the applications are described in detail, others are just mentioned with further reference to the literature. The description of the algorithms is restricted to explaining the main ideas without going into details. The new complexity results are: (1) MCNFP is NP-hard if the objective function is strictly convex (even for bipartite networks), and (2) for capacitated MCNFP there is no pseudopolynomial algorithm in the sum of the arc capacities (unless \(P=NP\), of course).
Recommendations
Cites work
- A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System—A Network Approach
- A branch‐bound algorithm for the capacitated facilities location problem
- A composite algorithm for a concave-cost network flow problem
- A Deterministic Multi-Period Production Planning Model with Piecewise Concave Production and Holding-Backorder Costs
- A Deterministic Multi-Period Production Scheduling Model with Backlogging
- A Dynamic Lot-Size Model with Make-or-Buy Decisions
- A Facilities in Series Inventory Model with Nested Schedules
- A Heuristic Adjacent Extreme Point Algorithm for the Fixed Charge Problem
- A minimum concave-cost dynamic network flow problem with an application to lot-sizing
- A New Branch-and-Bound Algorithm for the Fixed-Charge Transportation Problem
- A New Optimization Method for Large Scale Fixed Charge Transportation Problems
- A parallel algorithm for constrained concave quadratic global minimization
- Adjacent extreme flows and application to min concave cost flow problems
- Algorithms for the Simple Plant-Location Problem with Some Side Conditions
- An Algorithm for Separable Nonconvex Programming Problems
- An algorithm for the min concave cost flow problem
- An Analysis of Private and Public Sector Location Models
- An approximate solution method for the fixed charge problem
- An approximative algorithm for the fixed charge problem
- An approximative algorithm for the fixed-charges transportation problem
- An Efficient Branch and Bound Algorithm for the Capacitated Warehouse Location Problem
- An Efficient Branch and Bound Algorithm for the Warehouse Location Problem
- An Implicit Enumeration Algorithm for the Concave Cost Network Flow Problem
- Analysis of a flow problem with fixed charges
- Bounded Production and Inventory Models with Piecewise Concave Costs
- Capacity Expansion with Two Producing Regions and Concave Costs
- Checking local optimality in constrained quadratic programming is NP- hard
- Concave minimization over a convex polyhedron
- Constrained global optimization: algorithms and applications
- Convergent Algorithms for Minimizing a Concave Function
- Deterministic Production Planning with Concave Costs and Capacity Constraints
- Deterministic Production Planning: Algorithms and Complexity
- Enumerative techniques for solving some nonconvex global optimization problems
- Fixed-cost transportation problems
- Global Minimization of a Linearly Constrained Concave Function by Partition of Feasible Domain
- Global minimization of indefinite quadratic problems
- Global minimization of large-scale constrained concave quadratic problems by separable programming
- Graphical Interpretation of the Transportation Problem
- Hard Enumeration Problems in Geometry and Combinatorics
- scientific article; zbMATH DE number 3837777 (Why is no real title available?)
- scientific article; zbMATH DE number 3174052 (Why is no real title available?)
- scientific article; zbMATH DE number 3950235 (Why is no real title available?)
- scientific article; zbMATH DE number 4049354 (Why is no real title available?)
- scientific article; zbMATH DE number 47153 (Why is no real title available?)
- scientific article; zbMATH DE number 49534 (Why is no real title available?)
- scientific article; zbMATH DE number 51132 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 544186 (Why is no real title available?)
- scientific article; zbMATH DE number 3436898 (Why is no real title available?)
- scientific article; zbMATH DE number 3215121 (Why is no real title available?)
- scientific article; zbMATH DE number 3353055 (Why is no real title available?)
- Indefinite Quadratic Solid Transportation Problem
- Methods for Global Concave Minimization: A Bibliographic Survey
- Minimal universal covers in \(E^ n\)
- Minimizing a sum of staircase functions under linear constraints
- Minimum Concave Cost Flows in Certain Networks
- Minimum concave cost production system: A further generalization of multi-echelon model
- Minimum concave-cost network flow problems: Applications, complexity, and algorithms
- Minimum Concave-Cost Solution of Leontief Substitution Models of Multi-Facility Inventory Systems
- Minimum cost routing for static network models
- New Methods in Mathematical Programming—The Solid Transportation Problem
- Nonlinear cost network models in transportation analysis
- On a class of capacitated transportation problems
- On building minimum cost communication networks
- On building minimum cost communication networks over time
- Optimal Design of Regional Wastewater Systems: A Fixed-Charge Network Flow Model
- Optimal Facility Location with Concave Costs
- Optimal Inventory Policy with Multiple Set-Up Costs
- Production Smoothing of Economic Lot Sizes with Non-Decreasing Requirements
- Send-and-Split Method for Minimum-Concave-Cost Network Flows
- Smoothing Start-Up and Shut-Down Costs: Concave Case
- Solving the Fixed Charge Problem by Ranking the Extreme Points
- Some branch and bound techniques for nonlinear optimization
- Some branch-and-bound procedures for fixed-cost transportation problems
- Some NP-complete problems in quadratic and nonlinear programming
- Technical Note—A Vertex Ranking Procedure for Solving the Linear Fixed-Charge Problem
- Technical Note—Exact Solution of the Fixed-Charge Transportation Problem
- The Group-Theoretic Structure in the Fixed-Charge Transportation Problem
- Using shortest paths in some transshipment problems with concave costs
Cited in
(70)- Global search algorithms for minimum concave-cost network flow problems
- Algorithms for the single-source uncapacitated minimum concave-cost network flow problem
- A solution approach to the fixed charge network flow problem using a dynamic slope scaling procedure
- Parallel computing in nonconvex programming
- A composite branch and bound, cutting plane algorithm for concave minimization over a polyhedron
- A Lagrangean heuristic for the capacitated concave minimum cost network flow problem
- Minimizing a linear multiplicative-type function under network flow constraints
- An integer concave minimization approach for the minimum concave cost capacitated flow problem on networks
- Network cost minimization using threshold-based discounting
- GNU Oflox: an academic software for the minimal cost network flow problem
- On modelling non-linear quantity discounts in a supplier selection problem by mixed linear integer optimization
- A dynamic programming approach for the pipe network layout problem
- Valid inequalities for separable concave constraints with indicator variables
- The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs
- Approximation of convex curves with application to the bicriterial minimum cost flow problem
- A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables
- A deterministic annealing algorithm for the minimum concave cost network flow problem
- A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks
- Scalable algorithms for designing \(\mathrm{CO}_2\) capture and storage infrastructure
- A model for optimization of transport infrastructure for some homogeneous goods markets
- A novel matheuristic approach for a two-stage transportation problem with fixed costs associated to the routes
- Energy markets: optimization of transmission networks
- Fixed charge transportation problems: a new heuristic approach based on Lagrangean relaxation and the solving of core problems
- Minimum concave-cost network flow problems: Applications, complexity, and algorithms
- Minimum concave cost flow over a grid network
- Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables
- Optimization of an energy market transportation system
- Adaptive dynamic cost updating procedure for solving fixed charge network flow problems
- Complexity and algorithms for nonlinear optimization problems
- On the computational power of molecular heat engines
- A dynamic programming approach for solving single-source uncapacitated concave minimum cost network flow problems
- On budget-constrained flow improvement.
- A Lagrangian heuristic for concave cost facility location problems: the plant location and technology acquisition problem
- Minimum-aggregate-concave-cost multicommodity flows in strong-series-parallel networks
- On the computational complexity of minimum-concave-cost flow in a two-dimensional grid
- On Network Design Problems: Fixed Cost Flows and the Covering Steiner Problem
- Valid inequalities for separable concave constraints with indicator variables
- A minimum cost network flow model for the maximum covering and patrol routing problem
- Solving biobjective network flow problem associated with minimum cost-time loading
- On minimum concave cost network flow problems
- Strongly polynomial algorithm for a production-transportation problem with concave production cost
- Two classical transportation problems revisited: pure constant fixed charges and the paradox
- scientific article; zbMATH DE number 1330764 (Why is no real title available?)
- Upper bounds for single-source uncapacitated concave minimum-cost network flow problems
- scientific article; zbMATH DE number 1560355 (Why is no real title available?)
- On solving continuous-time dynamic network flows
- Minimum-cost strong network orientation problems: Classification, complexity, and algorithms
- Strongly polynomial algorithm for two special minimum concave cost network flow problems
- scientific article; zbMATH DE number 795215 (Why is no real title available?)
- Subdeterminants and concave integer quadratic programming
- Approximation algorithms for general one-warehouse multi-retailer systems
- The plant location and flexible technology acquisition problem.
- An integrated model for facility location and technology acquisition
- On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows
- Avoiding unnecessary demerging and remerging of multi‐commodity integer flows
- A general purpose exact solution method for mixed integer concave minimization problems
- On a finite branch and bound algorithm for the global minimization of a concave power law over a polytope
- An improved branch and bound algorithm for minimum concave cost network flow problems
- Open questions in complexity theory for numerical optimization
- Globally solving concave quadratic programs via doubly nonnegative relaxation
- A modified simplicial algorithm for convex maximization based on an extension of \(\omega \)-subdivision
- Complexity and approximation algorithms for fixed charge transportation problems
- Complexity and approximation algorithms for fixed charge transportation problems
- Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flow
- A facility-integrated flow increment problem for emergency evacuation under budget constraints
- A model for two-stage fixed charge transportation problem with multiple objectives and fuzzy linguistic preferences
- Bilinear modeling solution approach for fixed charge network flow problems
- Resource downgrading
- Strategic design of distribution systems with economies of scale in transportation
- Complexity analysis for maximum flow problems with arc reversals
This page was built for publication: Minimum concave-cost network flow problems: Applications, complexity, and algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277131)
