# Cut search

An algorithm strategy for global optimization (notably for integer programming) that consists of two alternating phases: search and cut. The search phase finds linearly independent vectors emanating from a root point, $LaTeX: x_0$, to setup a probe for the cut phase. Usually, $LaTeX: x_0$ is an extreme point, so the search is an edge probe phase that extends edges of the cone rooted at $LaTeX: x_0$ until it intersects the candidate solution points. Then, a cutting plane is added (usually a convexity cut) to exclude the root point. (A new root point is obtained by solving the new approximating problem on the smaller polyhedron.)