2004 | OriginalPaper | Buchkapitel
Separable Concave Optimization Approximately Equals Piecewise Linear Optimization
verfasst von : Thomas L. Magnanti, Dan Stratila
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We show how to approximate a separable concave minimization problem over a general closed ground set by a single piecewise linear minimization problem. The approximation is to arbitrary 1+ε precision in optimal cost. For polyhedral ground sets in $\mathbb{R}^n_+$ and nondecreasing cost functions, the number of pieces is polynomial in the input size and proportional to 1/log(1+ε). For general polyhedra, the number of pieces is polynomial in the input size and the size of the zeroes of the concave objective components.We illustrate our approach on the concave-cost uncapacitated multicommodity flow problem. By formulating the resulting piecewise linear approximation problem as a fixed charge, mixed integer model and using a dual ascent solution procedure, we solve randomly generated instances to within five to twenty percent of guaranteed optimality. The problem instances contain up to 50 nodes, 500 edges, 1,225 commodities, and 1,250,000 flow variables.