On the Computational Complexity of Minimum-Concave-Cost Flow in a Two-Dimensional Grid
From MaRDI portal
Publication:2828332
DOI10.1137/15M1045715zbMath1349.90153arXiv1602.08515MaRDI QIDQ2828332
Shi Li, Nemhauser, George I., Shabbir Ahmed, Qie He
Publication date: 25 October 2016
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1602.08515
computational complexitypolynomial-time algorithmlot sizingtwo-dimensional gridserial supply chainminimum-concave-cost flow
Nonconvex programming, global optimization (90C26) Production models (90B30) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Dynamic programming (90C39)
Related Items
Multiechelon Lot Sizing: New Complexities and Inequalities, An efficient algorithm for the 2-level capacitated lot-sizing problem with identical capacities at both levels
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An \(O(n^2)\) algorithm for lot sizing with inventory bounds and fixed costs
- Four equivalent lot-sizing models
- Lot-size models with backlogging: Strong reformulations and cutting planes
- The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs
- A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables
- Minimum concave-cost network flow problems: Applications, complexity, and algorithms
- Minimum concave cost flow over a grid network
- Linear-programming extended formulations for the single-item lot-sizing problem with backlogging and constant capacity
- A dynamic programming approach for solving single-source uncapacitated concave minimum cost network flow problems
- Dynamic Version of the Economic Lot Size Model
- Integrated Lot Sizing in Serial Supply Chains with Production Capacities
- A Polyhedral Study of Multiechelon Lot Sizing with Intermediate Demands
- Solving Multi-Item Lot-Sizing Problems Using Strong Cutting Planes
- Send-and-Split Method for Minimum-Concave-Cost Network Flows
- Deterministic Production Planning: Algorithms and Complexity
- Computational Complexity of the Capacitated Lot Size Problem
- A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods in 0(n log n) or 0(n) Time
- Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case
- Improved Algorithms for Economic Lot Size Problems
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- An O(T3) Algorithm for the Economic Lot-Sizing Problem with Constant Capacities
- Deterministic Production Planning with Concave Costs and Capacity Constraints
- A polynomial time solvable concave network flow problem
- Basis Paths and a Polynomial Algorithm for the Multistage Production-Capacitated Lot-Sizing Problem
- Lot Sizing with Inventory Bounds and Fixed Costs: Polyhedral Study and Computation
- Production Planning by Mixed Integer Programming
- A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System—A Network Approach
- Convex Analysis
- A Facilities in Series Inventory Model with Nested Schedules
