# Convexity cut

### From Glossary

A class of cutting planes derived by considering a convex set in a polyhedron, P. The form of the cut is

and it is derived as follows.

Let be an extreme point of a given polyhedron, which contains a given set, . Suppose is a convex set in whose interior contains but does not contain any point of . Let be linearly independent vectors in , and let be such that and for all (e.g., the edges emanating from in ). Define and (i.e., . Then, the cutting plane excludes without excluding any other in for which . The cut, , is equivalent to the above form, , where for some .

One special case is the *intersection cut* for a 0-1 integer program:

- ;
- , where are the cuts already added;
- is an extreme point of , obtained by solving the LP relaxation with a simplex method, so is a basic optimum.
- , where is the basis that transforms the original equations to ;
- is a sphere, .