Advances in Decision Sciences
Volume 8 (2004), Issue 3, Pages 155-174
doi:10.1155/S1173912604000100
Linear programs with an additional separable concave constraint
Takahito Kuno1
and Jianming Shi2
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
Abstract
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.