A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables

DOI10.1007/BF02592091zbMath0853.90116MaRDI QIDQ1919095

Saied Ghannadan, Peter Värbrand, Hoang Tuy, Athanasios Migdalas

Publication date: 6 January 1997

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

global optimizationconcave minimizationfacility locationstrongly polynomial algorithmstrongly polynomial timeparametric approachproduction-transportation problemconcave production cost

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items

Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables, A general purpose exact solution method for mixed integer concave minimization problems, Coalition structure generation: a survey, Solving the production transportation problem via a deterministic annealing neural network method, A simplicial branch-and-bound algorithm conscious of special structures in concave minimization problems, Complexity and algorithms for nonlinear optimization problems, Separable convexification and DCA techniques for capacity and flow assignment problems, Two level hierarchical time minimizing transportation problem, Max-min sum minimization transportation problem, On the Computation of Kantorovich--Wasserstein Distances Between Two-Dimensional Histograms by Uncapacitated Minimum Cost Flows, On the Computational Complexity of Minimum-Concave-Cost Flow in a Two-Dimensional Grid, Minimum concave cost flow over a grid network

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Open questions in complexity theory for numerical optimization
• A strongly polynomial minimum cost circulation algorithm
• Minimum concave cost production system: A further generalization of multi-echelon model
• Quadratic programming with one negative eigenvalue is NP-hard
• On-line and off-line vertex enumeration by adjacency lists
• On a general network location--production--allocation problem
• Strongly polynomial time algorithms for certain concave minimization problems on networks
• The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs
• The simple plant location problem: Survey and synthesis
• Minimum concave-cost network flow problems: Applications, complexity, and algorithms
• Integer Programming with a Fixed Number of Variables
• Concave minimization under linear constraints with special structure
• Decomposing the requirement space of a transporation problem into polyhedral cones
• Strongly polynomial algorithm for a production-transportation problem with concave production cost
• The Generalized Basis Reduction Algorithm
• An efficient solution method for rank two quasiconcave minimization problems
• Optimal Facility Location with Concave Costs
• Strongly polynomial algorithm for two special minimum concave cost network flow problems
• Deterministic Production Planning with Concave Costs and Capacity Constraints
• A polynomial time solvable concave network flow problem
• A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System—A Network Approach
• Convex separable optimization is not much harder than linear optimization