The person charging this material is re- sponsible for its return to the library from which it was withdrawn on or before the Latest Date stamped below. Theft, mutilation, and underlining of books are reasons for disciplinary action and may result in dismissal from the University. To renew call Telephone Center, 333-8400 UNIVERSITY OF ILLINOIS LIBRARY AT URBANA-CHAMPAIGN otv 6 m L161— O-1096 UCDCS-R-78-924 yK I > £ . . . > A. . Let h be the number of i l _ i 2~ i 3 ~ X n unsatisfied constraints and r be the smallest integer such that I, + I ,, +... + £_, > h. Then ZMIN is i, i i — 12 r calculated by ZMIN = r + XP, where XP is the number of variables which are fixed to 1 in the current par- tial solution. 2.1.3.2 Test if "ZBAR-ZMIN <_ DVSN" is satisfied, where ZBAR is the best value of the objective function obtained so far. If it is satisfied, then the program con- trol goes to the procedure BACKTRACKING. 2.1.4. BRANCHING Procedure This procedure consists of the following steps: 2.1.4.1 Choose a r . by some criterion. i 2.1.4.2 For each non-zero element a., in the row chosen at lk step 2.1.4.1 generate a subproblem by fixing vari- able x. to 1. k 2.1.4.3 Store all subproblems just generated with level num- bers in a stack XX (only (k, — £) is stored for each subproblem, where k is the index of the variable cor- responding to which a subproblem is generated and £ is the level number of this subproblem) . The subproblem DVSN is a parameter read from the input by the INITIALIZATION pro- cedure. ** The level number of the subproblem generated from the subproblem with level number k is k + 1. 10 corresponding to the column with the fewest non-zero elements in it is stored first. (The corresponding column of the problem generated by fixing variables x to 1 is column a.). Then, the subproblem corres- ponding to the column with the next fewest non-zero elements in it is stored next, and so on. 2.1.4.4 Get an entry (k,-£) from the top of stack XX. Set x. to 1 and delete all rows with their k-th element k equal to 1. The criterion used in step 2.1.4.1 for choosing a row is des- cribed as follows: 2.1.4.1.1 For each column i, calculate n. = (number of non-zero elements in column i) . + (number of "bicolumnar" rows covered by column i) . Here a row is said to be "bicolumnar" if it contains only two non-zero elements. 2.1.4.1.2 Find the column i with the largest n. . If there is o 1 o a tie, the column with the largest index is chosen. 2.1.5 CHECKING Procedure This procedure will check if any of the testing sets constructed at the BACKTRACING procedures satisfies YY. > 2 whenever row r. is in that testing set, i — x where YY. = Z a., x. and S is the current partial solution. If one of the 1 xjeS 1J J * Testing set will be explained in Section 2.1.8 BACKTRACKING procedure. 11 testing sets satisfies the above condition, then the program control goes to BACKTRACKING procedure [3], 2.1.6. HEURISTIC Procedure The current subproblem will be solved by the heuristic procedure consisting of the following steps: 2.1.6.1 Choose a column a by a criterion which will be de- o scribed later. 2.1.6.2 Fix x. to 1 and reduce the constraint matrix as l o much as possible by operations 1, 2, and 3 in Sec- tion 2.1.2. 2.1.6.3 If the constraint matrix is not null, then the pro- gram control goes to step 2.1.6.1. 2.1. 6.4 If parameter P4 (a parameter specified by a user) is 0, the program control goes to the PRINTING procedure. 2.1.6.5 Perform the TRANSFORMATION procedure (this procedure will be explained later) and transfer the program control to the PRINTING procedure. The criterion for choosing a column in step 2.1.6.1 is as follows: 2.1.6.1.1 For each non-deleted column i calculate ( 1 1 1 V w. = ( + + ) 1 v. V. V. 1, 1 1 1 2 r where i , i , ..., i are the row indices of those 12 r non-deleted rows covered by column i, and v. is x k the number of non-zero elements on row i, for k k = 1, 2, . . . , r. 12 2.1.6.1.2 Choose the column i with the greatest w, . If o 1 o there is a tie, the one with the smallest index is chosen. The TRANSFORMATION procedure in step 2.1.6.5 will transform a given feasible solution into another feasible solution and reduce this feasible solution if possible. This procedure consists of the following steps: 2.1. 6.5.1 Check if the feasible solution is reducible. (A feasible solution (x, ,x_, .... x ) is said to be 12 n reducible if there exists some non-zero element x. such that (x.,x„, ..., x. -, 0, x. .,, ..., x ) l i 2 l-l l+l n is also a feasible solution). If it is reducible, then set the variable x. to 0. Then we have ob- l tained a better solution. 2. 1. 6.5. 2 Based on a criterion which will be explained later, try to replace a column in the feasible solution set with some column not in it. Then we have ob- tained another feasible solution. If another feasible solution is obtained, then the program control goes to step 2.1.6.5.1. Else the pro- gram control goes to the PRINTING procedure. To explain the criterion used in step 2.1.6.5.2 to decide whether a column in a feasible solution set is to be replaced by another column, The feasible solution set of a feasible solution is the set of columns corresponding to the non-zero variables in that feasible solution. 13 we first define a "covering weight" for a feasible solution set F, denoted by W(F) , as the number of i's such that YY. >_ 2, n ^ where YY. ■ Z a., x. . Then a column a. in the feasible solution set 1 • i X J 3 i j=l -a. F is replaced by another column a. not in F if the set F f , obtained from F by replacing a. by a. in F, satisfies the following two conditions (1) F' is a feasible solution set, (2) W(F') > W(F). A column a. is tested to see if it can be replaced by some other column as follows: 2.1.6.5.2.1 Find the first row r. covered by column a. with 11 YY. = 1, where YY. = E a., x.. i i i ij J 2.1. 6. 5. 2. 2 All the columns covered by row r. are the candi- j 1 date columns that may replace column a.. Check only those columns to see if any of them can re- place column a . . 2.1.8. BACKTRACKING Procedure The whole procedure consists of the following steps. 2.1. 8.1 Get the subproblem in stack XSL with one level higher than the current subproblem. If there is no such subproblem, the program stops. De- lete the current subproblem (when a subproblem is deleted, all information related to this * A subproblem with level number k is said to be higher than a sub- problem with level number h if k < h. 14 subproblem, such as the numbers of non-zero elements in each column and each row, the testing sets of this subproblem, and the non-zero variables in the partial solution of this subproblem, are all deleted). Consider the subproblem just obtained (at the begin- ning of this step) as the current subproblem. 2.1.8.2 Test if "ZBAR-ZMIN <_ DVSN" is satisfied, where ZBAR is the best value obtained so far and ZMIN is a lower bound of the current subproblem. If it is satisfied, then program control goes to step 2.1.8.1. 2.1.8.3 Obtain a subproblem (from stack XX) with one level lower (greater) than the current subproblem. If there is no such subproblem, then the program con- trol goes to step 2.1.8.1. 2.1.8.4 Let x be the variable corresponding to which the o subproblem has just been deleted in step 2.1.8.1. Set variable x. to and delete a. from the con- ic k o o straint matrix of the current subproblem. 2.1.8.5 Store an entry (k ,-$,) in a stack XU, where k is o o the index of variable x. in step 2.1.8.4 and I is k o the level number of the current subproblem. Before it is stored, remove all entries with level numbers greater than I. 2.1.8.6 Generate the testing sets for the subproblem obtained at step 2.1.8.3. * Testing set will be explained later in this section. 15 2.1.8.7 Find a lower bound ZMIN by the method used in Section 2.1.3 Bounding Procedure. Test if "ZBAR-ZMIN <_ DVSN" is satisfied or not. If it is satisfied, the program control goes to step 2.1.8.1. 2. 1.8.8 Store the current subproblem with all information re- lated to this subproblem. Consider the subproblem ob- tained at step 2.1.8.3 as the current subproblem. Pro- gram control goes to the CHECKING procedure. Before we explain the testing sets which are stated in step 2.1.8.6 and tested in the CHECKING procedure, we first define the ter- minology E-set . The E-set of column a. with respect to column a. is defined to be the set of rows covered by column a. but not covered .1 by column a., and is denoted by E... It is proved in [3] that if (1) the subproblem with x. fixed to 1 has been enumerated, (2) S is the current partial solution with x. = 0, x. = x. 1 J 3 1 (3) E.. is covered by columns a. ,a. , ... ,a. , then there is no better feasible solution can be found under the current partial solution. So when the subproblem with x. fixed to 1 has been enumerated, we can construct an E-set, E.., for the subproblem with x. fixed to and x. fixed to 1 and test if E.. is covered by 1 J ij a. , a. , ... , a. for each partial solution S with x. = 0, x. = x. J l J 2 J r J J l ... = x. =1. The testing sets generated at step 2.1.8.6 are the E- J r sets for that subproblem. The number of E-sets generated for that subproblem is the same as the number of subproblems, which were gen- erated at the same time as that subproblem in step 2.1.4.2 and were 16 already enumerated. Each testing set is stored in a stack XQ to- gether with the level number of the current subproblem. When the pro- gram backtracks (i.e., program control goes to the BACKTRACKING proce- dure), those testing sets with level numbers greater than the current level number are deleted. 2.2. Storage Allocation In this section, we describe the storage allocation of this pro- gram. 2.2.1. Storage of Matrix A In order to efficiently process the procedure (stated in Sec- tion 2.1.2 REDUCTION Procedure) for checking the dominating relations among the rows and columns of the constraint matrix, the constraint matrix is stored both column-wise and row-wise. 2.2.1.1. Column-wise storage of matrix A The constraint matrix is stored column-wise, as follows: (See Figure 2.2.1). ROW CLPT % • f r f K- .N + 1 4 Figure 2.2.1 The column-wise storage of matrix A. 17 1. The row indices of non-zero elements in each column are con- secutively stored in ROW, column by column. The first column is stored first, then the second column, and so on. 2. The row indices of each column are stored according to their ascending order. 3. The location, in ROW, of the row index of the first non-zero element in column a. is stored in CLPT (i) . (The location, in ROW, of the row index of the last non-zero element in column a. is calculated as CLPT (i+1) -1). As an example, the following matrix A is stored, as shown in Figure 2.2.2. / A = .0 t J.JL i : o P. L i. . i ! o .o _ •_ _o_ A.L.P x 1 ! 1 / ROW 78 1482456 1367 ••• CLPT 1 6 9 13 17 • • • Figure 2.2.2 An example of the column-wise storage of matrix A. 18 2.2.1.2. Row-Wise Storage of Matrix A The constraint matrix A is stored row-wise, as follows: (See ' Figure 2.2.3). 1. The column indices of non-zero elements are consecutively stored in COL, row by row. The first row is stored first, then the second row, and so on. 2. The column indices of each row are stored according to their ascending order. 3. The location, in COL, of the column index of the first non- zero element in row r. is stored in RWPT(i). (The location, in COL, of the column index of the last non-zero element in row r. is calculated as RWPT(i+l)-l) . COL RWPT • ♦ • J f K- M + 1. V * Figure 2.2.3 The row-wise storage of matrix A. The matrix A in Section 2.2.1.1. is stored row by row as shown in Figure 2.2.4. 11 13 15 17 Figure 2.2.4 An example of the row-wise storage. 19 2.2.2. Storage of Subproblems When subproblems are generated in the step 2.1.4.2 of Section 2.1.4 BRANCHING Procedure, each subproblem (denoted by (k,-£)) is stored in stack XX as shown in Figure 2.2.5. -1 -I. -Si, -I A JX Figure 2.2.5 Storage for subproblems in XX. The last position in XX, where an entry, (k,-£) was stored, is stored in pointer JX. 2.2.3. Storage of Information Related to Subproblems When a subproblem is stored at step 2.1.8.2 in Section 2.1.8 BACKTRACKING Procedure, all information related to this subproblem such as the numbers of non-zero elements in each column and each row, the testing sets of this subproblem, the lower bound of this subproblem, the partial solution of this subproblem are stored. 2.2.3.1. Storage Of The Numbers of Non-zero Elements in Each Column And Each Row For each subproblem, two (two dimensional) array variables RWLT and CLLT are used to store the numbers of non-zero elements in each row and each column as shown in Figure 2.2.6. The number of non-zero elements in column a. of the subproblem with level number k is stored in CLLT(k,j), and the number of non-zero elements in row r. of the 20 LEVEL ^ — — M . * • • • < N — ■=> • • • Figure 2.2.6 Storage of the numbers of non-zero elements in each column and each row. XSL STK ~2> LEVEL XP Figure 2.2.7 Storage of partial solutions. 21 subproblem with level number k Is stored In RWLT(k,i). A column (or a row) with a non-positive number of non-zero elements means that this column (or this row) is deleted. 2.2.3.2. Storage of Partial Solutions For each subproblem, only the non-zero variables (variables with value 1) of its partial solution are stored as follows, and is shown in Figure 2.2.7. 1. The indices of these non-zero variables are consecutively stored in stack XSL. i 2. The position in XSL, where the last non-zero variable of a partial solution in the k-th level was placed, is stored in STK(k). 3. The non-zero variables of each partial solution are stored from the first position of XSL to succeeding positions. (This is because the partial solution of the k-th level sub- problem is obtained from that of the (k-l)-th level subpro- blem by fixing more free variables). 4. XP is the number of non-zero variables of the current partial solution. 2.2.3.3. Storage of Lower Bounds The lower bound ZMIN calculated at step 2.1.3.1 or 2.1.8.4 is stored in an array variable STKLBD as shown in Figure 2.2.8. The lower bound of the k-th level subproblem is stored in STKLBD (k). STKLBD LEVEL Figure 2.2.8 Storage of the lower bound of each subproblem 22 2.2.3.4. Storage of Testing Sets All the testing sets for each subproblem (See Section 2.1.4 BRANCH- ING Procedure and Section 2.1.8 BACKTRACKING Procedure) are stored in a stack XQ. How they are stored is shown in Figure 2.2.9 and is explained below. XQ STKXQ r* i r s- ' T 2^- T N. i a s > 4 •>'< -i iiJ H \ -1 h h -l -l *i *2 1 P _1 1, problem status will be printed every P2 iterations. For P2 = 0, no problem status will be printed until the number of iterations reaches the limit specified by PI. The problem status of a problem is expressed by two array vari- ables XX and XSL. The indices of non-zero variables (variables which are fixed to 1) of the current partial solution are stored in XSL. (See 2.2.2 Storage of Subproblems. ) Subproblems which are not initiated are stored in XX. (See 2.2.2 Storage of Subproblems.) For example, the following problem status XX -1 4 -2 21 -3 30 -3 32 -5 XSL 34 29 37 23 shows that four variables x„,, x , x~ 7 , x 9 ~ are fixed to 1 in the cur- rent subproblem, and four subproblems (4,-2), (21,-3), (30,-3) (32,-5) and are not initiated yet. (See 2.1.4. BRANCHING Procedure). The en- try "-1" means no subproblem, i.e. , the completion of enumeration. From this problem status (by estimating how long it took to enu- merate each subproblem) , a user can estimate how long his problem still has to be run in order to finish the enumeration. (4) P_3 This parameter specifies whether there are CONTINUATION cards or FIXING cards following the matrix cards. If there are CONTINUA- TION cards following the matrix cards in the input card deck for a * "A subproblem is initiated" means that some part of this subproblem is enumerated. 27 problem, P3 is set to 1. If there are FIXING cards following, P3 is set to 2. Otherwise, it is set to 0. (5) LIMT This parameter specifies a limit on the level numbers of sub- problems. A subproblem with a level number equal to this limit will be solved by the heuristic procedure HEURISTIC. No subproblem with a level number greater than this limit will be generated in the enumeration procedure. If the level numbers of subproblem never reach this limit in the enumeration procedure, this enumeration is said to be completely enumerated . Otherwise, (i.e., there are some sub- problems with level numbers equal to this limit) this enumeration is said to be heuristically enumerated . When a problem is heuristi- cally enumerated, the best solution obtained has no guarantee to be optimal. The highest level limit that can be specified is 30 in the current version. If a value greater than 30 or less than 1 is speci- fied, an error message will be given and value 30 is assumed the value to be specified. (6) P4 This parameter specifies whether the TRANSFORMATION procedure (see Section 2.1.6) will be applied in the procedure HEURISTIC or not. If it is to be applied, then P4 is set to 1. Otherwise, it is set to 0. (7) P5 This parameter specifies whether the CONSTRAINT matrix is to be read in column-wise or row-wise. When P5 is set to 1, the CON- STRAINT matrix is read in row-wise. Otherwise, it is read in column-wise. 28 2.3.4. MATRIX Cards These cards provide the program the constraint matrix of a problem. Depending on the parameter P5, the constraint matrix is read in column- wise or row-wise. 2.3.4.1. Column-Wise Reading The first column is read in first, then the second column, and so on. For each column, only the row indices of the non-zero elements in it are read in. The row indices of each column are consecutively punched (starting from the most left 4 columns of each card) on cards according to their ascending order. Each row index takes four columns (it must be fight justified in the four columns assigned to it) and each card can only provide 18 row indices (from column 1 through column 72). Column 73 through column 80 can be any characters and data in it will not be read in. The end of a column is indicated by a negative row index. So each row indices sequence for each column must be fol- lowed by a negative number (i.e., a negative row index). Each new column must start from a new card. The end of the constraint matrix is indicated by a card with value in column 1 through colums 4 (column 5 through column 72 must be blanks) . The last card of the constraint matrix must be a such card (a blank card is an acceptable card) . As an example, the matrix cards for the following matrix is pre- pared as shown in Figure 2.3.4. 29 \ / 73-80 ( /end ,fl 3 6 7 -1 /COLUMN 4 r, « 5 6 -1 /COLUMN 3 f 1 4 8 -1 /COLUMN 2 /; -l COLUMN 1 Figure 2.3.4 The MATRIX Cards for the matrix A (column-wise). 2.3.4.2. Row-Wise Reading The MATRIX cards for the row-wise input case is similarly prepared as stated in Section 2.3.4.1. with columns and rows switched. The matrix A in Section 2.3.4.1. for the row-wise input is prepared as shown in Figure 2.3.5. 30 2.3.5. CONTINUATION Cards These cards provide the program the information that is needed for a problem to be started from where it was terminated in the last run. These cards are those that were punched by the program in the last run when the number of iterations reached the number specified by parameter PI. These cards are needed only when parameter P3 is set to 1. 73-80 ( r ,<• / END (> ■ -1 / / ROW 8 f 1 4 -1 / ROW 7 3 4 • -1 / ROW 6 3 -1 /row 2 2 4-1 / ROW 1 Figure 2.3.5 The MATRIX cards for the matrix A (row-wise) 2.3.6. FIXING Cards These cards provide the program the information of which variables will be fixed to 1 before the program starts enumeration. The indices of these variables, which are fixed to 1 before the enumeration, are con- secutively punched on these cards. Starting from the first 4 columns of each card, each index takes 4 columns (it must be right justified in the four columns assigned to it) , and each card can only provide 18 indices (from column 1 through column 72). These indices are not necessary to 31 be in an increasing sequence. The end of those indices is indicated by an index with a non-positive value. As an example, if we want to fix variables x 5> x , x to 1 before the enumeration, then a FIXING card is prepared as shown in the Figure 2.3.6. 1-4 5-8 9-12 13-16 r 5j 10 i -1 Figure 2.3.6 An example of a FIXING card These cards are needed only when P3 is set to 2. It must be noted that FIXING cards and CONTINUATION cards are not simultaneously included in the input deck for a problem. When a problem (with some variables fixed to 1 at the beginning) is to be started from some point where it was terminated in the last run with CONTINUATION cards, P3 must be set to 1, and the FIXING cards are no longer needed. 2.4. Output For each problem, the title on the TITLE card is printed first, and then the values of M, N and the values of the parameters on the PARAMETER card are printed. Then the constraint matrix is printed column by column. Only the row indices of the non-zero elements are printed for each column. If some variables are fixed to 1 before the enumeration, the indices of those variables are printed. After the first reduction (i.e., the reduc- tion performed at the first iteration) , the number of non-deleted rows 32 and the number of non-deleted columns are printed as CONSTRAINT MATRIX SIZE AFTER FIRST REDUCTION M:mm N:nn, where mm is the number of non-deleted rows and nn is the number of non- deleted columns. In the enumeration procedure, when a feasible solution better than the one we keep is found, it will be printed immediately. Only the in- dices of the non-zero variables (variables with value 1) of this feasible solution are printed (not variables which are fixed to 1 before the enu- meration). Each better feasible solution found by the program is given a sequence number by the program. The sequence number of this feasible solution (i.e., 1, 2, 3, etc.), the value of this feasible solution (if there are some variables fixed to 1 before the enumeration, i.e. , before the first reduction, the value of these variables is not added in this value), and the number of iterations when the feasible solution was found are printed also. As an example, the print-out shown in Figure 2.4.1 shows that (1) The second feasible solution found is a solution with x = 1, x 2 = 1, x^ = 1, x g = 1, x = 1, x 2 ■ 1, x = 1 and other variables fixed to 0. (2) The objective value of this feasible solution is 7. (3) This feasible solution is found at the number of iterations 102. FEASIBLE SOLUTION FOUND 2: 5 2 11 8 9 20 24 ZBAR: 7 NTR: 102 Figure 2.4.1 The print-out of a feasible solution. 33 When the number of iterations reaches the number specified by pa- rameter P2, the current problem status (See Section 2.3.3 PARAMETER Card) is printed along with the current number of iterations. A print- out of the current problem status is shown in Figure 2. A. 2. This print- out is explained in Section 2.3.3 PARAMETER Card PROBLEM STATUS AT ITERATIONS 50: XX -1 4 -2 21 -3 30 -3 -5 XSL 30 29 37 23 Figure 2.4.2 The print-out of a current problem status. * If the problem is completely enumerated , a message, which shows this fact, will be printed. The total number of iterations, the total number of backtracks, the number of backtracks resulted from procedure CHECKING (see Figure 2.1.1), and the time used in centiseconds (Input- Output time and initilization time are not included) are also printed. As an example, the print-out of Figure 2.4.3 shows that: (1) The problem is completely enumerated. (2) The total number of iterations is 47. (3) The total number of backtracks is 24. (4) The number of backtracks resulted from CHECKING procedure is 3. (5) The time used is 0.93 seconds. If the problem is heuristically enumerated*, a message shows this fact is printed. Beside the algorithm statistics (such as NO. OF * See Section 2.3.3 PARAMETER Card 34 PROBLEM HAS BEEN IMPLICITLY SEARCHED NO. OF ITERATIONS: 47 NO. OF BACKTRACKS: 24 NO. OF BKTRK DUE TO NEW CONDITIONS: 3 TIME USED: 93 Figure 2.4.3 The print -out printed when a problem is completely enumerated. ITERATIONS, NO. OF BACKTRACKS, NO. OF BKTRK DUE TO NEW CONDITIONS, and TIME USED) which are shown in the completely enumerated case, the number of times the program went through the procedure HEURISTIC (see Figure 2.1.1) is al- so printed. The print-out of Figure 2.4.4 shows that the problem is heu- ristically enumerated and the program went through the heuristic procedure HEURISTIC 63 times. The other statistics are similarly explained as in the completely enumerated case. PROBLEM HAS BEEN HEURISTICALLY SEARCHED (63) NO. OF ITERATIONS: 122 NO. OF BACKTRACKS: 63 NO. OF BKTRK DUE TO NEW CONDITIONS: TIME USED: 3129 Figure 2.4.4 The print -out printed when a problem is heuristically enu- merated. If the number of iterations reaches the number specified by PI, the following things will be done before the program stops. (1) A message showing that the number of iterations specified is reached is printed. (2) The problem status at the last iteration is printed. 35 (3) The algorithm statistics shown in the completely enumerated case are printed. (4) If the program went through the heuristic procedure HEURISTIC, the number of times it went through is printed. (5) The information that is needed for this problem to be started from this last iteration is punched. An example of the print-out for the case that the number of iterations reaches the number specified by PI is shown in Figure 2.4.5. NO. OF ITERATIONS SPECIFIED IS REACHED THE PROBLEM STATUS AT THE LAST ITERATION IS: XX SXL ' ' ' NO. OF ITERATIONS: 500 NO. OF BACKTRACKS: 309 NO. OF BKTRK DUE TO NEW CONDITIONS: 76 TIME USED: 1335 Figure 2.4.5 The print-out printed when the number of iterations specified is reached. 36 3. PROGRAM ILLOD-MINIC-BP Program ILLOD-MINIC-BP, an extension of the program ILLOD-MINIC-B, is developed to solve the minimal covering problem with the constraint matrix of the following special form: / i A I I I 1 A ^ ! A / (3.1) where A. is a m. x n. zero-one matrix for i = 1, 2, . ... r, C. is a ill l c x n. zero-one matrix for i = 1, 2, ..., r and the remaining parts of A consists of zero elements. A structure of the following form: / \ 1 A ' 1 I 1 1 1 1 .1 1 1 1 1 1 . A 2 • ! — \ 1 ! A J 1 1 ^ i i C 2 • i C r-li C r / (3.2) 37 is considered as a special case of the structure (3.1) , in which A is a matrix with m = 0. r Throughout this Chapter 3, we will denote n + n~ + . . . + n. - with N. for i = 2, 3, ... , r, r + 1 and, as a special case, N. is as- signed value 0. Before a problem of this type (a problem with constraint matrix A of the special structure (3.1)) to be solved by this program, the opti- mal value of the following smaller problem P : minimize x__ , . + x. T , _ + ... + X. T J N.+l N.+2 N.+ n. i x i i subject to / \ V+l x X+2 i \ Y+n, i x / X 1 \/ m i N.+ j = or 1 for j = 1, 2, ..., n. must be known for i = 1, 2, . . . , r. That is, we have to first solve pro- blem P. and obtain the optimal value Z. for each i. (In the case of x x m = 0, we set Z =0). The values Z n , Z„ ..., Z will be used as input r r 1 2 r data for this program. (See Section 3.2. INPUT). Problems P., P , ..., P can be solved by the program ILLOD-MINIC-B or by some other available programs. Variables x.. , x_, ..., x of this type problem are grouped into r groups as 38 G 1 - {X r X 2 , .... X^} G 2 = {X N 2 +1' ^2+2' ••" X N 2 +n i > G r ~ {X N +1' \ +2' ••" X N +n } r r r r The values of N„, N_, . .., N , N . = n will also be used as input data for the program (see Section 3.2. INPUT). It is shown in [3] that if ZBAR is an upper bound on the optimal r value of the given problem P, then U. = ZBAR - E Z. is an upper bound on the value of group G. for each i. That is, any feasible completion of a partial solution S with more than U. - 1 variables of group G, fixed to 1 for some i, has an objective value greater than or equal to ZBAR. Such feasible completions must be ignored since we are trying to find the minimum value. Program ILLOD-MINIC-BP will calculate an upper bound U -1 for each group G. of variables, and use these upper bounds to reduce the number of partial solutions that have to be examined in the enumera- tion. How these upper bounds are used is described in Section 3.1. The New Feature of The Program ILLOD-MINIC-BP. For the current program version of ILLOD-MINIC-BP, the value of r is limited to be smaller than or equal to 20. It can be extended to any value by a slight modification. In Section 3.1, we describe how the program ILLOD-MINIC-B is modi- fied in the program ILLOD-MINIC-BP so that ILLOD-MINIC-BP can take 39 advantage of the special structure of the constraint matrix of problem (P). In Section 3.2, the differences in preparing the input data for the program ILLOD-MINIC-BP from those for the program ILLOD-MINIC-B are described. A user of the program ILLOD-MINIC-BP has to first read Chapter 1, PROGRAM ILLOD-MINIC-B and then this chapter. 40 3.1. The New Feature of the Program ILLOD-MINIC-BP The program structure of ILLOD-MINIC-BP is shown in Figure 3.1.1, C START 3 _4l INITIALIZATION f V REDUCTION BOUNDING A. BRANCHING t 4- CHECKING X- I "> >K BACKTRACKING NK C STOP -> PRINTING • BACKTRACKING ~XZ 1 RECHECKING 7? J Figure 3.1.1 Flow diagram of the program ILLOD-MINIC-BP 41 The additional procedures and the additional flows, that do not exist in the flow diagram of ILLOD-MINIC-B , are shown by dotted line in Fig. 3.1.1. In the following, we describe how the program ILLOD-MINIC-B is modi- fied in the program ILLOD-MINIC-BP so that the program ILLOD-MINIC-BP can utilize the special structure of the constraint matrix. (1) In the INITIALIZATION procedure, program ILLOD-MINIC-B will initilize UU. = ZBAR - ZU + Z., - 1 as a bound on the value x i of G. (the greatest value of G that can provide a feasible solution with a value smaller than ZBAR) for each i, where the values of Z. , Z_, ..., Z , and ZBAR are obtained from 1 2 r the input data and ZU is calculated by ZU = Z + Z + ... + Z . r (2) In the procedures REDUCTION, BRANCHING, and BACKTRACKING, the current partial solution S is checked to see whether there are UU. variables of G. fixed to 1 in S for each i. i i If there are UU. variables of G fixed to 1 for some i, then all free variables in G. are fixed to 0. After some free variables are fixed to 0, the current subproblem may be infeasible. In this case the program control goes to the procedure BACKTRACKING. (3) When a better feasible solution is found, i.e., a better up- per bound ZBAR is found, the value of UU. is updated for each i, in the procedure PRINTING. (4) Procedure RECHECKING consists of the following steps. (a) Check the current partial solution to see if there are 42 more than UU . variables of G, fixed to 1 for some i. If 1 i there are more than UU. variables of G. fixed to 1 for l i some i, then program control goes to procedure BACKTRACK- ING, (b) Check the current partial solution to see if there are UU. variables of G. fixed to 1 for some i. If there are l l UU. variables of G. fixed to 1 for some i, then fix all l l free variables of G. to and repeat this step. If there are no UU . variables of G. fixed to 1 for each i, then l i the program control goes to procedure CHECKING. 3.2. Input The input of ILLOD-MINIC-BP is prepared in the same manner as the input of program ILLOD-MINIC-B. Several problems can be concatenated together and executed at one run. The input stream for the program is shown in the Figure 3.2.1. END t PROBLEM K Figure 3.2.1 The input stream of the program ILLOD-MINIC-BP 43 The end of the stream is denoted by a card with 'END' punched at its first three columns. The input card deck for a problem is shown in the Figure 3.2.2. c 1 DECOMPOSITION CARD PARAMETER CARD |^(M,N) CARD f TITLE CARD Figure 3.2.2 The input card deck for a problem. The TITLE card, (M,N) card and MATRIX cards are the same as those cards for the program ILLOD-MINIC-B. CONTINUATION cards, as those cards for the program ILLOD-MINIC-B, are punched by the program. 3.2.1. PARAMETER Card Seven parameters: DVSN, PI, P2, P3, NG, ZBAR, P5 are provided by this card. Starting from the far left five columns, the values of these parameters are consecutively punched on this card as shown in Figure 3.2.3. 44 1-5 6-10 11-15 16-20 21-25 26-30 31-35 DVSN PI P2 P3 NG ZBAR P5 Figure 3.2.3 PARAMETER Card Each parameter takes five columns and the value of each parameter is punched right justified in each five columns. Parameters DVSN, PI, P2, and P5 are the same as those parameters on the parameter card for the program ILLOD-MINIC-B. (1) P_3. The value P3 can only assume value or 1. It only specifies if there are CONTINUATION cards following the matrix cards in the input card deck. If there are CONTINUATION cards following, then the value of it is 1. Otherwise, the value of it is 0. (2) NG This parameter specifies the number of groups, into which the variables of the given problem are separated. If the constraint matrix of the given problem is of the structure (3.1), then the value of NG is r. (3) ZBAR This parameter specifies an upper bound on the optimal value of the given problem (P). It can be set to the value of any fea- sible solution. It can also be set to any value greater than the number of variables of the given problem. 3.2.2. DECOMPOSITION Card This card specifies how the variables of the given problem are de- composed into the NG groups. The index numbers of the last variables 45 of groups are consecutively punched on this card. Each number takes four columns and is punched right justified in the corresponding four columns. The values of these numbers must be in an increasing order. As an example, the index numbers for a given problem with constraint matrix (3.1) are N., N 3 , .... N , N + -,(=n). Only one DECOMPOSITION card is permitted in the input card deck for each problem. 3.2.3. LOCAL-OPTIMAL Card This card provides the program the optimal values Z. , Z , ..., Z of the smaller problems (P.. ) (P~) , ..., (P ) . The values of Z , Z_, ..., Z are consecutively punched on this card. Each value takes four columns and is punched right justified in the corresponding four col- umns. Only one LOCAL-OPTIMAL card is permitted in the input card deck for each problem. 3.3. Output The output and its explanation of the program ILLOD-MINIC-BP are the same as those of the program IOOD-MINIC-B, except that the informa- tion about how the given problem is decomposed, (i.e., the values of N , N3, ..., N ,-) and the values of Z , Z„, ..., Z provided in the LOCAL- OPTIMAL card are also printed. 46 4. PROGRAM ILLOD-MINIC-BS In the case of the minimal covering problem (P) , a permutation n of the variables x. , x~, ..., x of (P) is said to be a symmetric per- mutation of this problem if this permutation has the following property: if (x. ,x„, . . . ,x ) is a feasible solution of (P) , then 1 z n (n (x ) ,n (x_) , . . . ,n (x )) is also a feasible solution. Program ILLOD-MINIC-BS is an extension of the program ILLOD-MINIC-B , and can further utilize the symmetric property of a given symmetric pro- blem (problem with symmetric permutation on it) in solving this problem. For given symmetric permutations n, , n~, ..., n f of the minimal covering problem (P) , we define G (x ) to be the set of ri! n 2 ... n f * all variables to which x, can be mapped by some permutation n n. P 1 k Jfc J k-1 9 ... ° ii, , where k, p., p~. ..., p are positive integers and n-, > tu> ■'l ..., n f , I (the identity permutation) for i = 1, 2, ..., k. The following properties are proved in [3]. (1) If r\ , n 9 > •••» n f are symmetric permutations of (P) , then all variables in G (x, ) can be fixed to without n-,^ n 2 ... n f k losing a better feasible solution, in the subproblem with x, fixed to 0, after the subproblem with x, fixed to 1 is k k enumerated. (2) If n. , n 9 > ••., n f are symmetric permutations of (P) , and (P0) is the problem obtained from (P) by fixing all variables in G (x. ) to (or fixing all variables G (x ) to 1), n 1 n 2 ... n f k Q n^ 2 k Q 47 then the permutations n', ni » •••» ^f obtained by re- stricting n,» n 2 > •••> n f to (PO) are symmetric permu- tations of (PO). (3) Let (P) be a problem with symmetric permutations n-. Ho* ..., n f . Then for any given x , the last updated permu- 1 k tations n_ , n„, ... n*. Then for any given x , the last up- 1 I r *q dated permutations n , ru> •••» n f » denoted by n-i > t^* ..., f| , of the following FG (Finding G- - - (x )) £ ri-. Ho • • • ^f k q procedure are symmetric permutations of (P) . Procedure FG (x, ) : k (a) H <- empty, D ■*■ {x } , Dl -*- empty. k o (b) For each i = 1, 2, ..., f and each x in D, do the following: (b.i) x s - n t (x v ) (b.2) If x is not a variable of H or D and a does s s not dominate a for any x in H or D, then store x in Dl. s (b.3) If x is not a variable of H or D and a dom- s s inates a for some x in H or D, then update t t r). to r) . defined as - n. (x d ) , if x d + x u , x v , where x is the variable such that n. (x ) = x . u l u t * For the word "restricting," see [3], 48 (c) H «e H UNION D, D «- Dl, Dl «- empty. (d) If D is empty, then procedure terminiates. Otherwise, go to step (b). • (4) Let (P) be a problem with symmetric permutations n-, » ru> •••> r l f Then the following GDCDP (General Dominated Column Deleting Pro- cedure) can be applied to reduce problem (P) . Procedure GDCDP : (a) Delete dominating rows from the constraint matrix A. (b) Find a dominated column a, . If no dominated column k o is found, then the procedure terminates. (c) Apply the FG procedure to x . (Note that r\ , n 9 » •••> f) f k are updated to r\ , n 9 , ..., fi in this step.) (d) Delete all columns with their corresponding variables in G- - - (x, ) to 0. (e) Update r^, n 2 » •••» H f to nj, n^ •••> H^, which are ob- tained by restricting r\ , n 9 » •••, n f to the problem reduced at step (4) and then go to step (1) . If (PI) is the reduced problem obtained by applying the GDCDP procedure to (P), then the last updated permutations r\ , n 9 , . . . , n f are symmetric permutations of (PI) . (5) Let (P) be a problem with symmetric permutations ri-,,n 9 ) •••> n f . Then the following procedure GECFP (General Essential Column Finding Procedure) can be applied to reduce problem (P) . Procedure GECFP : (a) Find an essential column a, of the constraint matrix. k o If no essential column exists, then the procedure 49 terminates. (b) Fix all variables in G (x ) to 1 and delete n x i\ 2 .-. n f k all rows covered by columns which have their correspon- ding variables in G (x. ). n l n 2 •'• n f k (c) Update n,, n 2 > •••» n f to r|-J» n 2 > •••» n f obtained by re- stricting n, , ti 9> •••» n f to this reduced problem (pro- n 1 n 2 ... n f blem obtained by fixing all variables in G (x, ) to 1) and go to step 1. * k Let (P2) be the reduced problem obtained by applying the GECFP pro- cedure to problem (P) . Then the last updated permutation n-i > n ? > . . . , ri f are symmetric permutations of (P2) . Program ILLOD-MINIC-BS will utilize the above properties during the implicit enumeration. So the number of partial solution that have to be examined in solving a problem with symmetric permutations by ILLOD-MINIC- BS is much more reduced, compared with the number of partial solutions that have to be examined by ILLOD-MINIC-B. In Section 4.1, we describe how the program ILLOD-MINIC-B is modi- fied in the program ILLOD-MINIC-BS so that the program ILLOD-MINIC-BS can utilize the symmetric property of a symmetric problem (a problem with some symmetric permutations on it). In Section 4.2, the differ- ences in preparing the input data for the program ILLOD-MINIC-BS from that for the program ILLOD-MINIC-B are described. A user of program ILLOD-MINIC-BS has to read Chapter 2 PROGRAM ILLOD-MINIC-B prior to this chapter. The current version of ILLOD-MINIC-BS can handle problems with a number of symmetric permutations up to 21. This number can be extended 50 to any value by a slight modification of the source program. 4.1. Modification of ILLOD-MINIC-B — The Program Structure of ILLOD- MINIC-BS The structure of the program ILLOD-MINIC-BS is shown in Fig. 4.1.1, I PRINTING WL C START -> C D J±L INITIALIZATION *- REDUCTION A BOUNDING _it: BRANCHING 2k. CHECKING BACKTRACKING TRNF STOP 3 ,J Figure 4.1.1 Flow diagram of the program ILLOD-MINIC-BS 51 This diagram is different from the flow diagram for the ILLOD-MINIC- B in that there is no heuristic procedure implemented in the program ILLOD-MINIC-BS and that there is the additional transformation proce- dure TRNF implemented in ILLOD-MINIC-BS. When the level number of a subproblem exceeds the default value, 30, the program will give a mess- age showing this fact, print a feasible solution found by a special routine, and stop its execution. A solution X = (x n ,x_,..,x ) is said to be of better form than an- I 2. n other solution X' = (x' ,x' , . . . ,x' ) if the values of these two solutions I 2. n are the same and m n m n E E a. x.> E E a! x!, i=l j=l X j J i=l j=l X j J where a!.s are the elements of the constraint matrix A (if the problem ij is the minimization problem of a switching function, then a solution of better form means a solution of fewer literals). The TRNF proce- dure will try to transform the best solution (the feasible solution • with the smallest value) obtained into another best solution of a bet- ter form before the program stops. The following are the modifications made in the program ILLOD- MINIC-BS so that ILLOD-MINIC-BS can utilize the symmetric property of a given symmetric problem. 4.1.1. The Order of Applying The Three Reduction Operations The order of applying the three reduction operations in Section 2.1.2 [4] in the REDUCTION procedure is changed. The REDUCTION pro- cedure used in the program ILLOD-MINIC-BS is: 52 4.1.1.1 Perform the GDCDP procedure (Consider the identity per- mutation as the only symmetric permutation of a problem if there is no symmetric permutation for this problem) . 4.1.1.2 Find all essential columns and fix all their correspond- ing variables to 1. If the constraint matrix is null, then the program control goes to the PRINTING procedure. 4.1.1.3 If no essential column is found in step 4.1.1.2, then the program control goes to the BOUNDING procedure. Other- wise, program control goes to step 4.1.1.1. 4.1.2. Setting More Variables To Zero During Program Backtracking Letting x be the variable corresponding to which a subproblem k o has just been enumerated and n-, > 1 9 > • ••> n f be symmetric permutations of the current subproblem, then all the variables in G n 1 n 2 • • • n f (x ) are set to instead of setting the variables x to (see k step 2.1.8.3 of the program ILLOD-MINIC-B) , when the program back- tracks. (Consider the identity permutation as the only symmetric per- mutation for this subproblem if there is no svmmetric permutation for this subproblem) . 4.1.3. Keeping Track Of Symmetric Property of Subproblem A two dimensional array, SYSW, is used to keep track of whether a given permutation r\ . is a symmetric permutation of the k-th level subproblem in stack XSL. SYSW(k,i) = 1 means that n . is a symmetric permutation of the k-th level subproblem, and SYSW(k,i) = means that n . is not a symmetric permutation of the k-th level subproblem. The following is the properties used in the program ILLOD-MINIC-BS to decide whether a subproblem is symmetric under a given permuta- tion n . . 53 (1) If the problem (P) is not symmetric under n . » then not every subproblem of (P) is symmetric under n . . (For the sake of convenience, we regard every subproblem of (P) is not sym- metric under n , , if (P) is not symmetric under n . • ) (2) If the problem (P) is symmetric under n . , and n. (x ) ^ x , i l k Q k Q then the subproblem of (P) obtained by fixing x to 1 is not symmetric under n . ■ (3) If the problem (P) is symmetric under n. and r\ (x ) = x , l 1 R Q k Q then the subproblem of (P) obtained by fixing x to 1 is symmetric under n! obtained by restricting n. to this reduced problem. (The symmetric property of n! is seen from the pro- perty (2) stated in Chapter 4.) (4) If T) , n , . .., r\ are symmetric permutations of (P) , then after fixing all the variables in G (x, ) to x] ± n 2 . . . n f k Q (in the procedure BACKTRACKING), the permutations n{» ni* ..., nir obtained by restricting r\ , n ? , •••, H-; on the re- duced problem (P') are symmetric permutations of (P 1 ). 4.1.4. Storing The Original Symmetric Permutation When It Is Updated When a symmetric permutation of n. is updated to n. in the proce- dure GDCDP , this update is stored as entry (i, v, t, u, s, I ) , where i is the index of the symmetric permutation of n , £ is the level number of the current subproblem, and s, t, u, v are the indices of variables x , x , x , x such that s t u v (1) n, (x u ) = v (2) n± (x u ) = V 54 (3) n. = X n(x d ) if d t u, V V >■ X . t when this £-level subproblem is implicitly enumerated, entry (i, v, t, u, s, I) can be retrieved, and the programs returns n. to n . • 4.2. Input The input can be prepared in the same manner as the input of the ILLOD-MINIC-B. Several problems can be concatenated together and exe- cuted at one run (see Figure 2.3.1). The input card deck for each problem is shown in the Figure 4.2.1, The TITLE card, (M,N) card, and MATRIX cards are the same as those for the program ILLOD-MINIC-B. CONTINUATION cards, which are the same as those for the program ILLOD-MINIC-B, are punched by the program. OPTIONAL Figure 4.2.1 The input card deck for a problem. 55 4.2.1.1. PARAMETER Card Six parameters: DVSN, PI, P2, P3, NFSN, P5 are provided by this card. Starting from the far left five columns, these six parameters are senquen- tially punched on this card as shown in the Figure 4.2.2. Each parameter takes five columns and the value of each parameter is punched right justi- fied in the corresponding give columns. 1-5 6-10 11-15 16-20 21-25 26-30 / 1 DVSN PI P2 P3 NSFN P5 Figure 4.2.2 PARAMETER Card Parameters DVSN, PI, P2, P5 provide the same information for the program ILLOD-MINIC-BS as those parameters provide for the program ILLOD- MINIC-B. The value of P3 is or 1. If there are CONTINUATION cards following the matrix card in the input card deck, then the value of it is 1. Otherwise, the value of it is 0. Parameter NSFN provides the pro- gram with the number of symmetric permutations (not the number of SYMME- TRIC-FUNCTION cards). The value of this parameter is the number it pro- vides. If the value is or negative, then there will be no SYMMETRIC- FUNCTION card in the input card deck. 4.1.1.2. SYMMETRIC-FUNCTION Cards These cards provide symmetric permutations for the program. In the program, each symmetric permutation n is represented by a number sequence n(l), n(2), ..., n(N), where n(i) is the index of the variable x. 56 such that x. = n(x.). So, for each symmetric permutation n, numbers n(l), n(2), ..., n(N), are sequentially punched on those SYMMETRIC^ FUNCTION cards. Starting from the far left four columns, each n (i) takes four columns (right justified in these four columns). Each card can only provide twenty numbers. n(l) must be in the first 4 columns; n(2) must be in the second 4 columns, etc. If N is greater than 20, then more than one SYMMETRIC-FUNCTION card is needed and n(21) must be in the first 4 colums of this second card. (The number of cards needed for each symmetric permutation depends on N) . If there are more than one symmetric permutation provided, the number sequence n(l)> n(2), ..., n(N) of a new symmetric permutation must start from a new card. As an example, a symmetric permutation ri defined by n = ( 1 — — ► 4, L ' J> o ■> C\ J ) D, /. .\ 1 4 "* -L> r. . -\ 9 D y *-> f ■ .* 1 -> J, 7 . . ^ 7 / ' 1 > o i P o '■> O, y > 1U, 1 o i o J.U y» is provided by the card shown in Figure 4.2.3. 10 Figure 4.2.3 An example of a SYMMETRIC -FUNCTION card 57 4.3 Output In addition to the print-out for the program ILLOD-MINIC-B, the number sequence n (1) , n(2), ..., r)(n) for each symmetric permutation provided by the user are printed at the beginning. Before the program stops, the best solution obtained before the TRNF procedure and the best solution obtained after the TRNF procedure are printed. The ex- planation of the print-out is exactly the same as that printed when a better feasible solution is found in the program ILLOD-MINIC-B. 58 5. PROGRAM ILLOD-MINIC-BA This program finds all optimal solutions for the minimal covering problem. The algorithm used in this program is a straightforward ap- plication of the branch-and-bound algorithm, in which no dominated col- umn is deleted and no E-set is tested. 5.1. Program Description The flow diagram of this program is shown in Figure 5.1.1. This flow diagram is different from that for the program ILLOD-MINIC-B in that there are no CHECKING and HEURISTIC procedures in the diagram. Since all optimal solutions are desired, dominated columns are not de- leted in the REDUCTION procedure and the condition 'ZBAR-ZMIN <_ DVSN' tested in the BOUNDING and BACKTRACKING procedures (See Sections 2.1.3 and 2.1.8) is replaced by 'ZBAR-ZMIN < 0'. Since no E-set is tested in the program, the REDUCTION, BRANCHING, and BACKTRACKING procedures are much more simplified. 5.2. Input The preparation of the input data for the program ILLOD-MINIC-BA is exactly the same as that for the program ILLOD-MINIC-BS , except that the parameter DVSN in the PARAMETER card is replaced by another parameter ZBAR, which specifies an upper bound for the optimal value. The value specified for ZBAR must be a positive integer. If a non-positive in- teger is specified, a high value 3000 is assumed by the program. 59 ( START 3 1 PRINTING INTIALIZATION REDUCTION BOUNDING BRANCHING BACKTRACKING C STOP ) Figure 5.1.1 Flow diagram of the program ILLOD-MINIC-BA 60 5.3 Output In addition to the output printed by the program ILLOD-MINIC-B, whenever a feasible solution comparable to the incumbent (a feasible solution X.. is said to be comparable to another feasible solution X 9 if the value of X.. is equal to the value of X„) is found, it will be printed immediately in the same way as a better feasible solution is printed when it is found in the program ILLOD-MINIC-B. 61 6. PROGRAM ILLOD-MINIC-BG This program finds an optimal solution for the generalized minimal covering problem. The generalized minimal covering problem is differ- ent from the minimal covering problem in that the coefficients of the objective function in the generalized minimal covering problem can be any non-negative integers, whereas those in the minimal covering pro- blem are or 1. The algorithm used in this program is an algorithm modified from the algorithm used in the program ILLOD-MINIC-B . So it also has the same properties as those in Chapter 2 for the program ILLOD-MINIC-B . 6.1. Program Description Since the algorithm used in this program is modified from the al- gorithm used in the program ILLOD-MINIC-B, it has the same program structure as the program ILLOD-MINIC-B. The operation 2 of the three reduction operations used in the REDUCTION procedure in Section 2.1.2 is modified in the program ILLOD-MINIC-BG as follows. Operation 2'. If column a. is dominated by column a. and c. < c., then column a. is deleted from the matrix and the variable x. is fixed J J to 0, where c. and c. are coefficients of variables x. and x. in the i J i 3 objective function, respectively. The method used in the BOUNDING or BACKTRACKING procedure for finding a lower bound ZMIN of a current subproblem is modified as fol- lows. 62 c . For each free variable x., let g. = /„ , where I is the J J j J number of non-zero elements in column i and c. is the coefficient J of the variable x. in the objective function. Arrange g!s in an ascending order: 8 i - 8 i 1 8 i J l J 2 J p Let h be the number of non-deleted rows and p be the greatest in- teger such that I. + . ... + Jt. < h. J l J 2 J r Then ZMIN is calculated by ZMIN =c. + c +...+C. + w, J I JO J T- where w is the value of the current partial solution S, i . e . , w = 1 c, x, . k k x, es k The BRANCHING procedure is modified in the program ILLOD-MINIC-BG such that among all the subproblems in the same level (subproblems gen- erated at step 2.1.4.2), the one corresponding to a column with the smallest cost is considered first (the cost of a column is the coeffi- cient of the variable corresponding to that column in the objective function). The criterion used in step 2.1.4.1 for choosing a row con- sists of the following steps: 2.1.4.1.1 For each row in the constraint matrix, find the small- est cost among all the costs of the columns covered by that row. This smallest cost will be referred to as "the choosing weight" for that row. 63 2.1.4.1. 2 Choose the row with the smallest choosing weight among all non-deleted rows. By using this modified BRANCHING procedure, the E-set mentioned in Section 2.1.8 can still be generated and tested in the program ILLOD- MINIC-BG for each subproblem, as it is generated and tested in the pro- gram ILLOD-MINIC-B. In the program ILLOD-MINIC-BG , we further test the reducibility of a partial solution for a subproblem, if there is no E-set generated for that subproblem. To test the reducibility of a partial solution for a subproblem, we first generate the set of rows covered by the column, corresponding to which that subproblem is gen- erated, as a testing set. Then this testing set can be tested in the CHECKING procedure as the E-set is tested. The criterion used for choosing a column in step 2.1.6.1 is modi- fied in the program ILLOD-MINIC-BG as follows: c . 2.1.6.1 .1 For each non-deleted column i, calculate w. = / , 1 v. l where c. is the cost of column i and v. is the number of i l non-zero element in column i. 2.1.6.1.2 Choose the column i. with the smallest w. among all non- i Q deleted columns. 6.2. Input Similar to the input of the program ILLOD-MINIC-B, several problems can be concatenated and executed at one run (see Figure 2.3.1). The in- put card deck for each problem is shown in Figure 6.2.1. Except the 64 OPTIONAL / (M,N) CARD / TITLE CARD Figure 6.2.1 The input card deck for a problem COST cards, all other cards are the same as those for the program ILLOD- MINIC-B. COST cards provide the coefficients of the objective function for the program. The coefficients c. , c„, ..., c are sequentially 1 I n punched on these cards, occupying four columns for each coefficient. Starting from column 1 through column 72, each COST card can only pro- vide 18 coefficients for the program. The number of COST cards needed for a problem is a function of N, the number of variables. If 1 <_ N <^ 18, then one card is sufficient. If 19 <_ N <_ 36 then there must be two cards. The number of COST cards needed can be expressed by No. of cards needed = TN/181 , where [xl is the smallest integer greater than x. Coefficient c must be in the first 4 columns of the first card; coefficient c_ must be in the second 4 colums of the first card, etc. Each coefficient must be 65 right-justified in the 4 columns assigned to it. 6.3. Output In addition to the print-out printed by the program ILLOD-MINIC-B , the cost of each variable provided by the COST cards is printed at the beginning of the program. All other outputs of this program are similar- ly explained as in the case of the program ILLOD-MINIC-B. 66 REFERENCES [1] R. Cutler, "MINSUM: A Library of Subroutines for Finding Irredun- dant Disjunctive Forms or Minimal Sums for Switching Functions- Reference Manual," to appear as a Department Report, Department of Computer Science, University of Illinois, Urbana-Champaign. [2] M. H. Young and R. B. Cutler, "Program Manual for the Programs ILLOD-MINSUM-CBGM, To Derive Minimal Sums or Irredundant Disjunc- tive Forms For Switching Functions," to appear as a report of Computer Science, University of Illinois, Urbana-Champaign. [3] M. H. Young, Ph.D. Thesis, Department of Computer Science, Univer- sity of Illinois, Urbana, Champaign. [4] McCluskey, E. J., "Introduction to the Theory of Switching Circuits," McGraw-Hill (1965), pp. 146-157. [5] T. Ibarki, T. K. Liu, C. R. Baugh and S. Muroga, "An Implicit Enum- eration Program for Aero-One Integer Programming," International Journal of Computer and Information Science, Vol. 1, No. 1, March, 1972, pp. 75-92. APPENDIX I. PROGRAM LISTING OF ILLOD-MINIC-BS 67 1. BKTRK: 2 . CHOOSE : 3. 4. CLTORW: COLRON: DCLM: 6. DELR: 7. DROW: 8. DGSET: 9. ESSENT: We first explain subroutines used in the program. This subroutine deletes the current subproblem and gets a subproblem 1-level higher in XSL as the current sub- problem. Before it returns to the main program, vari- ables in G (x. ) are fixed to in the cur- n 1 n 2 ... n f k Q rent subproblem, where x is just deleted. k o This subroutine chooses a variable to be fixed to 1 for the heuristic procedure HURIST. This subroutine stores the constraint matrix row-wise. This subroutine deletes dominated columns by checking the dominating relationship between each pair of columns, This subroutine deletes dominated columns by checking only columns that need be checked again. This subroutine deletes dominating rows after the pro- gram backtracks (returns from the subroutine BKTRK) , and generates a testing set by calling the subroutine GENW. This subroutine deletes dominating rows by checking only rows that need to be checked again. This subroutine generates G v given variable x . k o (x. ) for a n 1 n 2 ... n f k Q This subroutine finds essential columns and fixes the corresponding variables to 1 by examining rows that need to be examined. 68 10. FAFECL: 11. FLBD: 12. GENW: 13. GSET: 14. HESENT: 15. HURIST: 16. INITL: 17. NEWCON: 18. NSBP: 19. PICK: 20. PMTRX: This subroutine finds essential columns and fixes the corresponding variables to 1 by examining all rows. This subroutine finds a lower bound for the current subproblem. This subroutine generates testing sets for the next subproblem to be considered. This subroutine modifies symmetric permutations n 1 »n 2 » ••■! n f . to n 1 n 2 • • • » n f and generates \n 2 ...V f (x k ) for a given x fc . This subroutine finds essential columns and fixes the corresponding variables for the heuristic pro- cedure HURIST. This subroutine solves the current subproblem by a heuristic procedure. This subroutine initializes the value of each param- eter. This subroutine will check if any of the testing sets satisfies the backtracking condition. If some testing set satisfies the backtracking condition, then the program backtracks. This subroutine generates a new subproblem to be considered. This subroutine picks a row for branching operation. This subroutine prints the constraint matrix column by column. 69 21. PNCH: This subroutine punches intermediate result when the number of iterations specified is reached. 22. READ IN: This subroutine reads in the constraint matrix column by column or row by row, by calling subroutine ROWIN. 23. ROWIN: This subroutine reads in the constraint matrix row by row. 24. ROWLN: This subroutine deletes dominating rows by checking each pair of rows. 25. RWTOCL: This subroutine stores the constraint matrix column- wise. 26. SETCON: This subroutine reads in the continuation cards and sets up the continuation condition. 27. STRSUB: This subroutine generates subproblems based on the row chosen by the subroutine PICK and stores all subpro- blems just generated. 28. TRNF: This subroutine transforms the best solution obtained into a better form before the program stops. Following is the program listings of the five programs KOPTI AN IV LEVEL 21 MAIN DATE = 77259 IK 1.1 0002 00 3 ooou O0O5 OCof> 001,7 OU'O o«: i 9 CC10 0011 Oi i j oOiu 0C1? 0016 0017 OOiP 0919. OOA 00 21 0022 00 * J 00^4 00 t 5 THIS LFOGRAM IS IMPLEMENTED TC SOLVE MINIMAL COVt WITH SYMMETRIC PERMUTATIONS DbFINfcD IB THE AU1 THESIS THE BASIC ALGORITHM USED IN THIS PROGRAM IS THE Z IMPLICIT ENUMERATION AUTHOR:MINS HUEI TOUNG MAIN TPOGRAM IMPLICIT INTEGER*2(A-Z) INTEGER*!! NTH,NBK,TIMEl,TinE2,TlflE3 RFAL*U TL1 .TL2.EMK COMMON MP1 (50) ,MR2 (50) ,YY (33 0) ,MM1 (33 0) ,MM2 (3 00) , ROW PKLT (30,331) ,CLLT (30, 301) ,RWPT (J31) ,CLPT (301) STK(jO) ,STKLBD(30) , XX (UOO) ,XSL (180) ,STKX0(30) CKT (300) . KV,XP,,JX,INCUMB(300) , PKE Y , ZBAR ,ZH IN , JAD.N, N, UVSN,P1 ,P2. P3 , PPU ,C HEA D, J P, .10, JOO, JU , , FN (21 ,300) , KO.IISET (200) , NSFN.D1, D2, D3.SYSW (3 DIMENSION TL2(19) CA1A EMK/'END '/ 1 CONTINUE READ TITLE CARD, IF TITLE IS 'END' GO TO STOP PEAL>(5,60) TL1.TL2 60 FOPMAT (At, 19 AH) WRITE (6,2) TL1.TL2 2 FOFMAT (/,1X,AU,19 AU) •IS HIE END CARD FOUND? IF (T11 .EO. EMK) GO TO 500 (inK=(J STF=1 TIME3=0 NF=0 CAIL BEADIH (61) IF (F1 .Lt. 10) P1^200 -PRINT THE CONSTRAINT MATRIX CALL FUTia -INITIALIZE SOME PARAMETERS t CAII It.iTL HCT- P2 IF (P3 . hO.1) JO TO 2b CAIL STEFZ(TlMFl) -HErULilOS! AT THE FIRST ITERATION CAIL RCWLN CALL CCLPN 9 15/59/27 MM 100 MM 200 RING PROBLEMS MM 300 HOR'S PH. D. MM uoo MM 500 EPO-ONE MM 600 MM 700 MM 800 MM 900 MM 1000 MM 1100 MM 1200 MM 1300 MM 1400 MM «500 MM 1600 MM 1700 (4000) ,COL (UOOO) ,MM 1800 ,CCHA1N (301) , MM 1900 ,X0(500) XU (200) ,MM 2000 LEVEL, MN 2100 B1 MM 2200 0,21) MM 2300 MM 2400 MM 2500 MM 2600 MM 2700 MM 2800 MM 2900 MM 3000 MM 3100 MM 3200 ,1M 3300 MM 3U0O MM 3500 MM 3600 MM 3700 MM 3800 MM 3900 MM UOOO MM 14100 HH 14 7.00 MK '4 300 MM 1414OO MM 145J0 MM '4 00 MM U7u0 MM I480U MM 14900 MM SO JO MM 5 100 MM 5200 MM 5 3 00 MM 31400 MM 5500 MM 5600 MM 57J0 11 M 5 8 00 MM 5900 LEVEL 21 MAIN DATE = 77259 CALL FAFECL(R300,fi200) C C A.-f THERE SOME COLUMN NEED 10 BE CHECKED AGAIN? C IF (CCIIAIN ICHEADI . EO . -1) GO TO 1 H GO TO 8 r C FIND AND FIX ESSENTIAL COLUMN TO ONE C 11 CALL ESSFNT (F.3C0,6200) C C ARE THERE SOME COLUMN NEED 10 BE CHECKED AGAIN? C IF (CCHAItl (CHEAD) .Eg. -1) GO TO 1 « 8 CONTINUE C C DELETE DOMINATED COLUMN C CA1L DCLM C C ARE THERE SOME COLUMN DBLETED? C IF | K P .GT. 0) GO TO 11 C C NEED SOME COLUMN BE CHECKED AGAIN? C CEND=CHEAD CO 13 1-1, » IF |N('.2(I) .EQ. 0) GO TO 13 CCHAIN (CEND) =1 CEND=I MM2 (11=0 13 CONTINUE IF (LEND .EO. CHEAD) GO TO 1<4 GO TC 8 C r 1U CALL STEPZ (TIME2) TT=TIME I-TIME2 IIHB3-=TIHE3»TT r c PRINT THE REDUCED M AND N r PM=0 DO lb 1=1, H IF (FWLT (LEVEL, I) .Lfc. 0) GO 10 16 PM=RH»1 16 CONTINUE RH = U EO 18 1=1, N IF (CLI1 (LEVEL, 1) .LE. 0) GO TO IH RN=FN+1 18 COBTIHUE WnilF(e,13) RN.hH,TIME3 I" FOP:iAi (/, IX, 'COt. STIvAlNT MAriU> SIZE. AFTER FIRST REDUCTION * ID,' h'.'.lU,/,' TIME USED:',IU) CALL STEPZ(Iinkl) GO TC U? 15/59/27 MM 6000 MM 6100 MM 6200 MM 6300 MM 6U00 MM 6500 MM 6600 MM 6700 MM 6800 MM 6900 MM 7C00 MM 7100 MM 7200 MM 7300 MM 7U00 MM 7500 MM 7600 MM 7700 MM 7800 MM 7900 MM 8000 MM 8100 MM 8200 MM 8300 MM 8U00 MM 8500 MM 8600 MM 8700 NM 8800 MM 8900 MM 9000 MM 9)00 MM 9200 MM 9300 MM 9«00 MM 9500 MM 9600 MM 9700 MM 9800 MM 9') 00 MM 10000 MM 10100 MM 10200 MM 10300 MM 10100 MM 10500 MM lObOO Nil 10700 MM 10H00 MM 10900 MM 1 1000 MM 11100 MM 1 I200 MM 11310 »:•, MM 1 UOO 11 M 11SJ0 Ml 11600 MM 1 1700 MM 118'jJ 71 FflRlhAN IV 13 LEVEL 21 MAIN DATE = 77259 PF.AD THE CONTINUATION CARDS OOIjO 0061 00o2 00u3 OOhlt OOub 0066 00b7 0060 0C6 9 GU7G 00 71 0072 00 7 3 0074 00 7 5 0076 C077 0076 0f'7y 00 nO OiiiH 00 8? 0CH3 ooe« 00 D5 00 St 00 II 7 0008 0009 00°0 00'<1 0092 00 <3 00? n 0o*5 00- b oo n 00 9 B 0099 01 00 2? CONTINUE CALL SETCOH CALL 3TEPZ (TINE1) 100 CONTINUE NTR=NTR*1 THE RtDUCIlON PROCEDURE AFTER THE 1ST ITERATION CALL DCLM IF (KP .LE. 0) GO TO 42 .10 CALL ESSENT (S)CC,S200) IF (CCHAIN (CHEAD) .EO. -11 GO TO 42 32 CALL DCLM IF (Kt .GT. 0) GO TO 30 4 CONTINUE CFND=CHKAD CO U1 1 = 1, N IF IHM2 (I) .EQ. 0) GO TO U1 CCHAIN (CEND) =1 CEND=I MM2 (I)=0 41 CONTINUE IF (CLND .EO. CHEAD) GO TO 42 GO 10 32 -TEST IMF LOWER BOUND OF THE CURRENT SUBPROB 4 2 CONTINUE CALL Finn IF (ZBAR-ZMIN .LE. DVSN) GO TO 300 IF (LEVIL .LT. 3U) GO TO 44 LEVEL LIBIT IS REACHED, USE HEURISTIC METHOD KFJTE (6,43) 43 FOFKAT (/,1X, •****♦**♦ **LEVr;L LIBIT 30 IS REACHED, HEUP1S ♦IS USED**********') CALL HUHIST NF=1 WRITE (6,5) NF WRITE (6.10) (XSL (H) ,11=1 ,XP) DO 4*"- H~1,XP 46 IliCOBP. (H)=JE5I. (H) 7. n » R = X V WRITE (6,473) ZBAri 47-> FuFMAT (1 X, 'ZUAt' : ' ,14) C .A I L 1 Ml F HRI1L (P ,47) (INCUMIMH) ,li= I ,ZBA1') 47 FOFKAT (//,M,' SOLUTION OBTAINED AFiEP THE TRANSFORMATION * ( r X , J C 14)) W?ITE (6.U73) 7.PAR ;c TC 1 15/59/27 mm i 1900 BB 1 2000 MB - 2100 MM ' 2200 Bt1 ' 2 300 BB ' 2 400 BB ' 2500 BB ' 2600 BB 2700 BB 12800 BB ' 2900 BB 1 )000 BB 1 3100 BB ' 3200 BB 3300 BB 3400 MB ' 3500 MM M600 MM ' I3700 MM 1 3800 BB ' I3900 HM ' I4000 BB 14100 BB I4200 HH 1 4 3 00 MM ' 4 4 00 MM I4500 BB I4600 BM I4700 MB 1 4 800 BB 1 '1900 BM 15000 MM 15100 MM I5200 BM I5300 BM I5400 BM I5500 MM I5O00 MM I5700 MM I5600 MM I 5900 MM I -'.000 TIC MET1IODMH 16100 MM I6200 MM I6300 MM I6400 MM Ib500 MM »f)600 MM I 6700 MM I6800 MM I 6900 MM ! 7000 MM 17100 MM 17200 BM 17300 :'./. MM 17400 MM 17500 NH 17 (.00 MM 17700 72 FOI'TUN IV G LEVFL 21 NAIN DATE = 77259 OKI 44 CONTINUE c c- c 0102 OK3 0104 OloS STKLBC(LEVFL) = ZMIN 45 CONTINUE STKXO(LEVEL)=JO STK (LEVEL) = XP Cl0<- 01 Ol o ice 01 C«J 0110 uit I 1 1 ^ oi n 01 14 P1I5 0116 Oi 17 01)0 Olio 012L CU1 0122 OIJ 01 2U 0125 01 t h 0127 OUb 0U° 0'3L (j 1 3 i 0U< 0Ij3 013». C FICK A BOH FOR BRANCHING OPERATION C CALL FICK C C STCHE AIL SU8PP0BLEHS THAT NEED TO BE CONSIDERED C CALL STRSUB C C GET THK NEXT SIIBPROB TO BE CONSIDERED 150 CALL »SBP(f.3o0, 6200, SHOO) IF (NTP . ;E. P1) -10 TO 450 IF (N1F .NE. NCT ) GO TO 100 FRINT THE CURRENT PARTIAL SOLUTION CALL STCFZ (TIME2) 1T=TIME1-TIME2 TIKE3 = lIME3n'T WRITE(6.?20) NCT 220 FCRMAT (//,1X, 'PROBLEM STATUS AT ITEHATION ',16,/) HPITE (6.230) (XX (L) ,L = 1,JX) 330 FORMAT (1i, 'XX: ', (3X ,30 14)) HPITE (6,240) (XSL(L) ,L=1,XF) 240 FORMAT (IX, 'XSL: • , (2X,30 14)) NCT=HCT+P2 WRITF(b,410) TIHE3 CJLL STEPZ (TIMEl J GO TO 100 c 200 COMINUE SOLUTION IS FOUNC c STORE THIJ FEASIBLE SOLUTION DO 22l li = 1,XP 221 INCUI"P(H)=aSL (H) CALL STEPZ (TI11E2) TT=Ti!1F1-TIHE2 TIFL3 = TIt'E3 + TT c--- C --PRINT ttiSiBLE SOLUTION FOUND, UPDATE ZIUR ZBAP^XP NF=NF+1 WRITE (*,5) NF 5 FOFHAT (//IS, 'FEASIBLE SOLUTION FOUND' , 14, «:', /) WHITE (6.IC) (>SL (I) ,1=1 ,XP) 15/59/27 MM 17800 HH 17900 Hfl 18000 nn 18100 nn 18200 mm 18300 MH 18400 tin 18500 nn 18600 MM 18700 MM 18000 HH 18900 MM 19000 MM 19100 nn 19200 MM 19300 MM 19 400 UN 19500 nn 19600 MM 19700 MM 1 )800 MM 19900 MM 20000 nn 20100 nn 20200 nn 20300 MM 20400 MM 20500 nn 2J600 nn 20700 nn 20800 nn 20900 nn 21000 MM 21100 MM 21200 MM 21300 MM 21400 MM 21500 MM 21600 MM 21700 MM 21800 MM 219)0 MM 22000 MM 22100 MM 22200 MH 22300 MM 22400 MM 225U0 MM 22600 MM 22790 MM 228j0 MM 22900 MM 23000 MH 23100 Hfl 232u0 MM 23JOO MM 23400 MM 235C0 MM 2 )6C0 73 FORTRAN 0135 013 6 0137 0138 0139 01<40 01u1 IU2 IV rj LEVEL 21 MAIN DATE = 77259 15/59/27 74 10 FOFMAT (6X.30 IU) HI- T f K (6,20) ZDAR 20 FORMAT (/.1X, 'ZBAB: ' ,15) WRITE (6,203) NTR 203 FOFHM (/, ' NTH: ' ,16) WRITE (6,210) TIME3 210 FORMAT (/.U, 'TIME USED:', 16,/) CALL STEPZ (TIMF.1) »l )0 CONTINUE - — —THE CriDDITklT C II n i D*1 n TC EUMH CDlTCh PROGRAM BACKTRACKS c In r LUHrlM sDufMUB i. o fcnUnrHAItL), N8K=NCK*1 CALL PKTPK (f,400) 01143 01 'Ml 0145 C 1 « ( . LV=XX(JX-1) C GFNERATE TESTING CONDITION FOR THE NEXT SUBPROBLEM C ATI C DELETE DOMINATING ROWS, DCHINATED COLUMNS 0147 CALL Dtl.F (LV.C560) 01Uti CALL FLnn 0149 IF (ZBAR-ZM1N .LE. DVSN) GO TO 300 0150 3TKLBC (LEVEL) = 7MIN o i 51 <;o TO 1 50 0152 560 XSL (XFM) = LV 0(53 LEVEL=LFVEL»1 0154 50 TC 30C C PRC8LFM IS ENUMERATED C 015* 400 CCNTINME 015b CALL STKFZ(TIME2) 0157 WRIIF(b,408) 01 5P H08 FORMAT (//,1X, 'PROFLEM HAS BEEN IMPLICITLY SEARCHED' *,/,1X,'THE OPTIMAL SOLUTION OBTAINED :') 0159 WRITE (6,406) (I NCUM B ( H) , 11 = 1 ,ZBA R) 0160 WRITE(6.U73) ZPAR 01b1 406 FORMAT (/,6X, 3014) 01*2 rT=TIHb1-TIME2 01 h? 1IME3=TIME?*1T C C PRINT CCKPUTATIOCAL RESULT r 01b4 WRITE (6,50) N1H,IIBK 31b5 50 FOPMAT( /,1X.'N0. OF ITER AI 1CN : • , 16 ,/, 1X, • NO . OF BACKTRACK OUC . WRITE (5,410) 1IME3 0167 410 FORMAT (IX, 'TIME USED:', 16) OlbH CAIL STEPZ (IIHEI) 01b9 CALL TFHF 0170 CAIL STEFZ (TIME2) 0171 TT=TI«El-riHE2 0172 WHITE (6,470) (INCUM8 (II) ,H = I ,ZEAH) 0173 U7C FORMAT (//. IX.'TIIE SOLUTION OBTAINED AFTER THE U.7. WSFOFH ATIOH * (/,6V, 3C IU)) 0174 WRITc (6.473) ZUAP 017 5 WRIIF(6.U7i) n 0176 '471 FORMAT (//, IX, • 1 1 M i-. US5.U FOR i In. Th ABSFOBMAl IUN :*, If ,//) 15/59/27 MM 23700 MM 23800 MM 23<»00 MM 2'4 000 MM 2« 100 MM 2U200 MM 2(4300 MM 24400 MM 21500 MM 2U600 MM 21700 nn 24800 MM 24900 nn 25000 nn 25100 MM 25200 MM 25300 MM 25U00 MM 25500 nn 25600 nn 25700 MM 25800 nn 25900 MM 26000 nn 26 100 MM 26200 MM 26300 nn 26U0O MM 26500 MM 26600 MH 26700 MM 2 6800 MM 26900 MM 27000 MM 27100 MM 27200 MM 27 300 MM 271400 MM 27500 MM 27600 MM 27700 MM 27800 MM 27900 MM 29000 MM 28100 1 .16) MM 20200 MM 28 300 11 B 23400 MM 28500 MM 28600 MM 28700 Mil 28800 MM 23900 k:' , MM 29000 MM 23100 MM 2 3200 MM 21 30U MM V9U30 MM 2J500 FOBTFAN IV G LEVEL 21 MAIN DATE = 77259 15/59/27 75 C ANOTHER PROBLBM? MM 29600 C MM 29700 0177 GO TO 1 MM 29800 C MM 29900 017b 450 CONTINUE IP! 30000 C Mil 30100 C THE NO. OF ITERATIONS .SPECIFIED IS EXCEEDED MM 30200 C MM 30300 017* CAU. ilTEFZ (TIMF2) till 30400 OluC WRITE (6,460) MM 30500 0101 460 FORMAT {//,1X, 'NO. OF ITERATIONS SPKCIFIBD IS EXCEEDED 1 ,/ fill 30600 ♦ r IX, 'THE PROBLEM STATUS AT LAST ITERATION IS:',/) MM 30700 Olli;. WRITE (b, 230) (XX (H) »II = 1,JX) MM 30100 01bj WRITE 16,240) (XSL (H) , H=1 , XP) MM 30100 0IU4 WRITE (6. 407) (I NCUNB (H) ,11 = 1 ,7. BA B) MM 31000 01H5 407 FORMAT (1X, 'THE BEST SOLUTION OBTAINED SO FAR :', MM 31100 ♦ (/,6X,30I4)) MM 31200 Oloe WRITE (6,473) ZEAR MM 31300 01d7 TT = T1ME1-TIB.B2 MM 31400 OldB TIFE3=TIME3+TT MM 31500 0189 WRTTE(6,50) NTR.NBK HM 31600 0190 WRITE(6,410) TIBE3 MM 31700 C191 CALL TRNF MM 31800 0192 WRITE(6,470) (INCUMB (H) ,H = 1 , Z EAR) MM 31900 0193 KRI7.E(6,473) ZBAR MM 32000 0194 WRITE(b,471) TT , MM 32100 01?5 CALL ENCH MM 32200 0196 GO TO 1 MM 32300 C MM 32400 C END OF JOB MM 32500 0197 SOO CONTINUE MM 32600 0196 STOF MM 32700 019? F.NC MM 32800 FOFTUN IV ; LEVEL 21 DKTRK DATE = 77259 15/59/27 0001 SUPROUIINE BKTRKf*) MM 32900 C AM 33000 0002 IMPLICIT INTEGERS (A-Z) HH 33100 U0C3 COMMON nn 33200 1 MR1 (50) , HR2 (50) , YY(330) , (1 H 1 (330) , HH2 (300) ,ROK (4 300) ,C0L (4000) ,HH 3 3 300 2 RH1.T (30. 331) ,CLLT (30,301) ,KWPT (331) ,CLPT(301) ,CCHAIN(301) , (1(1 33400 3 :. 1 K (30) ,STKLRD(30) , XX (400) , ISL (1(30) ,SIKXO (30) ,XQ (500) , XU (2 00) ,HM 33500 4 CKT (300) ,KP, XP.. IX, INCUHB (300) , FKE Y , ZBA R , ZHIN . LEVEL, flfl 33bOO 5 JAD.M.N.DVSN ,P1,P2, P3,PP4,CHEAD,JP,J0,.1QQ,JU,R1 HCI 33700 6 ,FN (21 ,300) ,KC,IISBT (200) , NSFN , Ul , D2 , D3 , S Y5W (30,21) HH 33000 nn 33900 11(1 34000 nn 34 190 l\n 34200 nn 34300 nn 34400 nn 34500 nn 34600 nn 34700 nn 34030 HH 34900 nn 35000 nn 35100 IOH nn 35200 nn 35300 nn 35400 nn 35500 nn 35600 nn 35700 nn 35aoo nn 35900 nn 36000 HH 36 100 nn 36 2 00 nn 36 300 nn 36400 ttM 36500 nn 36600 nn 36700 MM 36000 nn 36900 nn 37ooo HH 3 7100 HH 37200 nn 37300 MM 3 7 400 flM 3 7 500 MM 37500 MM 37700 mm 3 7 800 nn 37joo MM 39000 MM 39100 MM 3 3 200 MM 30300 r MM 33400 004/; ZHT.II-5TKLBD (LI3VKL) MM 30500 r :1'I 3 9 600 C LHKOK THE LOWFJ HOUND AGAIN HM 30 700 0004 cnnnoN pbiif (400) ,obuf (400) 0005 C COMMON FNCH (300) ,PF 0006 310 CONTINUE 0007 PP4=0 oo ce LEVEL=LEVEL-1 001T-) KP^O < » > IF (LEVEL .EO. 0) RETURN 1 00 i 1 xp;=xp 0012 XP^.STK (LEVEL) 0013 XP1=XP+1 00 n C r - C IF (XP1 .GT. XP2) GO TO 313 •UPDATE THE CURRENT VALUE YT FOR BA OC 15 DO 314 K=XP1,TP2 ooio JV^XSL (K) 0O')7 .11=CLPT (.IV) 01' iM J2=-CLtT(JV + 1) -1 00 i 9 CO 312 .I=.)1 , J2 002C IR = RCW (,J) 00 21 YY (IP) =YY (IP) -1 01^2 312 CONTINUE 0J?3 314 CONTINUE 00 2 4 Q 313 JO^STKXO (LEVEL) c- c -UPrAIt SYMMETRIC FUNCTIONS 0025 322 IF (PF .LE. 0) GO TO 324 0026 IF (FNCII(PF) .LE. LEVEL) GO TC 32 4 0027 PF = PF- 1 CO 2b VAF1=FNCH (PF) OO^J P F = l> F - 1 OC 30 VAF2=FNCH (PF) 0C31 PF=PF- i 0012 Vfi P3 = FliCII(f F) 30 33 PF=PI -1 0034 VAPtt = FNCH(PF) 0035 EF-PF-1 003b I-FNCII (PF) 00 3 7 FN (I, VAF4) = VAR1 OojO FN (I, VAR2) =V AH3 003 9 FF=PF-i OCu GC 10 J22 0041 '2U CONTINUE FORThAN IV « LEVEL 21 PKTRK DATE = 77259 15/59/27 77 C 0C43 IF (ZDAR-ZHIN . Lfc. DVSN) GO IC 310 C c T py 10 GET THE NEXT SUBPROB TC BE CONSIDERED C 0044 315 CONTINUE 0045 LVT=-XX(JX) 0046 IF (LVI .GT. 0) GO TO 320 0047 316 JX=JX-1 G04 8 GO TO 315 0049 320 IF (LVi .EQ. LEVELED GO TO 350 0050 IF (LVT .GT. LEVELM) GO TO 370 ■THE CURRENT LEVEL SUBPROB IS ENUMERATED, TRT TO JET A SUBPROB ■WITH ONE LEVEL HIGHER C 0051 GO TO 310 005? 350 CONTINUE C C THE NEXT SUBPHCB TO BE CONSIDERED IS OBTAINED C C TEST IF THE NEXT SUBPROB IS DELETED 7 C 0053 JX1=JX-1 005H VAR=TX(JX1) 0055 IF (CLLT (LEVEL, VAP) .LE. 0) GO TO J16 005() .7V = XSL (TP+1 ) 0057 K0=JV 00:>8 CALL D JS FT C C DELETE ALL TUB CLOUMNS IN THE GENEBATBD D-SET C C0 r >5 CO 361 K=1.D3 00»U JV=HSET(K) 00t1 IF (CILT (LEVEL, J V) .LE. 0) GO TO 361 0Cu2 CLIT (LtVFL, JV)=0 Gl)h3 J1=C'LPT(JV) 0064 J2=CLPT (JV*1) -1 DO -j 5 CO 300 J = Jl ,J2 00 6 t. IF = RCW(J) 0067 IF (PWL1 (LEVKL,1R) . LE. 0) GO 10 360 DO 68 EWLT (ItVEL,IR) =F«LT (LcVEL.IF) -1 00b9 IF (DH1T (LEVEL, Ih) . EQ. 0) GO TO 310 Oj70 KF=KP*1 0071 CKT(KI)=IR C FOW II NEED [IE CHECKED AGAIN r 0072 FP4=FP4+1 0075 MMl(rt4)=IF 0174 360 CONTINUE 1/075 361 CONTINUE C C CHECK IF THE NEXT SUBPROB. TC be CONSIDERED IS Utl.LPKP C 0076 163 VAP=XS (.1X1) 0077 IF (CLLT (LEVEL, VAB) .GT. 0) GC TO j62 15/59/27 MM 38800 M 38900 fin 39000 nn 33100 nh 39200 mm 39300 nn 39i>00 11 H 39500 MH 39600 MM 39700 nn 3J800 MM 39900 nn 40000 )B nn 40100 nn 40200 nn 10300 MM 40400 MM 40500 Mn 406J0 MM U0700 nn (*0800 nn U0900 nn U1000 nn <*1100 MM 41200 MM «1300 MM itmoo nn U1500 MM 1*1600 nn 1*1700 nn 41800 MM 41900 nn 42000 MM 4 2100 MM 42200 MM 42300 MM 42400 MM 42500 MM 42600 MM 42700 MM 4 2 000 MM 42900 MM 43000 MM 43100 nn 43200 MM 43300 MM 43400 MM 43500 MM 43600 MM 4)700 MM 43P00 MM 43900 MM 44Ul>0 MM 44100 MM 4*200 MM 44300 MM 44400 MM 445O0 MM 44 6 00 FCRThAN IV 9 tFVEI 21 "TRK D»TE = 77259 c IT 15 oFlbTF.D, TRY THE NEXT ONE C .lX^.JX-2 LVT=-XX (JX) IF (LVT .LT. LEVELED GO TO 310 JX1=JX-1 GO TO 3*3 C sxcRt THE ENTRY (J. -K) FOR THE SUDPROB. JUST ENUMERATED C 362 IF (-XU(.IU) .LE. LEVEL) GO 10 365 C REMOVE ENTPY (J.-K) WITH K GREAIER THAN THE CURPENT LEVEL C JU=JU-2 •;0 TO 362 C c STORE JV 6 LEVEL C 365 CONTINUE DO 367 K=1,D3 .7V = HSET (K) JU=.U1 + 1 XU(JU)=.JV ,1U=JU-»1 XII (Jll) =-LEVBL 367 CONTINUE C RETURN C THE NEXT SUBPRCB TO BE CONSIDERED IS ALREADY IMPLICITLY c BHIIHEFATED. TRY HIE NEXT ONE C 370 JX=JX-1 LVI=-7X(.TX) IF (LVT .1ST. 0) GO TO 320 GO TO 3 70 F!1C 15/59/27 78 MM 44700 MM 44800 MM 44900 MM 45000 MM 45100 HM 45200 MM H5300 MM <*5<*00 MM 45500 MM 45600 MM 45700 MM 45B00 MM 45900 MM 46000 MM 46100 MM 46200 MM 46300 MM 46400 MM 46500 MM 46600 MM 46 700 MM 46800 MM 46900 MM 47000 MH 47100 MM 47200 MM 47300 MM 47400 MM 47500 MM 47600 MM 47700 MM 47800 MM 4 7 900 MM 49000 MM 48100 MM 48200 MM 48300 MM 49400 onriAH iv 0001 coo: OOL'3 OOuU ooor> 00 Lb 0007 OGuH 0001 00 10 00 11 0012 COI 3 00 m 00 i 5 C0I6 0u17 00 lb 00 19 00 it 0021 oc:2 0023 oo:u oo ; s CC26 oc;7 00^8 0029 LEVEL 21 CLTORW DATE 77259 SUBROUTINE CLTORU {*) 10 80 100 110 (4000 ■THIS ROUT •FY COIUMN II1FLtl.IT COUPON MH (5 RWLT ( STK (3 CKT (3 .JAD.M 11 = 1 12 = 1 RWFT (12) = IF (12 .L RETURN CONTINUE FWLT (1 ,12 CO 100 J= .11=CLPT (J J2=CLPT (J CO 00 K=J IF (hOW (K IF (HOW(K CCI (I1)=J PWI.I (1,12 11=11*1 GO TO 10C CC NT IN HE CONTINUE IF (RWLT( 12=12+1 GO 1C 10 WPITb (6, FORMAT flX RFTURN 1 BNC INE STORE HIE CONSTRAINT MATRIX PROM THE OPDEP TO THE ROW BY ROW ORDER INTEGKR*2 (A-Z) 0) ,MP2 (50) , TY (33 0) ,MM1 (330) ,MN2 (300) .ROW 30,331) ,CLLT (30,301) ,PKPT (331) ,CLPT(301) 0) ,3TKLBD (30) , XI (400) , XSL ( 160) ,STKXO (30) 00) ,KP,XP,JI,INCUMB(300) , FKEY.ZBAR.ZMIII, , N.DVSN, P1, P2, P3,PP44,CHEAD,.JP,JQ,JOO,JU, II E. M) GO TO fl )=0 1,N ) ♦ 1)-1 1 ,J2 ) .61. ) .LI. 12) GO TO 100 12) GO TO 80 )=RWLT(1,I2) »1 1 ,12) , EO. 0) GO TO 11 U000) 12 ,'THE PPOBLEfl IS INFEASIBLE, SINCE ROW, 9 15/59/27 MM U8 500 MM 1)8600 COLUMN MM l»8700 MM 4)8800 MM 448900 MM "49000 • MM 449100 (0000) ,col (44000) ,hm U9200 .CCHAIN (301) , MM 449300 ,X0(500) ,XU (200) , MM 449UOO LEVEL, MM U9500 R1 MM 1*9600 MM 449700 MM 143800 MM 449900 MM 50000 MM 50100 MM 50200 MM 50300 MM 504400 MM 50500 MM 50 600 MM 50700 MM 50800 MM 50900 MM 51000 MM 51100 MM 51200 MM 51300 MM 51400 MM 51500 MM 51600 MM 51700 MM 51800 MM 51900 1U,' IS ZERO') MM 52000 MM 52100 MM 52200 79 FORTRAN IV G LEVEL 21 COLRN DATE = 77259 000 1 SUBROUTINE COLRN C THIS ROUTINE DELETES DOMINATED COLUMN C 000* IMPLICIT IUTtGER*2 (A-Z) 00OJ CCPr.ON 1 MRl (50) ,NR2 (50) , YY (J30) ,BM1 (3 JO) , MM 2 (300) ,ROW (4000) ,COL(40 00) 2 PWLT (30,3 31) ,CLLT (30, 301) ,HWPT (331) ,CLPT (301) , CCH AIN (301 ) , 3 ?TK (3 0) ,5IKLBD(30) , XX (4 00) ,XSl (180) .STKXO (3 0) ,X0 (500) ,XU (200) ,MM 4 CKT (300) ,KP,XP,.JX,IHCUHB (300) , FK2I , ZBA R ,ZttIN, LEV EL, 5 JAD.M, N,UVSN,P1, F2, P3,PP4,CHEAD,JP, J0,JQ0,JU,R1 6 .FN (21 ,300) ,K0, HSET (2 00) ,NSrN,Dl,D2 ,D3,SYSW(30,21) r 0004 CO 60 1=1, N 0005 IF (CLLT (LEVEL, I) .LE. 0) GO TO 60 0006 I1=CLPT(I) 0007 I2 = CLPT (I*1)-1 C C FIND THE FIRST NON-DELETED RON COVERED BT COLUMN I C OCCP EO 1C J = I1 ,12 000° in=ROW (,I) 00 1 C IF (FKLT (LEVEL, IR) .GT. 0) GO TO 20 00 II 10 CONTINUE 0G1i WPITEI6.100) I 001 J 100 FOFMAK1X, 'STKANGE ROW:', Id) U01« STCP C C POfc IP IS THE FIRST NON-DELETFD ROW COVERED BY. COLUMN I C 0011; 2C K1=RKET (IB) 00)6 K2 = RWtT JIR + D-1 C C CHECK IF ANY CCLUMN COVEPED BY ROW IR DOMINATES COLUMN I C CC17 CO 40 .1 = K1 ,K2 001H IC=COL(J) 0019 IF (CUT (LEVEL, i.C) .L£. 0) GO TO 40 0020 IF (1C . FO. I) JO TO «0 C c 00 21 OlJ<.,_ L i, DELETL U,L I CIIFCK IF COLUMN IC DOMINATE J1=CLFT (IC) ,12=CLPT (IC< D-1 L = .l1 CO 30 K=II, 12 ir=i:cw (K) (F (F.WLT (LEVEL. IP) .LE. 0) G 25 CONTINUE IF (I .GT. J2) GO TO HO IF IFOV (t) . JT. IB) 5C TO 40 IF IICML) . tO. IF) GO TO 2 8 L=L*1 GO TC 2 5 2fl L=l + 1 30 CCNT1NI1F 15/59/27 MM 52300 MM 52400 MM 52500 MM 52600 MM 52700 MM 52 800 (4000) ,NM 52900 1) » MM 5J000 U (200) .MM 53100 MM 53200 MM 53 100 MM 53U00 MM 53500 MM 53600 MM 53700 MM 53800 MM 53900 MM 54000 MM 54100 MM 5U200 MM 54300 MM 54400 MM 54500 MM 54600 MM 54700 MM 54 800 MM 54 900 MM 55000 MM 55100 MM 55200 MM 55300 MM 55400 MM 55500 MM 55600 MM 55700 MM 55600 MM 55 900 MM 56000 MM 56100 Ml 56200 MM 56 300 MM 56400 MM 56500 MM 56600 MM 56700 MH 56800 MM 56900 MM 57000 11 M 57100 Mr 57200 MM 57300 MM 57400 MM 57500 MM 57 600 ii n 577C0 MM 57 8 00 MM 57 9 30 ;ih 53000 MM 531 OC FOMFAN IV i.; LEVEL 21 COLBN DATE = 77259 ■FIND Tilt G-SET OF COLUMN I 00J5 KO^I 0O3t CALL iSEl C C DELETE ALL COLUMNS IN THE G-SET C 0037 CO 38 L=1,D3 0036 VAF,= HSET(L) 0039 CLLT (LFVFL.VAR) =0 001.0 Vl=CLFT(VAH) 0OU1 V2=CLEI(VAE*1)-1 C0U2 CO 35 K=Vl,V2 0043 IH=FOW(K) 004U IF (RWLT(LEVEL,1R) .LE. 0) GO TO 35 C C SOW IF NEED UE CHECKED AGAIN C C('«5 FPU = PPlt + 1 OOUfc M!11 (FFM) =IR 0OU7 RWLT (IFVEL,IB)=BWLT (LEVEL, IB) -1 00H8 35 CONTINUE 0049 38 CONTINUE C C DFLETF DOMINATING ROWS C 0050 CALL CROW 0051 GO TO 60 C U052 MO CONTINUE 0053 60 CONTINUE 005U RFTt'RN 0055 FNC 5/59/27 MM 58200 MM 58300 MM 58H00 MM 58500 MM 58600 MM 58700 MM 58800 MM 58900 MM 59000 MM 59100 MM 59200 MM 59300 MM 59400 MM 59500 MM 59600 MM 59700 MM 59800 MM 59900 KM 60000 MM 60100 MB 60200 MM 60300 MM 60400 MM 60 500 MM 60600 MM 60700 MM 60800 MM 60900 MM 61000 MM 61100 MM 61200 MM 61300 MM 611*00 MM 61500 81 FOR] UN IV r, LEVEL 2 1 UCLH DATE ■ 77259 15/59/27 0001 0002 000 3 OOoli 0005 0006 0007 0008 0009 ooiC 0011 0012 001 3 oon ■01 15 001b 0017 001P OC 1 9 OO.o 0071 £. 2 on; j 0024 0125 0G*b r 0^7 OO* « 0029 00 JC 0C.11 0032 COjj CO 34 U03S 00^ 6 00j7 00J8 SUPPOUTINF DCLH C C ALL COLUMNS THAT NEEC TO BE CHECKED AGAIN TO SEE IF IT IS C DOMINATED BY OTHERS ARE SfORfcD IN A CHAIN 'CCIIAIN' WITH THE CHAIN C HEAD 'CHF.AD' C IMPLICIT :t,TEGliH*2 (A-Z) COMMON 1 KRl (5 0) ,NR2 (50) ,YY(3 30) ,MM1 (3 30) ,NN2 (300) ,ROW (400C) ,COL (4000) 2 PWLT (30,331) ,CLLT (3 0,301) ,RW PI (331) ,CLPT (301) .CCIIAIN (3 C1) , 3 STK (30) ,3TKLBD(30) , XX (4 00) ,XSL(1B0) ,STKXQ(30) ,X0 (500) ,XU (2 00) U CKT(300),KP,XP,JX,INCUMB (300) , FKET . ZBA R , ZMIN , LEVEL, 5 JAD,M,N,DVSN,P1 , P2, P3 , PP4 .CHtAD , Jl, JO, JOQ, JU, F1 6 , FN (21 ,3 00) ,K0, HSET (2 00) , NSFN , Dl , D2 , D3 ,S YSW (30,21) I = CCIIAIN (CHEAD) 5 IF (1 . FO. -1) GO TO 60 NEXT=CCHAIH (I) I1=CLPT(I) I2=CIFT (I*1)-1 IF (CLLT (LEVEL, I) .LE. 0) GO TO 45 --FIND THE FIRST ROM COVERED BY COLUMN I CO 7 .1=11,12 IR=ROW (.1) IF (PWIT (LEVEL, IF) .GT. 0) GO TO 8 7 CONTINUE WPIIF(6.70) .1 70 FCRMAT (IX, 'STRANGE COL: '.14) STOP FOW IF IS THE FIRST ROW COVERED BY COLUMN I 8 Kl^PWFl (IR) K2=PWFT(IR»1) -1 L1=J*1 •CHECK TF ANY COLUMN COVERED UY THIS ROW DOMINATE COLUMN 1 DO UO >1.1=K1,K2 J = COL (.1,1) IF (CLLT (LEV F.L.J) .LE. 0) GO 10 "4 IF (1 . EO. J) GO 10 40 J1=CIFT (.1) J2=C'1PT (.1 + 1) -1 L = J1 IF (1.1 .61. 12) GO TO 2 5 CC 20 K = L ( . 12 ip=pgw (K) IF (FWLT (LEVEL, IP) .IF. 0) GO TO 20 15 CONTINUE IF (L .GT. J2) GO TO 40 IF (IP .IT. POfc (L) ) JO TO UO IF (IP . EO. R01. (L) ) GO TO 1 8 L=L*1 GO XC 15 18 1=1*1 2 CCM'IKUF, MM 616J0 MM 61700 MM 61800 MM 61900 MM 62000 MM 62100 MM MM MM 62200 MM 6 2 300 ,MM 62100 MM 62500 ,HM 62600 MM 62700 MM 62800 MM 62900 MM 63000 MM 63100 MM 63200 MM 63300 63400 63500 MM 63600 MM 6 3700 MM 63000 MM 63900 MM 64000 MM 64100 MM 64200 MM 64300 MM 64400 MM 64 500 MM 64600 MM 64700 HH 64800 HM 64900 MM 65000 MM 65100 MM 65200 MM 65300 65400 63500 MM 65600 MM 65700 MM 6 5 800 HM 65<>00 MM 66000 HM 66100 MM 66200 MM 66300 MM 66400 MM 66500 HM 66 600 MM 667)0 MM 66 800 MM 6b900 MM 67000 MM 67100 MM 6 7200 MM 67300 1M 67400 MM MM 'CRIFAN IV LEVEL 21 DCLH DATE * 77259 15/59/27 83 HH 67500 HH 67600 nn 67700 nn 67800 nn 67900 nn 68000 MM 68100 nn 68200 nn 68300 nn 68 MM 72700 CTtl COMMON FP.UF (100) ,UBUF (100) MM 72800 r MM 72900 0005 JT=0 MM 71000 COOb CO 60 11=1. PP1 MM 73100 0CU7 IR=MM1 (II) MM 73200 00(0 IF (PKLT (LEVEL, IP) .LE. 0) GO TO 60 MM 73300 00wi9 .)1=FWPT (IP.) MM 73100 Old C J2 = RHFI(IR*1) -1 MM 73500 C MM 7 3600 C CHFCK IF HOW IP HAS A NON-ZERO ELEMENT ON COLUMN L? MM 73700 C MM 73800 CUD no 7 K = .11 , J 2 MM 73900 0012 IF (CCKK) .G'f. LV) GO TO 8 MM 71000 0013 IF (COL(K) .NB. LV) GO TO 7 MM 71100 OCH 30 TO 15 MM 71200 0015 7 CONTINUE MM 71300 C MM 71100 C FIND FIPST NON-DELETED COLUMN OF ROW I MM 71500 C MM 71600 OO'IO P CONTINUF MM 71700 0017 HO 12 K = J1,,12 MM 71800 U018 IC=COl (K) MM 71900 L0l9 IF (CLI. r (LEVEL, 1C) .GT. 0) GO TO 15 MM 75000 Oi:<.0 12 CONTINUE MM 75100 0I00 0032 L=I1 MM 76700 IQiti IF (Li .GT. .12) GO T r 25 MM 7b800 0135 EC .0 IL=L1,.I2 HM 76900 OOJ*: IC=COL(LL) MM 770)0 0057 tf KLL1 (LFVtL.lC) .LE. 0) GO TO it' MM 77100 uCit 16 CCKT1NDE M1 77200 CO 39 IF (L ,GT. 12) GO TO IC Ml 77300 one if (i<_ .n. ccl(D) go ro 10 mm 77100 IV G LEVEL 21 ir (ic .to. col(D) I = L + 1 GC TC 1h m 1 = 1*1 20 CONTINUE 2? CONTINUE c c- -ROW r DOMINATES RCK DELF GO TO 18 DATE = 77259 I7WIT (LFV1L.I) =C CO JO K=11 ,12 ic=cot (K) IF (CUT (LEVEL, IC) 30 140 U5 60 112 11! IP, DELETE ROW I ,LE. 0) GO TO 30 CUT (LEVEL, IC) MM2 (IC) =1 CONTINUF CONTINUE CONTINUE .1T^.JT + 1 OPUF (.IT) =IB CONTINUE J1=CIET (TV) J2=CLFT (LV + 1) -1 ,100 = J0 CAIL GEHW(J1,J2) IF (FKFY .GT. 0) = CLLT (LEVEL, IC) -1 11* RETURN 1 CO 200 11=1 ,JT IR=OBUF (II) IF (KfcLT (LEVEL. IR) 01=RWPT (IR) J2 = RWET (1R+1) -1 CO 112 K=J1,J2 IC=COl (K) IF (CUT (LEVEL, IC) CONTINUE ,LE. 0) GO TO 200 ,GT. 0) GC TO 115 •1 Kl=CLPT (IC) K2=CLET (IC+1) Ll=K*1 CC itO KK=K1,K2 I=PO« (KK) IF (I .F.O. IP) GO IF (RWLT (LEVEL,!) H = rtWFT (I) 12=RW[T (1 + 1) -1 1 = 11 IF (L1 .r,T. .12) GC CO iH L1=L1,.1? IC-COl (LI.) If (C1LT (LLVLL.IC) CONIIKIJE IF (L .GT. IF (IC . LT IF (1<- .tO L = 1 ♦ I 3C 10 116 TO 1<40 .LE. 0) ID 125 GO IC 1<4 LE. 0) GO TO 12 !<:) GO TO 1<4 coi id ) ;o to mo CGI (I.)) GO TO 1 l>J 15/59/27 MH 77500 MM 77600 MM 77700 I1M 77800 MM 77900 MM 7'J000 MM 79 100 MM 78200 11 M 78300 MM 79400 MM 79500 MM 70600 tin 78700 MM 78800 tin 78900 MM 79000 MM 79100 MM 79200 MM 79300 MM 79*400 MM 79500 MM 79600 MM 79700 MH 79800 nn 79900 n« 00000 nn 80100 MM 80200 m 80300 MM 80U00 m 80500 MM 80600 MM 80700 MM 80900 MM 60900 MM 81000 MM 81100 MM 91200 MH 8 1300 MM 81U00 MM 81500 MM 81600 MM 81700 MM 81000 MM 81900 MM 02000 MM 82100 MM 82200 MM 92)00 MM 82UOO MM ^2500 MM 92600 MM 02700 MM 82800 MM 82900 MM 83000 MM 83100 MM 93200 MM 93300 85 FORTFAN IV « LEVEL 71 DELR 000? 118 1 = 1*1 0094 120 CONTINUE 0095 125 r CONTINUE 0096 nwu (i.pvel.i)=o 0n r <7 DO 130 K = H,I2 009b IC=COL (K) 0099 01CC OKI IF (CILT(LEVEL.IC) .LE. 0) GO TO 130 CLLT(LEVEL.IC)=CLLT (LEVEL, IC)-1 FH2(IC)=1 0102 130 CONTINUE 01C3 no CONTINUE C194 200 CONTINUE OIoS PP4 = 0106 PETURN 0107 FNC DATE = 77259 g6 15/59/27 nn 83b00 H'FIFUN iV G IFVEL 21 00 '1 2 Or, 43 30 MM 2 ric) =1 CONIINUE OOUU OOUli OCUfi 00U7 ooue «o 60 continue coktinue ft«=o FETOR N FNC UFOH DATE = 77259 15/59/27 88 Mfl 30900 MM 91000 NH 9 S1Q0 (1(1 91200 MM 91300 nn 91H30 All 91500 ORTPAN IV G LEVEL 21 DGS2T DATE = 77259 15/59/27 89 0001 SUBROUTINE DGSET MM 91600 00U2 IMPLICIT iNTE«FF*2 (A-Z) HM 91700 0003 COMMON H.I 91300 1 HP1 (50) ,MR2 (50) ,JY (330) ,MH1 (330) ,HH2 (300) , ROM (4000) , COL (4000) , HM 91900 2 FWLT (30,331) ,CLLT(J0, 301) ,RWPT (331) ,CLPT (301) .LCHAIM (301) , Mil 92000 3 STK (30) ,STKLBD(J0) , XX (4 00) , X3L (180) ,STKXQ (30) ,10(500) ,111 (200) ,HH 9 2100 (3 0) ,XU (500) ,XU (200) U CKT(300),KP,XP,JX,INCUMB(300) , FKBY, ZBA R ,ZMIN, LEV EL, 5 J AD, M, N.DVSN.H, P2, P3 , PP« .CHEAD , JP, JQ, JOO, JU, Rl nn MM MM MM MM ooou co 60 11=1, KP 0CL5 I = CKT (II) 00 C 6 IF (PkLT(LEVEL,I) .NE. 1) GO 10 60 0C07 11 =EWPT(I) 0001) I2=RkPT (1*1) -1 0C09 CO 10 J = U,I2 00 It TC=COt (J) 0011 IF (CILT (LEVBL.IC) ,Gf. 0) GO TO 20 00 1 1 10 CONTINUE 00 I 3 c- 20 CONTINUE -COL 1C IS ESSENTIAL oo m KP=XP«1 00 i 5 IF (XF .LT. 7.BAR) GO TO 22 001f xp=xp-i 0017 RETURN 1 00 18 22 CONTINUE 0019 XSL (XF)=IC 0020 J1=CLF1 (IC) 0021 0?=CLPT (IC+1) -1 c- -UPCATt Tilt CURRENT VALUE YI AND THE NO. OF NOB ZERO c- -ELEMENTS OF EACH ROW 002 2 CC 30 J=J1,J2 CO* 3 in=Kow (,i) 00 20 YY (IF) =YY (IR) »1 00<5 IF (RhlTUE VFL, IP) .LE. 0) GO TO 30 0026 I1=-RWFT (IR) 00 27 I2=PWFT (IR+1) -1 COih CO 25 L=I1 ,12 002'-) c c- CC=CUL(L) -COLUMN CC HEED TO BE CHECKED A.JAIN CCJO MM 2 (CC)=1 001-1- 25 CUT (LEV EL, CC>=CLLT (LEVEL ,CC) -1 UO j 2 ^0 RWLT (IFVFL,IP)=0 0Cj3 CUT (LEVEL, IC) =0 00 2 u 60 C( NIIMJfc 0035 KF=0 00 30 CEND= CHEAP 00 j 7 FK=0 00 ~ib CO 7l I=1,N 00 J 9 IF (CLLT (LEVEL, i) .GT. 0) FK^i oouo IF (MI12 (I) . EO. 0) GO 10 70 ocm CCHAill (CIHO) =1 C0«2 CFND=I 00M3 MK2 (I) =0 96700 96 800 96900 37000 97100 MM 97200 MM 97300 ,MM 97U00 MM 97500 ,MM 97600 MM 977O0 MM 97800 MM 97900 MM 98000 MM 98 100 MM 98200 MM 98300 MM 98U00 MM 99500 MM 98600 MM 98700 MM 98800 MM 98900 MM 99000 MM 99100 99200 99300 MM 99'JOO MM 99500 MM 93600 MM 99700 MM 99800 MM 9)900 MM1 00000 MM100100 MM100200 MM100300 MM lOuqOO MMl 00500 MH100600 MMI00700 HM100800 MM100900 I1H101000 MH101100 MM1 01200 MM10130C MM1019UO M.'I101500 MH101600 MM10I700 MM101H00 MMI01 900 MM102C00 MM i02 100 ;1M 102200 MM1 02300 1M1 02U00 1M 10 25 30 MM MM Oil'" KAN IV ( 5 LFVFll. :1 KS5 OC'U'1 70 rotlllNUt 00 nb IF (fK .EO. 0) RETURN 2 00<.b CCHA1N (CEND) =-1 00U7 RFTUFN OUUf) END U»TE » 77259 15/59/27 91 NM102600 nnl027oo BH102800 W1102900 nnioiuoo FO;=0 CLLT (LEVEL, IC) =0 60 CONTINUE CENC=CIILAU FK^O CC 70 1=1, N l" (CLL'i (LEVEL, I) IF (MM2 (1 ) . EQ. 0) CC11AIK (CtNO) =1 CEND=I r,i"2(i)=o 70 CONTINUE IF (Fls . hO. u) HEIUBH 2 ST. 0) FK=1 JO TO 70 MHI03100 MMI03200 MN1O330O HM103U00 MM1 03500 MM103600 ,MM103700 MM103800 ,MM103900 MM1OU0OO MM10U100 MM104200 MH104300 MM10KU00 NM10U500 MM10U600 MM10U700 MM 104 800 MM1 04900 MM105000 MM105100 HM105200 MM105300 MM105UOO MH105500 MM 105600 MM105700 BM1 05800 MM1 05900 MM106000 MM106100 MM106200 MM106300 NM106H00 MM106500 MM106600 MM106700 MM1 06800 MH106900 MM 107 COO MM107100 MM1 07200 MM107300 MM107H00 MM I 07500 HM107600 MM107700 MM 107800 Ml 107 900 MMl 08 000 MM 108100 MM! 08 2 00 MM108300 MM I0d'*30 MM1C85O0 MM 109600 HM1 08700 Hf-i 03800 r.'.'A 08900 FORTRAN IV G LEVEl 21 FHFECL D»TB *= 77259 15/59/27 93 OOuti 0OH5 00U6 CCHAIN (CENDI =-1 PFTUFN ENC n (1109000 HN109100 HH 109 200 FOPTHAH IV !3 LEVEL 21 FLBD DATS ■ 77259 15/59/27 94 Oou1 SUBROUTINE FLBD HN1 01300 C NN109'400 C THIS ROUTINE FIND A LOWER BOUND Or CURRENT SUBPROBLBH MN1U9500 C IM109600 0002 IMPLICIT INTEJIR*2 (A-Z) MH107700 000? COMOH HM1 09800 1 MR1 (50) ,MR2 (50) ,]fY (33 0) ,HH1 (33 0) ,HH2 (300) .ROW (UOOO) ,COL («000) ,NN1 0)900 2 PWLT(30,331) ,CLLT(30,30 I) , RWPT (331) ,CLPT (301) ,CCHAIN(301) , HN 11 0000 3 STK (30) , STFLBD(3 0) , XX (U00) , XS L (160) ,5TKXQ(30) ,XQ (500) , XU (200) ,111111 01 00 t» CKT (300) ,KF,XP,JX,INCUMB (300) , FKET, ZBAR , ZH IN . LEV EL, I1N1 10200 5 JAU.M.N, DVSN,P1,P2,P3,PP4,CHEAD,JP,JQ,JQQ,JU,R1 HM 10300 6 .FN (21,300) ,KU,HSET (200) ,NSPN,D1,D2, D3,SYSW(30. 21) HH110M00 000U COHRCN PBUF (UOC) ,NW (U00) MH1I0500 C NW USF THE SAME STORAGE USED FOR OBUF «M1 10600 C HN110700 0005 7N^0 HHI10800 UOufc NC=0 HN110900 0007 co io 1=1, n an 11 iooo COJF IF (PWLT (LEVEL, 1) .LE. 0) GC TO 10 HM111100 0009 HC = NC»1 Hf1111200 0010 10 CONTINUE HM111300 0011 hp=o nnnmoo 0012 CO 20 1=1, N HHM1500 un|3 IF (CLLT (LEVCL.I) .LE. 0) 50 10 20 1111111600 U01H WP=WP+1 HM111700 0015 NW (WP)=CLLT (LEVEL, I) MM 1 11800 OOlf 20 CONTINUE (in11190O 0C17 25 DG = HM11200O OulB IT=0 (111112100 0019 CO 30 1=1, WP MN112200 0020 IF (NW(I) .LE. LT) GO TO 30 Mf11 12300 0021 BG=I MI1112100 0022 IT=NH(I) HB112500 0023 30 CONTINUE M(1112600 G0 2J X,1HCU«B(300),PKEY,ZBAR,Z«IN / LEVEL. S!|l!sSS 5 JAD,M.N.DVSN,P1.P2,P3.PP<»,CHEAD,JP,J0,J00,JU,R1 Si 1 MOO C FKEY IS USED TO SHOW IP THE TESTING SET IS EMPTY in\]tloO C MN114900 OOOU FKEY=0 HM115000 C MM115100 DOGE J0=J0*1 MM115200 OuOfj XO 1.10) =-1 ,„ NM115300 00L7 IF (-XU(JH) .LT. LEVEL, 30 TO 315 Si 1 MOO 000b JtlU=Jll-1 HM115500 COOy 250 .IW--XU(JiHl) MM115600 CU10 K1=CIPT(JW, HM115700 0011 K2 = CLfT(JH*1,-1 (111115800 Oo1<. 1" K1 HM115900 C , MM116000 BO'IJ CO 290 J=J1.J2 HH1 16100 UO,t IF = FO*< M) ^ nn MM116200 OOU, IF (RV.LT (LEVEL. IP, .IB. 0) GO TO 290 "„Ml 16300 0016 280 CONTINUE MM116U00 0017 IF U .GT. K2, GO TO 300 HH116500 OC-ib IF (IR .LT. ROW (LI) GO TO 285 HM 1166O0 CC19 IF (IB .HO. ROK(L)) GO TO 282 MM116700 0C2O L=L*1 MM116800 0U21 GO TO 280 HH1169O0 0022 282 CONTINUE MM117O00 0023 1=1*1 rin 1 17100 P02U GG *° 290 MH1 17200 c MM117300 C STCRF BOW IR IN THE ARRAY TEHP M1117U00 C HM1 17500 0025 285 JO-JO+1 MM117600 C026 XOUO, =TR MM1 17700 0027 290 CONTINUE MM117H00 OQtZ GC TC 320 HH, 17900 C NM1 13000 0029 300 CO 310 JJ = J.J2 MM 1 1 n 1 00 00 JC IK=ROM|JJ) , n „. ,.„ mi J |8 200 0031 IF (PWLT (LEVEL. IP, .hi. 0, GU iO ill) nNl 13300 0032 JQ = JO+1 Jin 1 18400 003 j HOUCI'I? MH) 18500 0034 310 COHTIHOE MH11860C 0035 GO TO 320 MM118700 C '1M1H800 C05b 31^ CONTINUE MH118900 till 318 S I F , H H e i/r« , .'—sT«i«. ■««>««« «•.*••••■ ;;j]|;;j c m;i'!19 200 c anl I n 00 00 3 y 3 20 CONTINUii FORI RAM IV G LEVEL 21 GENU DATE = 77259 15/59/27 96 CO '4 00 01 OOui ■TEST EMPTY SET? IF (XO (JO) .GT. 0) GO TO 325 IT IS EMPTY. PROGRAM BACKTRACKS FKf Y=1 PETUF. H ■TFSTING SET IS NOT EMPTY 0( U 3 325 CONTINUE OC'UU C C C c c JUU=JUU-1 ItST IF THE NEXT SUBPROB IS OF THE 00 US IF l-XU(JUU) .IT. LEVEL) RETURN FETCH THE VARIABLE CORRESPON CI NG c c HAS BFEN ENUMERATED OOUb J 011= .11) U-1 00"7 LVT=1EVEL-1 COtf) IF (LVT .EO. 0) PETURN 00U9 JO=J0*1 ou:o X0(J0)=-1 00 51 JW = XIJ (JUU) 0052 K1 =CIP1 (JW) 00 r o K2 = CLPT (JW+1) -1 005H I=K1 0055 CO 190 .1=.)1,J2 GO'.'t IR=ROW (.)) OOW IF (RWLT (LVT.IR) .LE. 0) GO TO 190 C05b IF (YY (IB) . ^T. 0) XO TO 190 005 9 180 CONTINUE OQuO IF (L .GT. K2) GO TO 200 006 1 IF (IF .IT. ROH(L)) GO TO 185 00 be IF (IR .EO. ROW(L)) GO TO 182 00 6 3 iml OOt-U GO TO 1 PO 00 05 182 CONTINUE 00 6 C L=L»1 001.7 10 10 190 OObG 185 J0=J0+1 0069 XO (JO)=IP 007 190 CONTINUE 0071 GO TO ?25 007 2 200 CC 210 JJ=J,J2 0073 ir = Fow (j.i) C07U If (RHLl (LVT, IF) .LK. 0) 10 10 210 00 7 5 IF (YY (J.R) .C.T. 0) GO TO 210 007b ,IQ=JO+1 0u77 XO (OC)=IR 0C7b 210 CON1IHUF GC79 30 TO 325 OObO EHC MM1 I9U00 MM 11 9500 MM1 19600 MN119700 NMl 19000 MH119900 HM12JOOO NN120100 MI1I20200 MM1203OO MM1 20U00 MM120500 MM120600 MM120700 MM120800 MM120900 MMI21000 MM1 21100 MH121200 MM121300 MM 12 moo MM121500 MH121600 MM121700 HM121800 MM121900 HM122000 HM122100 MM122200 HM122300 MM122I400 MM122500 MM122600 MM122700 MH122800 MM122900 HM12 3000 HM123100 MM123200 MH123300 MM123MOO MH123500 MM12 3 0OO MH123700 HN123800 1M12390O MM12U0JU nni2tloo MM12U200 ilM I2n 300 NMl2>|l|00 MM124500 MM12U60C MM I 24 700 MHJ2U800 M.112'4 900 MH125U00 (111251 JO FORTRAN IV G LEVEL 21 GSET DATE = 77259 15/59/27 97 0001 SUBROUTINE GSE1 MM125290 0002 IMFL1CIT INTFGHR*2(A-Z) MN125300 0003 COMMON MH125400 1 H81 (50) , MF2 {50) , YY (330) ,NH1 (3 30) , MM 2 (300) ,R0W (U000) ,C0L (U000) , MM 125 500 2 FWLT (30,3 31) ,CLLT (3 0,301) ,8WPT (3 31) ,CLPT(3 01) .CCHAIN (301) , NH1 25600 3 STK (30) ,SIKLBD(30) , XX (100) , XSLI18 0) ,STKX«(30) ,Xy (500) ,XU (2 00) , MM 125700 l» CKT (300) , KP.XP,. IX, INCUR P (300) , FKB I , ZBAH ,ZMIN , LEVEL, MR1 25BOO 5 .JAD,M,N,DVSN ,P1 ,P2, P3, PPl.CHEAD.JP, JQ,JU0,JU,R1 MN12590O 6 ,FN (21 ,300) ,KO,HSET (200) . NSFN , D1 , D2 ,D3,SYSW (30,21) MM126000 0u0<4 COMMON PPUF (400) ,OBUF («00) MM126100 0005 COMMON FNCH(30C),PF MM126200 C MM126300 C THIS SUBROUTINE GENERATE G-SET FOR A GIVEN VARIABLE KO AIID MH126M00 C GIVFN SYMMETRIC FUNCTIONS HM126500 C MM126600 C NSFH-.NC. OF SYMMETRIC FUNCTIONS F1,F2,...FN MM126700 C IISFT IS THE SET OF VARIABLES GENERATED MM126800 C MM126900 0C06 H3ET(1)=K0 MM127000 0007 D3=1 MM127100 0008 IF (NSFN .LE. 0) RETURN NMI27200 000* D1=1 NM127300 00 JO L2=1 MM127M00 C MM127500 0011 10 CONTINUE MMI27600 0012 DO 2C0 ,J=D1,D2 MM12770O 0013 VAP=HSET(JJ MM127800 001U CO 1C0 1=1, NSFN MM127900 0015 IF (SYSW (LEVEL, I) . EO. 0) GC TO 100 MMI23000 00)6 FVAR=FN (1, VAR) MM128100 0017 IF (CUT (LEVEL. FVAR) .LE. 0) GO TO 100 MMI28200 C MM12S300 C CilFCK IF FVAR IS ALREADY IN HSET MM128400 r HH128500 0018 CO 20 K=1,C3 MM128600 001S IF (H3LT(K) .EC. FVAR) GO TO 100 MMJ28700 0020 20 CONTINUE MM128800 C MN128900 r FVAR IS NOT IN HSEI MM1 29000 C CHECK IF COLUMN FVAR EQUAL TO ANY COLUMN IN HSET MH129100 C MM129200 0o*1 F1 =CLl 1 (FVAR) MM129300 00^ F2=CLPT(FVAR*1) -1 MM12J400 0023 CO 60 K = 1,D3 111129500 002H VIN = H£H(K) MM12160O 00/5 IF (CILT (LEVEL, VIN) .NF.. CLLT (LEVEL, F VA R) ) GO TO 60 MM12J700 C MMI2JH00 C COLUMN VIN = COLUMN FVAR? MM123900 C Mill 30000 00?f V»CLPI(VIN) M H i 30100 0027 V2=CLFT(VIM+1)-1 MM13020C 0028 H=F1 tin i 30300 00?9 DO UO L = V 1 , V2 NM13O400 0030 IR=noK(L) I1M1J05CO OOjJ IF (KWLT (LFVFL.iK) .Lt. 0) GO TO UC I1M1 30600 0032 35 IF (DOW (II) .ST. IK) i;o TO 60 II M 1 13 7 00 0033 IF (FOK(H) .r.O. IR) CO IP UO MM13U800 003M H=B+1 mi1J0300 00 35 GC 10 35 MM 13 JO JO FORTRAN IV 1 LEVEL 21 JSET DA 003ft C C uo CONTINUE COLUMN FOUAL TC COLUMN PVAB, UPDATE FN (I C c FIRST FIND VARU, WHICH IS HAPPED 10 VIN 0037 VT=VIN 00 38 U2 VAPU=FN U,VT) oo 19 TP (FN(I.VARU) .EO. VIN) GO TO «5 00 uo VT = VARII 0011 ?,0 TO «2 OOu? c c c 1*5 CONTINUE VARIABLE VARU IS FOUND, UPDATE FUNCTION 00-*3 FN (I.VAR) =VIN 00 uU r M (I, VARU) = PVAR 0(,<4b f F=PF»1 OO'tf- FNCU IFF) =1 > 00U7 PF=PF*1 00 Ud FIICII ((F) =VAB 00 '4 9 PF=PF»1 00 bO PUCH (IF) =VIN 00S1 PF=PF*1 0Cb2 FNCII (IF) = VARU 0053 TF=PF«1 005U FNCH (PF ) = FVAP 0055 FF=PF*1 00_>b FNCII (PF)=LEVFL 0057 GO TO 100 0058 c c 60 CONTINUE COLUMN FVAB DOES NOT DOMINATE ANY COLUMN c STORE FVAR IN HSET 00^9 L3=D3+1 0060 HSFT (D3) =FVAR 00 6 i 100 CONTINUE 006 2 200 CON1INUF 0063 IF (C2 .FO. D2) GO TO 210 oOt-u C1=D2*1 00 1 5 t2 = D3 00 bb SO TC 10 00b7 210 CONTINUE OObti PETUKN 0069 ENC DATE = 77259 15/59/27 98 HM131100 MM131200 MM131300 HM131U00 1111131500 MM131600 MM131700 MM131800 MI1131900 MM132000 tl (1132100 MM132200 : am 32300 MHI32U00 MM132500 MM132600 HM132700 NIJ1328O0 MM132900 HM1 33000 MN13H00 MM133200 MM133300 MM1 33UOO MM1335O0 MM133600 MM133700 MH1 33800 MM133900 MM13U000 HN13<4100 IN HSET MM13«200 MM1 30 300 MM13U«00 MM13M5D0 MM13U600 MM1 34700 MM1 3U800 MM1 3U900 MM135000 MM135100 MM135200 HM135300 MM135U00 FORTRAN IV C, LEVBL 21 INI1L DATE = 77259 15/59/27 99 0001 SUPROUTINF INIIL nHl35500 C «M1 35600 C INITIALIZE PARAMHERS MM135700 C H«135e00 00C2 IMPLICIT INTEGER*/ (A-Z) MM135900 0003 COflHOtl M113S000 1 KR1 (50) ,MR2 (50) ,YY (330) ,HH1 (330) ,11(12 (300) , ROW (9000) ,COL (9000) .HH136100 2 P WIT (30,3 31) ,CLLf (3 0,301) ,FKPT (331) ,CLPT(301) ,CCHAIN (301) , Mfll 36 200 3 STK (30) ,STKLBl>(3 0) .XX (9 00) ,ISL (180) ,STKXO(30) ,XQ (500) , XI) (200) ,(1(1136300 a CKT (300) ,Kf ,XP,JX,INCU(1B (300) , FKET , ZBA R , ZHIN , LEVEL, «fl!36900 5 JAD,(1,N,DVSN,P1,P2,P3,PP9,CHEAD,JP,JQ, J00,JU,R1 Nfl136500 6 ,FN (21 ,300) ,KO,HSET (200) . NSPN , Dl , D2 ,D3 , SYSW (30,21) HN136600 ooou comhon ppuf («00) ,obuf (900) nnl367oo 0C05 COKKON FNCH(300),PF HM36800 0006 PF^O MM136900 0007 CHEAD=301 MM37000 00OP KP^O HH137100 0009 ZBAR = 3000 11(1137200 0011 JU = 1 11M137300 0011 J0=1 MH137900 0012 J0C=1 MM137500 00 i 3 X0(«JO)=-1 MM.137600 0019 XM(JU)=0 nni377oo 0015 JC=0 M.H.137800 OOU JX = 1 MMI 37900 0n7 1X(JX)=-1 HH138000 001b LEVEL=1 HM138100 0019 XP = HM13B200 0020 PP9 = (1M138300 C0.1 DO 5 1 = 1, N (1(1133900 00*2 5 RH2(I)=0 HH130500 C02i CO 10 1 = 1, fl HH138600 00V9 10 YY (I)=0 (1M1387J0 002^ IF (KSFN .LT. 0) RETURN HM1 38800 0026 CO 20 I=1,NSFN (1M130900 0027 20 SYSW(1,I)=1 rt«1 39000 C028 FFTUPN (1(1139100 0029 ENC MN139200 FORfkAN IV 0001 uoc? 00 0.1 01 04 00 5 OOOh 0007 OOob 00o9 0010 0011 0012 0013 0014 0015 oO It 0017 I.FVEL 21 NEWCON DATE = 77259 15/59/2 7 100 SUtSOUTINE NEWCON [♦) ■TEST If AST OF 1HE TESTING SETS SATISPYES THE BACKTRACK CONDITION IHHICTT INTEGER*2(A-Z) COMMON MR1 (So) ,MR2 (SCI , YT (33 0) ,M(11 (330) , HH2 (300) , hOW (4000) ,COL (UOOO) FiiLT (30.331) ,CLLT (30,301) ,R HPT (331) ,CLPT (301) ,CCHAIN(301) , 5TK (30) ,STKLBD(30) ,XX (400) ,XSL(180) .STKXQ (30) .10 (500) ,XU (2 00) CKT(300).KP,XP,JX,INCUttB(300),FKEY,ZBAR,ZNIN.lEVEl., JAD.n.N.DVSN.Pl ,P2. P3, PP4.CHEAD.jp, JC.JOO.JU.Rl IF (JOO .EO. 1) RETURN 10 ON=XO (JOO) IF (ON .IT. C) GO TO 20 IF (YY (ON) .LT. 2) GO TO 30 J0O=J00-1 GO 10 10 C EKTPAK 20 CONTINUE RETURN 1 C CONDITION NOT SATISFIED, CONTINUE TESTING 30 JCC=JCO-1 , GE. 0) GO TO 30 IF (XO(JOO) J0C=JC0-1 IF (JOO .EO. GO TO 10 FNC 1) RETURN (1M133300 (1N139400 11(1139500 !1t1139600 MM139700 (1M139800 .(1M139900 MH140000 ,11(1140100 MM40200 (1M140300 MN140400 nnl40500 (1(1140600 nnlU0700 11(1140800 (1MI40900 (1M141000 nnl4iioo (1H141200 11(1141300 HM141400 1111141500 (1(1141600 NH141700 (1(1141800 NM141900 FORIFhN IV 000 1 COoi 000 3 I.FVEl l\ N5PP DATE 77259 15/59/27 101 COCO COO 3 OOCt 0007 COGR 00 C 9 00 10 001 1 0012 00 I? 0010 0015 0016 0017 00 IP 001? 0020 0021 O0<:2 Giuj 0020 C02.5 002 e 2 7 0020 0029 OOjO 0021 00.- 2 00 1-3 SUE POUT INF. NjRP (♦,*,*) •GFNFMIE A NEK SUPPFOB, IF NONE EXISTS, THEN CONTROL GO KS TO •THE PACKTRACKIin PROCEDURE IMPLICIT IHTEGtR*2 CCMNCN (A-Z) 1 MR 1 ( 50 ), M R2 ( SO), YY(330), MM (33 0),HH2 (300), RCH (00 CO) ,CCL (OOCO) 2 RWLT (30.331) ,CLLT(30, 301) ,Rt •FIX VARIABLE X (JV) TO 1 XP=XP+1 XSL (XF) =JV J1=CLPT |JV) J2=CLPT(JV+1) -1 ■UPDATE THE CURBEN1 VALUE AND THE NO. OF NON-ZERO ELEMENTS ■OF EACH FOW DO 100 J = J1 ,.12 IP=ROW (J) YY (IR)=YY (IB) +1 IF (F'WLT (LVT.If) .LE. 0) GO TO 100 RKI1 (LVT.IF.) =0 I1=BWPT (IP) I2 = RHFT (IR*1) -1 CO 90 1=11,12 IC=COL (I) IF (CLLT (LEVEL, IC) .LE. 0) GO TO 90 CLLT (LVT.IC) =CLLT (LVT,IC) -1 COLUMN IC NEED TO BE UlECKtiD AGAIN MM2 (IC) = 1 9 CONTINUE 1C0 CONTINUE CALL NFWCON (630Ci) CI-.NO = CIIEA[) FK=C -CHECK IF HIE CCNSTFAINT MATFIX IS HULL? AND STCI-K ALL COLUMNS mil (i:»ooo MM 10 21 00 MM1022C0 MM 102 3 00 MM102000 MM142500 MMI02600 ,MM102700 HH102800 ,MM102900 HM1OJ0O0 MM 103100 MM103200 MM 103 300 NM1O30O0 MMJ03500 MM1O3600 MM103700 MM103800 MM103900 HM100000 MM10I4 100 MM104200 HM100300 MH100O00 HM100500 MM100600 MH1 00700 MM100800 MM1O0900 MM100000 MM105100 MM105200 MM105300 MM105000 MM105500 MMl05f>00 MM I 05700 MM105800 .1M105900 MM106000 MM106100 MM iOt>200 MM1063O0 MM 10 6000 MM1005OO MM106600 MM10670O MK106HO0 MM (O6900 MM107000 MM I 071 30 MMSO720G MM i 07300 MM 107000 11 Ml 7 500 NM107*:00 MM107700 M M 1 7 ft F^JI 1 -A I. L r. V R I Nsnp LiATK 7725<* 15/5 9/2 7 102 THAI MID TO lit CHtCKfcD AGAIN IN LUIAIN 00-«. L? 12C 1=1, N 1/035 IF (CILULV1.I) .GT. 0) FK=1 00 Jt IF (riM2(l) .by. 0) GO TO 120 0057 rM2 (l) =0 0{ jfc CCIIAIK (CrND) =1 00 .3 CI CFND=I O'.^O 120 COM inim; Of HI IF (FK . FO. 0) GO TO 200 ui<9 J2=C1PT(I»1) -1 MN156100 00)1. IF (J1 .IE. J2) GO TO 8 (11156200 0011 WRTTfe (6,0030) I HM156300 0012 0030 F0RHA1C COLUMN ', 10, ' : NULL') MM156000 OOU <~, TO 00 MM) 56500 0010 B CONTINUE MM156600 0015 K1=J1 MH156700 0016 10 K2=K1«19 MM156800 0017 IF (K2 .GT. J2> GO TO 20 HH156900 OOIP IF (Kl ,GT. Jl) GO TO 15 MM157000 0019 WRITE (6,0000) I,(RO«(J), .J = Kl,K2) NH157100 U020 ic TO 18 MH157200 0021 15 WRITE (6.0010) (ROW (J), J=K1,K2) MM15730O C022 18 K1=K2*1 MM157100 0023 GO TO 10 MM157500 00^0 20 IF (K1 .EO. J1) GO TO 25 MM157600 U025 WRITE(6,1010) (ROW (J) ,J = K|,.)2) HM157700 0026 GC TC 00 MM157800 0027 25 WRITE(6,0000) I, (BOM (J), J=R1,J2) HM157900 0028 00 CONTINUE MM1 58000 0029 0010 FORMAT (12X, 20 16) HH158100 00J0 FEIURN HM158200 OOM ENt MM158300 FORTRAN IV 0001 0002 0CO3 ocou 00o5 000b 0007 OOOti 0C09 0010 0011 0012 0013 001U 0015 0016 0017 0C18 001" 0020 0C21 0022 002J 002U 0025 002b CO 27 00 2 H 0029 CO 30 00J1 Ov. M Ou j 3 v,OJU 00 J 5 OCifi 0C?7 003 b oOJ9 arm, Ocul 00^2 00*43 0014 it 001*5 00<4f 00(4 7 Oo'ie 00U9 00 50 LEVEL 21 PNCH DATE = 77259 15/59/27 105 SUBROUTINE PNCH ■PUNCH INTERMEDIATE RESULT FOR CONTINUATION 1100 1U10 1U20 11430 1141)0 11450 50 55 60 100 210 200 230 IMPLICIT COMMON MR1 ( Pl.LT STK ( CKI ( JAD, .FN | COMMON P CCMMCN F DIMENS10 FORMAT (5 WRITE (7, WRITE (7, FOFMAT (' WHITE |7, FORMAT (• WRITE (7, FOPMA1 (' WRITE (7, FOFMA1 (' WRITE (7, FOFMAT (* 0P=0 FP = CO 10G I FP=PP41 CP=OP*1 OBUF (OP) PBUF (FP) CO 50 J= IF (RKIT CO 2.5 1 = IF IPEUF CONTINUE FP=PF*1 PBUF (FP) CONTINUE DO 60 J = IF (LLLT DO 55 1= IF (ypilF CONTxNliE CP=Ut+1 CBUF (CP) CONlINUt. CONTINUE WPITF (7. FORMAT (' WFITE (7, FCFMA1 (' wrilh (7 FCPBA'I ( ' A 1=0 I=CCHAIN INTEGKR»2 (A-Z) 50) ,BR2 (50) ,VY (33 0) ,MB1 (i30) ,MM2(300) ,ROW (1*000) ,COL (14000) (3 0,331) ,CLLT (30, 301 ) ,R WPT (331 ) ,CLPT (301) ,CCHAIN(3 01) , 30) .STKLBP ( JO) ,XX (<400) ,XSL (180) .STKXQ (30) ,XO (500) ,XU (200) 300) ,KP, XP,JX,INCUMB (300) .FKISY.ZBAR , ZflIN , LEVEL, ti.N,DVSN,Pl, P2, P3,PPI4,CIIEAD,JP,JC, JQQ,JIJ,R1 21 ,30 0) , KO.HSET (200) , NSFN , C1, D2, D3.SYSW (30,21) BUF (1400) ,OBUF (MOO) NCH (300) ,PF N AAJ18) I«,141X, 'LEVEL, JX.XP.ZBAR.PF') 11400) LEVEL, JX, XP,ZBAR,PF 11410) (XX (I) .1 = 1, JX) XX »,19 1«) 11420) (XSL(I) ,I = 1,XP) XSL ',19 I«) 1430) (STK (I) ,1=1 .LIVED STK ',19 I«) 1U140) (STKLBU(I) ,1=1, LEVEL) STKLBD ',18 Il») K50) (J NCUMB (H) ,11 = 1 ,ZBAR) INCUMB ',18I<4) 1=1 ,LBVEL =-IL = -IL 1,M (IL,J) ,GT. 0) GO TO 50 1.PP (I) .EC. J) GO TO 50 I.N (1L.J) .GT. 0) GO TO 60 1 .OP (I) .EO. J) GO TO 60 =J 210) PP,OP IPQP', 2 lU) 2C0) (PBUF (I!) ,11 = 1 ,PP) PBUF', 19 114) ,230) (OPUF (II) ,H = 1 ,OP) OBUF',19 i<4) (CHEAD) MM158UO0 MM1 58500 MM153600 MM150700 MM I 58800 MM15B900 .MB159000 BM159100 .MM159200 BB15SU00 MN159U00 MM159500 MM 159 600 MM159700 MB1 59800 HM159°00 HM-i60000 MM160100 MH160200 HM160300 MM160400 MH160500 MM160600 MM160700 MM1 60800 MM160900 HM161000 MM161100 MM161200 MM161300 MM161400 MM161500 HM161600 MM161700 I1M161800 MM161900 MM162000 MM162100 MM162200 MM162300 MM162H00 M'1162500 MM1 62600 MM162700 MM162800 MM16290C HM163COO m I 6 3 100 MM163200 MM163300 KH1 6J1400 HB1 6 3500 MM16 3 6 00 M fl i 6 3 7 MM I 63 800 B3 1 63900 Ml65 WFIIE|7,280) (XU (H) ,H=1,JU) 0066 280 F0FHA1 ('XII ' ,19 I**) 0067 WRITE (7,290) (STKXO(H) ,H=1, LEVEL) 00 bti 290 FOPHAK'STKO',19 I<*) 0Co9 WRITE (7,295) (YY (LI) ,H=1,H) 0C70 295 FOFMATCYY ',19 It) 0071 IF (N5FH .LB. 0) RETURN 0072 DO 310 1=1, LEVEL 0073 WRITE (7,306) (SYSW(I.H) ,H = 1,NSFN) 007** 3 06 FCRHAT(l*0 12) 0075 310 CONTINUE 0076 IF (PF ,LE. 0) RETURN 0077 W.UTE|7,i*06) (FNCH (H) ,H=1 ,PF) 0U78 1*06 FOPRAT(20 IM) 0079 FETURN 00130 END FORTRAN IV 1 LEVFL 21 BEADIN DATE = 77259 15/59/27 107 0OO1 SUPFOUTINE FEADINI*) MM167300 C READ INPUT DATA HM1671»00 C002 IMPLICIT 1NTEGER*2 (A-Z) MN167500 OU03 COMMON NM167600 1 MR1 (50) ,MR2 (50) , If If ( 33 0) ,MM1 (J 30) ,«H2 (300) ,ROW (4000) ,COL (4000) , MM 167700 2 FWLT (30,3 31) ,CLLT(3 0, 301) ,RWPT (331) ,CtPT (301) , CCHAIN (301 ) , MM 167 800 3 STK(30) ,SIKLBD(30),XX(400),XSL(180),STKXQ(30) ,X0 (500) ,X0 (2 00), Mill 67 900 4 CKT|300),KP,XP,JX ,INCUMB (300) , FKEY , ZBA R , ZMIN, LE V EL , (1(116 8000 5 JAD,M,N,DVSN.P1,F2, P3,PP4,CHfcAD,JP,JQ,JQQ,JU,Rl MM16S100 6 ,FN (21,300) ,K0,HSET (200) , NSFN, Dl , D2 ,D3 ,SYSW (30, 21) 11(1168200 OOOU C1CEKS10N IA(18) (1(1168300 0005 FEAU(5.3) H,N MM168400 000b 3 FORMAT (2 15) MM168500 0U07 IF |M .GT. 0) GO TO 400 MM168600 0008 WRI1E(6,«030) M HM168700 C0v9 1)030 FORMAT (//, IX. ' ERROR WRONG VALUE OP N ',15) HM168800 Colt STCP MM168900 00 11 100 CONTINUE (1(1169000 00J2 READ (5,10) DVSN , Pi . P2 . P3 , NSFH, P5 MIH69100 OOIj 10 FORMAT(6 15) (1(1169200 0014 KRITK6.600) M ,N , P1 , P2, P3 .DVSN.NSPN ,P5 (1(1163300 0015 600 FORMAT JH 00« 9 CU'l 0051 oo r ,; iusj OC ;U OOSfc 00 V 7 005 H 0059 OOt.O 00 b 1 0062 U0b3 OObU 00 b 5 PO If. I I CO 15 20 0010 '10 145 4040 120 W I i I = IA( -; »♦ NT IN TC = I*« fO NT IN =12- (12 rrr ( FT, AT .1" 12 NT IN OPE IL C TURN ITF ( B1IAT CP IURN C )=IA(J) J) 1 OF 8 1 5 HE 1 . El). H) GO TO 40 0.40 10) N.I2 (IX, ' ***WA&HING*** NO. OF INPUT COLUMN IS DIFFERENT FROM • , • , • .14, ' IS ASSUMED') UK THF CONSTRAINT HATBIZ IN HOW El ROW 1TCRW (6120) 6,4040) IA (//,' ERROR CHECK ROW SEQUENCE: • , / ,5X ,20 ID) MK17 J2uO Mill 73 300 M M i7 34uO NMI7J500 mm 173600 MH17J700 MM17307U MM173900 MM t 7 <4 .) MM i 7 '4 100 MM 174 200 HMWI300 MM 17 '4 400 MMl 74500 MM 174600 MM174700 MM174800 MMI74900 MM175000 NM175I00 KH175400 MM175300 MM175400 HM175500 FORTPAN II I! LEVEL 21 ROWLN DATE = 77259 15/59/27 109 00U1 SUBROUTINE ROWLN 1(1175600 C MN175700 C THIS ROUTINE DELETES DOMINATING ROW MM 1 75800 C MH175900 0002 IMPLICIT INTESER*2 (A-Z) MM176000 0003 COMMON MM1761O0 1 HR1 (50) ,MR2 (50) ,tt (330) ,HH1 (330) , MM 2 (300) .ROW (1000) ,COL ( 0031 Ouji 0^33 00 JU CGJ5 LEVEL ROWIN DATE 77259 15/59/27 110 SUBROUTINE P0W1N •THIS ROUTINE READ IN MATPIX ROW BY HOW IMTLIC COMMON 1 Hi- 2 BW 3 sr 1 CK 5 JA CI MENS 11=1 12-1 55 EWFT (I PWll (1 IE=-1 58 READ ( UOOO FOFMAT C IF EN IF (IA DC 59 C END OF IF (IA C IF ERR IF (IE RWLT (1 COL (11 C STORE IF. = IA ( 11=11* 59 CONTIN C READ K GO TO 65 12-12* C READ II GO TC 70 CONTIN 12=12- I" (12 h' B ITE( U010 FORMAT * ' ,' .1 M=T2 90 CONTIN RETURN 95 WRITE 0050 FORMAT srcr FCC IT INTEGFR*2 (A-7.) 1 ( 1 CjO) ,MB2 (50) , YY(330) ,MM i (330) ,MM2 (300) ,ROW (l»000) ,C0L (1)000) LT (J0.3 31) ,CLLT (30,301) ,RWPT(131) ,CLPT (301) ,CCHAIN (301 ) , K (30) ,STKLBD(30) , XX (DOO) ,XSL(180) ,STKXQ(30) , XQ (500) ,XU (200) T (300) , KP, XP,JX,INCUMD (30U) , rKE Y , ZBAR ,ZNIN,I.fcVEL, 0,M,N,DVSN,P1,P2, P3,PP1),CHEAD,JP,J0,J0Q,JU,R1 ION IA (Ifc) 2) =11 ,I2)=0 5.1000) IA (1b ID) D OF INPUT MATRIX CARD IS READ GO TO 70 (1) .EO. 0) GO TO 70 .1=1. 18 AN INHIT ROW IS DETECTED 30 TO 65 (.1) .IE. 0) GO TO 65 OR INPUT SEOUENCE IS DETECTED 30 TO 95 •GE. IA(J) ) GO TO 95 ,12) = RWLT (1,12) *1 )=IA (J) rA(J) FOP TESTING INPUT COLUMN INDICES SEOUENCE .1) 1 BE EXT CARD 58 1 EXT ROW 55 UE 1 .EO. M) GC TO 90 6.UO10) M,I2 (IX, ' ***WARHIH J*** NO. CF INPUT ROW IS DIFFERENT FROM ',!«, U,' IS ASSUMED') UE (6,«U50) IA (//,' ERIOR.. .CHECK COLUMN INDEX S FOU ENCF. : • ,/, 5X , 18 ID) MM181100 MM181200 MM18I300 MM1810UO HM101500 MMl81b00 ,MM181700 (1t11 81 OUO .MM181900 n;il82000 MM132100 r.M'l 82200 MM182300 MN182U00 HM102500 MM18260U MM182700 Mill 82800 MM182900 HM183000 MM183I00 MM183200 MM183300 npil83uoo HH183500 HM18360U MM183700 MM103800 MM183900 MN18U000 MM184100 MM181200 MM18H300 MM I8U400 MM184500 MM18U600 MM18")700 MI118U800 MM18<)900 1N185000 I1M185100 Ml 185200 MK105100 MM1054U0 MM185500 MM185600 MM135700 MM *i8580O MMI85900 MK 18 6000 FOiUlAN IV 01-01 do o ; Oil j C'jOu OOo? JuOf- 00 7 ocoo 00o9 UC'SC 00 11 00 w 00',? 00 u 00 i 5 00 lb 0017 OOIP 0019 00 2 1 oo;i 00 22 0J2J Oo;" II- V t L 2 1 RWTOCL DATE 7 7;. 5 9 15/59/27 111 PUFt'CUTINK HKICCL ■THIS POUlifiF Rlf.TORES INPUT MA1R1X INTO COLUMN DY COLUMN ORDEF IMPLICI1 ccrrtN INTEGER*? (A-/.) 1 MIW (50) ,HB2 (50) , YY (3 JO) ,BH1 (j3 0) ,NM2 (3 00) ,ROW (UOOO) ,COL (UOOO) 2 I-KLT (30,331 ) ,CLLi'(30, 301) ,K HIT (331) ,CLPT (301) ,CCHAI N (301) , 3 SIR (30) ,STKLDD(JO) , IX (U 00) , XSL ( 18 0) ,STKXO(30) ,X0 (50 0) , XU (20 0) U LKT (30G),KP,iP,JX,INCUMF(J0O) ,FKEY,ZBAR.ZMIN,LEVFL, 5 .1AD,H,N ,DVSN ,Pl,P2,P3,PPI»,CHEAD t JP,JO,JOy,JU,Rl 11 = 1 12=1 10 CI FT(12) =11 CLIT (1 ,12) =0 IF (12 .LE. H) GO TO 8 RETURN 8 DO 10C .1 = 1 , n .)1 = HVitT (J) .12 = ftWPl (.)♦ 1) -1 to 80 K=J1 ,J2 IF (CCL(K) .GT. 12) GO TO 100 IF (CCL(K) . LT. 12) GO TO 80 ROH(II) =J CUT (1 ,I2)=CLLT (1,12) + 1 11=11+1 no to 100 80 CONTINUE 100 CONTINUE 12=12+1 GO 10 10 ENC MM18MO0 MM'I862')U MI1186 300 Hina-juoo MM I8u500 MM186600 ,(111166700 MM (80800 .MM 136900 Hrt1 87000 HMJ87I00 MM187200 HM187300 HM187I»00 MM187500 MI1187600 MM187700 MM187800 HK18790O nn)39000 MM108100 MM188200 MM188300 MM188I»00 HM1 83500 HM188«)00 MM188700 KH188800 I1M188900 (1H189000 nr.189100 MN189200 Fm: T r A "4 IV 001 1 u0o2 OjO J 0004 C0u5 OCO't 00U7 00of> 000 V 0G10 00 1 1 0011 00 u 00 I 4 00 i f 001b 0017 no io 0C19 002c 00 4.1 002* 0023 0021. 0o25 00.: f- 0<,^7 0010 00*9 CCJC on; | 00: ! c OOjj OC3 4 0')jf- oo : 6 U037 003b 00 J 9 0C40 oem 00 4 2 0043 ootu 0045 0046 004 7 0046 0'j4<> 00 St. LEVEL 4 1 -ETCON DATE = 7 725 9 15/59/27 112 IFS'OUTIHE SF.TCON ■--THIS I-CUT1NE READS IN THE CUNTJ NU Af J.0N CARDS WHEN P3 = 1 in CO 1 2 3 4 5 6 CO CC 01 PE 400 FO RE 410 FC FF RF F E 44 FO RE FF 450 FO DE 4 60 FC RK CI 00 IP IF .11 02 CC IC cl so CO GO 60 L= IF Li 62 01" LL IF IF CL J1 J 2 CO IH [-W 68 CC 10 09 CO CO 7C CL ELI nnu 11 p s c .1 MML MMC FtIA AD FMA AD AD AD ( I- 11 A AD AD RMA AD PfIA AD = 1 IC = PU (I IT( = RW =na 5C = CC LT[ »T1 10 -IP (L -L- =UB =on (L re LI ( = C1 =C1 6a = HC LI ( Nil TO N'il 70 IK CIT I. M (00) UI.T (30 IK (?0) Kl 1100 AC,(1,N FN (21 , N PPOF N FNCII ..lot; A (5,400 1 (5 14 (S«10 1 (4X.1 (E.I'iO (5,410 5,440) 1 (fly ,1 (5,440 (5,450 1 (4X,2 (5,460 I (<*X, (5,460 1NiIi;l , R*2 (A-7.1 ,(1R2 ( . 33i) ,STKL ),KP, ,DVSR 300) , (400) (300) M18) ) LEV ) ) 9 ) ) 50) , YY (3 5 0) .MM 1 (3 30) .(1.12 (300) , ROW (4000) , COL (4000) ,CLLT (30,301) ,HWPT (331) ,CLPT (301) ,CCI!AIH (3d) , BD(30| ,XX (400) ,XSL (180) .STKXy (30) ,X0 (500) ,XU (200) XF,JX,INCUNB(300),FK.EY,ZBAR.ZMN,LEVEL, , P1, P2, P3,PP4,CHEAD,JP,J0,JQQ,JU,RI KO.IISF.T (200) ,NSFN, Cl, D2,D3,SYSH (30,21) .ORUF (1400) ,PF LL,JX,XP,ZBAR,rF (I).I = 1,JX) (XX I'M (IS (ST (STK 8 14) ) (IN ) TF, It) ) (FBUF(I) ,1=1, PP) 19 14) ) (CBUF(I) ,1 = 1, QP) L(I) .1=1, XP) K (I) ,1=1, LEVEL) LCD (I) ,1=1, LEVEL) CUBB(II) ,H=1,ZBAR) OP = 1 ,PP :i T. 0) GO TO 60 )=0 :r) [p*D -1 11, J2 c 1= UF (I R .L I.IFi PT (T. PI (I J = .7 L(.l) L,IC) =CLLT (L,IC) -1 HUE 100 • EC 1) 00 10 100 1 ♦ I OF (OB) L .LT. 0) GO TO 6<» 1LT (L1 ,LL) .LE. 0) ^0 10 t>2 LI, ID =0 PT (LL) PI (LL*1> -1 .)=J1 ,J? - (J) 11, IP) =RWLT (Li, 13) -1 HUE 62 SUE J = 1,U I., J) =CILT (L1 ,,1) (H1 18)300 MM I 8 J 4 JO MM189500 MM189600 MM189700 I1M189B00 ,mm18?900 mmi iooo ,nnl90ioo (1(11*0 200 HM19U300 (1(1190400 (1(1190500 (1M906 90 1111190700 MM190800 (1 (1190900 hmi 91000 nnl9lloo (1(1191200 MH191300 NM191400 MM191500 (1(1191600 11(1191700 HM191000 11(1191900 MM'I9?000 (1(1192100 MM192200 MM192300 (1 (1192400 (1(1192500 MMI92600 (1H192700 (1(1192800 1111192900 MI11 93000 (1H193100 MM932O0 flMl 93300 11(1*9 3400 0(1193500 (1(119 3 600 (1M193700 (1M193BUO (1(1193900 (1(11940 30 MH19410C MM i 9 4200 (1.1194 300 HH 194400 (1(119 4 500 MM" 94630 MM1 91*700 Ml 94 800 MH194900 Mdl 95000 HH19 5.00 FORTRAN IV ; LEVEL 21 SKTCON DATE ■ 77259 15/59/27 113 0051 0052 005J 01' 5 u 0055 005b 0057 OOSH 0U59 0060 00b1 00 e I 0063 OOoU 0065 00b6 0067 006 a t,0b9 00 70 0071 C072 0073 0071 0C75 0076 0077 0C7fa 0079 0000 00 U I G0U2 oor<3 COtll 0D35 GO HO 0"B7 Or'BB 0069 oo;o 0091 0092 01/93 0j91 CO 80 K=1,N 80 PWIT (L,K) = RWLT(L1,K) 100 CONTINUE CFNL=CHFAD 160 PhAU |5,110) AA J=1 165 CCHAIN (CF.ND) =AA ( J) IF (AA (J) . £0. -1) GO TO 170 CEND=AA (.1) J = J ♦ 1 IF (J . JT. 18) GO TO 160 GO TO 165 170 CONTINUE PliAU (5,175) J0,,1U 175 FORMAT (IX, 2 II) 485 FDRMAT(1X, 19 II) FEADC,185) »00 MM196900 MH197000 MM197100 MM197200 MM197300 MM197100 MM197500 MM1 97600 MM1W700 MMl 97800 MM197900 MM198000 MM198100 MM198200 MM193300 MM198100 MM198500 MM19«600 NM198700 MM1 98000 MM198900 MMl 99000 MM199100 MM - i99290 MM19<>300 MM 199100 MH1 99500 MM 19 9690 MM199700 MMl 99800 FOFTPAtl IV G LEVEL 21 STRSIIB DATE = 77259 15/59/27 114 ocol 0002 000 3 0QOU 0005 OC'Jt- 00 07 00 UO (009 0010 001 I 0PI2 00 13 00 i« 0015 0016 00 I 7 0019 00^0 oo.il 00*2 0023 OOc'j ocie 00<:7 0T20 0024 OCJu oo n 0uj2 O033 On?U 00 3 5 0036 0C37 Oojl" 00 39 OCiJO Ojul 00*2 OOnJ SIIEhOOTINE STRSUB ■THIS ROUTINE STORE ALL SUBPROBLEBS JUST GENERATED IN CO 1 2 3 5 Kn KB M DO IC IF IP R1 HI. HP 60 CC Kl K? 65 CO DO IF 70 CO JX XX J? XX FE 72 CO WE Sfl IF II DO IF IF SH HF 75 CO 80 JX X v . MP J/ x:< GO FN PL1 HHO n R s c J 1 = R 2 = ii -0 60 =C0 (I (C =H1 1(fi 2(R NTi =CL =CL NTI 70 It! Nil = JX (JX = JX (JX IUB NTI IT= 1=1 (1 = 1 + 75 (M in L = J 11 = NTI -JX IJX i (S = JX u:: TO C C1T INTEGEF*2 (A-Z) N R1 (50) ,HP2 (50) ,YY (33 0) ,Hfl1 (33 0) ,HH2 (300) , ROW (UOOO) , COL (1*000) WLT (30,3 31) ,CLLT(30,301) ,RWPT (33 1) ,CLPT (301) .CCIUIH (301) , TK (30) ,S1KLBD(30) , XX (1*00) ,XSL (180) ,STKIQ(30) ,XQ (500) ,XU(2 00) Kl (300) ,KP,1P,JX,INCUHB(30U) , FKBl,ZBAR,ZniN, LEVEL, AD.H.N ,DVSN,P1,P2, P3,Pt>M ,C HEA D , JP , J (J , JOO , JO . F 1 WPT (JAD) WPT(JAD*1) -1 I=KR1 ,KR2 MI) C . EO. JP) GO TO 60 LLI (LEVEL, IC) .LE. 0) GO TO 60 ♦ 1 1) =IC 1) =CLLT (LEVEL, IC) NUK IT (JP) PT (JP+1) -1 NUE 1=1, F1 F2 (1) .GT. 0) GO TO 72 NUE ♦ 1 )=JP ♦1 ) =-LEVEL-1 N NUE HF2 (I) .GK. R1) GO TO 80 1 J=I1,R1 F2(J) .LE. 0) GO TO 75 P2 (J) .GE. HEIT) GO TO 75 HP 2 (J) NUE ♦1 ) = MP1 (S.1L) KL) =-1 ♦ 1 ) =-LEVEL-1 65 HH1 99900 HH200000 HH200I00 HH200200 HH200300 HH200U00 ,nn200500 MH20J600 ,HM200700 HH200800 HH200900 MH201000 HM201100 HH20I200 HH2013O0 nn20|i»oo HH20I500 HH201600 HH201700 HH201800 HH201900 HM202COO nn202loo WH202200 HH202300 HH202400 HH202500 HH202600 HH202700 HH202800 HH202900 HH203000 HH203100 HH203200 MH203300 HM203U00 HK203500 MH203600 HH203700 MM203800 HH203JOO N(120'*000 HM20U100 HM 2 04 200 nn 204 300 HM204I4OO MH2045OO HH204600 MK20470C HH20U800 HH2049 30 FORTRAN IV ', LFVEL 21 CHOOSE DATE = 77259 15/59/27 115 00C1 SUBROUTINE CHOOSE flri2O5O00 0U02 IMFLIC1I INTEJER*2 (A-Z) BH2O5100 0003 PEAL*0 WEI1,VW,WT . n(12O520O 000U CONHCN HM205300 1 1R1 (50) ,NR2 (50) ,YY{33 0) ,flM (330) ,BJ12 (300) .ROW (4000) ,COL (1000) ,NH?05«.)0 2 RWLT (30,331) ,CLLT (3 0,301) ,RWPT (331) ,CLPT(301) ,CCHAIH (301) , MN205 5O0 3 STK (3 0) ,SIKLBD(30) , XX (U00) ,XSL(180) ,STKXQ (30) ,XQ (500) ,XU (200) , MM 2 05 600 U CKT (300) ,KP,XP,JX, INCUHB(300) , FKBY , ZBA R , ZfllN , LEVEL, HH205700 5 JAD.fl. N.DVSN, Pi, P2, P3 , PUU .CHEAD, JP ,JQ, JQQ, JU, Rl HN2058O0 MM205900 HM206000 HB206100 MM206200 BM206300 HM206U00 HB206500 HH206600 NH206700 MH206800 HM206900 MH207000 HM2O710O HM207200 MM207300 HK2 07«tOO HH207500 BN207600 HN207700 0005 JP=0 CO 06 H£IT=0. 0007 to 1Co .1=1, h 0008 IF (CLLT (LEVEL, J) .LE. 0) 50 TO 100 C009 WT=0. 0010 J1=CIPT (J) 0011 J2=CIPT (J + 1) -1 0012 C') 50 I=J1,.12 00)3 IF=RGW (I) Oo 14 IF (RWLT(LEVEL,1R) ,LE. 0) GO TO 50 OC IE VW^RHLT (LEVEL, IH) 0016 tiT = WT*1/VW 0017 50 COHTINOE oo ie IF (WT .LE. HEIT) GO TO 100 0019 WETT^kiT 0020 JP = J 0021 100 CONTINUE 0022 FETURN O02J ENC FORTRAN iV r, IEVFL 21 HURIST DATE = 77259 15/59/27 116 0001 SUBROUTINE HURIST(IND) MM207800 000* IMFLICIT INIEGER*2 (A-Z) MM207900 u003 COMMON MM20U000 1 MF) (SO) ,MR2 (SO) , YY (3J0) ,HH1 (JJU) ,NH2 (300) ,ROW (400G) , COL (HO 00) , MM 2 OR 100 2 F WIT (30,3 31) ,CLLT (30,301) ,RWPT|331) ,CLPT(301) ,CCHAIN (301 ) , HM208 200 3 STK (3 0) ,STKLBD(30) ,XI (U00) ,XSL(180) ,3TKXO (30) , XQ (500) ,XU (200) ,MM2O8 300 U CKT (300) ,KP,XP,JX,IMCUMB(300) , FKEY, ZBA R.ZHIH. LEVEL, MM208U00 5 JAD.M, N,DVSN,H.P2,P3,PI»<»,CIIEAD,.1P,JQ,J0Q,JU, Rl MM20H5O0 OOCtt 10 CAIL CHCOSF MM208600 C JF IS THE VARIABLE. CHOSEN BT 1»IE SUBROUTINE CHOOSE. IE IT IS MM208700 C 0, 1HF.N A FEASIBLE SOLUTION IS POUND HM208800 000?: IF (JP .EO. 0) GC TO 30 MM208900 0006 XP=XP*1 NM209000 0007 XSL(JP)=JP MM209100 0008 J1=CIFT|JP) HM209200 OOuy .)2 = CLPT(JP+1)-1 MM209300 0010 CO 20 .J = .11,J2 HN209400 00)1 tS=FOV(J) MM203500 00)2 YY (Ilt) = YY(IF) *1 (1(1209600 0013 IF (RHLT (LEVEL, IR) .LE. 0) GO TO 20 11(1209700 001U RWIT (LtVFL,IF)=0 (1(1209800 0C15 I1=RWF1(1R) BH209900 0016 I?. = RWPT (IR + 1) -1 (1(1210000 0017 DO 15 1-11,12 (1(1210100 00 it' IC=CCL(I) (1(1210200 0019 IF (CUT (LEVEL, IC) .LE. 0) GO TO 15 (1(1210300 0020 CLLT (LEVEL, IC) =CLLT (LEVEL, IC) -1 I1M210U00 0021 MH2(IC)=1 MM2I0500 0022 15 CONTINUE (1(1210600 0023 20 CONTINUE (1(1210700 0024 CEND=CHEAD HM210000 OC-25 FK=0 MN210900 OO/Jfi CO 23 1 = 1, II (1(1211000 00.77 TF (MM2(1) .EQ. 0) GO TO 21 MM211100 OC28 CCHA1S (CFND)=I MM2112G0 0029 CEND=I MM2113O0 0030 MM?(I)=0 MM211U00 0031 21 IF (CUT (LEVEL. I) .LE. 0) JO TO 23 (1(1211500 C0J2 FK=1 HM211600 0033 23 CONTINUE MM211700 C FK IS USED TC SUCH IF A FEASIfcLE SCUTICN IS FOUND OR EOT MM211800 0031 IF (FK . F.O. 0) GO TO 30 0(1211990 00j5 CCHAIN (CE(.D)=-1 MH212000 OCjb 2 C CAIL LCLM MM.^12100 0037 IF (KP .CO. 0) GC TO 10 .'1.1212200 C036 27 CCKTINUF NM212300 0J39 CALL HISNT(IND) (K1212U00 C INl)=2 SHOWS A FEASIBLE SOLUTION IS FOUND HR212500 C IND=1 SliCWS SCCE ESSENTIAL COLUMNS ASE FOUND BM212600 0040 IF (INC .EO. 2) ;C TO 30 MM212700 OO'll IF (iNU .EO. I) liC TO 2 5 MM/f 12 800 00 Hi GO 1"J JO MM2 12^00 00U3 30 CONTINUE HM213000 00 u«* RETURN MM213100 00U5 END MM211200 FOTIKAN IV 0001 0002 OUOi ooou OOvlS orc6 0007 CGC8 0019 00 ii, oon D01i 0C13 00 »« G0J5 oo if 00 17 00 i 8 001? 0020 00 21 0C22 0023 0024 uO?5 0026 o0 2 7 002 b 00*9 0G3u 00 J 1 0032 0033 0034 0035 uOJb 0U37 00 38 0039 ocuo 004 i 00m 2 00u3 OOUU OOuS 00U6 0047 0CM8 LEVEL 21 HESNT HFSNT (IND) E FIND AND FIX TEGER*2 (A-Z) DATE ESSINT1AL COLUMNS 77259 10 20 25 30 60 70 7S SUBROUTINE ■THIS ROUTIll IMTL1CTT IN conncN BR1 (50) RKLT (30 STK (30) CKT (300 JAD,M,N INL = CO 60 11=1 I=CKT(IT) IF (KKIT (LEVEL, I) .Nfc. 1) GO 10 60 I1=HKFT (I) I2 = FWFa (1*1 CO 10 J=l1 IC=COL(.J) IF (CLLT (LEVEL. IC) .GT. 0) GO TO 20 CONTINUE ,HR2 (50) , YY(330) ,MM1 (3 30) ,MM2 (30C) ,ROW (400 0) .COL (40 00) ,331) ,CLLT(30,301) ,RHPT (331) ,CLPT (301) ,CCHAIN(301) , ,STKLBD(30),IX(4GO),XSL(180) t STKXQ(30),XO(500),XU(2 00) ) ,KP,XP,JX,INCUMB (300) , FKKY, ZBA R , ZH1K , LEVEL, , DVSN.P1, P2, P3,P44,CHEAD,JP,JQ, Jyy, JU, Rl ,KP D-1 ,12 CONTINUE COt IC 15 I H D=1 XP=XF+1 XSL (XF)=IC Jl=CLPT (IC) J2=CLPT (IC* DO 30 J = J1, IK = RCH (.)) YY (1R)=YY(I IF (RHL'KLE I1=RWFT (IR) I2=RWFT (IK* CO 25 L = I1. CC=COL (L) MM? (CC) =1 CLLT (LEVEL, RHIT (IEVEL, CLLT (LEVEL, CONTINUE KP = STORE ALl T ANC CHECK I CE')C=CHEAD FK=0 CC 70 1 = 1, N IF (>:iLT(LE TF 01M2 (I) CCHA1N (CF.IiD CENE=I nn2(i)=o CONTINUE IF (FK .EO. A FEASIBLE IHE = 2 FET'IPN CONTINUE CCHf IK (CFCC FETUP.il ESSENTIAL D-1 J 2 R) +1 VEL.IR) .LE. 0) GO TO 30 D-1 12 CC)=CLLT (LEVEL, CC) -1 IR)=0 IC) =0 HE COLUMNS THAT NEED BE CHECKED AJAIN IN CCHAIN F A FEASIBLE SOLUTION IS POUND VEL.I) .ST. 0) FK=1 .EO. 0) GO TO 7 )=I 1) GC TC 75 SOLUTION IS FOUNC )=-! 15/59/27 MM2 I3300 MM2 I 3400 » MM2 I 3500 MM 2 I3500 (4000) ,MM2 M700 1), MM2 I3800 U (200) ,MM2 I3900 MM 2 I'tOOO MM2 14100 MM2 14200 HM2 H300 MM2 14400 MM2 14500 MM2' 14600 MM2 14700 MM2 14800 MH2' 14900 MM2" 15000 MM2 5100 MM 2 15200 MM 2 15300 MM2" 5400 M12 15500 HH2' 5600 MM2' 15700 MM2' 5 800 MM^ 5900 MM2 16000 HM2 16100 NM2 I6200 MM2 I6300 MM2 I6400 MM2' I6500 MM2 I6600 MM2 I6700 MM2 I6800 MM2 I6900 MM 2 I70C0 MM2 17100 MM2 7200 MM2 I 7 300 MM2 I7400 MM2 7500 MM2 1 7 600 MM2" 7700 MM 2' 7800 MM2 I7900 MMi I8000 MM2 3 1 00 MM2 |fl.!00 MM 2 13300 MH2' T400 BM2 «500 MMi' 8 b 30 :m'i' 9700 MM 2 8 8.10 MM2 18900 M"12 19000 MM 2 19130 117 FOHIRAN IV <; LEVEL 21 HESNI DATE = 77259 15/59/27 118 00U9 END MH219200 FORTRAN IV G LEVEL 21 TPNF DATE 77259 15/59/27 119 P0001 00o2 0003 OO0U 00(£ OCut 0'J0 7 OolO 0C09 00 iO 0011 0011 00 I J 001 1* 0011> ocu 1/0 17 ocib 0014 co:o 00 ^ 1 .=CLPT (VAF» 1) -1 .)L = Jl-.l1 CO HO J=J1,J2 IF = 3C« (J) FBUh (IF) =PPUF (IP) -1 IF (IBUF (ID .GX. 0) 10 TO HO FV=PV+1 CBUF (FV) =I» HO COHIIHUF IF (PV .10. 0) GC TO BO Flllti CANDIDATES FOR SUBSTIl'UTIUG VAR IP=OB0F (11 MM219300 MM219U00 MM213500 .MM219600 MM219700 .MM219000 MM219700 MM220000 MM220100 MM220200 HM220300 HM220U00 MM220500 MH220600 NM220700 MM220800 MM220900 HH221000 MM221100 MM221200 MM221300 MM221H00 MM221500 MM221600 MH221700 MM221800 MM221900 MM222000 MM222100 MM222200 MM222300 MJ1222U00 MH222500 MM222600 MM222700 MM222U00 MM222900 MM223000 MM22 3100 MM2232Q0 MM223300 HI1223 400 .1M2235UO (1M2 2 3 600 11 [1223700 HM223300 MM2 2 3 900 MMi2«000 MM^2l» )00 kh;.2<»200 MN224300 Mtl22'i'<00 MM*2a500 MM22Uc00 MM22U7G0 tWU2U9 )0 HM:2U900 M»U250JO title 25 '.00 FORTRAN IV J LEVEL 21 IRHF 0033 I1=RWET (IR) 003U C I2 = R^ET (IRM)-1 0035 CO 60 K=I1,I2 0036 IC=COL (K) 0037 IF (IC . EO. V»F) GO TO 60 003U R1=CLPT (IC) 0039 K2=CLPI(IC»1)-1 OOUO C c c c IF Ml .GE. (K2-K1) ) GO TO 60 COL IC COVERS MORE VECTORS Tilt 15 IT FEASIBLE IF WE SODSTIXIIT 00« I IF |PV .EQ. 1) GO TO 55 0OU2 LO 50 L=2,PV OOUJ JR = OBUF (I,) 00 'IU LL = K1 0045 <45 IF (IR .EO. ROW (LL) ) GOTO 50 >Ju«b I" (±R .LT. ROW (LL) ) GO TO 60 00u7 L1=LL»1 ooue IF (11 .GT. K2) GO TO 60 0C<*9 GO TO U5 oo : i c 50 CONTINUE IT IS FEASIBLE or 3i c 55 CPNTIM1E REPLACE VAR BY IC 0L5? VAP^IC 00 03 .)L = K2-K1 0054 J1=K1 001/5 c J2 = K2 SFT SWITCH ON 003b SW = 1 005 7 c 60 CONTINUE 0058 INCUHB(I)=VAR 0059 CO 70 J=J1.J2 00'; IR=HCW (.]) COfcl 70 EOUF (IR) -=PBUF (IR) +1 0002 GO TO 100 00 6 3 80 CO NT I HUE c VAH CAN BE DELETED FROH INCUHB OOuU J = I + 1 00t5 IF (J .GT. ZBAP) GO TO 95 00f6 CO 90 K=J,ZBAR 0017 9C :NCUr.F (K-1) = 1NCIIMB (K) OUbfi 95 7,PAh = ZBAP-1 0Cb9' 100 CONTItlOE 00 70 IF (SW .FO. U) RETURN CC71 GO 10 35 Of. 71 END DATE = 77259 15/59/27 120 P1M225200 (1M225300 NM225U00 MN225500 HH225600 API225700 MH225 300 NM225900 HM226000 HH2261O0 HN226 200 MH226300 HM226U00 JM226500 I1M226600 MK226700 HM226B00 HM226900 MH227000 (1H227100 HH227200 NH227300 NH2271I00 HM227500 (1H227600 HN227700 B.M227800 (1fl227900 HH228000 NH228100 NN228200 HM228300 HB228K00 HM228500 HM228600 11(1228700 (1H228800 MM228900 HN229000 MM229100 HM229200 MH229300 tiii229aoo HM229500 MM229600 HH229700 HM229800 HH229900 3(1230u00 MH;30 100 121 The above program can be executed with the following Job Control Cards: /*ID // EXEC FTNHLKGO, REGION -FORT=348K, REGION-GO 128K [SOURCE PROGRAM] //GO-SYSIN DD * [DATA CARDS] /* 122 APPENDIX II FLOW CHARTS OF THE PROGRAM ILLOD-MINIC-BS We give only the flow charts of the program ILLOD-MINIC-BS, since we believe that this program is the most complex one among the five programs. If one understands this program, then the other four programs can easily be understood without the flow charts of the four programs. The flow charts of the program ILLOD-MINIC-BS are shown in the fol- lowing Figures Al through A8. 123 ( START 3 PRINTING !_ y_ INTIALIZATION C 4- REDUCTION BOUNDING L BRANCHING CHECKING BACKTRACKING TRNF STOP ) 7S -y Figure Al Flow charts of the main program, 124 REDUCTION r. Figure A2 Flow charts of the REDUCTION procedure. 125 REDUCTION BOUNDING r FIND A LOWER BOUND ZMIN OF THE SOLUTION 1 Figure A3 Flow charts of the BOUNDING procedure. 126 [ING BOUNDING BRANCE 1 \ ' 1 1 SELECT ONE ROW 1 V BASED ON THE SELECT ROW DECOMPOSE THE CURRENT PROBLEM INTO SUBPROBLEMS \ 1 PUSH ALL THOSE GENERATED SUBPROBLEMS INTO A STACKXX > PUSH UP ONE SUBPROBLEM L_ \f CHECKING -A Figure A4 Flow charts of the BRANCHING procedure 127 BRANCHING CHECKING r CHECK IF THE CURRENT SUBPROBLEM SATISFIES BACKTRACK CONDITION "1 Figure A5 Flow charts of the CHECKING procedure REDUCTION PRINTING PRINT THE FEASIBLE SOLUTION FOUND 1 UPDATE THE UPPER BOUND ZBAR OF THE OPTIMAL SOLUTION | L 1 / ._ J BACKTRACKING Figure A6 Flow charts of the PRINTING procedure 128 PRINTING BOUNDING BACKTRACKING r _^ J