Deep cuts in concave and linear 0-1 programming

A technique for the construction of deep cuts in the global minimization problem for a continuously differentiable concave function on a polytope and in a Boolean programming problem is proposed. The introduced cuts are based constructively on the so-called best concave extension. The theoretical analysis is based on the properties of the image of the target function under the gradient mapping. Illustrative examples and results of a preliminary numerical experiment are presented.