USER'S GUIDE TO MATCOV by Clovis Perin under supervision of Prof. K. G. Murty Technical Report 80-5 Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 September 1980 Research effort is partially supported by the Department of Industrial and Operations Egineering of The University of Michigan and by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under grant no. AFOSR 78-3646. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation hereon. This paper was typed by Mrs. Geraldine Cox.

TABLE OF CONTENTS Page INTRODUCTION............. 1 PROGRAM INPUT.......................... 2 PROGRAM EXECUTION........................ 6 PROGRAM OUTPUT......................... 19 ERROR MESSAGES.............23 CPU TIMES............................ 25 DATA STRUCTURE,......................... 30 PROGRAM ST'UCTURE.................. 43 ADDITIONAL OUTPUTS....................... 47 MODIFYING THE PROGRAM SIZE................... 49 REFERENCE......................... 51 APPENDIX..................... 52 i

1. INTRODUCTION This report discusses a FORTRAN implementation of the algorithm presented in [1] for the minimum cost 1-matching/covering problem. Given a network G = (N,A,c) where N is a nonempty set of n nodes, A is a set of m edges (an edge is an unordered pair of distinct nodes), and c = [ci;] is a vector of edge costs, the minimum cost 1-matching/ covering problem is formulated as follows: Find an m-vector x = x..],;j To minimize.... x. 1;J 1;J 1;J Subject to 1 for i C N -x 1 for i E N j i;j ] j i 1 for i E N K unconstrained for i E N x.. - 0, 1 for (i;j) E A 1i;j < > - = _ where N, N, N, N is a given partition of N. It is assumed that the reader is already familiar with the solution of this problem, which is discussed in [1].

2. PROGTRAM INPUT Every node and edge of the network is uniquely identified by a user assigned node/edge number. Each pseudonode created during the execution os the program is automatically associated with a unique pseudonode number. These numbers need not be serial, but they should lie within the ranges specified later on. The program starts by reading the network which is defined by the data below: a) node data (node number., subSe^ the node belongs to); b) edge data (edge numberr pair of nodes joined by the edge, and edge-cost). Successive iterations of post-optimality can be carried out. Changes introduced at each iteration define a new network, and these changes are always made on the latest network. Changes in the network are classified into the following types: a) edge-cost change (edge number, and new edge-cost); b) partition change (node number, and new subset); c) edge elimination (edge number); d) node elimination (node number); e) new node introduction (node number, and subset); f) new edge introduction, (edge number, pair of nodes joined by the edge, edge-cost). In short, the program input has the following structure: 2

i) network data (node and edge data); ii) first post-optimality iteration (change data); iii) second post-optimality iteration (change data); and so on. Just as a remark, this implementation is able to work with multi-networks; i.e., it is possible to have two or more edges joining the same pair of nodes. Therefore, every edge must be uniquely identified by an user assigned edge number (the cost of two parallel edges may be the same). The description of the input data is based on the variables given below. title - string with at most 48 characters, choosen by the user to identify the problem. n - number of nodes ( n. 100 ). m - number of edges ( m = 3000 ). option - program option (see section 5 for details) option = 1: program prints statistics only; option = 2: program prints final solution only (suggested for most of the applications); option = 3: program prints progress report, final solution, and statistics; option = 4: program prints input data, progress report, final solution, and statistics. node - node number (integer between 1 and 100); mdst be unique for each node. 3

set - indicates the subset that node belongs to, under the code: set = 0: node ~ N0 set = 1: node E N set = 2: node E N set = 3: node E N edge - edge number (integer between 1 and 3000); must be unique for each edge. cost - edge cost (real number between -9999.9 and +9999.9). nodel, node - numbers of the pair of nodes joined by edge. k1 - total number of edges which have the cost coefficient changed during a post-optimality iteration. k2 - total number of set changes. k3 - total number of edge eliminations. k4 - total number of node eliminations. -4 k- - total number of node introductions. k1 - total number of edge introductions. The user must provide the input data in FORTRAN free format; i.e., blanks ar commas can be used as separator of data, and each line below must start in a new line of the input file. 4

Tnput Data title m, n, option node, set (one line per node) edge, nodel, node2, cost (one line per edge) kl, k2, k3, k4, k5, k6 edge, newcost (one line per cost change) node, newset (one line per set change) edge (one line per edge elimination) node (one line per node elimination) node, set (one line per node introduction) edge, node1, node2, cost (one line per edge introduction) 0, 0, 0, 0, 0, 0 (last line) The 2nd, 3rd., and 4th. lines define the original network. From the 5th. line to the 11th. line above, a post-optimality iteration is defined. Every post-optimal iteration should be given under such a general form. WThen several iterations are used, the network at the beginning of iteration k is the same as the network at the end of iteration k-1. Finally, the last line of the input data should be a line with zix zeros separated by commas or blanks. 5

3. PROGRAM EXECUTION This section is appropriate for users of the Michigan Terminal System (MTS) of the University of Michigan; users of different installations should prepare the necessary modifications. Batch Mode On batch mode, the deck of cards to be punched should have the following structure: $SIG ccid password $RUN K45V:MATCOV T=time ~ input data $END' ILE $SIG where ccid, and password are assigned for each user of MTS. As an order of magnitude for time, MATCOV is able to solve a network with 50 nodes and 1000 edges in less than 5 s. 6

Example 1 Consider the network in Figure I. The input data to be used in the solution of these three problems is shown in Output I. Note that the original network has 4 nodes and 5 edges, the first modified network ha s 4 nodes and 5 edges, anqd the last network has 3 nodes and 2 edges. Output II shows the optimum solution for the original network. The first post-optimality iteration was performed with 1 edge cost change, 1 edge elimination, 1 node elimination, 1 node introduction, and 2 edge introduction; edge 240 = (20;40) was automatically eliminated from the network because it became incident with a nonexisting node (node 40 was eliminated). The optimum solution for the first modified network is given in Output III. In the second post-optimality iteration, one edge and one node were explicitly removed from the network, and two edges were automatically removed because they were incident with eliminated node. The final solution for the second modified network, which is infeasible, is presented in Output IV; the last network corresponds to an infeasible minimum cost 1-matching/covering problem. 7

N= N N ----- 200 -— 20 200y ~edge cost 200 20.0 NETWORK # 1 230 210 240 210 -50.0 220 -4.0 7X\ an~ ~ 230 2.57 (30 ) —--- 220 40 240 -2.0 N N~ N N N 60 -- 290 ---........ —... 200 -- 20'\N.~~~ /(~~~~~~~ ^edge cost 1~~\ /I~ X190 10.0 190 230 210 200 20.0 210 -50.0 230 3.0 NETWORK #2 ( 30 290 -10.0 N N f ( 60 ) (20 edge cost 190 210 ~~~190.~ 210 ~190 10.0 N 210 -50.0 NETWORK # 3 Figure I - Example 1 8

() r-4 a 0 CO C-) *rC) rrrh~~~~~~~~~~~~~~~~~~~~~~~~~~0 G) 4-3 C o'. C' t. C' c T~f.< ~ t ~ t> ~; f >; tx - c H~~~~~~ _,':'..C r,:J c C I VIL-~~~~~C eC^~~~~~~~~~, O~^ L'".. C. C C C C C.. *- CO I- W~ ~. - 0 r C(]-:';!ttt C - O C e r - c rr-r.c ~'.1 c < 9 u Z FU-:: Of O CJ c C CC O cf, O CI Cf C C' O C^0 cr - cn d a N t;:t tIJ ci rV 0f T-: C r. o W 00 0 Clw N N N N t~i N N N _ w. 9

'-4-4 r; * ) 0 fsi *u~~~~~~~~~~~l 0 F"- 0 J":~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~o o.~ tr ~.-.,;S f-. [L- tr 0 t3^~~~~~~~~~~~~~ ^3~~~~~~~~~~~~~4-I.. * ** U b?i O t? * O i..-4 z c,F.' Pe ~c * * 0C F- 14I1r* l *U C * * O t - Cj I C O o C C' *. C *r 0 ~" C-* ~ ^ - t yi,.~ r ~'.,. n. t- r — 3 C Ct - C c. r- = - r O) C) C F mj _ 10 C4 M C 3 S' ^ U

c. C) 0 CCC H o 0 H C O., O rY ~~~~~~~~~~~~~~~~~~~~~ t^T; V)~~~~~~~~~~~~~~~~~~~0. 0T0 0 o- CCTE C L'.~..'f.- 4 I — * _0 C0 _0 tI C 0 c- o: — c ~. -. 0 Z> * L^ ^.;J. * 0 I 4* C I - _c t-z ^ o z G. sr Z _ (' X o: &. _ > 4;OC- z C ~ b- w,, c C c c* c 0 ** f tv w C * * 4* D. ~< r: f.L = * C ~. C S I 0 E C r_ e C C C t. O r. ~ r^ c' r o c Cr: C r C, * c * H! i. r. r i- ( C- 4.. C. 1 V'- ) C- O n C C C C cr. r' - t. C*. C C H U. I;. 11 H M 0 c= c1 v

u3 -- * n 2' V) ooc Er;k~~~~~~~~~~~~~~~~~~ u; uxr T W *-' 1 I1: f.- cc *-' L-r n c 0 o r r * L$ c 0 0 C ) C 000' ~ ~ o.V. 0 * - * C H L'c-?~~~~~~ V.2~~~~~~ * *i " "'(0, C -cC * 4 0 * C. 0 * I: 5A: 0' - E Lt P tS, Z U: C' -* M C. C C C- C M'23 * (HZ _ _4 =.-'ooo o ~ c-; >r' IEc ~3c, CH r:E.< 4-1 t v. sI 0, C O' I-4 C C 0.H **?- U rs C *- * C + vi "^ w =. I I *,I:tC; 00 * 0 C C c. C1 cp V)U U) M* t() C C N 2H C f C: H (s C H;H PC~ to C~ 1N 1r> 0 C C ~: - S O _ N,, O C C H ~-~ 3 IU:

Terminal Mode On terminal mode, it is convenient to create a file containing the input data previously to the execution of the program. In the MTS statement below, infile indicates such a file, and outfile represents the file to which the output will be directed, such as *PRINT*. As an order of magnitude for time, MATCOV is able to solve a network with 50 nodes and 1000 edges in less than 5 s. $RUN }K45V:MATCOV 5=infile 6=outfile T=time Example 2 Consider the networks in Figure II. The input data for such an example is listed in Output V. All three networks have 9 nodes and 11 edges. In the first network, all nodes are in the subset N During the first post-optimality iteration, node 9 is transferred to subset N. During the second post-optimality iteration, node 9 is transferred to subset N. The final solution for the original network, which is infeasible, is presented in Output VI; it contains 2 pseudonodes. Output VII shows the optimum solution for the first modified network, which contains just one pseudonode. Finally, the solution of the last network has two pseudonodes and it is shown in Output VIII. 13

-ojo C.4 0 -, rI CM I 00 00 0 (N Io 41, 1 CM 3 i zJ 0(1 0 " " CA C) C) 0, 0 0 0 * C ('.,.., CY),c / OQ).~l-C. 4Hn 0 " d o O "0, C).H.H o s( -~.I~ t~0 o' oU v 0) o 0 0 (N I o o CM C4 * *H ) U) U3 Ir g Fl X t t S a}.H.. Z a) a), / \ a.. I (~J )^^ 14

N Q) 0 *c 0 4J.-4.., cz,-. 1~: C L. C'. 0 n, cr r:C' a cC,' C' C' C e. cz r, a,-. O 15 15

C: c CT C4 eq O,~,","rCW r'c. b"~~~c ~ ~ ~ ~,r * * * * * 0 a m; LI i J* 0n CC C.,. Oct 0 U-. i;g-~~~~~~~~~~~~~ Itr (~ C " * LL * * t. -; P. * -. rF >L' *~- _- ~i3 f CZ 0I L_ * _ r, 7Ze ~ tr 0 > > C-C - - I -- C~, a "s (U % (^ ^ r^ cr 4.. 3 0 t. C.4-1, *. CU ccI O0 V e c c r U C I'.. ~ ct. F r- r 0 * * *_'"r* t t4 4s O':+~~~~~~. C 11C fl ~ * C VC C 0 V U 0a C0 *r, _ > t.: CJ O! _ P., H ~c, L' c~ C V 16

