Variations on a cutting plane method for solving concave minimization problems with linear constraints

Abstract A cutting plane method for solving concave minimization problems with linear constraints has been advanced by Tui. The principle behind this cutting plane has been applied to integer programming by Balas, Young, Glover, and others under the name of convexity cuts. This paper relates the question of finiteness of Tui's method to the so‐called generalized lattice point problem of mathematical programming and gives a sufficient condition for terminating Tui's method. The paper then presents several branch‐and‐bound algorithms for solving concave minimization problems with linear constraints with the Tui cut as the basis for the algorithm. Finally, some computational experience is reported for the fixed‐charge transportation problem.