PROC NETDRAW: Branch and Bound Trees :: SAS/OR(R) 9.22 User's Guide: Project Management

The NETDRAW Procedure

Example 9.18 Branch and Bound Trees

This example illustrates a nonstandard use of PROC NETDRAW. The TREE option in PROC NETDRAW is used to draw a branch and bound tree such as one that you obtain in the solution of an integer programming problem. Refer to Chapter 5, The LP Procedure (SAS/OR 9.22 User's Guide: Mathematical Programming), for a detailed discussion of branch and bound trees. The data used in this example were obtained from one particular invocation of PROC LP.

The data set NET (created in the following DATA step) contains information pertaining to the branch and bound tree. Each observation of this data set represents a particular iteration of the integer program, which can be drawn as a node in the tree. The variable node names the problem. The variable object gives the objective value for that problem. The variable problem identifies the parent problem corresponding to each node; for example, since the second and the seventh observations have problem equal to '-1' and '1', respectively, it indicates that the second and the seventh problems are derived from the first iteration. Finally, the variable _pattern specifies the pattern of the nodes based on the status of the problem represented by the node.

data net;
   input node problem cond $10. object;
   if cond="ACTIVE"          then _pattern=1;
   else if cond="SUBOPTIMAL" then _pattern=2;
   else                           _pattern=3;
datalines;
 1       0     ACTIVE         4
 2      -1     ACTIVE         4
 3       2     ACTIVE         4
 4      -3     ACTIVE 4.3333333
 5       4 SUBOPTIMAL         5
 6       3   FATHOMED 4.3333333
 7       1     ACTIVE         4
 8      -7     ACTIVE         4
 9      -8   FATHOMED 4.3333333
10       8   FATHOMED 4.3333333
11       7     ACTIVE         4
12     -11   FATHOMED 4.3333333
13      11   FATHOMED       4.5
;

The next DATA step (which creates the data set LOGIC) uses this child-parent information to format the precedence relationships as expected by PROC NETDRAW. Next, the two data sets are merged together to create the Network input data set (BBTREE) for PROC NETDRAW. The ID variable in the data set BBTREE is formatted to contain both the iteration number and the objective value.

Finally, PROC NETDRAW is invoked with the TREE, ROTATE, and ROTATETEXT options to produce a branch and bound tree shown in Output 9.18.1. Note that the ROTATE and ROTATETEXT options produce a rotated graph with a top-down orientation.

/* set precedence relationships
   using child-parent information */
data logic;
   keep node succ;
   set net(firstobs=2);
   succ=node;
   node=abs(problem);
   run;

proc sort data=logic; 
   by node;
   run;

/* combine the logic data and the node data */
/* set ID values                            */
data bbtree;
  length id $ 9;
  merge logic net; by node;
  if node < 10 then id=put(node,1.)||put(object,f8.2);
  else              id=put(node,2.)||put(object,f7.2);
  run;

goptions border rotate=portrait;
pattern1 v=s c=green;
pattern2 v=s c=red;
pattern3 v=s c=blue;

title     j=c 'Branch and Bound Tree';
title2    ' ';
footnote1 h=1.2 j=c c=red   'Optimal  '
                    c=green '   Active  '
                    c=blue  '   Fathomed ';
footnote2 ' ';
footnote3 ' Node shows Iteration Number and Objective Value ';
proc netdraw data=bbtree graphics out=bbout;
   actnet /activity=node
           successor=succ
           id=(id)
           nodefid
           nolabel
           ctext=white
           coutline=black
           carcs=black
           xbetween=15
           ybetween=3
           font=swiss
           compress
           rectilinear
           tree
           rotate
           rotatetext
           arrowhead=0
           htext=2;
   run;

Output 9.18.1 Branch and Bound Tree

In the next invocation, PROC NETDRAW uses a modified layout of the nodes to produce a diagram where the nodes are aligned according to the iteration number. The following program uses the Layout data set produced in the previous invocation of PROC NETDRAW. The same $\text{[math]}$ coordinates are used; but the $\text{[math]}$ coordinates are changed to equal the iteration number. Further, the ALIGN= specification produces a time axis that labels each level of the diagram with the iteration number. Each node is labeled with the objective value. The resulting diagram is shown in Output 9.18.2.

data netin;
   set bbout;
   if _seq_ = 0; drop _seq_ ;
   _x_ = _from_;
   id = substr(id, 3);
   run;

goptions rotate=landscape;
title         'Branch and Bound Tree';
title2 h=1.5  'Aligned by Iteration Number';
footnote1 h=1.2 j=c  c=red   'Optimal     '
                     c=green '      Active     '
                     c=blue  '      Fathomed ';
footnote2 ' ';
footnote3 j=l ' Node shows Objective Value ';
pattern1 v=e c=green;
pattern2 v=e c=red;
pattern3 v=e c=blue;
proc netdraw data=netin graphics;
   actnet /id=(id)
           ctext=black
           carcs=black
           align = _from_
           frame
           pcompress
           rectilinear
           arrowhead=0
           nodefid
           nolabel
           htext=2.5
           xbetween=8;
   run;

Output 9.18.2 Branch and Bound Tree: Aligned by Iteration Number

Top of Page