http://preserve.lehigh.edu/cgi/viewcontent.cgi?article=1780&...

> Since tree search is a basic solution technique employed in both constraint and integer programming, we begin with a generic overview of tree search as a technique for finding feasible solutions to mathematical models.

> Every tree search algorithm is defined by four elements: a node- processing procedure, pruning rules, branching rules, and search strategy. The processing step is applied at every node of the search tree beginning with the root node, and usually involves some attempt to further reduce the feasible set associated with the node by applying logical rules. [...]

> One particularly well-developed solution technique, called branch and bound, was introduced by Land and Doig. Branch and bound is frequently used to find solutions to integer programming problems; it is a tree search procedure in which a bound on the optimal value to each subproblem is obtained by solving a relaxation. In this thesis we assume the use of a linear programming relaxation in the branch and bound tree.

> The last piece of a branch and bound algorithm is a search strategy specifying the order in which to explore nodes of the tree. Depth-first search can be used to save memory in a branch and bound tree, since we must only remember the difference in solution between two successive nodes of the search tree.

Chapter nine of Applied Mathematical Programming from MIT classifies integer program solvers into three major groups:

http://web.mit.edu/15.053/www/AMP-Chapter-09.pdf

> Whereas the simplex method is effective for solving linear programs, there is no single technique for solving integer programs. Instead, a number of procedures have been developed, and the performance of any particular technique appears to be highly problem-dependent. Methods to date can be classified broadly as following one of three approaches:

> i) enumeration techniques, including the branch-and-bound procedure;

> ii) cutting-plane techniques; and

> iii) group-theoretic techniques. [...]

> Branch-and-bound is essentially a strategy of ‘‘divide and conquer.’’ The idea is to partition the feasible region into more manageable subdivisions and then, if required, to further partition the subdivisions. In general, there are a number of ways to divide the feasible region, and as a consequence there are a number of branch-and-bound algorithms.

> An integer linear program is a linear program further constrained by the integrality restrictions. Thus, in a maximization problem, the value of the objective function, at the linear-program optimum, will always be an upper bound on the optimal integer-programming objective. In addition, any integer feasible point is always a lower bound on the optimal linear-program objective value. The idea of branch-and-bound is to utilize these observations to systematically subdivide the linear programming feasible region and make assessments of the integer-programming problem based upon these subdivisions.

The book describes the "cutting-plane" approach, which does seem to work more like how you're describing (a series of transformations), but also says:

> In practice, the branch-and-bound procedures almost always outperform the cutting-plane algorithm. Nevertheless, the algorithm has been important to the evolution of integer programming. Historically, it was the first algorithm developed for integer programming that could be proved to converge in a finite number of steps. In addition, even though the algorithm generally is considered to be very inefficient, it has provided insights into integer programming that have led to other, more efficient, algorithms.