Convexity cut

From Glossary

Jump to: navigation, search

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\}.

Personal tools