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

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.

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.