if/wood.gif">

## Appendix A Detailed Pseudo Codes and Output of Our Codes

### A.1 Detailed Pseudo Code for the procedure find_in_arc in the Nonscaling Premultiplier Algorithm

Procedure find_in_arc
begin
let E be the set of eligible nodes; empty E; put root into E; set node pointer i=root;
set D=M where M is a very big number;
while ( CurrentArc(i)<>-1 ) do
begin
if CurrentArc(i) is a nontree arc then
begin
compute its reduced cost;
let u=tail of CurrentArc(i); v=head of CurrentArc(i);
if (u=i, cpuv<0 and ruv>0) or (v=i, cpuv>0 and ruvuv) then return (u,v);
end
CurrentArc(i)=CurrentArc(i)+1;
if CurrentArc(i)>n_arc(i) then CurrentArc(i)=-1;
end
let j=FirstChild(i); (assume j always exists, i.e. root is not a leaf)
get pred_arc(j); compute reduced cost of pred_arc(i);
while ( j<>root ) do
begin
while ( j<>-1 and pred_arc(j) has zero reduced cost ) do
begin
mark j to be eligible; put j into E;
while ( CurrentArc(j)<>-1 ) do
begin
if CurrentArc(j) is a nontree arc then
begin
compute its reduced cost;
let u=tail of CurrentArc(j); v=head of CurrentArc(j);
if (u=i,cpuv <0 and ruv>0) or (v=i,cpuv >0 and ruv< uuv) then return (u,v);
end
CurrentArc(j)=CurrentArc(j)+1;
if CurrentArc(j)>n_arc(j) then CurrentArc(j)=-1;
end
let i=j;
let j=FirstChild(i);
get pred_arc(j); compute reduced cost of pred_arc(j)
end
if ( pred_arc(j) has zero reduced cost and FirstChild(j)=-1) then
begin
mark j to be eligible; put j into E;
while ( CurrentArc(j)<>-1 ) do
begin
if CurrentArc(j) is a nontree arc then
begin
compute its reduced cost;
let u=tail of CurrentArc(j); v=head of CurrentArc(j);
if (u=i,cpuv <0 and ruv>0) or (v=i, cpuv >0 and ruv< uuv) then return (u,v);
end
CurrentArc(j)=CurrentArc(j)+1;
if CurrentArc(j)>n_arc(j) then CurrentArc(j)=-1;
end
end
if ( the reduced cost of pred_arc(j)<> 0) then
D=min{ D , absolute value of the reduced cost of pred_arc(j) };
while ( j<>root and Rightsibling(j)=-1 ) do
j=pred(j);
if ( j<>root ) then
begin
i=pred(j);
j=RightSibling(j);
get pred_arc(j); compute reduced cost of pred_arc(j);
end
end
return -1;
end

### A.2 Sample Output of our premultiplier codes

```The following are the outputs of running a 512 nodes network by NETGEN-HI
PNS==> 		premulti21 simplex
PS1==> 		premulti3 simplex
PS2==> 		premulti4 simplex
OLD==>		original simplex
CS2==>		CS3.4

-----------the following is premulti21 simplex--------------
n_node=513 (512 + 1 supernode); n_arc=4608 (4096 + 512 artificial arcs)
CPU time in find_in_arc is 5.733333
CPU time in find_out_arc is 0.066667
CPU time in update_tree is 0.100000
CPU time in update_pi is 0.083333
CPU time in total is 6.150000
# pivots: 1990 (non-deg: 1109 + deg: 881)
# arcs scanned in find_in_arc: 1875865 (pivots: 809295 + update_pi: 1066570)
# eligible nodes / pivots: 47
# eligible nodes / update_pi: 56
# arcs / nondegen. cycle: 16
# arcs scanned / deg. cycle: 8
# arcs scanned to find in_arc<>-1 / pivot: 406
# arcs scanned to find in_arc=-1 / update_pi: 569
# arcs scanned in update_tree / pivot: 27
primal value=24398649.000000, dual value=24398649.000000
optimal conditions are satisfied
~/Public/c/all> premulti3 /var/tmp/net pp ppp
-----------the following is premulti3 simplex--------------
n_node=513 (512 + 1 supernode); n_arc=4608 (4096 + 512 artificial arcs)
CPU time in find_in_arc is 2.350000
CPU time in find_out_arc is 0.116667
CPU time in update_tree is 0.050000
CPU time in update_pi is 7.333333
CPU time in total is 10.366667
# pivots: 1542 (non-deg: 746 + deg: 796)
# nodes whose pi is multi-eps/4: 18739 (in method2: 18729)
# pi updates: 14232 (delta1: 1443 + delta2: 12785 + d1=infty: 4)
# arcs scanned in find_in_arc: 433153 (pivots: 53871 + update_pi: 379282)
# eligible nodes / pivots: 57
# eligible nodes / update_pi: 129
# nodes whose pi is multi-eps / method2 pivost: 1
# arcs / nondegen. cycle: 14
# arcs scanned / deg. cycle: 9
# arcs scanned to find in_arc<>-1 / pivot: 34
# arcs scanned to find in_arc=-1 / update_pi: 26
# arcs scanned in update_tree / pivot: 38
primal value=24398649.000000, dual value=24398649.000000
optimal conditions are satisfied
~/Public/c/all> premulti4 /var/tmp/net pp ppp
-----------the following is premulti4 simplex--------------
n_node=513 (512 + 1 supernode); n_arc=4608 (4096 + 512 artificial arcs)
CPU time in find_in_arc is 1.300000
CPU time in find_out_arc is 0.116667
CPU time in update_tree is 0.083333
CPU time in update_pi is 2.300000
CPU time in total is 4.100000
# pivots: 1529 (non-deg: 758 + deg: 771)
# nodes whose pi is multi-eps/4: 1259 (in method2: 1002)
# pi updates: 2081 (delta1: 1428 + delta2: 650 + d1=infty: 3)
# arcs scanned in find_in_arc: 113441 (pivots: 49085 + update_pi: 64356)
# arcs scanned in update_pi: 506312
# eligible nodes / pivots: 60
# eligible nodes / update_pi: 52
# nodes whose pi is multi-eps / method2 pivots: 1
# arcs / nondegen. cycle: 15
# arcs scanned / deg. cycle: 8
# arcs scanned to find in_arc<>-1 / pivot: 32
# arcs scanned to find in_arc=-1 / update_pi: 30
# arcs scanned in update_tree / pivot: 38
# arcs scanned in update_pi / update_pi: 243
primal value=24398649.000000, dual value=24398649.000000
optimal conditions are satisfied
~/Public/c/all> yu1 /var/tmp/net pp ppp
-----------the following is original simplex-------------
24398649.000000    512     4096 [/var/tmp/net,pp]
Simplex done.  Report is in file
CPU time is 1.483333
total # pivots: 4842
total # arcs_scanned: 187778
# arcs / cycle: 18
# arcs scanned / pivot: 38
~/Public/c/all> ./gold/cs2 < /var/tmp/net
c----------- CS 3.4 --------------
c
c nodes:             512     arcs:             4096
c scale-factor:       12     cut-off-factor:   23.3
c
c time:             0.55     cost:         24398649
c refines:             4     discharges:       6450
c pushes:           7137     relabels:        10095