Return to Index
Operations Research Models and Methods
Computation Section
Subunit 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.


Return to Top

tree roots

Operations Research Models and Methods
by Paul A. Jensen
Copyright 2004 - All rights reserved

Next Page