Separable concave optimization approximately equals piecewise linear optimization
From MaRDI portal
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 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.
Recommendations
- Global optimization of separable objective functions on convex polyhedra via piecewise-linear approximation
- Maximin Problem and a Duality Theorem for Mixed‐Integer Quadratic Programming
- Convex separable optimization is not much harder than linear optimization
- Practical piecewise-linear approximation for monotropic optimization
- scientific article; zbMATH DE number 3916036
Cited in
(10)- Compact mixed-integer programming formulations in quadratic optimization
- A polynomial local optimality condition for the concave piecewise linear network flow problem
- Global optimization of separable objective functions on convex polyhedra via piecewise-linear approximation
- Practical piecewise-linear approximation for monotropic optimization
- A unifying polyhedral approximation framework for convex optimization
- Modeling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints
- Graph Clustering in All Parameter Regimes
- Subdeterminants and concave integer quadratic programming
- Modeling disjunctive constraints with a logarithmic number of binary variables and constraints
- Approximation algorithms for supply chain planning and logistics problems with market choice
This page was built for publication: Separable concave optimization approximately equals piecewise linear optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5712456)
