# Cutting plane

A hyperplane whose halfspace cuts off a particular point, such as a non-integer extreme point solution of a linear program relaxation of an integer program. The cut is such that it does not eliminate any solution to the original problem. For example, suppose we want to solve

$LaTeX: \max \{x: (x,y) \in \{0,1\}^2, \; 2x + 2y \le 1 \}$.

The only feasible point is $LaTeX: (0, 0)$. The LP relaxation is

$LaTeX: \max \{x: (x,y) \in [0,1]^2, \; 2x + 2y \le 1\}$,

and an optimal solution is at $LaTeX: (1/2, 0)$. One cutting plane is $LaTeX: \{(x,y): x + y \le 1/3\}$. A deeper one is $LaTeX: \{(x,y): x + y \le 0\}$. (When adding a cutting plane to the LP, a new relaxation is obtained, and the solution is closer to the IP solution.)