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