Journal of Applied Mathematics and Decision Sciences
Volume 8 (2004), Issue 3, Pages 155-174
Linear programs with an additional separable concave constraint
1Institute of Information Sciences and Electronics, University of Tsukuba, Ibaraki 305-8573, Japan
2Department of Computer Science and Systems Engineering, Muroran Institute of Technology, Muroran 050-8585, Hokkaido, Japan
Copyright © 2004 Takahito Kuno and Jianming Shi. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
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.