Cutting plane

From Glossary

Jump to: navigation, search

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.)

Personal tools