Cut search

From Glossary

Jump to: navigation, 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.)

Personal tools