(4 (* 0' in oh C C' a- c r.;) C,:-4 -4 C Q00 ^~.: Z: W. U,4 V). a O *.* L L~~~~ V ~ ~ ~~) o - *40 - vC CE.'a U u. ~ W, -_ r:r (s Ct. r-o r-: 4J: VL, * a,r. -1 C C C O *-o _ " P}C C' -fCrc C; - C C } c — ct/)t`~~~~1 *- y) H * * C i * C 0 Q C' * y, cc: t E. t- CF C C14; *- a' a M * < H o r* _n ZC H O uo. r to v'. CbsS C'rC C r4 r, U C - e.l C' f- 0 C CH C. 0- c'C O Ir _-4. c- C* C C^ r Oj1 tr.- c -:: c- ~,' -' _. c e c o. _ c. ~ H - t- r t C C *- Cs r: r-?,. t- 3: C Hc rO C^ 0~ C T U 0 t? 4

Lr. cO ~ Ci _- P.; f iN 00- 0 "r O4 4 t^Va (\J CN CM I 0, — -. C, CJ'c V;o) c C; O C.. C t- r\; Cs C: c-,3 ( -' e X r._ _ 2t 3 _ C C Q co r C t c, c; C(, O - (- CO - C * p C. 0 -4, t - t^, l - SL * *' c. 0 4 C, r-,.-., t' {C,'. O * - (t- e C r t rci r' 0.'. C O c4 &- 4-) _3 cr c F-A 0.' ~ "- - ~C- C C 0 - 0 c -.C C4 F H <~;' cr,c- cj C)~;?* r-~- - I-. [... t,- t;, C- H c,~ r — 0.,__' -,: o_ _ T..c C t; ^, 7T r S C -CC L CC oC NC t.' rL- 0 h-,,J _r _ _ A -r. t - _ C H F l - r L " ":",.- J,.. r_- ct':1 18

5. PROGRAM OUTPUT There are several possible outputs in accordance with the value assigned by the user to the variable OPTION. They are classified into: option = 1: statistical output only; option = 2: final solution output only; option = 3: progress,final olutiOn. and statistical outputs; option = 4: input data, progress, final solution, and statiscs; see section.9 for options providing debuggingoutput. The final solution output is printed at the end of each iteration; there is one for each network being solved (this output is produced by all options except by option 1). Such a report consists of the following information: a) message "PROBLEM IS INFEASIBLE", if appropriate; b) total number of nodes and total number of edges; c) dual objective value of the final solution (this is the optimum objective value whenever the problem is feasible); d) list of all nodes, comprising for each node, i) node number, <.. > ii) subset code (0, 1, 2, 3 for N, N, N, N, respectively), iii) node price (dual variable); 19

e) list of pseudonodes (if appropriate), comprising for each pseudonode, i) pseudonode number, ii) pseudonode price (dual variable), iii) list of nodes in the simple blossom; f) list of edges, comprising for each edge, i) edge number, ii) and iii) pair of nodes joined by the edge, iv) edge cost; g) list of all edges in the (primal) solution. Statistics are provided for every option, except by option 2. It is expected to be used by researchers who are interested in comparing performance of codes. This report, provides a table with the following information: a) Dual Solution Changes - number of times the dual solution change step was executed during the iteration; b) Paths rematched - number of alternating paths rematched during all augmentations of the iteration. c) Nodes Remated - number of nodes in those alternating paths; 4U lyde&8^arlanend.! ~- number f. odeS! I.aidved- from- th j;i st of. unsoarined nodes; 20

e) Edges Scanned - number of (equality) edges which were scanned; f) Nodes Labelled - number of outer and inner labels assigned; g) Shrinkings - number of simple blossom shrinkings; h) Unshrinkings - number of pseudonode unshrinkings; i) LINK/MATE's Used - number of starage positions used for LINK/MATE information (the value of P2 was estimated by this statistic); j) CPU MSEC (INPUT) - time in cpu msec used for initialization and input operations; k) CPU MSEC (SOLUTION) - time in cpu msec used for solving the problem; 1) CPU MSEC (OUTPUT) - time in cpu msec used for performing the final solution transformation and printing the output. The progress autput. is available by option: 3 andi option.4; it contains a number of messages indicating important marks that the algorithm achieves during the solution, such as the following: number of exposed nodes at initialization; node scanning; node labelling; augmentation; simple blossom shrinking; pseudonode unshrinking; 21

dual solution change; node/edge inspection; etc. In this report, several symbols are used; among them we have the following: <R> - indicates the root of an alternating tree <+> - indicates an outer node <-> - indicates an inner node < > - indicates an unlabelled node <=> - indicates an equality edge edge = (nodel,node2) - indicates an edge and the pair of nodes joined by the edge; DUAL SOLUTION CHANGE: XXXX.X - indicates the increase in the dual objective value per exposed node (variable h in [1]). Only option 4 provides a listing of the input data at the time data is entering; such output is useful for detection of errors in the input data. 22

5. ERROR MESSAGES This section deals with the events that cause error messages and the subsequent halt in the execution of the program. It is expected that the message printed to be sufficient to lead to the error; however, since no indication is given to the input line the error was detected, it may be useful to rerun the program using option 4. F-or some errors, it may be necessary to augment the size of the program and recompile it (see section 10 for such cases). The complete list of error messages is given below. UNEXPECTED END OF FILE self explanatory. ILLEGAL PARAMETER n< < O, k3 < 0, k5 < 0, < m < O, k2 < 0, k < 0, 6 < ILLEGAL NODE node < 1, node > N2 (100), duplication of an existing node, edge incident with a nonexisting node, elimination of a nonexisting node. 23

ILLEGAL EDGE edge < 1 edge > M2 - L2 (3000) duplication of an existing edge elimination of a nonexisting edge, ILLEGAL NODE SET set < 0 set > 3 NODE STORAGE SPACE EXCEEDED [see section 10] n > N2 (100) introducing more than N2 (100) nodes. EDGE STORAGE SPACE EXCEEDED [see section 10] m > M2 - L2 (3000) introducing more than M2-L2 (3000) edges. LINK/MATE STORAGE SPACE EXCEEDED [see section 10] HINK > P2 (1500) ERROR NO. XXX not used 24

6. CPU TIMES Minimum cost 1-matching/covering problems were randomly generated by the program NET.OBJ (the source code called NET.FTN is listed in the appendix). The input for such a program should have the following structure (FORTRAN free format): title n, m, #ptts, mincost, maxcost, seed k1, k2, k3, k4, k5, k6 k1, k2, k3, k 4 k5, k6 0, 0, 0, 0, 0, 0 where title, m, n, k, to k6 have the meaning presented in section 2. 1 6 The parameter #sets indicates the number of subsets to be used as the partition for the set of nodes; #sets -1 indicates that all the nodes should be in the set N; #sets - 3-indicates that all nodes should be evenly distributed among the sets N, N, N (no node in N ); #sets = 4 indicates that all nodes should be evenly distributed among the sets N, N, N N. The parameters mincost, maxcost represent the range in which the edge costs are to be uniformily distributed. The parameter seed is used as an initialization number for the random number generator; different networks are generated just by changing seed. The number of post-optimality iterations to be generated are indicated by the number of nonnull lines with the parameters kl to k. All problems are generated with -1 6 program option = 1, which means that the execution of MATCOV will produce only statistics. 25

It should be noted here that the output produced by NET.OBJ can be used directly as input for MATCOV, execpt when there are node eliminations because this may imply that some edges become incident with nonexisting nodes; such edges are automatically eliminated by MATCOV from the network. Since NET.OBJ does not take into account such automatic edge eliminations, it may generate inconsistent changes afterwards. Table I shows a set of average cpu times obtained from outputs of MATCOV under the statistic CPU MSEC (SOLUTION). These cpu times do not include the cpu time spent during the reading of the input data and during the printing of the final solution. All problems in Table I correspond to networks with 50 nodes; 1000 edges; edge costs (integers) generated in the intervals [-10,10], [-100,100], [100,200], [-200,-200]; and partitions with 1, 3, 4 sets of nodes. Three problems were generated for each cell of Table I. Table II presents the average cpu times obtained for problems with edge costs generated in the range [-100,100]; partitions with 1, 3, 4 stes of nodes; and (#nodes,#edges) taking the values (20,200), (40,800), (60,1800). Three problems were generated for each cell of Table II. Note that #nodes = (#edges)2 / 2..for all cases. 26 ~ 2 cell of Table II. Note that #nodes = (#edges) / 2 for all cases. 26

Edge Cost Range Partition [-10, 10] [-100, 100] [100, 200] [-200, -100] N 902 907 1064 887 N, N, N 485 505 1372 477.......... e N, N, N, N01 355 354 905 354 Table I - cpu msec (no readings, no writings) for solving minimum cost 1-matching/covering problems with 50 nodes and 1000 edges using AMDAHL 470/V7. Figures are the average of 3 different problems. ( # Nodes, # Edges ) Partition (20, 200) (40, 800) (60, 1800) = 1 63 472 1796 N N., N I 39 252 887 N N N0 N N N, N N 34 199 640 Table II - cpu msec (no readings, no writings) for solving minimum cost 1-matching/covering problems with edge cost ranging in the interval [-100,100] using AMDAHL 470/V7. Figures are the average of 3 different problems. 27

Table IIT indicates the average cpu times obtained for networks with 50 nodes, 1000 edges, edge cost range [-100,100], and partittions with all 4 sets. Post-optimality analysis was applied to the problems in order to have 1000 edge cost changes. Due to the way problems are generated, some edges may have their edge costs changed more than one time in the same post-optimality iteration; this means that some edges may keep their edge costs du ing one iteration. Two postoptimality iterations were applied for each problem; each cell of Table III corresponds to the average of 3 problems. Cpu times spent for reading the input data, for initialization, and for preparing a post-optimality iteration are shown as CPU TIME (INPUT); they can be compared against the CPU TIME (SOLUTION) spent for solving the problems. 28

CPU TIME (MSEC) Input Solution Original 3 361 315 Network 3 1000 edge 31 cost changes 1000 edge 299 113 cost changes 29 11 Table III - cpu times for input and solution of problems with 50 nodes and 1000 edges, edge cost range [-100,100] using AMDAHL 470/V8. Problems had twice 1000 edge cost changes. Figures are for the average of 3 different set' f problems. 29

7. DATA. STRUCTURE Intenally, every node is identified by an unique number between NO (1) and N2 (100); every pseudonode by a number between LO (101) and L2 (150); and every edge by a number between MO (151) and M2 (3150). So, the external and internal representation of nodes and pseudonodes is based on the same node/pseudnnode number. However, the internal representation of an edge is obtained by the expression internal edge number = external edge number + L2. Moreover, each edge is decomposed into two arcs joining the same pair of nodes, but with different directions; one of the arcs is identified by the edge number corresponding to its edge; the other arc is identified by the complement of that number to M9 = 2.M2 + 1 - 6301. arc1 = edge arc2 = M9 - edge In this way, every arc is uniquely identified by an arc number in the range MO (151) to M9 - L2 - 1 (6150). In the context of this section, all node/pseudonode/edge/arc numbers refer to the internal representation, unless it is explicitly sated as external. 30

Main Variables N - number of nodes M - number of edges N2 = 100 - maximum node number L2= 150 - maximum pseudonode number M2 = 3150 - maximum edge number P2 = 1500 - maximum position in LINK/MATE INF = 9999.9 - maximum edge cost -50 TOLER = 10 - tolerance for numerical comparisons VALUE - dual objective value ROOTS - number of exposed nodes The variables NODE, PNODE (pseudonode), EDGE (edge.or. arc), IND (index), BLSM (node in a simple blossom),-.BASE (base of a simple blossom), APICE (apex of a blossom), BNODE or BCINOD (BCI of a blossom), PT (pointer) are used throughout the program with numerical appendices (e.g., NODE2); all these variables have always the meaning indicated, except NODE which is normally used as node or pseudonode, bit it may indicate an edge or an arc. The variables ROOTS, NODE$, EDGES, SHRK$, UNSH$, A.UGM$, DUALS, RMAT$, LABL$, LINKS, TIMEI, TIME2, TIME3 have statistical usage. The values assigned to the variables PRINT, TRACE depend on the program option. 31

List of existing node/edge numbers LIST(ind) - three-stack vector containing all node/edge numbers which correspond to existing elements in the network. node numbers: head.-_NO tail = N1 psaudonode numbers: head = LO tail = L1 edge numbers: bead = MO tail = M1 The heads NO, LO, MO are fixed during the execution; the tails N1, M1 are fixed for each post-optimality iteration; the tail L1 depends on the number of pseudonodes in the solution. INDEX(node/edge) - vector of indices for LIST NO = INDEX(node) = N1 NO - node = N2 LO = INDEX(pnode) = L1 LO = pnode = L2 MO = INDEX(edge) =M MO = edge = M2 INDEX(node/edge) = 0 implies a nonexisting node/edge INDEX(node/edge) > 0 implies an index to LIST for existing node/edge: LIST(INDEX(node/edge)) = node/edge for a valid ind: INDEX(LISr(ind)) = ind 32

INDEX LIST NO N ind node node N2 N2 pnnode e _________________2~ ~ ~ ~ ~ ~ ~ ~ Y.::L2''.- j lilnd | edge. -D..-...," Figure III - i.st of existing node /edge numbers. -' 33 pnode _:.:.:~'.',...:...: l|: f ^'.,..[ der-L21~~~~~~~~~~ "'..... i.-'.;..;.....:..... nonexi sting pnode MP I I:.MO edge edge. ind' Ml - M2- M'.' Figure III - list of existing node/edge numbers 33

Network Specification: SET(node) - indicates the partition subset that node belongs to, under the code: 0 - node of N~ 1 - node of N 2 - node of N 3 - node of N PRICE(edge) - edge cost of edge HEAD(arc) - indicates the node that arc is heading to. in order to determine the two nodes joined by an edge,- use the formulas: arc1 edge arc2 M9 - edge node = HEAD(arc ) node = HEAD(arc ) 34

Arc Lists LINK/MATE(pt) - pair of vectors used for storing the following lists: incidency-list(node) - contains all current equality ares heading from node (incidency in-the current- equality network); mating-list(node) - contains all current solution arqs heading from node; internal-list(pnode) - contains equality arcs joining two nodes inside pnode LINK(node) - head of MATE(node) - head of mating-list(node) LINK(pnode) - head of internal-list(pnode) MATE(pnode) - base of pnode MATE(pt) - contains the arc number of an element in one of those three lists LINK(pt) - points to LINK/MATE indicating the next element in the list Obs.: MATE(node) = 0 implies that there is no solution are:headi ngt- frotn node MATE(node) > 0 implies that arc = MATE(node) is the only solution arc heading from node MATE(node) < 0 implies that pt -MATE(node) is the position in LINK/MATE containing the first element of mating-list(node). if APEX(PSEUDO(node)) P node then MATE(node) is meaningless; in words, the solution edges inside a pseudonode are determined only at the time the final solution is being printed. *,I'

LINK MATE arc. —-- — k node base pnode,Pt pt ~ g /~~p -/ / arc Pt Figure IV - LINK/MATE pair of vectors 36

Labelling Structure (current nodes)LABLO(node) - label of node (OUTER, INNER, UNLABD) PREDA(node) - predecessor arc; this is the second arc on the path from node to the root; defined only for outer nodes HEAD(node) - points to the apex of the root of the alternating tree TPEE(node) - single-linked list containing all nodes of an alternating tree. The head of such a list id the apex of the root of the alternating tree, Simple' Blossom Structure (noncurrent nodes) LABLO(node) - pseudonode number of the simple blossom containing node. HEAD(node) - node number of the next node in the cyclic list containing all nodes in a simple blossom PREDA.(node) - arc number of the arc heading from node to HEAD(node) MATE(pnode) - base of the simple blossom associated with pnode 37

node2 oVNVVVV\4b + ^ T +4+/ / " 4. - + node."'VV root (apice) Alternating tree LABLO(node = outer LABLO(node2) = inner LABLO(root) = outer HEAD(node ) apice HEAD(node2) = apice apice = APEX(root) HEAD(root) = apice PREDA(node ) arc PREDA(node) = null PREDA(root) - null Figure V - Labelling Structure 38

node bism LABLO(node) base - MATE(blsm) arc - PREDA(node) simple blossom node,= HEAD(node) Fiur VI Boo an Smeblossom 39 | — apice - APEX(pnode) \ base = MATE(pnode) node __...~ blsm = LABLO(node)'_.,. ~ —-- " pnode = PSEUDO(node) Figure VI - Blossom and Simple Blossom Structure 39

Blossom Structure (noncurrent nodes) PSEUDO(node) - node in the current network which contains node; PSEUDO(node) = node implies node is current APEX(pnode) - points to an original node inside pnode; for original nodes: APEX(node) - node PRICE(node) - corresponds to the dual variables; let y(i), z(s) be the dual variables defined in [l 1; let node i, pnode - s < y(i) for i E N ULN PRICE(i) = y(i) +Z [ Iz(s) /2: s contains i ] for i N s > y(i) + [ |z(s): s contains i ] for i F. N s PRICE(s) = |z(s) / 2 for s -~ S At the time_ the final solution is to be printed, the values of y(i) and z(s) are computed from the above expressions and printed. BCI(node) - points to the Blossom Constraint Identifier. < > BCI(node) = node node E N UN UN0 BCI(node) = null node E N < > BCI(pnode) = node node E N UN BCI(pnode) = null all nodes inside pnode are in N MPRICE(node) - maximum value for PRICE(BCI(node)) 40

<, MPRICE(node) = 0 for node E NU N~ MPRICE(node) = INF for node ~ N or current node ~ N MPRICE(node) = variable for noncurrent node E N MPRICE(pnode) = MPRICE(BCI(node)) For noncurrent node of N the value of MPRICE is assigned at the time the node becomes noncurrent by setting MPRICE(node) = 2.PRICE(node) Special Lists NSCAN(pt) - cyclic queue of unscanned nodes Head: HSCAN Tail: TSCAN Usa'ble size: N9 = N + 1 Nodes to be scanned are removed from the head of NSCAN; nodes just outer labelled are introduced in the tail of NSCAN; inner nodes of just erased alternating trees are introduced in head of NSCAN; pnodes to be scanned just removed from NSCAN have the nodes in their simple blossoms introduced in the head of NSCAN. INSP(pt) stack of nodes/edges to be inspected after a dual solution change step have been performed head: HINSP usable size: M + N 41

NO()I[G(IpL) - stack of nodes inside a blossom iead: HORIG Usable size: 3 N / 2 42

8, PROGRAM STRUCTURE This section discusses the main characteristics of each subroutine in the FORTRAN program MATCOV. MATCOV (main program) call GETNET 10 call GRWFOR call PUTSOL call POSTOP go to 10 Subroutine GETNET (Get network) read the original network initialize the variables plant the alternating forest special calls: MATCH main divisions: i) initialization; ii) read node data and set node variab.; iii) read edge data and set edge variables; iv) plant alternating tree. Subroutine GRWFOR (Grow Forest) solve a network with an alternating tree controls the scanning, dual solution change, and inspection proce sses; starts unshrinking and augmentation processes; checks both termination criteria: optimality and infeasibility; special calls: SCAN, MINIM, RMATCH, NSHRINK main divisions: i) scanning; ii) dual solution change; iii) inspection Subroutine PUTSOL (Put Solution) transform the final solution: internal to external representation prints the final solution no special calls main divisions: i) get solution edges and transform node prices; ii) get simple blossoms and solution edges inside pseudonodes; iii) print statistics 43

Subroutine POSTOP (Post-Optimality) controls the post-optimality process; reads and performs the changes in the network plants the alternating forest special calls: NMATCH, OPEN, DECRSE, MATCH, INCRSE, INCLUD main divisions: i) introduction; ii) edge cost changes; iii) node set changes; iv) edge elimination; v) node elimination; vi) node introduction; vii) edge introduction; viii) plants alternating forest Subroutine SCAN (Scan arc) Scan an equality arc whose tail is an outer node starts shrinking, unshrinking, and augmentation processes; assigns inner and outer labels; special calls: SHRINK, RMATCH, NSHRNK main divisions: i) initialization; ii) shrinking check; iii) double augmentation check; iv) type 2 augmentation check; v) type 0 augmentation check; vi) type 1 augmentation check; vii) node labelling; viii) type 3 augmentation check; ix) unshrinking check. Subroutine SHRINK (Shrink a simple blossom) Given an edge joining two outer nodes of the same alternating tree, this subroutine finds the simple blossom containing that edge and shrinks it into a pseudonode special calls: ORIG, STPSDO, RMATCH main divisions: i) get simple blossom; ii) shrink simple blossom and determine BCI; iii) type 3 augmentation check. Subroutine NSHRNK (Unshrink a pseudonode) Given an inner labelled pseudonode with null pseudonode price, this subroutine unshrinks it into its simple blossom. special calls: STPSDO, STAPEX main divisions: i) get alternating path in simple blossom; ii) unshrink pseudonode; iii) forest growing chekk; Subroutine RMATCH (Rematch alternating path) special calls: STAPEX main divisions: i) remate the nodes in the alternating path ii) erase the alternating tree 44

Subroutine MATCH Match two nodes joined by a given edge Subroutine NMATCH (Unmatch) Eliminate the mate connections of two nodes joined by a given edge. Subroutine MINIM (Minimization) Checks and updatds the inspection list Subroutine STPSDO (Set Pseudo) Update the variable PSEUDO of all nodes inside a pseudonode special call: ORIG Subroutine STAPEX (Set Apex) Update the basis and apices of all nodes inside a pseudonode with a new ape)x, Suibroutine ORIG (Original nodes) Get the nodes in the simple blossom of a given pseudonode. It is useful for obtaining the original nodes inside a blossom. Subroutine OPEN Unshrink all pseudonodes containing a given noncurrent node Remove all solution edges incident with a given current node special calls; NMATCH, ORIG, STPSDO, STAPEX main divisions: i) open pseudonodes containing a noncurrent node; ii) remove the solution edges incident with a current node. Subroutine INCLUD (Include edge) Include a new edge in the network special calls: OPEN, DECRSE, MATCH 45

Subroutine DECRSE (Decrease node price) Attempts to decrease the node price of a given current node by a given amount Subroutine INCRSE (Increase node price) Increases the price of a given current node to zero. Special calls: OPEN, DECRSE Subroutine ERROR Prints error messages. Subroutine DUMP Dumps node and edge tables 46

9. ADDITIONAL OUTPUTS This section deals with program options which produces outputs with debugging purpose. Options 5 to 9 activate;the subroutine DUMP which prints tables with node, pseudonode, and edge internal information at specific points during the execution of the program, as follows: option subroutine timming 5 PUTSOL before and after each final solution transformation 6 POSTOP before and after each post-optimality iteration 7 GETNET after the initialization of the original network 8 GRWFOR after each dual solution change step 9 GRWFOR before and after each scanning step Options corresponding to nonpositive integers causes messages indicating all subroutine calls and respective parameters to be printed during the periods of time given below. Also, dumps are provided at the biginning and at the end of these periods. The word trace is used as a referrence to such actions. option = 0: traces while there are no exposed nodes during the solution of the original network; option = -r: traces while there are r exposed nodes during the solution of the original network; option -N2: traces since initialization until the first augmentation; 47

option = -(k.N2+r): traces while there are r exposed nodes during the k-th post-optiinality iteration; option = -(k.N2): traces since the beginning of the (k-l)-th postoptimality iteration until an augmentation occurs. Finally, option =10 is useful in determining the period of time a trace is desirable. Such an option prints a message stating the number of exposed nodes every time an augr ntation is performed. A remark should be made here with respect to the dumps and traces which are produced by the options described in this section. The information is always given in terms of the internal representation and of the internal values. This means (cf. section 8): a) edges are internally identified by (edge number + L2); in the current version of the program, L2 - 150; so, an edge number 200 is internally represented by 350 = 200 + 150; b) node prices of original nodes inside a pseudonode are internally represented by: i y(i) for i C N PRICE(i) = y(i) - Z [ z(s): s contains i ] for i C N s > = y(i) - 2 [ 2z(s): s contains i ] for i C N s c) solution edges inside a pseudonode are not provided. 48

-10. MODTFYTNG THE PROGRAM SIZE!he design of MATCOV allows for modifications in the total number of nodes (N2 - 100), in the total number of edges (M2-L2 = 3000), in the total number of LINK/MATE's (P2 = 1500), and in the range of the edge costs ( [-INF,INF]; INF - 9999.9 ) to be easily performed, as explained below. Such modification should be made on the file PD.FTN which contains the source code in FORTRAN for MATCOV and it is listed in the appendix. a) Modifying the total number of nodes Let n' denote the new maximum number of nodes that will replace the current value 100. In BLOCKT.ATA assign N2 = n', L2 - (3n'+1)/2. Every vector with dimension 100 should be redimensioned with n'. Every vector with dimension 101 should be rediniensioned with (n'+l). Every vector with dimension 150 should be redimensioned with (3n'+1)/2. It may be necessary to rewrite some FORMAT statements. It should be noted here that the maximum number of edges will be modified also; if necessary, follow the instructions in (b). b) Modifying the total number of edges Let m' denote the new maximum number of edges that will replace the current value M2 - L2 (3000). In BLOCKDATA assign M2 - L2 + m'. Every vector with dimension 3150 should be redimensioned to L2 + m'. Every vector with dimension 6150 should be redimensioned to L2 + 2m'. It may be necessary to rewrite some FORMAT statements. 49

c) Modifying the total number of LINK/MATE positions Let p' denote the new maximum number of LINK/MATE positions that will replace the current value P2 (1500). In BLOCKDATA assign P2 p p'. Every vector with dimension 1500 should be redimensioned to p'. d) Modifying the value of INF or TOLER In BLOCKDATA assign INF (TOLER' to its new value. Note that this variable is in the current version of the program a REAL*4 variable. 50

11. REFERENCE C. Perin, "Matching and Edge Covering Algorithms", Ph.D. Dissertation, Department of Industrial and Operations Engineering, The University of Michigan, 1980. 51

APPENDIX 52

c C -- NETWORK GE FEPATCR C ITHE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PERIN C AUGUST 1980 C C C THIS PROGRAM GENERATES A NETWORK FORMATTED IN ACCORDANCE WITH C THE INPUT CF MATCOV C C REAL MINCSI, MAXCST INTEGER SET(100), EtGE, CPTION, HEAD1(3150), HEAD2(3150) INTEGER FFEE(1) /'*' / IOGICAL SAVE (3150)/31150*.FALSE./ C C READ N (#NCDES), M(fEDGES), NSETS(#SETS), MINCST, MAXCST C (EDGE COSTS RANGE. POM MINCST TO MAXCST), IX (SEED) WRITE (6,1) READ (5,2) WRITE (7,2) WRITE (6,3) READ (5,FREE) N, M, NSETS, MINCST, HAXCST, IX IF (N.LT.OOR.N.GT. 100) GO TO 999 IF (B.LT.0.OR.M.GT.3000) GO TO 999 IF (NSETS.IT.1.OR.NSET.GT.4) GO TO 999 IF (MINCS.GT.MAXCST) GO TO 999 WRITE (7, 4) N, H C C GENERATE NCDES -- 1 TO N DO 10 NODE = 1, N SAVE (NODE) = TRUE. SET (qCDE) = RAND (IX) * NSETS + 1 IF (SET(NODE).GT.3) SET(NODE) 0 10 WRITE (7,5) NODE, SET (NODE) DELTA = MAXCST- MINCST Ml = 150 + M C C GENERATE EDGES -- 151 TO 151+M DO 30 EDGE = 151, Ml SAVE(EDGE) =.TRUE. NODE1 = 1 + RAND(IX) * N 20 NODE2 = 1 + RAND(IX) * N IF (NCDE1.EQ.NODE2) GO TO 20 HEAD1 (EDGE) = NODE1 HEAD2(EDGE) = NODE2 CST = RAND(IX) * DELTA + MINCST 30 WRITE (7,5) EDGE, NODE1, NODE2, CST C C GENERATE INPUT FOR POST-OPTIMALITY ANALYSIS N1 = N M1 = M C C GET PARAMEIERS K1 TO K6 100 WRITE {(6,6) READ (5, FREE) K1, K2, K3, K4, K5, K6 IF (K1.LT.C.OB.K2.LT.0.OH.K3.LT-O.OR.K4LT.O 0.OR.K5.LT.0.OR.K6. 6 LL.O) GO TO 999 53

WRITE (7,7) K1, K2, K3, K4, K5, K6 IF ( K1+ K2+ K3+ K4+ K5+ K6.EQ. 0 ) STOP C C GENERATE K1 CHANGES OF EDGE COSTS IF (K1.EC.C) GC TO 200 DO 120 K = 1, K1 110 EDGE = 151 + RAND(IX) *M IF (.NOT.SAVE(EDGE)) GO TO 110 IF (.NOT.SAVE (EAD1(EDGE))) GO TO 110 IF (.NOT.SAVE {(EAD2 (EDGE))) GO TO 110 CST = BAND(IX) * DELIA + MINCST 120 WRITE (7,8) EDGE, CST C C GENERATE K2 CHANGES OF NODE SUBSETS 200 IF (K2.EQ.0) GO TO 300 DO 220 K = 1, K2 210 NODE = 1 + RAND IX) * N IF (.NOI.SAVE(NODE)) GO TO 210 SET (NCDE) = RANDIX) * NSETS + 1 IF (SIT(NODE).GT.3) SET(NODE) 0 220 WRITE (7,5) NODE, SET(NODE) C C GENRATE K3 EEGE DELETIONS 300 IF (K3.EQ.0) GO TO 400 IF (K3.GT.M1) GO TO 999 DO 320 K = 1, K3 310 EDGE = 151 + RAND(.IX)* M IF (.FOT.SAVE(EDGE)) GO TO 310 IF (.NCT.SAVE(EEAD1(EDGE))) GO TO 310 IF (.NOT.SAVE (HEAD2(EDGE))) GO TO 310 SAVE (EDGE) =.FALSE. 320 WRITE (7,5) EDGE M1 = M1 - F3 C C GENERATE K4 NODE DELETIONS 400 IF (K4. E.C) GO TO 500 IF (K4.GT.H1) GO TO 999 DO 420 K = 1, K4 410 NODE = 1 + RANE(IX) * N IF (.IOT.SAVE (NODE)) GO TO 410 SAVE (NODE) =.FALSE. 420 WRITE (7,5) NODE N 1 N1 - 4 C C GENERATE K5 NEW NODE INTETDUCTIONS 500 IF (K5.EC.0) GO TO 600 IF (N+KS.G1.1C0) GO TO 999 DO 510 K = 1, K5 N N + 1 NODE = N SAVE(ECGDE) -. TUE. SET(NCDE) = RAND(IX) * NSETS + 1 IF (SET (NODE).GT.3) SET(NODE) = 0 510 WRITE 17,5) NODE, SET (NODE) C C GENERATE KE NEW EDGE INTRODUCTIONS 600 IF (K6. E.C) GO TO 100 IF (M+K6.GT.3000) GC TO 999 DO 630 K = 1, K6 M = -+ 1 54

EDGE = M + 151 SAVE (EDGE) =.TRUE. 610 NODE 1 = 1 + RAND (IX) * N IF (.NOI. SAVE(NODE1)) GO TO 610 620 NODE2 = 1 + RAND (IX) * N IF (.NCT.SAVE(NODE2)) GO TO 620 IF (NCDE1.EQ.NCDE2) GO TO 620 HEAr1 (EDGE) = NODE1 HEAE2 (EEGE) = NODE2 CST = HAND(IX) * DELTA + MINCST 630 WRITE 17,5) EDGE, NODE1, NODE2, CST C C EETURN FOF A NEW POST-OPIIMALITY ITERATION GO TO 100 C C ERROR 999 WRITE (6, c9) STOP C C FORMATS 1 FORMAT(' ENTER TITLE') 2 FORMAT (48H 123456789012345678901234567890123456789012345678 ) 3 FORMAT(' EFTER N,., #SEIS, MINCST, MAXCST, IX') 4 FORMAT(2I,' 1') 5 FORNAT(3IS5,F10.4) 6 FORMAT(' ENTEF K1, K2, K3, K4, K5, K6') 7 FORMAT(6I5) 8 FORMAT(I5,F10.4) 99 FORMAT(' *** -EROR *****) END C C GENERATE FANDCM NUMEERS FUNCTION RAND (IX) IX = IX * 5539 IF (IX.LT.C) IX = IX + 2147483647 + 1 RAND = IX *.4656613E-9 RET UP N END 55

IMPLICIT INTEGER (A-Z) REAL VALUE,DELTA,MCOST,TOLER,I NF PRICE,MPRICE LOGICAL TRACE, PRINT COMMON /NODES/ SET (100),LABLO(150),PSEUDO(150),APEX(150),PRED & 150),TREE (150),MPRICE (150),BCI ( 150). COMMON /EDGES/ HEAD (6150),PRICE (3150),LIST (3150),INDEX (3150) COMMON /LISTS/ NSCAN(101) INSP (3100),NORIG(100),LINK(1500),MAT 6 E(1500) COMMON /PNTRS/ HSCAN TSCANlHINSPHORIGHINK COMMON /PARMS/ NN,NN2, N9, I LOL0 L1 2, MMO 1, M.2,9, POP2 COMMON /VARBS/ VALUE,DELTA,MCOSTOPTION,TRACE, PRINT COMMON /STATS/ ROOT$,NODE$,EDGE$,SHRK$,UNSH$,AUGl.$,DUAL$,RMAT$.E, LABL$, LINK$, TIME1,TIME2 TIME3 COMMON /CONTS/ TOLER,INF,OUTER,INNERUNLABD, ST0, SET1, SET2,SET & 3, NULL COMMON /PRNTS/ STACK(3000),lRCK (100) C C... ~ w. I *. * o. J.. ~ g e e ~ ~., o * ~ * * C C C C MINIMUM COST 1-MATCHING/COVERING PROBLEM C THE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PERIN C AUGUST 1980 C C C C -W. --- - ------— *'m-swam _- __ — _ _ C C THIS PROGRAM COMPnTES A MINIMUM COST 1-MATCHING/COVERING FOR A C NETWORK WITH C C N NODE S AN D M EDGES C WHERE EVERY EDGE HAS AN ASSOCIATED EDGE COST AND C N<, N=, N>, NO IS A GIVEN PARTIT.ION OF THE SET OF NODES: C C N< - SUBSET OF MATCHED NODES (CODE = 2) C N= - SUBSET OF PERFECT MATCHED NODES. (CODE = 1) C N> - SUBSET OF COVEREC NODFS (CODE =3) C NO - SUBSET OF UNRESTRICTED NODES, (COF = 4) C C THIS PROGRAM ALLOWS FOP POST-OPTIMALITY.. ANALYSIS. IT IS C POSSIBLE TO HAVE A SEQUENCE OF POST-OPTIMALITY ITERATIONS. C EACH ITERATION IS SUBDIVIDED INTO THE FOLLOWING PIASES: C C A) EDGE COST CHANGE, C B) NODE SUBSET CHANGE, C C) EDGE ELIMINATION, C D) NODE ELIMINATICN, C E) NEW NODE INTRODUCTION, C F) NEW EDGE INTRODUCTION. C C LET K1, K2, K3, K4, K5, K6 DESIGNATE THE NUMBER OF NODE/EDGES C TO BE WORKED OUT AT EACH OF THE ABOVE PHASES.. C C C PROGRAM INPUT (FORTRAN FREE-FORMAT): 56

c C 1) TITLE (MAX. 48 CHARACTERS) C 2) N, M, OPTION (#NODES, EDCBS,PROGRAM OPTION) C C 3) NODE,SUBSET <N TIMES> (NODE DATA) C 4) EDGE,NODE1,NODE2,COST <M.TIMES> (EDGE DATA) C C 5) K1, K2, K3, K4, K5, K6 C 6) EDGE, NEWCOST <K1 TIMES> (EDGE COST CHANGE) C 7) NODE, NEWSUBSET <K2 TIMES> (NODE SUBSET CHANGE) C 8) EDGE.<<3 TIMES> (EDGE ELIMINATION) C 9) NODE <K4 TIMES> (NODE ELIMINATION) C 10) NEWNODE, SUBSET <K5 TIMES> (NODE INTRODUCTION) C 11) NEREDGE,NODE1,NODE2,COST <K6 TIHES> (EDGE.INTRODUCTION) C C 12) 0 0 0 0 0 0 (TERMINATION) C C C OBS.: 3) TO 4) DEFINE THE NETWORK; C C 5) TO 11) DEFINE A POST-OPTIMALITY ITERATION, C THEY ARE REPEATED FOR EACH ITERATION; C C PROGRAM EXECUTION: C $RUN MATCOV SCARDS=XXX SPRINT=YYY T=ZZZ C C C EXAMPLE: C C $R MATCOV T=1 C 1) EXAMPLE C 2) 4 5 3 C C 3) 10 2 C 20 1 C 40 0 C 30 1 C 4) 240 20 40 -2.0 C 220 30 40 -4 0 C 200. 20 10 20..0 C 210 20 30 -50.0 C 230 10 30 2. 57 C 5) 0 1 1 1 2 C 6) 230 3.0 C 7) C 8) 220 C 9) 40 C 10) 60 3 C 11) 290 10 60 -10.0 C 190 60 30 +10.0 C C C C EXAMPLE DESCRIPTION: C C 1) TITLE= "EXAMPLE" C 2) N= 4 NODES, M= 5 EDGES, OPTION= 3, C 57

C 3) NODES: C NODE 10 IS IN N< C NODE 20 IS IN N= C NODE 30 IS IN N= C NODE 40 IS IN NO C 4) EDGES: C EDGE 200 = (10;20) WITH COST 20.0 C EDGE 210 = (20;30) WITH COST -50s0 C EDGE 220 = (30;40) WITH COST -4.0 C EDGE 230 = (10;30) WITH COST 2. 57 C EDGE 240 = (20;40) WITH COST -2.0 C C 5) K1= 1 EDGE COST CHANGES, C K2= 0 SUBSET CHANGES C K3= 1 EDGE ELIMINATION C K4= 1 NODE ELIMINATION C K5= 1 NODE INTRODUCTION C K6= 2 EDGE INTRODUCTION C 6) CHANGE COST OF EDGE 230 TO 3.0 C 7) DO NOT CHANGE ANY NODE SUBSET C 8) ELIMINATE EDGE 220 C 9) ELIMINATE NODE 40 C 10) INTRODUCE NODE 60 IN N> C 1.1) INTRODUCE EDGES 290 = (10;60) WITH COST -10.0 C 190 = (30;60) WITH COST -10.0 C C 12) TERMINATE C C AFTER 5) TO 11) THE NEW NETWORK IS: C NODES: NODE 10 IN N< C NODE 20 IN N= C NODE 30 IN N= C NODE 60 IN N> C C C EDGES: EDGE 190 = (30;60) WITH COST 10.0 C EDGE 200 = (10;20) WITH COST 20.0 C EDGE 210 = (20;30) WITH COST -50~0 C EDGE 230 = (10;30) WITH COST 2.57 C EDGE 290 = (10;60) WITH COST -10.0 C C OBS.: EDGE 240 = (20;40) WAS AUTOMATICALLY ELIMINATED FROM C THE NETWORK AT THE TIME NODE 40 WAS ELIMINATED C BECAUSE IT BECAME INCIDENT WITH. A. NONEXISTING NODE. C C C PROGRAM OPTIONS: C C OPTION = 1 - PRINTS STATISTICS ONLY C C OPTION = 2 - PRINTS INPUT AND SOLUTION (SHORT OT!TPUT) C C OPTION = 3 - PRINTS INPUT, HISTORY, AND SOLUTION (LONG OUTPUT) C C OPTION > 3 - DUMPS NODE INFORMATION AT SPECIFIC POINTS C (DEBUG PURPOSES) C OPTION =-R - TRACES WHILE THERE AE R R ROTS (DEBUG PURPOSES) C C 58

CALL GETNET 10 CALL GRWFOR CALL PUTSOL CALL POSTOP GO TO 10 C END BLOCKDATA C C MINIMUM COST 1-MATCHING/COVERIWN PROBLEM C THE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PERIN C AUGUST 1980 C C /BLOCK DATA/ C C DATA STRUCTURE DESCRIPTION C C N = #NODES M = #EDGES L = MAX #PSEUDOS C C LIST (IND) - NODE/EDGE, NODE/EDGE EXISTS C LIST (IND) = NULL NODE/EDGE DOES NOT. EXIST C C LIST( INDEX(NODE/EDGE) ) = NODE/EDGE IFF NODE/EDGE EXISTS C C EXISTING NODES: FROM LIST (NO) TO LIST(N" ) C EXISTING PSEUDOS: FROM LIST ( LO) TO LIST (L ) C EXISTING EDGES: FROM LIST(M0) TO LIST(M1) C C MAX NODE = N2 >= N1 C MAX PSEUDO = L2 >= L1 C MAX EDGE = M2 >= Ml C C VALUE = DUAL OBJECTIVE VALUE C ROOT$ = - EXPOSED NODES C C SET(NODE) = 0, 1, 2, 3 (NO, N=, N<, N>,.ESPECT.IVSLY) C LABLO(NODE) = OUTER, INNER, UNLABD FOR CURRENT NODES C LABLO(NODE) = SIMPLE BLOSSOM FOR NONCURRENT NODES C C PSEUDO(NODE) - CURRENT NODE CONTAINING NODE (OR NODE) C C APEX(NODE) - ORIGINAL NODE INSIDE NODE (OR,NODE) C C PRED(NODE) - PREDECESSOR ARC IN ALTERNATING PATH TO ROOT C TREE - LISTS OF NODES IN A TREE (HEADS = EXPOSED NODES) C C BCI(NODE) - BLOSSOM CONSTRAINT IDENTIFIER. (OR NODE) C C MPRICE(NODE) - MAXIMUM PRICE OF BCI (NODE) C C HEAD(NODE) = ROOT OF TREE C HEAD(.RC) = NODE POINTED. BY THE ARC C C PRICE(NODE) = NODE DUAL VARIABLE C PRICE(EDGE) - EDGE COST C C NSCAN - CIRCULAR LIST OF UNSCANNED NODES 59

c C INSP - LIST OF NODE/EDGES TO BE INSPECTED C C NORIG - LIST OF NODES IN A SIMPLE BLOSSOM (SEE ORIG) C C LINK/MATE - LISTS OP EQUALITY/MATE EDGES C HEADS FOR CURRENT EQUALITY EDGES = LINK(NODE) C HEADS FOR NONCURRENT EQUALITY EDGES = LTNK(PNODE) C HEADS FOR MATE EDGES.= -MATF(NODE) C LINK(PT) = NEXT ELEMENT IN THE. LIST C MATE (PT) = EDGE C PT <= HINK <= P2 = MAX ELEMENT C IMPLICIT INTEGER (A-Z) REAL VALUEDELTAMCOSTTOLERINFPRICE,MPRICE LOGICAL TRACEPRINT COMMON /NODES/ SET(100),LABL (150),PSEUDO(150),AP'E X(150),PPED ( & 150),TREE (150),MPRICE (150),BCI (150) COMMON /EDGES/ HEAD(6150), PRICE (31 50)., LIST (3150),INDEX (3150) COMMON /LISTS/ NSC'N (101),INSP (3100),NORIG (1Q00},LINK ( 500),MAT.~ E O(1500) COMMON /PNTRS/ HSCAN,TSCANHINSPHORIG,HINK COMMON /PARMS/ N,N0,N1,N2,N9, L,LO,L.1 2,M, 0M,Ml,M2,M9,P0,P2 COMMON /VARBS/ VALUE,DELTA,MCOST,OPTION,TRACEPRINT. COMMON /STATS/ ROOT$,NODE$,EDGE$,SHRK$,UNSH $,AUGM$,DUAI$, M.ATt &, LABL$,LINK$.,TIME1,TIME2,TIME3 COMMON /CONTS/ TOLERINFOUTERINNERUNLABDSETSET 1, SET2, SET G 3,WIJ3NULL COMMON /PRNTS/ STACK (3000),PACK.(100) C C C NODE VECTORS DATA SET/1 00*0/, LABLO/1 50*0/,PSETUDO/150*0/, APEX/1 50,*0/, PR D/1 5 &= Ql0*0/,TREE/1 50*0/, MPRICE/150*. /, BCI/150*0/ c C NODE/EDGE VECTORS DATA IEAD/61 500/, PR TC E/3 150* 0,0/ C C LIST OF EXISTING NODE/EDGES DATA LIST/3150*0/,INDEX/31 50*0/. C C LINK/MATE VECTORS DATA LINK/1000*0/, MATE/1000*0/ C C HEAD/TAILS POINTERS DATA HSCANTSCAN,HINSP,HORIG,HINK/5*0/ C C CONTROL VARIABLES DATA VALUE,DELTA,MCOSTTRACE,PBINT/3*0.O0,2*. FALSE. / C C STATISTICAL VAR IAT.BLES DATA ROOT, NODE$, DGE$,SHRK$,tNSH$,AUGM$, ALtBMAT$,fABL.ABLTN & K$/10*0/ C C CONSTANTS DATA IPF,TOLER OUT ER NR,UNLAD S ET SET 1, S ET2ET3,N LL/9 9 9 & 9.9, 1. E-50,.,-1, 0,0, 1,2, 3,C/ C PROBLEM PARAMETERS 60

DATA N2, L2, M2, P2 / 100, 150u 3150, 1500 / END 61

SrTBROrJTINE GETNET C - - - - - - - - - - _ -_ _ _ - _ -_ _ _ -_ _ _ _ C C MINIMUM COST 1-MATCHING/COVERING PROBLEM C THE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PERIN C AUGUST 1980 C C /GET NETWORK/ C READ NETWORK DATA C INITIALIZE VARIABLES C IMPLICIT INTEGER (A-Z) REAL VALJE, DELTA,MCOSTTOLER,INFPRICE,MPRICE LOGICAL TRACE, PRINT COMMON /NODES/ SET (100),LABLn 150),PSEUDO(150),APEX (150),PRED( & 150),TREE (150),.MPRICE (150),BCI (1 50) COMMON /EDGES/ HEAD (6150), PRICE (3150),LIST(3150),INDEX (3150) COMMON /LISTS/ NSCAN (101),INSP (3100),NORIG(100),LINK (1500),MAT & E(1500) COMMON /PNTRS/ HSCANTSCAN,HINSP,HORIGHINK COMMON /PARMS/ N,NO, N1,N2, N9,L,LO,L1,L2,M, M0,M1,M2,M9,POP2 COMMON /VARBS/ VALUEDELTA,MCOST,OPTION, TRACE,PRINT COMMON /STATS/ ROOT$,NODESEDGP$,S HRK$,UNSH$,AUGM$,DDUAL$, RMAT~ &,LABL$,LINK$,TIME1,TIME2,TIME3 COMMON /CONTS/ TOLER,INFOUTER,INNER,UNLABD, SET0 SET1, SET2,SET & 3,NULL COMMON /PRNTS/ STACK(3000),PACK(100) REAL MCOST,COST,TITLE (12) LOGICAL FREE(1) /'*'/ C C C READ PROBLEM PARAMETERS CALL TIME(0) READ (5, 1, ND=999) TITLE 1 FORMAT(12A4) READ(5,FREE,END=999) N, M, OPTION TRACE =.FALSE. PRINT =.FALSE. IF (OPTION.EQ.-N2) TRACE = *TRUE. I (0. GT IO. ANOPTIONANDPTION.GE..-N2) PRINT =.TRUE. IF (OPTION.EQ.3.OR.OPTION.EQ 4) PRINT.TFUE. WRITE(6, 2) 2 FORMAT(1H1 30X,'***** MINIMUM COST 1-MATCHING/COVERTNG PROBL & EM *****'//) WRITE(6, 3) TITLE 3 FORMAT(40X,12A4) IF ( N.Le.O.OR. M.LE.0 ) CALL ERRO (2) IF ( N.GT.N2 ) CALL EREOR (3) IV ( M.GT.M2-L2 ) CALL ERROOR(4) C C INITIALIZE PARAMETRIC VARIABLES NO N1 = N Nq = N + 1 L = N /2 LT.O N2 + 1 LI = N2 MO. 1,=2 + 1

M1 = L2 + M M9 = 2 * M2 + 1 PO = L2 + 1 C C INITIALIZE LINK/MATE STORAGE SPACE DO 10 PT = P0, P2 10 LINK (PT) - PT + 1 LINK(P2) = NULL HINK = MO C C READ NODE DATA C INITIALIZE NODE VECTORS DO 20 IND = NW, N1 READ(5, PREE,E ND=9 99) NODE, SET (NO DE) IF (TRACE.OR.OPTION.EQ.4) WRITE (6,4) NODE, SET(NODE) 4 FORMAT(' NODE DATA:',215) IF (NODE. LT. NO. OR. NODE. GT. N2. OR. INDEX (NODE). NE. NLL) CALL & ERROR (6) IF (SET (NODE).LT. O.ORSET (NODE).GT. 3) CALL ERROR(7) INDEX (NODE) = IND LIST (IND) = NODE PSEUDO (NODE) = NODE APEX(NODE) NODE LABLO(NODE) = UNLABD ST = SET (NO E) IF (ST.EQ.SET1.OR. ST.EQ SET2) PRICE(NODE) = -INF/2 VALUE = VALUE + PRICE(NODE) BCI (NODE) NODE IF (ST.EQ.SET1) BCI(NODE) =L2 IF (ST.EQ.SET1) XPRICE (NODE) = IN 20 CONTINUE MPRICE(t2) = INF H = 0 C C READ EDGE DATA C INITIALIZE EDGE VECTORS C LINK EQUALITY EDGES C MATCH EDGES IN ADO 40 IND = M0, Ml READ(5,FREE,END=999) EDGE, NODE1, NODE2, COST IF (TRACE.OR.OPTION.EQ. 4).WITE(6,5). EDGE,..NODE1, NODE2, 6 COST 5 FORMAT (' EtGE DATA:'315, F7 1) EDGE1 = EDGE + L2 IF (EDGE1.LT. MO.OR.EDGE1. GT. M2.OR.INDEX (EDG1). NE. NULL) C ~ ALL ERROR(7). IF (NODE1.LT.NO OR.NODE 1.GT. N2. OR.INDEX(NODE ). EQ NULL) C & ALL ERROR (6.) IF (NODE2. T. NO. OR.NO E2. GT. 2 12. OR. INDEX (NODE 2). FEQ. NULL) C & ALL ERROR(6) IF (COST.GT.INF.OR.COST.LT.-INF) C E ALL ERROR (9) EDGE2 = M9 - EDGE1 HEAD(EDGE 1) = NODE2 HEAD(EDGE2) = NODE1 PRICE (EDGE1) = COST INDEX(EDGE1) = IND LIST (IND) = EDGE1 COST = PRICE EDGE1) - PRICE (NODE1) - PRICE(NODE2) IF (COST.GT.+TOLER) GO TO 40 63

IF (COST.LT.-TOLER) GO TO 30 C "EDGE1" IS AN EQUALITY EDGE IF (HINK.EQ NULL) CALL ERROR(5) PT = HINK HINK = LINK (HINK) MATE (PT) = EDGE 1 LINK(PT) = LINK(NODEI) LINK (NODE1) = PT IF (HINK.EQ. NULL) CALL ERROR (5) IF (HINK.GT.LINK$) LINK$ = HINK PT = HINK HINK = LINK (HINK) MATE (PT) E= DGE2 LINK (PT) = LINK(NODE2) LINK (NODE2) = PT GO TO 40 C "EDGE1" IS AN EGE OF A30 CALL MATCH(EDGE1) VALUE = VALUE + PRICE(EDGEI) H =H + 1 STACK (H) = EDGE1 40 CONTINUE IF (PRINT. AND. H. GT. 1) WRITE(6,6) (STACK (I), HEAD (STACK (I)),EAD ( & M9-STACK (I)),PRICE(STACK.(I)),I=1,H) 6 FORMAT(//' EDGES OF A- (EDGE,NODE1,NODE2, COST): /5(I12,2T3,F6 &.1)) C C INITIALIZE PSEUDONODE LIST DO 50 IND = LU, L2 50 LIST(IND) = IND C C PLANT ALTERNATING FOREST DO 60 IND = NO, N1 NODE = LIST {IN)) IF (SET (NODE) EQ. SETO.OR. MATE (NODE).NE.N nLL) GO TO 60 LABLO (NODE) = OTTTER HEAD (NODE) = NODE HSCAN = HSCAN + 1 NSCAN(HSCAN) = NODE ROOT$ = ROOT$. 1 60 CONTINUE LABL$ = ROOT$ IF (PRINT) WRITE(6,7) ROOT$ 7 FORMAT(//' ALTERNATING FOREST PLANTED WITH',14,' ROOTS') C IF (OPTION.EQ.7) CALL DUMP CALL TIME(1,0,TIME1) IF [OPTION. NE.-ROOT$) RETURN TRACE =.TRUE. CALL DUMP RETURN C C UNEXPECTED END-OF-FILE 999 CALL ERROR (1) STOP END 64

SU7BROUTINE MINIM (NODE, NDETA) C C MINIMUM COST 1-MATCHING/COVERING PROBLEM C THE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PERIN C AUGUST 1980 C C /COMPUTE MINIMUM DELTA/ C COMPARE DELTA AND NEWDELTA AND CONTROL INSPECTION LIST C IMPLICIT INTEGER (A-Z) RBAL VALUEDELTA,MCOST,TOLER,I NF PRICE MPRICE LOGICAL TRACE, PRINT COMMON /NODES/ SET (100),LABLO(150),PSEUO (150),APX (150),PRED( & 150),TREE (150), MPRICE (150), BCI (1 50) COMMON /EDGES/ HEAD(6150):,PRICE(3150),LIST.(3150),ITNDEX (3150) COMMON /LISTS/ NSCAN (101),INSP (3100),NORIG (100):,LINK ( 500),MAT & E(1500) COMMON /PNTRS/ HSCAN,TSCAN,HINSP,HORIG,HINK COMMON /PARMS/ N, N0,N1 NN2,N9,L,.LOL1,L2, M, MD,M.l,.2, M9, PO,P2 COMMON /VARBS/ VALUE,DELTAMCOSTOPTION,.TRACE,PRINT COMMON /STATS/ ROOT$,NODES,EDGE$,SHRK$,UNSH$,SAU GM$, DTAL$, RMAT$ & LABL$, LINK$, TIM E1, TIM E2.,.TIME3 COMMON /CONTS/ TOL ER,INF,OUTE INNEINER,NLABD, SETO, SET1, SET2,S ET & 3,NULL COMMON /PRNTS/ STACK (3000),PACK.(100) R AL NDELTA C C C IF (TRACE) WRITE(6,1) NODE, NDELTA C 1 FORMAT(' #TRACE# MINIM (',I4,,' F6. 1.)..) C NIWDELTA > DELTA -- RETURN C NEWDELTA = DELTA - SAVE NODE/EDGE FOR INSPECTION C NEWDELTA < DELTA -- ERASE LIST, SAVE NODE/EDGF FOR INSPECTION IP (NDELTA.GT.DELTA+TOLER) RETUWR IF (NDELTA.GE.DELTA-TOLER) GO TO 10 HINSP = 0 DELTA = NDELTA 10 HINSP = HINSP + 1 INSP(HINSP) = NODE RETUR N END 65

SUBROUTINE MATCH (EDGE1) C.C C MINIMUM COST 1-MATCHING/COVERING PROBLEM C THE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PERIN C AUGUST 1980 C C /MATCH NODES JOINED BY "BDGE1"/ C FOR BOTH NODES DO: C IF "MATE(NCDE) = NULL" -- "MATE(NODE) = EDGE!" C IF "NODE(NODE) > NULL" - "-MATE(NODE)" BECOMES A HEAD C IF "NODE (NODE) < NULL" -- INTRODUCE "EDGE1" IN LIST C IMPLICIT INTEGER (A-Z) REAL VALUJE,DELTA, MCOSTTOLE'^IN FPPRICEMPRICE LOGICAL TRACE,PRINT COMMON /NODES/ SET (100),LABLO(150),PSEUDO (150),APEX (150),PRED( & 150),TREE ( 150), MPRICE (150), BCI (150) COMMON /EDGES/ HEAD(6150),PRICE(3150),LIST(3150)-.INDEX(3150) COMMON /LISTS/ NSCAN (101).INSP(3100),NORIG(100),LINK(1500),MAT s E(1500) COMMON /PNTRS/ HSCAN,TSCANHINSP,HORIGHINK COMMON /PARMS/ N,NON1 N2,N9,LLO,1,L2,, M, MO0,M1,M2,M9,POP2 COMMON /VARBS/ VALUE,DELTA,MCOST,OPTION,TRACE, PRINT COMMON /STATS/ ROOT$,NODE$,EDGE$,SHRK$,UNSH$, AUGMS, DTIAL$,PMAT$ &,LABL$,LINK$ T,IME1,TIME2TIME3 COMMON /CONTS/ TOIER,INF,OUTEKR,INNER,UNLABD, SETQSET1, SET'T,SET s 3,NULL COMMON /PRNTS/ STACK(3000),PACK(100) C C IF (TRACE) WRITE(6,1) EDGE1 1 FtRMAT(' TRACE# MATCH (',I4,')') C C DO 10 TO 40 FOR BOTH NODES JOINED BY "EDGE1" EDGE = EDGE1 10 NODE = HEAD(M9-EDGE) IF (MATE (NODE).NE. NULL) GO TO 20 C NO MATES MATE(NODE) = EDGE GO TO 40 20 IF (MATE (NODE).T.NULL) GO TO 30 C ONE MATE -- "-MATE(NODE)". BECOMES A LIST HEAD IF (HINK.EQ.NULL) CALL ERROR (5) PT = HINK HINK = LINK(HINK) MATE(PT) = MATE(NODE) LTNK(PT) = NULL MATE(NODE) = -PT C INTROlDUCE "EDGE" IN THE MATE LIST WITH. HEA). "-lMATv(NODE)" 30 IF (HINK.Q. NULL) CALL ERROR(5) IF (HINK.GT.LINK$) LINK$ = HINK PT = HINK HINK = LINK (HINK) MATE (PT) = EDGE LINK (PT) = -MATE (NODE) MATE(NODE) = -PT 66

C GGET SECOND NODE OR RETURN 40 IF (EDGE.NE.EDGE1) RETURN EDGE = 19 -EDGE1 GO TO 10 C END 67

SUBROUTINE NMATCH(EDGE1) C C MINIMUM COST 1-MATCHING/COVERING PROBLEM C THE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PERIN C AUGUST 1980 C C /UNMATCH NODES JOINED BY "EDGE1"/ C FOR BOTH NODES DO: C IF EDGE IS NOT A MATE, RETURN C IF EDGE IS THE ONLY MATE, MAKE "MATE(NODE)' NULL C IF EDGE IS ONE OF THE MATES, REMOVE IT FROM THE LIST WITH C HEAD "-MATE(NODE)", AND IF SUCH A LIST CONTAINS NOW C JUST ONE EDGE, TRANSFORM "MATE(NODE) " INTO A POINTER C IMPLICIT INTEGER (A-Z) REAL VALUE,DELTA,MCOST,TOLERINPPRICEMPRICE LOGICAL TRACE,PRINT COMMON /NODES/ SET (100),LABLO (150),PSEUDO(150),APX (150),PPED( & 150), TREE (150),MPRICE (150) BCI (1 50) COMMON /EDGES/ HEAD(6150),PRICE(3150)-, LI ST (31 50), IN DE (3 150) COMMON /LISTS/ NSCAN (1 01), INSP (3100),NORIG (100),LINK (1 500), MAT F E 1500) COMMON /PNTRS/ HSCANTSCAN,HINSPHORIG HI NK COMMON /PARMS/ N,N0,N2N1,N2, N9,LL0,L1,L2,,l0, M 1,M2, M9,POP2 COMMON /VARBS/ VALUE,DELTA,MCOSTOPTION,TRACE, PRINT COMMON /STATS/ ROOT$,NODE$,EDGE$,SHRK$,UNSH$,AUGM$,O DUAL$, RMATS E;6 1 IBLLABL$,LINK$,TIME1,TIME2,,.TIIE3 COMMON /CONTS/ TOLERINF,OUTER,INNERUNLABDS.ETOSET 1,SET2,SET & 3,NUILL COMMON /PPNTS/ STACK(3000),PACK(100) C C. a..... 4 8 o S.... *0 8' * 4. * 8 4 * * ~..0 C IF (TRACE) WRITE(6,1) EDGE I FORMAT(' #TRACE# NMATCH (',I4,')') IF. (EDGE1.EQ.NULL) RETURN C C DO 10 TO 50 FOR BOTH NODES JOINED BY "EDGE1" E)GE = EDGE1 10 NODE = HEAD(M9-EDGE) PT = MATE (NODE) IF (PT.LT NULL) GO TO 20 C "MATE(NODE)"IS A POINTER C "MATE (NODE)" POINTS TO EDGE -- POINT IT TO NULL IF (PT.EQ.EDGE) MATE (NODE) = NULL GO TO 50 C C "-MATE (NODE)" IS A LIST HEAD 20 PT = -PT IF (MATE (PT).NE.EDGE) GO TO 30 C "EDGE" IS THE FIRST ELEMENT LIST MATE (NODE) = -LINK (PT) GO TO 40 C "EDGE" IS NOT THE FIRST ELEMEENT LIST 30 PT 1 = PT PT = LINK(PT1) C ",DGF" IS NOT IN THE LIST -- DONE IF (PT.EQ.NUL.) GO TO 50 68

IF (MATE(PT).NE.EDGE) GO TO 30 C "EDGE" IS IN THE LIST LINK(PT1) = LINK(PT) 40 MATE(PT) = NULL LINK(PT) = HINK HINK = PT C C GET SECOND NODE OR RETURN 50 IF (EDGE.NE.EDGE1) RETURN EDGE = M9 - EDGE GO TO 10 C END 69

SUBROUTINE RMATCH (NODE) C c C MINIMUMI COST 1-MATCHING/COVERING PROBLEM C THE UNIVERSITY OF MICHIGAN. C WRITTEN BY CLOVIS PERIN C AUGUST 1980 C C /REMATCH ALTERNATING PATH/ C "PSEUDO(NODE)" IS AN OUTER NODE C REMATCH ITS ALTERNATING PATH C ERASE ITS ALTERNATING TREE C IMPLICIT INTEGER (A-Z) REAL VALUEDELTA,MCOSTTOLERIN, PRICE MPRICF LOGICAL TRACE,PRINT COMMON /NODES/ SET(100),LABLO(150),PSEUDO(150),APEX(150).,PRFD( & 150),TREE (150),MPRICE(15Q),BC.I (150) COMMON /EDGES/ HEAD(6150).,PRICE (31 50),LIST(3150).,INDEX(3150) COMMON /LISTS/ NSCAN (101),INSP (3100),NQR.IG (100 ) LINK ( 500), MAT E (1500) COMMON /PNTRS/ HSCANTSCANHINSPHORIGHINK COMMON /PARMS/ N,NON1,t N2, 9,L.LOL1,L2,M,0 M1.,M2,.M9,PO0,P2 COMMON /VARBS/ VALUEDELTAMCOSTOPTIONTRACE, PRINT COMMON /STATS/ ROOT$,NODES,EDGE$,SHRK$,UNSH$,AUGM$,DUAL, RMAT$ &,LABL$,LINK$,TIME1,TIME2 TIME3 COMMON /CONTS/ TOLER,INF,OUTERINNER,UNLABD,SrTO, SET.1,SET2, SET & 3,NULL COMMON /PRNTS/ STACK(3000),PACKC(10). C C IF (TRACE) WRITE(6,1) NODF 1 FORMAT(' #TRACE# RMATCH [',I4,)') AUGM$ = AUGM$ + 1 RMAT$ = RMAT$ + 1 C C IUPDATE "NODE" VECTORS PNODE = PSEUDO(NODE) IF (NODE NE. PNODE) CALL STAPEX (NODE) K =1 STACK(K) = PNODE C C DO 10 FOR ALL CUTER NODES IN THE PATH PNODE1 = PNODE 10 EDGE1 = PRED(PNODE1) C "PRED(NODE1) = NULL" -- "PNODE1" IS A ROOT IF (EDGE1.EQ. NULL) GO TO 100 C "PNODE2" IS INNER LABELLED C "PNODE2" IS OUTER LABELLED C TUPDATE "NODEI" AND "NODE2" VECTORS RMAT$ = RMAT$ + 2 DGE2 = M9 - EDGE 1 NODE1 = HEAt C(DGE1) NODE2 H= EAD(EDGE2) PNODE1 = PSEUDO(NODEI) PNODE2 = PSEUDO (NODE2) K = K + 4 STACK (K-3) = PNODE1 STACK (K-2) = MATE(NODEI) 7n

STACK(K-1) = PNODE2 STACK (K) = EDGE1 MATE(NODE1) = EDGE2 MATE(NODE2) = EDG1E IT (NODE1. E. PNODEI) CALL STAPEX( {ODE.1) IF (NODE2. NE.PNODE2). CALL STAPEX( ODE2). GO TO 10 C C ERASE THE ALTERNATING TREE C DO 110 FOR EVERY NODE IN THE TREE 100 ROOTS = ROOTS - 1 J = 0 NODE2 = HEAD(PNODE) 110 -NODE1 = NODE2 IF ( NODE1.EQ. NULL ) GO TO 120 C SAVE "NODE2" C UPDATE "NODEl" VECTORS NODE2 TREE(NODE1) PNODE1 = PSEUDO {NODE1) TREE(NODE1) = NULL J = J +1 PACK (J) = NODE1 IF ( PNODE1.NE. NODE1 ) GO. TO 110 C "NODE1" IS A CURRENT NODE, LABEL = LABLC (ODE1) LABLO (MODE1) = UNLABD HEAD (NODE1) = NULL PRED(NODE1) N= ULL IF ( LABEL.NE.INNER ). GO TO 110 C "MODE1" IS INNER LABELLED C STACK IT FOR SCANNING LATER NSCAN(TSCAN) =- MODE1 TSCAN = TSCAM - 1 IT (TSCAN.LT.1) TSCAN = N9 GO TO 110 C C PRINT PATH AND TREE 120 IF. (PRINT) WRI TE(6,2) (STACK (I) I= 1., K) 2 FORMAT(' REHATCH ALTERM. PATH:',185/.(24X,18I5).) IF (PRINT) WRITE (6, 3) (PACK (I).,I=1,J). 3 FORMAT (# ERASE ALTERNAT. TREE:,1815/(24X,181.5)) IF (OPTION.EQQ10) WRITE.(6, 4) ROOT$ 4 FORMAT( t#PRE-TRACE# ALTIR3..ATtNG FOREST WITH',I4,.': ROOTS') IF (TRACE) GO TO 130 IF (OPTIOl.NE. — ROOT$) RETURNB TRAC =.TRUE. PRINT = *TRUE. RETURN 130. TRACE =.FALSE. PRINT =.TRUE. OPTION = 3 RETURN END 71

SUBROUTINE SHRINK (EDGE) C C MINIIMnM COST 1-MATCHING/COVERING PROBLEM C THE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PERIN C AUGUST 1980 C C /SHRINK SIMPLE BLOSSOM/ C "EDGE" JOINS TWO OUTER NODES IN THE SIMPLE BLOSSOM. C IMPLICIT INTEGER (A-Z) REAL VALUE,DELTA, MCOST,TOLER,INP,PRICE,MPRICE.LOGICAL TRACEIPRINT COMMON /NODES/ SET (100),LABLO 150),PSEUDO (150),APEX ('150), PRED( & 150),TREE (150',* PRICE(150),BCI(150) COMMON /EDGES/ HEAD (6150),PhfICE( 3150).,LIST (315.0)-,INDEX (3150) COMMON /LISTS/ NSCAN(101).,INSP (310.0),NQRIG (100),LINK(1 500), MAT & E 1500) COMMON /PNTRS/ HSCAN,TSCAN,HINSP,HORIGHINK COMMON /PARMS/ NNO,N,1N2,N9,L,L0,L1,L2 M, M.0, O1,M2,M9,POP2 COMMON /VARBS/ VALUE,DELTAMCOST,OPTION,TRACE, PRINT COMMON /STATS/ ROOTSNODE$,ED.GE$,SHBK$,UNSH$, AUGM$, DUAL$,RMAT$, LABL$,LINK$.,TIE1,TIME2,TIME3 COMMON /CONTS/ TOLER,INF,OUTER,INNER, UNLABD, SETO,SET1,SET2,SET & 3,NULL COMMON /PRNTS/ STACK(3000),PACK(100) REAL DD, DD1, DD2 C C IF (TRACE) WRITE(6,1) EDGE 1 FORMAT(' #TRACE# SHRINK (',I4,.')') SHRK$ = SHRK$ + 1 LABL$ = LABL$ + 1 C C GET FIRST ALTERNATING PATH H =1 PACK(H) =0 EDGE1 = EDGE 10 NODE1 = PSEUDO (HEAD(EDGE1)) H = H + 1 PACK(H) = NODE1 EDGE1 = PRED (NODE1) IF (EDGE1.NE. NULL) GO TO 10.. C C GET SECOND ALTERNATING PATH T = 50 PACK(T) =-1 EDGE2 = M9 EDGE 20 NODE2 = PSETnDO (HEAD (EDGE2)) T T- 1 PACK(T) = NODE2 EDGE2 = PRED (NODE2) IF (EDGE2. NE. NOLL) GO TO 20 C C ELIMINATE COMMON NODES IN THE PATHS 30 a - H - 1 T T 1 IF (PACK (H).EQ.PACK (T)) GO TO 30 79

c C CREATE "PNODE" L1 = L1 + 1 PNODE = LIST (L1) INDEX(PNODE) = L1 BASE = PACK(H+1) LABLO(PNODE) = OUTER PS EUDO (PNODE) = PNODE PRICE (PNODE) = 0 LINK (PNODE) = NULL HATE(PNODE) = BASE APEX(PNODE) = APEX(BASE) PR ED(PNODE) = PRED(BASE) ROOT = HEAD (BASE.) HEAD (PNODE) = ROOT TREE (PNO DE) = TREE (R OOT) TREE(ROOT) = PNODE C C UPDATE NODE VECTORS OF THE FIRST PATH PNODE1 = PACK(2) 40 IF (PNODE1.EQ. BASE) GO TO 50 EDGE1 = MATE (APEX (PNODE1)) PNODE2 = PSEUDO (HEAD (EDGE1) ) EDGE2 = PRED (PNOD.E 1) PRED(PNODE1) = EDGE1 HEAD(PNODEI) PNODE2 PNODE1 = PSEUDO(HEAD(EDGE2)) PRED(PNODE2) = EDGE2 HEAD (PNODE2) = PNODE1 GO TO 40 C C UPDATE NODE VECTORS OF THE SECOND PATH 50 PNODE1 = PACK (49) EDGE2 = PRED(PNODE1) PRED(PNODE1) = EDGE HEAD(PNODE1) = PACK(2) 60 IF (PNODE1.EQ.BASE) GO TO 70 EDGE1 = MATE(APEX (PNODE1)) PNODE2 = PSE DO(HEAD(EDGE1)) HEAD(PNODE2) = PNODE1 PRED (PNODE2) = M9 - EDGE1 PNODE1 = PSEUDO (HEAD (DGE2) ) HEAD(PNODE1) = PNODE2 EDGE1 = PRED (PNODE) PRED(PNODE1) = M9 - EDGE2 EDGE2 = EDGE1 GO TO 60 C C DETERMINE "BCI (PNODE)" 70.BCINOD = L2 DDl =INF J = 1 STACK (J) = PNODE CALL ORIG(PNODE) DO 80 H = 1, HORIG NODE = NORIG(H) LABLO(NODE) = PNODE J = J + 1 STACK ({J) = NODE BNODE = BCI (NODE) 73

IF (SET (BNODE).EQ.SET3 AND. BNODE. EQ. NODE) MPRICE(BNODE) & 2 * PRICE (BNODE) I)D1 = MPRICE(NODE) - PRICE (BNODE) I? (DD.GE.DD) GO TO 80 DD DD 1 BCINOD = BNODE 80 CONTINUE C C PRINT SIHPLE BLOSSOM BCI(PNODE) = BCINOD MPRICE(PNODE) = PRICE(BCINOD) IF (PRINT) WRITE (6,2) (STACK(I), I=1 J). 2 FORMAT ( SHRINK SIMPLE BLOSSOM',I6, WITH.NODES,1I3,' (BASE)', & 10I4/ (47X,10I4)) C SET PSEUDO OF ALL NODES INSIDE "PNODE" CALL STPSDO (PNODE) IF (DD.GT.0) RETURN C TYPE 3 AUGMENTATION MATE(BCINOD) = NULL IF (PRINT) WRITE(6,3) ROOT, PNODE 3 FORMAT(' TYPE 3 AUGMENTATION:',I6,'<R>...',3,'<+>') CALL RMATCH (BCINOD) RETUR N END 74

SUBROUTINE NSH NK (PNODE) C -. - - - - --- - - - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ C C MINIMUM COST 1-MATCHING/COVERING PROBLEM C THE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PERIN C AUGUST 1980 C C /UTNSHRINK "PNODE"/ C "PNODE" IS AN INNER LABELLED PSEUDONODE.WITH NULL NODE PRICE C "PNODE" "PNODEO" ARE MATED BY "EDGEO" C "BLSMO" AND "BASE" ARE THE EXTREME OF THE ALTERNATING PATH C TO BE CONSTRUCTED ON THE SIMPLE BLOSSOM OF "PNODE" C IMPLICIT INTEGER (A-Z) REAL VALUEDELTA,MCOST,TOLER,I NFPRICFMPRICE LOGICAL TRACE, PRINT COMMON /NODES/ SET (100),LABLO (150),PSEUDO (150),APEX (150), PRED ( & 150),TREE (150),MPRICE (150). BC.(1 50) COMMON /EDGES/ HEAD(6150),PRICE(3150),.LIST (3150),TNDEX (3150) COMMON /LISTS/ NSCAN (10 1),INSP.3100),NORIG (100), LINK.(500),MAT & E (1500) COMMON /PNTRS/ HSCAN,TSCAN,HINSP,HORIGH.INK COMMON /PARMS/ N,NON1,N2,N9,L,LOL1,L2,M, MO.M1,M2, M9, PO,P2 COMMON /VARBS/ VALUEDELTAMCOST,OPTION,TRACE,PRINT COMMON /STATS/ ROOT$,NODE$,EDGES,SHRK$.,UNSH$,AUGM$,DUAL$,RMAT$ & v LAB L$, LINK$, TIM E1,TIME2,T.IME3 COMMON /CONTS/ TOLER,INF,OUTER,INNER,UNLABD, SET, SET1,SET2,SET & 3, NULL COMMON /PRNTS/ STACK(3000), PACK (100) INTEGER LAB(3)/'<+>','<->','< >'/ LOGICAL DONT C C. l..... * e *. * 0 C IF (TRACE) WRITE(6,1) PNODE 1 FORMAT(' #TRACE# NSHRNK (',1.4,)' UNSH$ = UNSH$ + 1 C C ELIMINATE "PNODE" FROM TREE. NODE = HEAD (PNODE) 10 IF (TREE (NODE).EQ.PNODE) GO TO. 20 NODE = TRPE(NODE) GO TO 10 20 TREE(NODE) TREE(PNODE). TR EE (PNODE) = NULL C DETERMINE "BASE", "PNODEO", AND. "BLSM0" BASE = MATE (PODE) PNODEO = PSEUDO (HEAD (MATE (APEX (PNODE) ))) EDGEO = PRED(PNODEO) BLSMC = HEAD(M9-EDGEO) 30 IF (LABLO(BLSMO).EQ.PNODE).GO TO 40 BLSMO = LABLO(BLSMO) GO TO 30 C C DETERMINE NUMBER OF NODES BETWEEN "BASE" AND "BLSMO" 40 BI.SM = BASE PT = 1 50 IF (BLSM. EQ. BLSMO) GO TO 60 PT = PT + 1 75

EDGE1 = PRED(BLSM) BLSM1 - BLSM BLS M = HEAD (BLSM) GO TO 50 C EVEN NUMBER OF NODES -- RIGHT DIRECTION 60 IF (PT.EQ.PT/2*2.OR.PT.E. 1) GO TO 80. C ODD NUMBER -- REDIRECT THE SIMPLF BLOSSOM 70 EDGE2 = PRED(BLSM) BLSM2 = HEAD (BIS ) PRED(BLSM) = M9 - EDGEI HEAD(BLSM) = BLSM1 EDGE1 = EDGE2 BLSM 1 = BLSM BLSM = BLSM2 IF..(BISM NE.BLSO0) GO TO 7.0 C C UPDATE NODE VECTORS FOR NODJS IN THE ALTERPATING PATH PO nnGr =. EDGrC BLSM1 = BISMO ROOT = HEAD(PNODE) BLSM2 = TREE(ROOT) TREE (ROOT) = BASE J = 1 STACK (J) = BISM1 PACK (J) = 2 90 LABLO (BLSM1) = INNER LABL$ = LABL$ + 1 CALL STPSDO (BLSM ) TREE (BLSM1) - BLSM2 BLSM2 = HEAD(BLSM.) HEAD(BLSM1) = ROOT EDGE1 = PRED(BLSM 1) PRED(BLSM1) = NULL IF (BLSM1.*EQ.BASE) GO TO 100 LABLO(BLSM2) = OUTER LABL$ = LABL$ + 1 CALL STPSDO (BLSM2) EDGE2 = M9 - EDGE1 NODE1 = HEA (EDGE2) NODE2 = READ (EDGE1) MATE (NODE 1) = EDGE1 MATE(NODE2) = EDGE2 CALL STAPEX (NODE1) CALL STAPEX (NODE2) TREE (BLSM2) = BLSH1 BLSM1 = HEAD(BLSM2) HEAD(BLSM2) = ROOT EDGE2 = PRED(BLSM 2) PRED(BLSM2) = EDGE EDGE = M9 - EDG.: 2 HISCAN = HSCAN + 1 IF (HSCAN. GT.N9) HSCAN. = 1 NSCAN(HSCAN) = BLSM2 J = J +2 STACK(J-t) = BLSM2 STACK (J) = BLSM1 PACK(J-1) = 1 PACK (J) = 2 GO TO 90 76

C UPDATE NODE VECTORS FOR NODE NOT IN THE ALTERNATING PATH 100 PRED(PNODEO) = EDGE DONT =.FAlSE. ^0 Ir (BI.SM2.1'Q.BLSMIC) GO TO 120 BLS M1 = IH!A1) (BLSM2) LABLO(BLSM2) = UNLABD LABLO(BLSM1) = UNLABD CALL STPSDO(BLSM2) CALL STPSDO(BLSM1) EDGE1 = PRED(BLSM2) EDGE2 = M9.- EDGE1 NODE2 = HEAD R(DGE) NODE1 = HEAD (EDGE2) MATE (NODE2) = EDGE2 MATE(NODE 1) = EDGE1 CALL STAPEX(NODE1) CALL STAPEX (NODE2) PRED(BLSM2) = NULL PRED(BLSt1I) = NULL NSCAN(TSCAN) = -BISM2 TSCAN = TSCAN - 1 IF (TSCAN.LT.1) TSCAN = N9 NSCAN(TSCAN) = -BLSM1 TSCAN = TSCAN - 1 IF (TSCANLT.1) TSCAN = N9 J = J + 2 STACK(J-1) = BLSM2 PACK (J-) = 3 STACK (J) = BLSM1 PACK (J) 3 HEAD(BLSM2) = NULL BLSM2 = HEAD (BLSM1) HEAD(BLSM1) = NULL GO TO 110 C C UPDATE THE EDGE VECTORS FOR EDGES LINKED. TO PNODE 120 PT1 = LINK(PNODE) LINK PNODE) = NULL 130 PT = PT1 IF (PT.EQ.NULL) GO TO 150 PT1 = LINK(PT) EDGE = MATE(PT) IF (EDGE.EQ.NUJLL) GO TO 140 NODE = HEAD (EDGE) LINK(PT) = LINK(NODE) LINK(NODE) = PT GO TO 130 140 LINK(PT) = HINK HINK = PT GO TO 130 C C UPDATE PSEUDONODE LIST 150 NODE = LIST(L1) IND = INDEX(PNODE) LIST (L1) = PNODE LIST (INP) = NODE INDEX (NODE) = IND INDEX(PNODE) = NULL L1 = L1 - 1 IF (PRINT) WRITE (6,2) PNODE, (STACK (I),LAB (PACK (I) 77

2 FORMAT(' UNSHRINK PSEUDONODE:',14,' WITH NODES',10(I5,A3)/( & 339X, 10 (I5, A3)) ) RETURN END 78

SUBROUTINE STPSDO (PNODE) C C MINIMUM COST 1-MATCHING/COVERING PROBLEM C.THE UNIVERSITY OF MICHIGAN C WPITTEN BY CLOVIS PERIN C AUGUST 1980 C C /SET PSETUDO FCR NODES INSIDE "PNODE"/ C IMPLICIT INTEGER (A-Z) REAL VALUTE,DELTAMCOST, TOLER,INF,PRICE,MPRICE LOGICAL TRACE,PRINT COMMON /NODES/ SET (100),LABLO(150),PSEUDO (150),APEX (150),PRED( & 150), TRE (150),MPRICE (150), BCI 50) COMMON /EDGES/ HEAD (61 50), PRICE(31 50);,LIST (3150),INDEX (3150) COMMON /LISTS/ NSCAN (101),I NSP (3100),NORIG( 100),LINK(1500),MAT & E(1500) COMMON /PNTRS/ HSCAN,TSCANHINSP,HORIGHINK COMMON /PARMS/ N,NO,N1, 2, N9,L,LO,L1,L2, M, 0,M1,M2,HM9,PO,P2 COMMON /VARBS/ VALUE,DELTA MCOSTOPTIONTRACE PRINT COMMON /STATS/ ROOT$,NODE,EDGE$,SHRK$,UNSH$ AUGM$, DUAL$,RMATt &,LABL$,L.INK$,TIME1,TIME2,TIMB3 COMMON /CONTS/ TOLER,INF,CUTERINNER,UNLABD,SET0,SET1,SET2,SET & 3, NULL COMMON /PRNTS/ STACK (3000),PACK (100) C C0 0 0 0 0 a c IF (TRACE) WRIIE(6,1) PNODE 1 FORMAT(' #TRACE# STPSDO (',I4,')') PSEUDO (PNODE) = PNODE C "PNODE" IS AN ORIGINAL NOCE -- RETURN IF (PNODE.LE.N2) RETURN C C SET PSEUDO FOR ALL ORIGINAL NODES INSIDE "PNODE" CALL ORIG (PNODE) 10 IF (HORIG.EQ.0) RETURN NODE = NORIG (HORIG) HORIG = HORIG - 1 PSEUDO (NODE) = PNODE IF (NODE.GT.N2) CALL ORIG(NODE) GO TO 10 C E.ND 79

SUBROUTINE STAPEX (NODE) C C C C MINIMUM COST 1-MATCHING/COVERING PROBLEM C TIE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PERIN C AUGUST 1980 C C /SET "NODE" AS APEX/ C "NODE" IS AN ORIGINAL NODE C SET "NODE" AS APEX OF All PSEUDONODES C SET "BASE" AS BASE OF ALL PSETJDONODES C IMPLICIT INTEGER (A-Z) REAL VALUE,DELTA, MCOST,TOLER INFPRICE,MPRICE LOGICAL TRACEPRINT COMMON /NODES/ SET (100),LABLO(150),PSEUDO (150),APEX (150),PRED( 15)TEE150),EEMPCE(150),,BCI( 50) COMMON /EDGES/ HEAD (6150),PRICE(3150),LIST(3150),INDEX(3150) COMMON /LISTS/ NSCAN (101),INSP(3100),NORIG(100),LINK(1500), MAT E (1500) COMMON /PNTRS/ HSCAN,TSCAN,HINSP,HORIG,HINK COMMON /PARMS/ N,N0,N1,N2,N9,,L,0,L1,L2,, M0,M1,M2,M9, POP2 COMMON /VARBS/ VALUE,DELTA,MCOST,OPTION,TRACE,PRINT COMMON /STATS/ ROOT$,NODE$,EDGE$,SHRK$,UNSH$, AIGM$, DTUAL$,RMAT$ &,LABL$,.INK$,TIME1,TIME2,TIME3 COMMON /CONTS/ TOLERINF,OUTE RINNER, UNNABD, SET0SET1,SET?,SET S 3,NULL COMMON /PRNTS/ STACK (3000),PACK (100) C C IF (TRACE) WRITE(6,1) NODE 1 FORMAT (' TRACE# STAPEX (',I4,')') C C "NODE" IS CONSTANT FOR ALL. PSEUDOS C "BASE" IS VARIABLE C "BLSM" IS THE SIMPLE BLOSSOM WITH BASE "BASE" BASE = NODE 10 BLSM = LABLO(BASE) IF (BLSM. E.N2) RETURN MATE(BLSM) = BASE APEX (BTLSM) = NODE BASE = BLSM GO TO 10 END 80

ST BROUTINE SCAN (EDGE 1) c C C MINIMUM COST 1-MATCHING/COVERING PROBLEM C THE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PERIN C -AUGUST 1980 C C /SCAN EDGE/ C "EDGE" IS AN EQUALTIY EDGE C "NODE " < — "EDGE" — < "NODE2" C "NODE3" IS THE MATE OF "NODE2" C C CHECK AUGMENTATION C CHECK SHRINKING C CHECK NODE LABELLING C IMPLICIT INTEGER (A-Z) R AL VALUF,,DELTA,MCOSTTOLERI NFPRICEMPRICE LOGICAL TRACE,PRINT COMMON /NODES/ SET (100),LABLO(150), PSEUDO (150)- APEX(150),PRD( & 150),TRBE (150), PRICE(150), BCI(150) COMMON /EDGES/ HEAD(6150),PRICE(3150),LIST(3150),TINDEX (3150) COMMON /LISTS/ NSCAN (101).INSP(3100),NORIG(100)-,LINK (1500),MAT & E (1500) COMMON /PNTRS/ HSCAN TSCANHINSPH ORIGINK COMMON /PARMS/ N NO N1.N2.N9,.L.LO. L01,L2, M MOl.M2,M9.PO, P2 COMMON /VARBS/ VALUEDEITAMCOST,OPTIONTRACE, PRINT COMMON /STATS/ ROOT$,WNODE$, EDGE$,SHRK$, UNSH$,AUGM$, DUTAL$,RMATS &, LABL$, I.I NK$, TIM 1, TIME2,TIME3 COMMON /CONTS/ TOL ER,INF,OUTER,INNERu NLABD, SETOQ SET1,SET2 SET & 3,NULL COMMON /PRNTS/ STACK (3000).,PACK (100) REAL COST C C IF (TRACE) WRITE (6, 1) EDGE1 1 FORMAT(' ~TRACE# SCNEDG (',I4,')') EDGE$ EDGES + 1 C C DETERMINE "NODE1", "NODE2" EDGE2 = M9 - EDGE1 NODE2 = HEAD(EDGE1) NODE1 = HEAD(EDGE2) PNODE1 = PSEUDO(NODE1) PNODE2 = PSEUDO (NODE2) APEX1 = APEX(PNODE1) APEX2 = APEX (PNODE2) POOT1 = HEAD(PNODE1) ROOT2 = HEAD(PNODE2) LABEL1 = LABLO(PNODE1) LABEL2 = LABLO(PNODE2) C START CHECKS EDGE = EDGE1 - L2 IF (PRINT) WRITE(6,9) EDGE, NODE1, NODE2 9 FORMAT(' SCAN EDGE:',I5,' = ('.I?,';,I3,')) C NONCURRENT EDGE -- RETURN IF ( PNODE1.EQ. PNODE2 ) RETURN 81

IF ( LABEL2.EQ. UNLABD ) GO TO 20 C "NODEl", "NODE2" ARE BOTH OUTER NODES IF ( ROOT1.NE. ROOT2 ) GO TO 10 C "NODE1", "NODE2" ARE IN THE SAME TREE -- SHRINK CALL SHRINK (EDGRE1) RETURN C "NODE1", "NODE2" ARE IN DIFFERENT TREES - AUGMENT 1C MATE(NODE1) = EDGE1 MATE(NODE2) = EDGE2 IF (PRINT) WRITE(6,2) ROOT1,PNODE1,PNODE2,ROOT2 2'ORMAT(' DOUBLE AUGMENTATION:',I6, <R>...', 13,'+>',I4, &s~~'<+>..,I3,'<R>) CALL RMATCH (NODE) CALL RMATCH (NODE2) RETUR N C C "NODE 2" IS UNTABELLED 20 IT ( PRICE PNODE2) GT.TOLER.OR. PNODE2.GT. N ) GO TO 30 IF [ SET (PNODE2).NE.SETO.AND. SET(PNODE2). N. SET3 ) GO TO 30 C "NODE2" CAN BE A TYPE 2 NODE- AUGMENT MATE(NODE1) = NULL CALL MATCH(EDGE1) IF (PRINT) WRITE (6,3) ROOT1,PNODE1, PNODE2 3 FORMAT(' TYPE 2 AUGMENTATION:' I6,'<(R>...',I3,'<+>',14, ~6 *~'< >,) CALL RMATCH (NODEl) RETURN C 30 IF (MATE (APEX2).NE.NULL) GO TO 40 C "NODE2" IS A TYPE 0 NODE - ATUGENT MATE (NODE1) = EDGE1 MATE(NODE2) = EDGE2 IF (PRINT) WFITE(6,4) ROOT1,PNODE1, PNODE2 4 FOR MAT(' TYPE 0 AUGMENTATION:',I6,'<R>.', 3,'<+>', I4, $'< >') IF (NODE2.NE. PNODE2) CALL STAPEX(NODE2) CALL RMATCH (NODE1) RETURN C 40 EDGE3 = MATE(APEX2) APEX3 = HEAD(EDGE3) IF ( MATE(APEX3).GE.NULL ) GO TO 50 C "NODE2" IS A TYPE 1 NODE -- AUGMENT CALL NMATCH(EDGE3) MATE(NODE1) = EDGE1 MATE(NODE2) = EDGE2 IF (PRINT) WRITE (6,5) ROOT1,PNODE1, PNODE2 5 FORMAT(' TYPE 1 AUGMENTATION:',I6,'<R>.., 3,'<+>',I4, S''< >') IF (NODE2.NE.PNODE2) CALL STAPEX(NODE2) CALL RMATCH (NODE1) RETURN C C LABEL "NODE2" INNER C LABEL "NODE3' CUTR 50 PNODE3 = PSEUDO (APEX3) LABLO(PNODE2) = INNER HEAD(PNODE2) = ROOT1 LABLO(PNODE3) = OUTER TREE (PNODE2) = PNODE3 82

TREE(PNODE3) = TREE(ROOT ) TREE (ROOT ) = PNODE2 PRED (PNODE3) = EDGE2 HEAD (PNODE3) = ROOT1 LABL,$ = LABL$ + 2 IF (PRINT) WRITE(6,6) ROOT1,PNODE1,PNODE2, PNODE3 6 FORMAT(' NODE LABELING: *,I6, <F> e..,I3,'<+>,I4,'<->' &,I4,' <+>') CNODE3. = BCI(PNODE3) IF ( PRICE(NODE3).NE. MPRICE(PNODE3) ) GO TO 60 C "NODE3" CAN BECOME A TYPE 0 NODE - AUGMENT MATE(NODE3) = NUL IF (PRINT) WRITE(6,7) ROOTl,PNODE3 7 FORATMAT(' TYPE 3 AUGMENTATION:',I6,'<R>..',3,'<+>') CALL RMATCH (NODE3) RETTJRN 60 IF ( PRICE(PNODE2),NE.0.0.OR. PNODE2.LE.N ) GO TO 70 C'PNODE2" IS A INNER PSEUDO WITH NULL NODE PRICE - C -- UNSHRINK IT CALL NSHRNK (PNODE2) RETURN C C PUSH "PNODE3" INTO THE LIST OF UNSCANNED NODES 70 HSCAN = HSCAN + 1 IF (HSCAN.GT.N9) HSCAN = 1 NSCAN(HSCAN) PNODE3 RETUR N END 83

SUBROUTINE GRWFOR C - -m - - -- _,. a. w _ ~mm m mm,a w_ _ _ _ _j _ o _ _ _ _ _ _ _ C C MINIMUM COST 1-MATCH'ING/COVERING PROBLEM C THE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PERTN C AUTGUST 1980 C C C /GROW ALTERNATING FOREST/ C SCAN UNSCABNED NODES C PERFORM DUAL SOLUTION CHANGE C CHECK TERMINATION OR INPEASIBILITY C IMPLICIT INTEGER (A-Z) REAL VALUE,DELTA, MCOST,TOLER, NF,PRICE,MPRICE LOGICAL TRACE,PRINT COMMON /NODES/ SET (100),LABLO(150),PSEUDO 150),APEX (150),PRED( & 150),TREE (150),MPRICE (150),BCI(1 50) COMMON /EDGES/ HEAD(6150),PRICE(3150),LIST(3150),INDEX (3150) COMMON /LISTS/ NSCAN(101),INSP(3100),NORIG(100),LINK(1500),MAT & E(1500) COMMON /PNTRS/ HSCANTSCANHINSP,HORIG,HINK COMMON /PARMS/ N,N0,N1 I2,N9,L,L0,L1,L2, M, MOM1,M2,M9,P0OP2 COMMON /VARBS/ VALUEDELTAMCOST,OPTIONTRACE, PRINT COMMON /STATS/ ROOT$,NODE$,EDGE$,SHRK$,UNSH$, AUGM$, DUAL$,RMATS &, LABL$,LINK$,TIME1,TIME2,TIME3 COMMON /CONTS/ TOLER,INF,GUTER,INNER, UNLABD,SET0,S.TT 1,SET2,SFT & 3,NUJLL COMMON /PRNTS/ STACK(3000)PPACK(100) REAL COST C C 10 IF (TRACE) WRITE (6,1) 1 FORMAT(' *TRACE# GRWFOR') IF (OPTION.EQ.9) CALL DUMP C C DO 20 TO 80 FOR EVERY NODE IN "NSCAN" 20 IF (HSCAN.EQ.TSCAN) GO TO 100 TSCAN = TSCAN + 1 IF (TSCAN.GT.N9) TSCAN = 1 NODE = NSCAN (TSCAN) LABEL = OUTER IF (NODE.GT.0) GO TO 30 C "NODE > 0" -- OUTER NODE C "NODE < 0" -- EX-INNER NODE LABEL = UNLABD NODE = -NODE C CHECK WHETHER "NODE" IS A DESTROYED PSEUDO 30 IT (INDEX(NODE).EQ.NTLL) GC TO 20 PNODE = PSEUDO(NODE) C CHECK WJHETHER LABEL IS STILL OUTER OR EX-INNER (UNLABPFLTED) IF (LALLG (PNODNE).NE. LABIL) GO TO 20 IF (PRI1 T) WRITE(6,7) NODC f FORMAT(( SCAN NODE:',14) NO DE$ = qODE$ + 1 P"' -= ODE C BIFURCATE NODE: PSEUTDO IF (NODE. LF.I2) GO TO 50 84

c C "NODE" IS A PSEUDONODE C PUSH ITS SIMPLE BLOSSOM INTO "NSCAN" LABEL = 2 * LABEL - 1 BASE = MATE(NODE) BLSM = BASE 40 NSCAN(TSCAN) = LABEL * BLSM TSCAN = TSCAN - 1 IF (TSCAN.LT.1) TSCAN = N9 BLSM = HEAD(BISM) IF (BLSM.NE.BASE) GO TO 40 GO TO 20 C C "NODE" IS AN ORIGINAL NODE C SCAN ALL EQUALTIY EDGES INCIDENT WITH "NODE" 50 PT1 = PT 60 PT = LINK(PT1) IF ( PT.EQ. NULL ) GO TO 20 EDGE1 = MATE (PT) C CHECK FOP tESTROYED EDGE IF (EDGE1.EQ.NULL) GO TO 70 C DETERMINE DIRECTICN OF ARC IF (LABEL.EQ.UNLABD) EDGE1 = M9 - EDGE1 EDGE2 = m9 - EDGE1 EDGE = EDGE1 IF (EDGE.GT.EDGE2) EDGE = EDGE2 NODE1 = HEAD(EDGE2) NODE2 = HEAD EDGE1) PNODE1 = PSETDO(NODE1) PNODE2 = PSEUDO(NODE2) COST = PRICE (EDGE) - PRICE(NODE1) - PRICE(NODE2) C CHECK OUTER > — EDGE — > UNLABELLED IF (LABLO(PNODE1) NE.CUTER ) GO TO 50 IF (LABLO(PNODE2).EQ. INNER ) GO TO 50 C CHECK FOR EQTALITY E:GE IF ( COST.GT.TOLER ) GO TO 70 C CHECK FOR CURRENT EDGE IF (PNODE1.EQ.PNODE2) GO TO 80 CALL SCAN(EDGE1) C CHECK AUGMENTATION IF (LABLO (PSEUDO (NODE1)). NE. OUTER. AND. LABEL. EQ. OUTER) GO & TO 20 GO TO 50 C C RETURN "LINK/NATE(PT)" TO HINK 70 LINK(PT1) = LINK(PT) MATE (PT) = NULL LINK(PT) = HINK HINK = PT GO TO 60 C C TRANSFER "LINK/MATE(PT)" TO "PNODE1" 80 LINK (PT1) = LINK (PT) LINK (PT) = LINK(PNODE1) LINK(PNODE1) = PT GO TO 60 C C NO MORE ATJGMENTATIONS, SHEINKINGS, UNS HRINKINGS, OR LABEI,.ING. C ST ART DUAL SOLUTION CHANGF 100 IP (TPACE) CALL DUMP 85

IF (OPTION.EQ.9) CALL DUMP C CHECK TERMINATION I (ROOT$. Q.O) R) ETJURN C INITIALIZE CONTROL VARIABLES DELTA = INF HINSP = 0 C C CHECK ORIGINAL NODES DO 110 IND = NO, N1 NODE = LIST(IND) LABEL = LABLO(NODE) PNODE = PSETDO (NODE) IF ( PNODE.NE.NODE ) GO TO 110 C ONLY CURRENT ORIGINAL NODES C CHECK MAXIMUM INCREASE IF ( SET (NODE).EQ.SET2.AND. LABEL. EQ.OUTER ) CALL MINIM & ( NODE, -PRICEiNODE)) C CHECK MAXIMUM DECREASE IF ( SET(NODE).EQ.SFT3.AND. LABEL.EQ.INNER ) CALL MINIM & ( NODE, PRICE(NODE) ) 110 CONTINUE C C CHECK PSEUDONODES IF (LO.GT.L1) GO TO 130 DO 120 IND = LO, L1 NODE = LIST (IND) LABEL = LABLO(NODE) C CHECK MAXIMUM DECREASE IF ( LABEL.EQ.INNER ) CALL MINIM (NODE,PRTCE(NODE ) BNODE = BCI (NODE) C CHECK MAXIMUM INCREASE IF ( LABEL.EQ.OUTER.AND. BNODE.LT.N2 ) CALL MINIM( NODE, & tMPRICE (ENODE)-PRICE(BNODE)) 120 CONTINUE C C CHECK EDGES 130 DO 140 IND = MO, Ml EDGE = LIST (IND) NODE1 = HEAD (EDGE) NODE2 = HEAD(M9-EDGE) PNODE1 = PSEUDO(NODE1) PNODE2 = PSEUDO(NODE2) IF (PNODE1.EQ.PNODE2) GO TO 140 C ONLY CURR IT EDGES LABEL1 = IABLO(PNODE1) LABEL2 = IABLO(PNODE2) IF ( LABEL1.NE.OUTER.AND.LABEL2.NE. OUTER ) GO TO 140 C "AT LEAST ONE OF "IABEL1" OR "LABEL2" IS OUTER C CHECK MAXIMUM INCREASE COST = PRICE(EDGE) - PRICE(NODE1) - PRICE(NODE2) IF ( LABEL1.EQ. OnTER AND. LABEL2.EQ.UNLABD ) 1 CALL MINIM (EDGE,COST) IF ( LABEL1.EQ.UNLABD.AND. LABEL2.EQ.OUTER ) 1 CALL MINIM (EDGE,COST) IF ( LABEL1.EQ. OUTER.AND. LABEL2.EQ. OUTER ) f CALL MINIM(EDGE,COST/2) 140 CONTINUE C C NO NODE/EDGE TO INSPECT -- RETURN IF (HINSP.EQ.O) RETURN 86

C C UPDATE DUAL SOLUTION DUAL$ = DJUAL.$ + 1 IF (PRINT) WRITE(6,2) DELTA 2 FORMAT(' DUAL SOLUTION CHANGE:',F6.1) C C UPDATE ORIGINAL NODE PRICES DO 210 IND = NO, N1 NODE = LIST (IND) 210 PRICE(NODE) = PRICE(NODE) + DELTA*LABLO(PSEUDO(NODE)) C C UPDATE PSEUDONODE PRICES IF (LOGT.L1) GO TO 300 DO 220 IND L0, L1 NODE - LIST( IND) IF (NODE. EQ.PSEUDO (NODE)) 1 PRICE(NODE) = PRICE (NODE) + DELTA*LABLO(NODE) 220 CONTINUE C C UPDATE DUAL OBJECTIVE VALUE 300 VALUE = VALUE + BOOT$*DELTA C C START INSPECTING EVERY NODE/EDGE IN "INSP" DO 340 PT = 1, HINSP NODE = INSP(PT) C BIFURCATE NODE: EDGE IF (NODE.GE.MO) GO TO 330 IF (PRINT) WRITE(6,3) NODE 3 FORMAT(' INSPECT NODE: *,I6) LABEL = LABLO(NODE) IF (LABEL.EQ.INNER) GC TO 310 IF (LABEL.NE.OUTER) GO TO 340 C ONLY OUTER NODES -- AUGMENT BNODE = BCI (NODE) HATE (BNODE) = NULL IF (PRINT) WRITE (6,4) HEAD (NODE), NODE 4 FORMAT(' TYPE 3 AUGMENTATION:',16, <R>.'13'<+> CALL RMATCH(BNODE) GO TO 340 C ONLY INNER NODES C BIFURCATE NODE: PSEUDO 310 IF (NODE.GT.N2) GO TO 320 C ONLY INNER ORIGINAL NODES -- AUGMENT EDGE = PRED (HEAD (MATE (NODE) ) ) CALL MATCH(EDGE) APEX1 = HEAD(EDGE) PNODE = PSEUDO(APEX1) IF (PRINT) WRITE(6,5) HEAD (NODE),PNOD, NODE 5 FORMAT(' TYPE 2 AUGMENTATION:',I6,'<R>...',3,'<+>',I4,'< >') CALL RMATCH (APEX1) GO TO 340 C ONLY INNER PSEUDONODES -- UNSHRINK 320 CALL NSHRNK(NODE) GO TO 340 C C ONLY EDGES C FQnALITY EDGE 330 EDGE! = NODE 87

EDGE2 = M9 - EDGE1 NODE1 = HEAD (EDGE2) NODE2 = H1AD(EDGE1) IF (HINK.EQ.NULL) CALL ERROR(5) PTR = HINK HINK = LINK (HINK) MATE(PTR) = EDGE1 LINK(PTR) = LINK (NODEI) LINK(NODE1) = PTP IF (HINK.EQ.NULL) CALL ERiROR(5) IF (EIINK.GTLINK$) LINK$ = IINK PTR = HINK HINK = LINK (HINK) MATE (PTR) = EDGE2 LINK (PTR) = LINK (NODE2) LINK(NODE2) = PTR LABEL1 = LABLC(PSEJDO(NODE1)) LABEL2 = LABLO (PSEUDO (NOTE2)) EDGE = EDGE1 - L2 IF (PRINT) WRITE(6,6) EDGE, NODE1, NODE2 6 FORMAT(' INSPECT EDGE:' ( C CHECK OUTER > — EDGE -> OUTER C OUTER > — EDGE — > UNLABD C UNLABD > — EDGE — > OUTER IF (LABEL1.EQ.INNER OR. LABEL2.EQ.INNER) GO TO 340 IF (LABEL1.NE.OUTER.AND.LABEL2.NF.OUTER) GO TO 340 IF (LABEL1.EQ.OUTER) CALL SCAN(EDGE1) IF (LABEL1.NE.OUTER) CALL SCAN(EDGE2) 340 CONTINUE C CHECK TERMINATION IF I(TACE) CALL DUMP IP (OPTION.EQ.8) CALL DUMP IP (ROOT$.GT.O) GO TO 10 RETURN END

SUBROUTINE ORIG(PNODE) C - -.-., --- - -- - - - - - - _ _ _ -- _ _ _ _ _ _ __ C C MINIMUM COST 1-MATCHING/COVERING PROBLEM C THE UNIVERSITY OF MICHIGAN C -WRITTEN BY CLOVIS PERIN C AUGUST 1980 C C /GET SIMPLE BLOSSOM, EVENTUALLY ALL ORIGINAL NODES/ C PUSH INTO NORIG ALL NODES IN THE SIMPIL BLOSSOM OF "PNODE" IMPLICIT INTEGER (A-Z) FPAL VALUEDELTAMCOST,TCLER,I F, PRIC,MPRICE LOGICAL TRACEPRINT COMMON /NODES/ SET (100),ABLO(150),PSEUDO (150),APEX (150),PRED( & 150),TREE ( 150), MPRICE (150), BCI (1 50) COMMON /EDGES/ HEAD(6150),PRICE(3150),LIST(3150), INDEX(31 r0) COMMON /LISTS/ NSCAN (101),INSP (3100),NORIG (1OC),LINK (1500), MAT & E(1500) COMMON /PNTRS/ HSCAN,TSCAN,HINSP,HORIG,HINK COMMON /PARMS/ N,N0, N1,N2,1N9,L,L0,L1,L2, M, Mo M 11,M2,M9,P0,P2 COMMON /VARBS/ VALUE,DELTA,MCOST,OPTION,TRACE,PRINT C.OMMON /STATS/ ROOT$,NODE$,EDGES,SHRK$, NSH$,AUGM$,DUAL$,RMAT$ &. LABL$,ILINK$, TIM E1,TIME2,TIME3 C OMMON /CONTS/ TOL ER INF, OUTER,X INERU NLA.BD, SFTO SET1,SET 1 2, SET & 3, NULL COMMON /PRNTS/ STACK (3000), PACK(100) C C....... 0 *.. *..*. I 0 0.... 0.... 0. C 1F (TRACE) WRITE (6,1) PNODE 1 FORMAT(' TRACF,# ORIG t'I4 1)') C C "PNODE" IS ORIGINAL NODE? -- RETURN IF (PNODE.LE.N2) RETURN C C fPUfSH SIMPLE BLOSSOM INTO NCRIG BASE = MATE(PNODE) NODE = BASE 10 HORIG = HORIG + 1 NORIG(HORIG) = NODE NODE = HEAD (NODE) IF (NODE. NE.BASE) GO TO 10 C RETURN END 89

SUBROUTINE PUTSOL C- -- - - - - - - _ _ _ _ _ _._ _ C C MINIMUM COST 1-MATCHING/COVERING PROBLEM C THE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PERIN C AUGUST 1980 C (C /PUT SOLUTION/ C TRANSFORM NODE PRICES C TRANSFORM TYPE r CONFIGURATION C IMPLICIT INTEGER (A-Z) REAL VALUE,DELTA,MCOSTTOLER,INF, PRICE,M PRICE LOGICAL TRACE, PRINT COMMON /NODES/ SET (100),LABI' (150),PSEUDO(150),APEX(150),P ED( & 150),TREE (150),MPRICE ( 150),BCI (150 ) COMMON /EDGES/ HEAD (6150),PRICE (31 50),LIST(3150),INDEY (3150) COMMON /LISTS/ NSCAN(101),INSP (3100),NORIG (100) LINK (1500) MAT E E(1500) COMMON /PNTRS/ HSCAN,TSCAN,HINSP,HORIG,HINK COMMON /PARMS/ N,NO, N1,N2, N9,L,JLO,L1,L 2, MMO, 1MM2,M9,P0,P2 COMMON /VARBS/ VALUEDELTAMCOST, OPTION, TRACE, PRINT COMMON /STATS/ ROOT$,NOCE$,EDGE$,SHRK$,UNSH$,AUGM W,DUTAL$, RMAT$ 6,,LABL$, LINKS, TIME1,, TIME2 TIME3 COMMON /CONTS/ TOLER,INFOUTER INNER,U NTLABD, SETO, ST1,SET2,SET S, 3,NULL COMMON /PRNTS/ STACK(3000),PACK(100) INTEGER EDLIST (3000) REAL SIGMA, NPRICE(100) C C CALL TIME (1,.0,TIME2) IF (OPTION.EQ.5) CALL DUMP IF (OPTION.EQ.1) GO TO 310 C C PRINT HEADING K = 0 WRITE(6,1) N, M 1 FORMAT(//43X,' ***** SOLUTION *****'//43X, NETWORK:',15 &,' NODES,',15,' EDGES') C C CHECK INFEASIBILITY IF (DELTA.GE.INF) WRITE (6,2) 2 FORMAT(//43X,' = ROBLEM INFEASIBLE =') C C PRINT DUAL OBJECTIVE VALUE WRITE(6,3) VALUE 3 FORMAT(//43X,' OBJECTIVE VALUE:'.F9.2) C C FOR ALL NODES DO 70 IND = NO, NI NODE = LIST (IND) NPRICE (NODE) = PRICE (NODE) C C CHECK CURRENCY IF (PSEUDO (NODE),NE. NODE) GO TO 40 C GET MATES (SOLUTION EDGES) OF CYURRENT NODES PT = -MATE (NODE) 90

IF (PT) 30, 70, 10 C SEVER AL MATES 10 EDGE = MATE PT) IF (EDGE.GT.M2) GO TO 20 K = K + 1 STACK (K) EDGE - L2 20 PT = LINK(PT) IF (PT.NE.NYULL) GO TO 10 GO TO 70 C EXACTLY ONE MATE 30 IF (-PT.GT. M2) GO TO 70 K K + 1 STACK (K) = -PT - L2 GO TO 70 C NONCURRENT NODES 40 IF (NODE. NE APEX(PSEUDO (NODE))) GO TO 50 C IF APEX — > GET MATE (SOLUTION EDGE) EDGE = MATE(NODE) IF (EDGE.EQ.NULL.OR.EGBE.GT.M2) GO TO 50 K = K + STACK (K) = EDG - L2 C TRANSFORM NODE PRICES 50 IF (SET (NODE).EQ.SET2) GO TO 70 C N< OK! C N= PRICE DECREASED ON EVERY PSEUDO C N> PRICE DOUBLE DECREASED ON EVERY PSEUDO BLSM = NODE SIGN = 1 IF (SET (NODE).EQ. SE3) SIGN = 2 60 BLSM = LABLO(BLSM) IF (BLSM.LE.N2) GO TO 70 NPRICE (NODE) = NPRICE(NODE) - SIGN * PRICE(BLSM) GO TO 60 70 CONTINUE C C PRINT NODES AND EDGES WRITE(6,4) (LIST(I),SET (LIST(I)),NPRICE(LIST(T)), =NO,N1) 4 FORMAT(//' LIST OF NODES (NODE,SETPRICE):'/5(I15,I2,F7.1)) DO 80 INn = MO, M1 80 EDLIST(IND) = LIST(IND) - L2 WRITE (6, 5) (EDLIST (I),HEAD (LIST(I)), HEAD (M9-LIST (I),PRICE(LIS F T (I)) I=MOSM1) 5 FORMAT(//' LIST OF EDGES (EDGE,NODE1,NODE2,COST):'/5(I112,213, & 17.1)) C C CHECK EXISTENCE OF PSEUDONODES IF (I.3GT.L1) GO TO 200 WRITE (6,6) 6 FORMAT(//' PSEUDO PRICE SIMPLE BLOSSOM') C C CORRECT SOLUTION EDGES ON EVERY SIMPLE BLOSSOM DO 150 IND = LO, L1 PNODE = LIST (IND) BASE = MATE(PNODE) C GET SIMPLE BLOSSOM I =0 NODE = BASE 110 I = I + 1 PACK (I) = NODE NODE = HEAD (NODE) 91

IF (NODE. NE.BASE) GO TO 110 WRITE(6,7) PNODE, PRICE(PNODE), (PACK(J), J=, I) 7 FORM AT (17,F7. 1,2X, 2015/(19X,20I5) ) C CHECK TYPE C SIMPLE BLOSSOM APICE = APEX (NODE) IF (BASE.GT. N2.OR.SET(APICE). NE.SET3.OR. MATE (APICE).NF. NT ~'LL.OR.NPRICE(APICE).GT.TOLER) GO TO 130 C TYPE C SIMPLE BLOSSOM C GET SOLUTION EDGES BLSM1 = BASE 120 BLSM2 = HEAD (LSM1) K = K + 1 STACK (K) PRED (BLSM1) IF (STACK(K).GT.M2) STACK(K) = M9 - STACK(K) STACK (K) = STACK K) - 12 IF (BLSM2.EQ.BASE) GO TO 150 BLSM1 = HEAD (BISB2) GO TO 120 C TYPE A, TYPE B, TYPE D, OR ROOTED SIMPLE BLOSSOM C GET SOLUTION EDGES 130 BISM1 = HEAD (BASE) 140 K = K + 1 STACK(K) = PRED(BLSM1) IF (STACK K) GT.M2) STACK (K) = M9 - STACK(K) STACK(K) = STACK(K) - L2 BLSM1 = HEAD (HEAD(BLSM1)) IF (BLSM1.NE.BASE) GO TO 140 150 CONTINUE C C PRINT SOLUTION EDGES 200 WRITE(6,8) (STACK (I),=1,K) 8 FORMAT(//' SOLUTION EDGES:'/(10T12)) C C PRINT STATISTICS 300 IF (OPTION.EQ.2) RETURN WRITE (6, 11) 11 FORMAT (///45X, - STATISTICS =') 310 CALL TIME(1,0,TIME3) TIME3 = TIME3 - TIME2 TIME2 = TIME2 - TIME1 WRITE(6, 12) DUAL$,AUGM$,RMAT$,LABL$,NODE$, DGE$,SHRK$,N.TSH$, LT & NK$,TIME1,TIME2,TIM 3 12 FORMAT(// 119XI5,' DUAL SOL. CHANGES', 5,' PATHS REMATCH1D' 2 IS, NODES REMATED'/19X,I5, NODES LABELLED 3 I5,' NODES SCANNED, I5' EDGES SCANNED / 419X,I5,' SHRINKINGS, 15,' UNSHRINKINGS 5 I5,' LINK/MATES USED'/19X,I5,' CPU MSEC (INPTT) 5 15,' CPU MSEC (SOLUTION) 15,' CPU MSEC (OUTPUT) IF (OPTION.EQ.5) CALL DTUMP RETURN EN D

SUBROUTINE DUMP C C C MINIMUM COST 1-MATCHING/COVERING PROBLEM C THE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PlERIN C AUGUST 1980 C C /DUMaP NODE/EDGE INFORMATION/ C C IMPLICIT INTEGER (A-Z) REAL VALUE,DELTA, MCOSTTCLER,I F, PRICE,MPRICE LOGICAL TRACE, PRINT COMMON /NODES/ SET (100),LIABLO (150), PSFUDO (150),APEX (150), PRED ( & 150),TREE (150), MPRBICE ( 150), BCI ( 1 50) COMMON /EDGES/ HEAD (6150)-, PRICE(3 "50),LIST (3 150), INDEX (3150) COMMON /LISTS/ NSCAN (101),INSP (3100),NORIG(100),LINK ("500).,MAT C& E(1500) COMMON /PNTRS/ HSCAN,TSCANHINSP,HORIG,HINK COMMON /PARMS/ N, NO, Nl,N2,N9,L,,L,L1,L2, M, M,M1,M2, M9, PO,'P2 COMMON /VARBS/ VALUE,DEITA,MCOST,OPTION,TRACE, PRINT COMMON /STATS/ ROOT$,NOD.$,EDGE$,SHRK$,UNSH$,AUGM$, DUAL$, PMAT$ &, LABL$, LINK,TIM E, TIME2,TIME3 COMMON /CONTS/ TOLER,INF,OUTER,INNER,NLABD, SETO, SET1,SET2,SET & 3,NULL COMMON /PRNTS/ STACK(3000),PACK (100) C C C DUMP NODE INFORMATION WRITE (6, 1) 1 FORMAT (///' NODE SET LABEL PSEUD HEAD PR"D TREE AP'X 6 BCI PRICE MPRICE LINK(S) ) J = 0 DO 60 IND = NO, Ni1 NODE = LIST(IND) IF (NODE.EQ.NUJLL) GO TO 60 PT = LINK(NODE) PACK(1) = 0 K =0 10 IF (PT.EQ.NULL) GO TO 20 K K + 1 PACK (K) = MATE (PT) PT = LINK(PT) GO TO 10 20 IF (APEX (PSEUDO (NODE)). NE. NODE) GO TO 50 PT = -MATE (NODE) IF (PT) 30, 50, 40 30 J = J + 1 STACK(J) = -PT GO TO 50 40 J = J + 1 STACK (J) = MATE(PT) PT = LINK(PT) IF (PT.NE.NULL) GO TO 40 50 WRITE (6,2) NODE,SET (NODE),LABtO(NOD.E),PSFUDO(NODE).,HFAD (N E~ Q~ODE),PRED (NODE), TREE (NODE),APEX(NODE),BCI(NODF), 2 OR MAT (916,2F7.1, 1X,10I5/(69X, 10I 5)) 93

60 CONTINUE C C DTMP PSEUDO INFORMATION IV (LO.GT.L1) GO TO 200 WR ITE (6, 3) 3 FORMAT(//' PNODE BASE IABEL PSEUD HEAD PRE'n TR-E APEX B & CI PRICE MPRICE LINK(S)') DO 120 IND = LO, L1 NODE = LIST(IND) PT = LINK (NODE) PACK(1) 0 K =0 110 IF (PT.EQ.NULL) GO TO 120 K = K + 1 PACK (K) = MATE(PT) PT = LINK (PT" GO TO 110 120 WRITE(6,2) NODE,MATE (NODE),LABLO(NODE),PSEUDO(NODF),IHEAD( l NODE),PRE (NODE),TREE (NODE), APEX (NODE),BCI(NODE) C C DUMP EDGE INFORMTTON 200 IF (J.EQ.0) RETURN WRITE(6,4) (STACK (I),HFAD (STACK (I)),HEAD(M9-STACK(I)), I=1,J) 4 FORMAT(//'MATES: (EDGE,NODE1, NODE2)'/5(I9, 214)) RETUR N END 94

SUBROUTINE ERROR (I) C., — - - —.,, —.. - --.. -- C C C MINIMUM COST 1-MATCHING/COVERING PROBLEM C THE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PERIN C AUGUST 1980 C C /PRINT MESSAGE OF ERROR/ C C IMPLICIT INTEGER (A-Z) REAL VALUEDELTA, MCOSTTOLERINF, PRICE,MPRICE LOGICAL TRACE,PRINT COMMON /NODES/ SET (100),LABLO(150),PSEUDO(150,APEX (150),PRED( &. 150),TREE (150),MPRICE (150), BCI (150) COMMON /EDGES/ HEAD(6150),PRICE(3150), LIST 3150.),INDEX(3150) COMMON /LISTS/ NSCAN (101),INSP(3100),NORIG(100),LINK(1500),MAT S E(1500) COMMON /PNTRS/ HSCANTSCANHINSP HORIGHINK COMMON /PARMS/ N,NON1I N2,N9,L,L0,L1,L2,M,MO,M1,M2,M9,PO,P2 COMMON /VARBS/ VALUE,DELTA,MCOST,OPTIONTRACEPRINT COMMON /STATS/ ROOT$,NODE$,EDGE$,SHRK$,UNSH$,AUGM$, DUAS,RMAT$ ~,LABL$,LINK$,TIME1,TIME2,TIME3 COMMON /CONTS/ TOLER,INF,OUTER,INNER,UNLABDSETOSET1SET2,SET & 3, NULL COMMON /PRNTS/ STACK (3000),PACK(100) C C 1 ~ ~ ~.. e. e,. ~ ~ 1 ~! I o. ~.......... tt... C GO TO (10,20, 30,40,50,60,70,80,90,100), I GO TO 110 C 10 WRITE (6, 1) 1 FORMAT(' ***** UNEXPECTED END OF FILE ****') STOP C 20 WRITE(6,2) 2 FORMAT (' ***** ILLEGAL PARAMETER *****') STOP C 30 WRITE (6,3) 3 FORMAT(' ***** NODE STORAGE SPACE EXC'EEDED ****') STOP C 40 WRITE(6,4) 4 FORMAT(' ***** EDGE STORAGE SPACE EXCEEDED *****') STOP C 50 WRITE (6,5) 5 FORMAT' ***** LINK/MATE STORAGE SPACE EXCEEDED *****') STOP C 60 WRITE(6,6) 6 FORMAT (' ***** ILLEGAL NODE *****') STOP C 70 WRITE(6,7) 7 FORMAT(' ***** ILLEGAL EDGE *****') 95

STOP 80 WRITE(6, 8) 8 FORMAT(' ***** ILLEGAL NODE SET **i, ) STOP 90 WRITE 6,9) 9 FORMAT ( ***** ILLEGAL COST ****') STOP C 100 CONTINTUE 110 WRITE (6,12) I 12 FORMAT(' ***** ERROR NO.',13,' *****') STOP END 96

SUBROUTINE POSTOP C C C C MINIMUM COST 1-MATCHING/COVERING PROBLEM C THE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PERIN C ATIGUST 1980 C C /POST-OPTIMALITY ANALYSIS/ C K1 EDGE COST CHANGES C K2 SUBSET CHANGES C K3 EDGE ELIMINATIONS C K4 NODE ELIMI NATIONS C K5 NODE INCLUSIONS C K6 EDGE INCLUSIONS C C IMPLICIT INTEGER (A-Z) REAL TALUEDELTA, MCOST,TOLTER,IN1,PRICE,MPRICE LOGICAL TRACE,PRINT COMMON /NODES/ SET(100),LABLO(150),PSEUDO(150),APEX(150),PRED( & 150),TREE (150),MPRICE(150),BCI (150) COMMON /EDGES/ HEAD(6 150),PRICE (3150), LIST(3150),INDEX (3150) COMMON /LISTS/ NSCAN (101),INSP (31C0),NORIS (100),LINK (1500),MAT & E(1500) COMMON /PNTRS/ HSCAN,TSCANHINSP,HORIG,HINK COMMON /PARMS/ NNON1,N2, N9,L,LO,L1,L2,M,MO,I1,M2,M9,POP2 COMMON /VARBS/ VALUE,DELTA,MCOST,OPTION,TRACE, PRINT COMMON /STATS/ ROOT$,NODE,EDG E$, SHRK$,UNSH$,,AUGM.$,DUALS, RMATt 6,LABL$,ILINK$,TIME1,TIME2,TIME3 COMMON /CONTS/ TOLER,INF,OUTER,INNER, NLABD, SETC,SET 1,SET2, SET C 3,NULL COMMON /PRNTS/ STACK(3000),PACK 100) LOGICAL FREE(1) /'*'/ REAL NPRICE, COST C C CALL TIME(O) IF (.NOT.TRACE) GO TO 10 WRITE (6,1) 1 FORMAT(' #TRACE* POSTOP') TRACE =.FALSE. PRINT =.TRUE. OPTION = 3 10 IF (0.GT. OPTION.AND. OPTION.GE.-N2) OPTION = 3 C C GET NUMBER OF MODIFICATIONS READ(5,FRE!,END=1000) KI,K2, K3,K4,K5,K6 IF (K1+K2+K3+K4+K5+K66.EQ.0) STOP IF (K1.LT.0.OR.K2.LT.O.OR.K3.LT.O OR.K4.LT..OR.OK5 LT. OOR K6. & LT.0) CALL ERROR (2) WRITE (6,2) K1, K2, K3, K3, K5, K6 2 FORMAT ( 1H,40X, ***** POST-OPTIMALITY ANALYSIS *****'// 139X,' CHANGES:,I4,' EDGE COSTS,I,14,' NODE SETS'/ 239X,'ELIMINATIONS:',I4,' EDGES,',I4,' NODES'/ 339X,'INTRODUCTIONS:',14,' NODES,',I4,' EDGES') IF (OPTION.GE.0) GO TC 100 97

OPTION = CPTION + N2 IF (OPTION.EQ.-N2) TRACE =.TRE. IF (O.GT.OPTION. AND.OPTION. GF.-N2) PRINT =.TRUE. C C EDGE COST CHANGES 100 IF (KI.LT. 1) GO TO 200 DO 110 K = 1, K1 IF (TRACE) CALL DUTMP C GET E)GE AND NEW COST READ(5,FREE, END=999) EDGE, NPRICE IF (TRACE. OR. PTION. EQ 4) WRITE(6,4) EDGE, NPRICE 4 FORMAT(' EDGE COST CHANGE:',I5,F7.1) STACK (K) = EDGE EDGE = EDGE + L2 IF (EDGE.LT.MO.OR.EDGE.GT. M2.OR.INDEX (EDGE).EQ. NLL) CALL ERRO & R (7) IF (NPRICE.GT.INF.OR.NPRICE. TT.-INF) CALL EPRO & B (9) IF ( NPRICE.EQ.PRICE(EDGE) ) GO TO 110 EDGE1 = EDGE EDGE2 = M9 - EDGE NODE2 = HEAD(EDGE1) NODE1 = HEAD(EDGE2) PRICE (EDGE) = NPRICE COST = PRICE(EDGE) - PRICE(NODEI) - PRICE(NODE2) CALL NMATCH(EDGE) IF (PSEUDO(NODE1).NE. PSEUDO (NODE2).AND.COST. G.-TOLER) GO TO 1 S ~ 010 C EDGE IS OTT-OF-KILTER C TRY TO DECREASE PRICE(NODE1) CALL OPEN(NODEI) CALL DECRSE(EDGE1,COST) IF (COST.GT.-TOLER) GO TC 110 C TRY TO DECREAS PRICE(NODE2) CALL OPEN(NODE2) CALL DECRSE(E ZGE2, COST) IF (COST.GT.-TOLER) GO TO 110 C EDGE OF ACALL MATCH(EDGE) VALUE = VALUE + COST 110 CONTINUE IF (PRINT) WRITE (6,5) (STACK (K),HEAD(STACK (K)),HEAD (MV-STACK(K 6 )),PRICE (STACK (K) ),K1,K1) 5 FORMAT(//' EDGE COST CHANGE (EDGE,NODE1, NODE2, NEWCOST):'/5 (I9, F8,; 2I3,F6.1)) C C SUBSET CHANGE 200 IF (K2.LT.1) GO TO 300 DO 250 K = 1, K2 IF (TRACE) CALL DUMP C GET NODE AND NERSET READ (5,FREE,END=9 9) NODE, NSET IF (TRACE. OR.OPTION. EQ.4) WRITE(6,6) NODE, NSET 6 PFORAT(' CHANGE NODE SET:',215) STACK (K) = NODE IF (NSET.LT. SETO.OR.NSET. GT.SET3 ) CALL ERROR (8) IF (NODE.LT. NO.OR. NODE.GT. N2. OR. INDEX ( NODE).EQ.NLL) CALL ERRO g R(6) I' ( N SET. EJQ. SET (NODE) ) GC TO 250 C UPDATE SET(NODEO, MPRICE(NODE), AND BCI(NODE) 98

J = SET (NODE) + 1 SET (NODE) = NSET MPRICE(NODE) = 0 IF (SET(NODE).EQ.SET1) MPRICE(NODE) =IN? T (StSET (NODE).EQ. SET3) MPR'ICE(NODE) = INF BCI(NODE) = NODE IF (SET (NODE).EQ SET1) BCI(NODE) = L2 PNODE = PSEUDO(NODE) C FORCE NODE TO BECOME CURRENT IF (PNODE.NE.NCDE) CALL OPEN(NODE) C BRANCH IN ACCORDANCE WITH OLD SUBSET GO TO (210,220,230,240), J C C OLD SUBSET WAS SETO C SET3 IS OK 210 IF ( NSET.EQ.SET3 ) GO TO 250 C SET1, SET2: UNMATCH ALL MATES OF NODE 212 PT = MATE (NODE) IF (PT) 214, 218, 216 214 EDGE = MATE(-PT) CALL NMATCH(EDGE) GO TO 212 216 CALL NMATCH(PT) C UPDATE PRICE(NODE) 218 VALUE = VALUE- PRICE (NODE) PRICE (NODE) = -INT/2 VALUE = VALUE + PRICE(NODE) GO TO 250 C C OLD SUBSET WAS SET1 220 IF (NSET.NE.SETO) GO TO 222 C NEW SET IS SETO CALL OPEN(NODE) IF (PRICE (NODE).LT.-TOLER) CALL INCRSF (NODE) VALUE = VALUE - PRICE(NODE) PRICE(NODS) = 0 GO TO 250 C. C NEW SET IS SET2 222 IF (NSET.NE.SET2) GO TO 224 IF (PRICE(NODE) LE.+TOLER) GO TO 250 CALL OPEN (NODE) VALUE = VALUE - PRICE(NODE) PRICE(NODE) = -INF/2 VALUE = VALUE + PRICE(NODE) GO TO 250 C C NEW SET IS SET3 224 IF (PRICE(NODE).LT.-TOLER) CALL INCRSE(NODE) GO TO 250 C C OLD SET WAS SET2 C NEW SET IS SET1 OK 230 IF ( NSET.EQ.SET1 ) GO TO 250 C NEW SET IS SETO OR SET3 CALL OPEN (NODE) CALL INCRSE(NODE) GO TO 250 C C OLD SET WAS SET3 99

240 IF (SET (NODE).EQ.SETO.AND. PRICE(NODE).LE. TOLER) GO TO 250 I (SET(NODE).EQ.SET. AND. MATE (NODE).GE.NULL) GO TO 250 IF (S^T (NODE).EQ.SET2. AND.PRICE (NODE).LE.TOLE. AND. MATE (NODE). & GE.NULL) GC TO 250 C C UNMATCH ALL MATES OF NODE 242 PT = MATE(NODE) IF (PT) 244, 248, 246 244 EDGE = MATE(-PT) CALL NMATCH (EDGE) GO TO 242 246 CALL NMATCH (PT) C UPDATE PRICE (NODE) 248 VALUE - VALUE - PRICE(NODE) PRICE (NODE) = -INW/2 IF ( SET (NODE).EQ. SETO ) PRTn (NODE) = 0 VALUE = VALUE + PRICE(NODE) C 250 CONTINUE IF (PRINT) WRITE(6,7) (STACK(K),SET(STACK(K)),K=1,K2) 7 FORMAT(//' NODE SET CHANGE (NODE,NEWSET):'/10(110,12)) C C EDGE ELIMINATION 300 IF (K3.LT. 1) GO TO 400 DO 310 K = 1, K3 IF (TRACE' CALL DUMP C GET EDGE READ(5, FREE,END=999) EDGE IF (TRACE.OR. OPTION.EQ.4) WRITE(6,8) EDGE 8 FORMAT(' EXCLUDE EDGE:',5) STACK (K) = EDGE EDGE = EDGE + L2 I? (EDGE.LT.MO.OR.EDGE.GT.M2.OR.INDEX(ETGE).EQ.NTULL) CALL EIRO R (7) C UPDATE POINTERS CALL NMATCH(EDGE) IND = INDEX (EDGE) LIST(IND) = NULL INDEX (EDGE) NULL M = M - 1 C CHECK LINK/MATE POSITIONS DO 310 PT = PO, P2 IF (MATE(PT).EQ.EDGE.CR.MATE(PT).EQ.M9-EDGE) MATF(PT) = N & ULL 310 CONTINUE IF (PRINT) WRITE(6,9) (STACK (K),HEAD (STACK(K),HEAD(M9-STACK(K & )), PRICE(STACK (K)),K=1,K3) 9 FORMAT(//' EDGE EXCLUSICN (EDGE, NODE1,NODF2, COST):'/5(I9,2I3,F & 6.1)) C C NODE ELIMINATION 400 IF (K4.LT. 1) GO TO 500 DO 420 K 1=, K4 IF (TRACE) CALL DU!MP C GET NODE READ(5,FREE, ENt=999) NODE IF (TRACE. OR OPTION. EQ. 4) RIT E (6,11) NODE 11 FORMAT(' EXCLUDE NODE:',I5) STACK (K) = NODE IF ([NODE.LT.N0.OR.NODE.GT. N2.OR.INDEX (NODE).EQ.NUTT) CAT.L EREO 100

&. (6) CALL OPEN (NODE) DO 410 IND = MO, Ml EDGE = LIST(IND) IF (HEAD (EIGE).NE.NODE.AND.HEAD(M9-EDGE).NE.NODE). GO TO 4 & 10 IF (TRACE) WRITE(6,8) EDGE CALL NMATCH(EDGE) M = M - 1 INDEX(EDGE) = NULL LIST (IND) = NULL DO 410 PT = P0, P2 IF (MATE (PT) EQ.EDGE.OR,MATE(PT). EQ.M9-EDGE) MAT (PT) = N t;. ULL 410 CONTINUE VALUE VALUE PRICE(NODE) IND = INDEX NODE) LIST (IND) = NULL INDEX (NODE) = NULL 420 N = N - 1 IF (PRINT) WRITE(6,12) (STACK (K),SET(STACK (K)),K= 1,K4) 12 FORMAT(//' NODE EXCLUSION (NODE, SET):'/10(I10, 12)) C C NODE INTRODUCTION 500 IF (K5.LT.1) GO TO 600 DO 510 K = 1 K5 IF (TRACE) CALL DUMP C GET NODE AND SUBSET READ(5, FREE, END=999) NODE, NSBT IF (TRACE.OR, OPTION.EQ.4) VRITE(6,13) NODE, NSET 13 FORMAT(' INCLUDE NODE:',I4,I2) STACK(K) = NODE IF (NODE.LTN0. OR. NODE.GT. N2.OR.INDEX(NODE). NE. NULL) CALL ERRO & R (6) IF (NSET.LT0.OCR.NSET.GT.3) CALL ERROR (3) IF (N1.GE.N2) CALL ERROR(2) C UPDATE POINTERS N =N +1 N1 i N1 + 1 INDEX (NODE) = N1 LIST(N1) = NODE SET (NODE) = NSET LABLO (NODE) = UNLABD PSEUDO(NODE) = NODE PRED(NODE) = NULL APEX (NODE) = NODE MPRICE (NODE) = 0 IF (NSET.EQ.SET1) MPICE (NODE) = INF MATE (NODE) = NULL BCI(NODE) = NODE IF (NSET.EQ.SET1) BCI(NODE) = L2 PRICE (NODE) = 0 IF (SET (NODE).EQ. SET1. OR. SET (NODE).EQ.SET2) PRICE (NODE) =-INF/2 VALUE = VALUE + PRICE (NOE) LINK (NODE) = NULL 510 HEAD(NODE) = NULL IF (PRINT) WRITE(6,14) (STACK (K),SET (STACK (K) ), K= 1, K5) 14 FORMAT(//' NODE INCLUSION (NODE,SET):'/10(110,I2)) C C EDGE INTRODUCTION 101

600 IF (K6.LT 1) GO TO 700 DO 610 K = 1, K6 IF (TRACE) CALL DUMP C GET EDGE, NODES, AND EDGE COST READ (5, FREE, ENE=999) EDGE, NODE1, NODE2, NPRICE IF (TRACE.OR. CPTION.EQ.4) BRITE(6,15) EDGE,NODE1,NODE2, NPRICE 15 FORMAT(' INCLUDE EDGE:,3T5 F7 1) STACK (K) = EDGE EDGE = EDGE + L2 IF (E)GE.LT.M0 OR.EDGE.GT.M2.OR. INDEX(EDGE ).NE.NULL) CALL E 8 RROF (7) IF (NODE1.LT.NO0 OR.NODE 1GT. N2. OR. INDEX(NODE1).EQ. NULL) CALL E 6 BRBOR (6) IF (NODE2.LT.NO.OR.NODE2.GT. N2.OR. INDEX( NODE2).EQ.NTLI.) CALL E & BROR (6) IF (NPRICE. GT. INF. OR.NPRICE LT.-INF) CALL E & REOR (9) I, (M1.GE.M2) CALL ERROR(4) 610 CALL INCLUD(EDGF,NODE1,NODE2,NPRICE) IF (PRINT) WRITE (6, 16) (STACK (K),HEAD(STACK (K)),HEAD ( 9-STACK ( ~ K) ),PRICE (STAC K (K) ),K=1,K6) 16 FORMAT(//' EDGE INCLUSION (EDGE, NODE1,NODE2, COST): /5 (19, 213,F & 6.1)) C C RE-INITIALIZE VARIABLES 700 ROOT$ = 0 NODE$ = 0 EDGE$ = 0 SHRK$ = 0 UJNSH$ = 0 AUGM$ = 0 DTAL$ = 0 LABL$ = 0 RNAT$ = 0 HSCAN 0 TSCAN = 0 C C UPDATE LIST OF VALID NODE/EDGES C PLANT ALTERNATING FOREST I = NO N1 = N DO 720 IND = NO, N1 710 NODE = LIST(I) I =1 + 1 IF (NODE.EQ.NULL) GO TO 710 LIST (IND) = NODE INDEX (NODE) = IND PNODE = PSEUDO (NODE) LABLO(PNODE) = UNLABC H EAD (PNODE) = NTUL PREDT (PNODE) = NULL TREE(PNODE) = NULL IF (MATE(NODE).NE.NULL) GO TO 720 IF (SET (NODE).EQ. SET0) GO TO 720 IF (SET (NODE).EQ. SET2o AND. PRICE (NODE).GE.-TOLER) GO TO 72 & 0 IF (NODE.NE. APEX (PNODE)) GO TO 720 IF (SET (NODE).EQ. SET3. AND. PRICE (NODE).GF. MPRICE (NODE) -TOL & ER) GO TO 720 C EXPOSED NODE 102

LABLO(PNODE) = OnTER IHEAD(PNODE) = NODE PRED(PNODE) = NULL LINK (PNODE) = N ULl ROOT$ = ROOT$ + 1 HSCAN = HSCAN + 1 IF (HSCAN.GT.N9) HSCAN = 1 NSCAN (HSCAN) = PNODE 720 CONTINUE I = MO M. = MO + M - 1 DO 740 IND = MO, Ml 730 EDGE1 LIST (I) I = +1 IF (EDGE1.EQ.NULL) GO TO 730 LIST (IND). EDGE1 740 INDEX(EDGE1) = IND IF (TRACE) CALL DPIMP LABL$ = ROOT$ IF (PRINT) WBITE(6,17) ROCT$ 17 FORMAT(/' ALTERNATING FOREST PLANTED WITH' I4, ROOTS') DELTA = 0 IF (OPTION.EQ.6) CALL DUMP CALL TIME(1,0, TIME1) IF (OPTION.NE.-ROOT$) RETURN TRACE =.TRUE. CALL DUMP RETURN C C ERROR MESSAGE 999 CALL ERROR(1) 1000 STOP END 103

SUBROUTINE INCIUD(EDGE1,NODE1,NlODE2,NPRICE) c C C C MINIMUlM COST 1-MATCHING/COVERING PROBLEM C THE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PERIN C AUGUST 1980 C C C /INCLUDE EDGE1 IN THE NETWORK/ C NODE1 -- EDGE1 — > NODE2 C PRICE(EDGE1) =NPRICE C IMPLICIT INTEGER (A-Z) REAL VALUE,DELTA, MCOSTTOL FRIN%,PRICE,MPRICE LOGICAL TRACE,PRINT COMMON /NODES/ SET(100),LABLO(150),PSEUDO(150),APvEX(150),PRED( & 150),TREE(150),MPRICE(150),BCI (150) COMMON /EDGES/ HEAD(6150),PRICE(3150),LIST(3150),INDEX(315n) COMMON /LISTS/ NSCAN(101),INSP(31(00),NORIG (10 O),LINK (1 500),MAT & E(1500) COMMON /PNTRS/ IHSCANTSCANHINSP,HORIG,HINK COMMON /PARMS/ N,N0,r N1, N2, N9, L,LO,L1,L2, M, MO M1 s M2 M9, PO DP2 COMMON /VARBS/ VALUEsDELTAMCOST,OPTION,TRACE, PRINT COMMON /STATS/ BOOT$,NOCE$, EDGE$,SHRK$,UNSH$,AUGM$,snUAL$t, AT$ &,LABL$,LINK$,TIlME1,TIME2,TIME3 COMMON /CONTS/ TOLER, I NF, OUTER INNER, NLABD, SETO,SET 1,SET2,SET & 3,NULL COMMON /PRNTS/ STACK(3000),PACK (1(0) LOGICAL FREE(1) /'*'/ REAL COST, NPRICE C C IF (TRACE) WRITE(6, 1) EDGE1, NODE1, NODE2, NPPICE 1 FORMAT(' #TRACE# INCLUD (',3 (14,') F6 1, )') C C UPDATE VARIABLES M = M +1 M1 = M1 + 1 LIST(M1) = EDGE1 INDEX(EDGE1) = M1 EDGE2 = M9 - EDGE1 HEAD (EDGE 1) = NOnEl HEAD (EDGE2) = NODE2 PRICE (EDGE1) = NPRICE COST = PRICE (EDGE 1) - PRICE (NODE1) - PRIC 1 (NOTn 2) IF (COST.GE.0) RETURN C C EDGE IS OrUT-OP-KILTER C TRY TO DECREASE THE PRICE OF NODE" CALL OPEN (NODE 1) CALL DECRSE (EDGE1,COST) IF (COST.GE.O) RETURN C TRY TO DECREASE THE PRICE OF NODE2 CALL OPEN(NODE2) CALL DECRSE(ETnGE2,COST) IF (COST.LT.-TOLEF) CALL MATCTI(EDGE1) RETURN 104

c 999 CALL ERROR(3) RETURN END 105

SUBROUTINE DECRSE(EDGE,COST) C C C MINIMUM COST 1-MATCHING/COVERING PROBLEM C THE UNIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PEPIN C ATGUST 1980 C C /DECREASE PRICE(NODE) UNTIL COST = ZFO / C NODE -- EDGE —> C C IMPLICIT INTEGER (A-Z) REAL VALtE,DELTA, MCOSTTOLERINE,PRICE,MPRICE LOGIC AL TRACE,PRINT COMMON /NODES/ SET(100),LAB- 0(150),PSEUDO(150),APEX (r10),PRED( & 1S50),TREE (150) MPRICE (150),BCI ( 50) COMMON /EDGES/ HEAD(6150),PRICE(31 50),LIST {3150),INDEX (3150) COMMON /LISTS/ NSCAN(101),INSP(3100),NORIG(100),LINK(1500),MAT & E(1500) COMMON /PNTRS/ HSCAN,TSCANHINSP, HORIG,HINK COMMON /PARMS/ N,NON1,N2,N9,L,LOTIL2, MMOM1,M2M9, PO,P2 COMMON /VARBS/ VALUE,DELTAMCOST,OPTION,TRACE,PRINT COMMON /STATS/ ROOT$SNODEt,DGE$,SHRK$,UNSH$, AUGM$, DtAIL$,tRAT &,LABL$,LINK$,TIME1,TIME2,TIME3 COMMON /CONTS/ TOLEP INF, CUTERINNEPR, TNLABD, E TO,S T 1, SET, SET & 3,NULL, COMMON /PRNTS/ STACK(3000),PACK (100) REAL COST C IF (TRACE) WRITE(6,'1) EDGF, COST 1 FORMAT(' ~TRACE# DECRSE (' I4,',',F6. 1') C C GET NODE NODE = HEAD(M9-EDGE) C NODE IN SETO CANNOT HAVE ITS PRICE DECREASED I (SET (NODE) EQ.SET0) RETURN C NODE IN SET3 WITH NULL PRICE CANNOT HAVE ITS PRICE DECREAS;D IF (SET (NODE).EQ.SET3. AND PRICE (NODE).LT.TOLER) RETUTRN C DECREASE NODE PRICE PEICE(NODE) = PRICE (NODE) + COST VALUE = VALUE + COST COST = 0 IF (SET (NODE) NE. SET3. OR PRICE (NODE) GE -TOLER) R ETURN" C EDGE OF ACOST = PRICE (NCDE) PRICE (NO DE) = 0 VALUE - VALUE - COST RETUTIRN END 106

SUBROUTINE INCRSE(NODE) C C C MINIMUM COST 1-MATCHING/COVERING PROBLEM C THE T NIVERSITY OF MICHIGAN C WRITTEN BY CLOVIS PERIN C AUGUST 1980 C C /INCREASE PRICE(NODE) UP TO ZERO/ C CHECK EDGES INCIDENT WITH NODE C C IMPLICIT INTEGER (A-Z) REAL VALUE, DELTA,MCOST,TOLER,INF, PRICEMPRICE LOGICAL TRACE, PRINT COMMON /NODES/ SET (100),LABLO (150), PSEUDO (150),APEX (150),PRED( S 150),TREE(150),MPRICE150 BCI 50)BC 0) COMMON /EDGES/ HEAD (6150), PRICE (3150),LIST(3150),INDEX (31 0) COMMON /LISTS/ NSCAN (101),INSP (3100),NORIG (100),LINK (1500),MAT S E(1500) COMMON /PNTRS/ HSCANTSCANHINSPHORIGHINK COMMON /PARMS/ N,N0,N1,N2, N9.L,.LOL1,L2,M, M0,1, M2,M9, P0,P2 COMMON /VARBS/ VALTJEDELTA,MCOST,OPTION, TRACE, PRINT COMMON /STATS/ ROOTS, NOrDE,EDGES, SHRK$, NSH$,A GM$, DUAL$,? RAT5 &,LABL$,LINK$,TIME1,TIME2,TIME3 COMMON /CONTS/ TOLER,INF,OUTER,INNER, UNLABD,SRTTO, SET, SET2, SET & 3,NULL COMMON /PRNTS/ STACK(3000),PACK 100) REAL COST C C I? (TRACE) WRITE (6,1) NODE 1 FORMAT(' #TRACE# INCRSE (',I4,' )') C C INCREASE PRICE(NODE) TO ZERO VALUE = VALUE - PRICE(NODE) PRICE (NODE) = 0 C C CHECK EDGES INCIDENT WITH NODE DO 10 IND = MO, M1 EDGE = LIST(IND) NODE1 = HEAD (M9-EDGE) NODE2 = HEAD(EDGE) IF (NODE.NE.NODE1.AND.NODE.NP,.NODE2) GO TO 1C COST = PRICE(EDGE) - PRICE(NODE1) - PRICF (NOTn2) IF (COST.GE.-TOLER) GO TO 10 C NEGATIVE COST NODEO = NODE1 + NODE2 - NODE CALL OPEN (NODEO) CALL DECRSE(EDGE,COST) IF (COST. LT.-TOLER) CALL MATCH (EDGF) 10 CONTINUE RETURN END 107

SUBROUTINE OPEN (NODE) c c C C MINIMUTM COST 1-MATCHING/COVERING PROBLEM C THE UNIVERSITY CF MICHIGAN C WRITTEN BY CLOVIS PERIN C AUGUST 1980 C C /OPEN PSETDO (NODE)/ C UNSHRINK PSEUDO(NODE) OR UNMATCH MATE(NOD?') C IMPLICIT INTEGER (A-Z) REAL VALUE,DELTA, MCOSTTCLER,INF,PRICEMPR ICE LOGICAL TRACE,PRINT COMMON /NODES/ SET (100),I.ABB'O 150),PSEUDO(150),APEX (150r)),PRED( & 150),TREE (150,,MPRICE(150),BCI(150) COMMON /EDGES/ HEAD(6150),PRICE(3150),LIST (3150),INDEX (31 0) COMMON /LISTS/ NSCAN (101),INSP(3100),NORIG(100i ),LITIK(1500),MAT & E(1500) COMMON /PNTRS/ HSCAN,TSCAN,HINSP,HORIG,HINK COMMON /PARMS/ N,N0,N1,N2,N9,LLQL1,L2, 9LL 0,LMOM1,M2,MD9, PO,P2 COMMON /VARBS/ VALnE, DELTA,MCOST,OPT ION,TRACE,, PRINT COMMON /STATS/ ROOT,NODE$,EDGE$,SHRK$,UNSH$, AUGMS, DTYAL$, RMAT't &,LABL$,LINK$,TIME1,TIME2,TIME3 COMMON /CONTS/ TOLER,INF,CUTER,INNER, TNLABD,SETO, SET1,SF,.T2,SET & 3 NULL COMMON /PRNTS/ STACK (3000),PACK (100) C C IF (TRACE) WRITE(6,1) NODE 1 FORMAT(' #TRACE# OPEN (',I4, )) C C BRANCH IF NODE IS NONCURRENT IF (PSEUDO (NODE).NE. NODE) GO TO 10 C NODE IS CURRENT IF (SET(NODE).EQ. SETO) RETURN IF (SET (NODE).EQ. SET3.AND PRICE(NODE).EQ.0) RETURN C TNMATCH MATE(NODE) EDGE = MATE (NODE) CALL NMATCH(EDGE) RETURN C C UNSHRINK PSEUDO (NODE) 10 PNODE = PSEUDO(NODE) EDGE = MATE (APEX(PNO'DE)) C UNMATCH MATE (NODE) CALL NMATCH(ECGE) IF (PNODE. EQ. NCDE) RETURN IF (TRACE) WR ITE (6,2) PNODE 2 FORMAT(' #TRACE# OPEN PSEUDO:'1 4) C C REDUCE NODE PRICES HORIG = 0 CALL ORIG (PNODE) DO 20 H = 1, HORIG NODE2 = NORIG (H) IF (NODE2.GT. N2) CALL ORIG(NODF2) IF (NODE2.LE. N2) PRICE(NODF2) = PRICE( (NOn.E2) - P.ICE(PNOD 108

& E) 20 CONTINUE VALUE = VALUE - PRICE(PNODE) C C UPDATE MATES, APICES, HEADS, ANI) PREDS BASE = MATE(PNODE) CALL STPSDO(BASE) LABLO (BASE) = UNLABD BLSM = HEAD(BASE) 30 EDGE1 = PREDB(LSM) EDGE2 = M9 - EDGE1 NODE2 = HEAD (EDGE1) NODE1 = HEAD (EDGE2) ATE (NODE l) = EDGE1 MATE(NODE2) = EDGE2 BLSM1 = HEAD (BISM) CALL STPSDO (BLSM) CALL STPSDO(BLSMl1) LABLO (BLSM) = UNLABD LABLBL LABLO(BS1) U CALL STAPEX (NODE1) CALL STAPEX(NODE2) HEAD [BLS.M) = 0 PRED (BLSM) 0 BLSM = HIEAD (BLSM1) liEAD(BLSM1) = 0 PRED (BLSM1) = 0 IF ( BLSM.NE. BASE ) GO TO 30 HEAD(BASE) = 0 R ED (BAS E) = 0 C C UPDATE PSEUDONODE LIST IND = INDEX (PNODE) LIST(IND) = LIST (L1) LIST (L1) = PNOtE INDEX (LIST (INP)) = IND INDEX (PNOOTE) = L1 L1 = 1 - 1 GO TO 10 C N D) 109

UNIVERSITY OF MICHIGAN 901504732 7484111111 3 9015 04732 7484