Resources

Branch and Bound Tree (netdr18)

/****************************************************************/
/*          S A S   S A M P L E   L I B R A R Y                 */
/*                                                              */
/*    NAME: NETDR18                                             */
/*   TITLE: Branch and Bound Tree (netdr18)                     */
/* PRODUCT: OR                                                  */
/*  SYSTEM: ALL                                                 */
/*    KEYS: NETDRAW                                             */
/*   PROCS: FORMAT, NETDRAW                                     */
/*    DATA:                                                     */
/*                                                              */
/* SUPPORT:                             UPDATE:                 */
/*     REF: Example 18 from the NETDRAW Chapter(PM User's Guide)*/
/*          Publc Domain IP Program, STEIN9                     */
/*    MISC:                                                     */
/*                                                              */
/****************************************************************/

 /*** Iteration log obtained from PROC LP

stein9 --- lp3rw149.sas

      1       0     ACTIVE         4 0005     0.667       2      2         .
      2      -1     ACTIVE         4 0002     0.667       2      3         .
      3       2     ACTIVE         4 0004     0.667       2      4         .
      4      -3     ACTIVE 4.3333333 0007     0.667 1.66667      5         .
      5       4 SUBOPTIMAL         5 .            .       .      2         1
      6       3   FATHOMED 4.3333333 .            .       .      1         1
      7       1     ACTIVE         4 0008     0.333       2      2         1
      8      -7     ACTIVE         4 0007     0.667       2      3         1
      9      -8   FATHOMED 4.3333333 .            .       .      2         1
     10       8   FATHOMED 4.3333333 .            .       .      1         1
     11       7     ACTIVE         4 0007     0.667       2      2         1
     12     -11   FATHOMED 4.3333333 .            .       .      1         1
     13      11   FATHOMED       4.5 .            .       .      0         .

   *****/

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
;


/* 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 h=3    j=c 'Branch and Bound Tree';
title2    ' ';
footnote1 h=1.5 j=c c=red   'Optimal  '
                    c=green '   Active  '
                    c=blue  '   Fathomed ';
footnote2 ' ';
footnote3 h=1.5 ' 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
           compress
           font=swiss
           rectilinear
           tree
           rotate
           rotatetext
           arrowhead=0
           htext=2;
   run;

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


goptions rotate=landscape;
title h=3   'Branch and Bound Tree';
title2 h=2  'Aligned by Iteration Number';
footnote1 h=1.5 j=c  c=red   'Optimal     '
                     c=green '      Active     '
                     c=blue  '      Fathomed ';
footnote2 ' ';
footnote3 j=l h=1.5 ' 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;