Combinatorial optimization problems with concave costs
Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2009.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2009
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/46661 |
| _version_ | 1811094451715571712 |
|---|---|
| author | Stratila, Dan |
| author2 | Thomas Magnanti. |
| author_facet | Thomas Magnanti. Stratila, Dan |
| author_sort | Stratila, Dan |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2009. |
| first_indexed | 2024-09-23T16:00:17Z |
| format | Thesis |
| id | mit-1721.1/46661 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T16:00:17Z |
| publishDate | 2009 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/466612019-04-11T00:36:56Z Combinatorial optimization problems with concave costs Stratila, Dan Thomas Magnanti. Massachusetts Institute of Technology. Operations Research Center. Massachusetts Institute of Technology. Operations Research Center. Operations Research Center. Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2009. Includes bibliographical references (p. 83-89). In the first part, we study the problem of minimizing a separable concave function over a polyhedron. We assume the concave functions are nonnegative nondecreasing on R+, and the polyhedron is in RI' (these assumptions can be relaxed further under suitable technical conditions). We show how to approximate this problem to 1+ E precision in optimal value by a piecewise linear minimization problem so that the number of resulting pieces is polynomial in the input size of the original problem and linear in 1/c. For several concave cost problems, the resulting piecewise linear problem can be reformulated as a classical combinatorial optimization problem. As a result of our bound, a variety of polynomial-time heuristics, approximation algorithms, and exact algorithms for classical combinatorial optimization problems immediately yield polynomial-time heuristics, approximation algorithms, and fully polynomial-time approximation schemes for the corresponding concave cost problems. For example, we obtain a new approximation algorithm for concave cost facility location, and a new heuristic for concave cost multi commodity flow. In the second part, we study several concave cost problems and the corresponding combinatorial optimization problems. We develop an algorithm design technique that yields a strongly polynomial primal-dual algorithm for a concave cost problem whenever such an algorithm exists for the corresponding combinatorial optimization problem. (cont.) Our technique preserves constant-factor approximation ratios as well as ratios that depend only on certain problem parameters, and exact algorithms yield exact algorithms. For example, we obtain new approximation algorithms for concave cost facility location and concave cost joint replenishment, and a new exact algorithm for concave cost lot-sizing. In the third part, we study a real-time optimization problem arising in the operations of a leading internet retailer. The problem involves the assignment of orders that arrive via the retailer's website to the retailer's warehouses. We model it as a concave cost facility location problem, and employ existing primal-dual algorithms and approximations of concave cost functions to solve it. On past data, we obtain solutions on average within 1.5% of optimality, with running times of less than 100ms per problem. by Dan Stratila. Ph.D. 2009-08-26T17:14:47Z 2009-08-26T17:14:47Z 2009 2009 Thesis http://hdl.handle.net/1721.1/46661 427554148 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 89 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Operations Research Center. Stratila, Dan Combinatorial optimization problems with concave costs |
| title | Combinatorial optimization problems with concave costs |
| title_full | Combinatorial optimization problems with concave costs |
| title_fullStr | Combinatorial optimization problems with concave costs |
| title_full_unstemmed | Combinatorial optimization problems with concave costs |
| title_short | Combinatorial optimization problems with concave costs |
| title_sort | combinatorial optimization problems with concave costs |
| topic | Operations Research Center. |
| url | http://hdl.handle.net/1721.1/46661 |
| work_keys_str_mv | AT stratiladan combinatorialoptimizationproblemswithconcavecosts |