Article ID: | iaor20051121 |
Country: | United States |
Volume: | 8 |
Issue: | 3 |
Start Page Number: | 155 |
End Page Number: | 174 |
Publication Date: | Oct 2004 |
Journal: | Journal of Applied Mathematics & Decision Sciences |
Authors: | Kuno Takahito, Shi Jianming |
Keywords: | programming: branch and bound, programming: convex |
In this paper, we develop two algorithms for globally optimizing a special class of linear programs with an additional concave constraint. We assume that the concave constraint is defined by a separable concave function. Exploiting this special structure, we apply Falk–Soland's branch-and-bound algorithm for concave minimization in both direct and indirect manners. In the direct application, we solve the problem alternating local search and branch-and-bound. In the indirect application, we carry out the bounding operation using a parametric right-hand-side simplex algorithm.