 # Convexity cut

A class of cutting planes derived by considering a convex set in a polyhedron, P. The form of the cut is $LaTeX: \sum_i \frac{y_i}{t_i} \ge 1$,

and it is derived as follows.

Let $LaTeX: x_0$ be an extreme point of a given polyhedron, which contains a given set, $LaTeX: S$. Suppose $LaTeX: C$ is a convex set in $LaTeX: \mathbb{R}^n$ whose interior contains $LaTeX: x_0$ but does not contain any point of $LaTeX: S$. Let $LaTeX: v_1, v_2, \ldots, v_n$ be linearly independent vectors in $LaTeX: \mathbb{R}^n$, and let $LaTeX: t_i$ be such that $LaTeX: t_i > 0$ and $LaTeX: [x_0, x_0 + t_i v_i] \in C$ for all $LaTeX: i=1, 2, \ldots, n$ (e.g., the edges emanating from $LaTeX: x_0$ in $LaTeX: V$). Define $LaTeX: V = [v_1,..., v_n]$ and $LaTeX: M = [\mbox{diag}(t_i)V]^{-1}$ (i.e., $LaTeX: M(i,.) = V^{-1} / t_i)$. Then, the cutting plane $LaTeX: \{x: M(x-x_0) \ge 1\}$ excludes $LaTeX: x_0$ without excluding any other $LaTeX: x$ in $LaTeX: S$ for which $LaTeX: V^{-1}(x-x_0) \ge 0$. The cut, $LaTeX: M(x-x_0)\ge 1$, is equivalent to the above form, $LaTeX: y \, \mbox{diag}(1/t_i) \ge 1$, where $LaTeX: y = x_0 - Vw$ for some $LaTeX: w \ge 0$.

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

• $LaTeX: S = \{(x, s): x \in \{0, 1\}^n, \; s \in \mathbb{Z}^m, \; Ax + s = b \}$;
• $LaTeX: P = {(x, s): x \in [0, 1]^n, \; s \in \mathbb{Z}^m, \; Ax + s = b\} \cap \{x: Cx \le c\}$, where $LaTeX: \{Cx \le c\}$ are the cuts already added;
• $LaTeX: x_0$ is an extreme point of $LaTeX: P$, obtained by solving the LP relaxation with a simplex method, so $LaTeX: x_0 = (u, w)$ is a basic optimum.
• $LaTeX: V = B^{-1}N$, where $LaTeX: B$ is the basis that transforms the original equations to $LaTeX: u + B^{-1}Nw = x_0$ $LaTeX: ( =B^{-1}b )$;
• $LaTeX: C$ is a sphere, $LaTeX: \{y: \|y\|^2 \le 1/4\}$.