ON THE CONVERGENCE OF FENCHEL CUTTING PLANES IN MIXED-INTEGER PROGRAMMING

Fenchel cutting planes are based on the dual relationship between sepa ration and optimization and can be applied in many instances where alt ernative cutting planes cannot. They are deep in the sense of providin g the maximum separation between a point ($) over cap x and a polyhedr on P as measured by an arbitrary norm which is specified in the proces s of generating a Fenchel cut. This paper demonstrates a number of fun damental convergence properties of Fenchel cuts and addresses the ques tion of which norms lead to the most desirable Fenchel cuts. The stren gths and weaknesses of the related class of 1-polar cuts are also exam ined.