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;