Separable Concave Optimization Approximately Equals Piecewise-Linear Optimization

Details Separable Concave Optimization Approximately Equals Piecewise-Linear Optimization Separable Concave Optimization Approximately Equals Piecewise-Linear Optimization

2012-01-16

arxiv.org/abs/1201.3148v1

Mathematics

Optimization and Control

Full paper

Scientific paper

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 piecewise-linear 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 piecewise-linear cost problem can be formulated as a well-studied discrete optimization problem. As a result, a variety of polynomial-time exact algorithms, approximation algorithms, and polynomial-time heuristics for discrete optimization problems immediately yield fully polynomial-time approximation schemes, approximation algorithms, and polynomial-time 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.

Affiliated with

Also associated with

No associations

Rating

Separable Concave Optimization Approximately Equals Piecewise-Linear Optimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Separable Concave Optimization Approximately Equals Piecewise-Linear Optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Separable Concave Optimization Approximately Equals Piecewise-Linear Optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-409443