|
|
 |
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. |
| |
|
|
