Cut search methods in integer programming

Cut search is a new approach for solving integer programs based on extending edges of a cone to probe the solution space for sets of hyperplanes that are proxies for solution points in the space. Once all proxy hyperplanes associated with a given point have been intersected by at least one of the extended edges, this point is included in a set of points to be examined for feasibility (algorithmically or by inspection). Thereupon, all edges of the cone are extended an additional distance to create a cut by passing a hyperplane through the endpoints of these extended edges.The flexibility of the cut search procedure permits a variety of strategies for exploring and cutting into the solution space. One useful version arises by taking the proxy hyperplanes to be members of a positive or semipositive coordinate system. Relative to such a system the procedure can be organized to reduce the set of vectors to be examined for feasibility and also to generate deeper cuts at the end of the edge probe.