  


Separable Concave Optimization Approximately Equals PiecewiseLinear Optimization
Thomas L. Magnanti(magnantimit.edu) Abstract: We study the problem of minimizing a nonnegative separable concave function over a compact feasible set. We approximate this problem to within a factor of 1+epsilon by a piecewiselinear minimization problem over the same feasible set. Our main result is that when the feasible set is a polyhedron, the number of resulting pieces is polynomial in the input size of the polyhedron and linear in 1/epsilon. For many practical concave cost problems, the resulting piecewiselinear cost problem can be formulated as a wellstudied discrete optimization problem. As a result, a variety of polynomialtime exact algorithms, approximation algorithms, and polynomialtime heuristics for discrete optimization problems immediately yield fully polynomialtime approximation schemes, approximation algorithms, and polynomialtime heuristics for the corresponding concave cost problems. We illustrate our approach on two problems. For the concave cost multicommodity flow problem, we devise a new heuristic and study its performance using computational experiments. We are able to approximately solve significantly larger test instances than previously possible, and obtain solutions on average within 4.27% of optimality. For the concave cost facility location problem, we obtain a new 1.4991+epsilon approximation algorithm. Keywords: Category 1: Combinatorial Optimization Category 2: Network Optimization Citation: Download: [PDF] Entry Submitted: 01/15/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  