Enumeration Tree The LP/IP add-in uses a branch-and-bound procedure for finding solutions. The procedure uses an implicit enumeration tree to search for the optimum or for a solution within a specified percentage of the optimum. This page illustrates the tree for an example from Chapter 8 of the book Operations Research Models and Methods. A complete discussion of the tree structure is in that text and other texts describing the method.
 The example problem is shown below with the problem solved as an LP. For the remainder of this page we enforce integrality on all the variables.

 When we use the Change button to express all variables as integer, we see the model below. All the variable indices in row 6 have a predecessor of "I-". This identifies the integer variables. The figure shows the solution to the integer problem. Note that it is much different than the LP solution. In fact the LP and IP solutions are entirely reversed with respect to nonzero values. Both X2 and X6 are 0 for the LP and nonzero for the IP. The enumeration tree created by the add-in is shown below. Each line of the display shows one node of the tree. The list is a description of the more commonly represented tree structure below. Although this figure more clearly represents the process, it is difficult to draw for anything but the smallest of problems. Nodes in the figure have one underline if they are fathomed because of bounds and two underlines if they are fathomed because of infeasibility.

Operations Research Models and Methods
Internet
by Paul A. Jensen