zbMATH — the first resource for mathematics

Linear programs with an additional separable concave constraint. (English) Zbl 1092.90028
Summary: 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.

90C05 Linear programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI EuDML