A concave function minimization algorithm under 0–1 knapsack constraint using strong valid inequalities

The aim of this paper is to develop the B & B type algorithms for globally minimizing concave function under 0–1 knapsack constraint. The linear convex envelope underestimating the concave object function is introduced for the bounding operations which locate the vertices of the solution set. And the simplex containing the solution set is sequentially partitioned into the subsimplices over which the convex envelopes are calculated in the candidate problems. The adoption of cutting plane method enhances the efficiency of the algorithm. These mean valid inequalities with respect to the integer solution which eliminate the nonintegral points before the bounding operation. The implementations are effectively concretized in connection with the branching strategies.