Journal of Applied Mathematics and 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.