Digitized by the Internet Archive in 2013 http://archive.org/details/implicitenumerat884youn Report NO. % UIUCDCS-R-77-884 UILU-ENG 77 1740 AW IMPLICIT ENUMERATION PROGRAM FOR ZERO -ONE INTEGER PROGRAMMING - ILLIP-2 by Ming Huei Young rune 1977 DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN URBANA, ILLINOIS The Library &f the SEP 3 1977 University or Illinois '.aign Report No. UTUCDCS-R-77-881+ AN IMPLICIT ENUMERATION PROGRAM FOR ZERO-ONE INTEGER PROGRAMMING - ILLIP-2 by Ming Huei Young June 1977 Department of Computer Science University of Illinois at Urban a- Champaign Urbana, Illinois 6l801 ..is work was supported in part by the National Science Foundation under Grant 1. DCR73-03^21 and was submitted in partial fulfillment of the requirements ir the degree of Master of Science in Computer Science in the Graduage College ( i the University of Illinois at Urbana-Champaign, 1976. ill ACKNOWLEDGEMENT The author wishes to express his gratitude to his advisor, Professor S. Muroga. His helpful advising in preparing of this thesis, careful reading and correcting of the original manuscript are most appreciated. Discussion with Dr. T.K. Liu of his program of ILLIP is acknowledged . The author would also thank his family's support during his study- in University of Illinois. This work was supported in part by the Department of Computer Science, University of Illinois and also the National Science Foundation under Grant No. DCR 73-031+21. Mrs. Arbatsky's nice typing is also appreciated. IV TABLE OF CONTENTS Page CHAPTER 1 INTRODUCTION 1 CHAPTER 2 NEW FEATURES IN ILLIP-2 3 CHAPTER 3 MODIFICATIONS OF ILLIP 8 CHAPTER k COMPARISON OF THE FORTRAN AND PL/l VERSIONS OF ILLIP-2 13 CHAPTER 5 SOME COMPUTATIONAL RESULTS 15 REFERENCES 23 CHAPTER 1 INTRODUCTION The integer linear programming problem can be stated as: minimize c • x subject to b + A • x > where c is a vector of n non-negative coefficients, b is a column vector of m constraints, A is an m x n matrix and x is a column vector of n integer variables. When variables are restricted to zero or one, the problem is called the zero-one linear programming problem. Many problems such as logical network design problems, traveling- salesman problems, flight-scheduling problems and set covering problems can all be formulated into zero-one linear programming problems [l]. The implicit enumeration algorithm, developed and improved by Balas [2], Glover [ 3 ], Geoffrion [4], Ibaraki, Liu, Baugh and Muroga [ 5 ], is a very powerful algorithm for solving the zero-one linear programming problem. A computer program package named ILLIP was developed based on the algorithm, incorporating improved procedures discussed in [ 5 ] such as -pseudo- underlining". Since its completion in 1 9 68, ILLIP has been used by many i people inside and outside the University of Illinois. In this paper, ILLIP-2, a revision of ILLIP is presented. ILLIP-2 adds new options that (1) find more than one optimal solution, (2) print feasible solutions found during the executioin i (3) at a user's specification, it can skip checking underlining and pseudo-underlining conditions, (h) find a suboptimal solution which has a specified deviat: from an optimal value (only one suboptimal solution). ;ion Some minor mistakes in ILLIP are also corrected. Although ILLIP is available in FORTRAN, the ILLIP- 2 is available in both FORTRAN and PL/ I. This report describes new features added in the ILLIP- 2 and how the ILLIP is modified. The features of the FORTRAN and the PL/ I versions are compared. Some computational examples by ILLIP and ILLIP- 2 are presented. Computational result shows that ILLIP- 2 is more efficient than ILLIP. Also more error messages will be printed when the input data prepared by a user are not in correct form. Integer programming with non-linear objective function or non- linear constraints can be converted into zero-one linear problems. Conversion methods are discussed in [12], Reader who wants to modify the program in order to more efficiently solve their problems can get sufficient information from [12]. CHAPTER 2 NEW FEATURES IN ILLIP-2 Four new features have been added in ILLIP-2. 2.1 Alternative Optimal Solutions. The first feature added is that a user can specify a maximum number of alternative optimal solutions he wants. The user provides two parameters to the program; one indicates that more than one optimal solution is desired and the other parameter indicates the number of alternative optimal solutions that he needs. When the number of alternative optimal solutions is greater than the number specified, only the specified number of alternative optimal solutions is printed. When the number of alternative optimal solutions found is less than or equal to the number specified, only those that are found are printed. In order that this feature be implemented, some subroutines in ILLIP are modified and two subroutines, NEWSOL and STRSOL, are added to the main subroutine CHK-IEQ (Check-Inequality). (1) NEWSOL • When the CHK-IEQ routine finds the first feasible solution, the CHK-IEQ routine will call subroutine NEWSOL to clear all the previous best feasible solutions that have been found and to store this new feasible solution as I the best feasible solution. (2) STRSOL ! When the CHK-IEQ routine finds a feasible solution which has the same objective I i value as the best feasible solution that has been found, the CHK-IEQ routine will call subroutine STRSOL to store this new feasible solution along with the best feasible solutions found so far. h Incorporating these two subroutines, the CHK-IEQ of ILLIP procedure is modified as shown inside the dotted line square in Figure 2.1. In order to facilitate finding more than one optimal solution, some modifications were made in the algorithm stated in [6], as follows. 1. The inequality ZMAX-1 - c • x > that is augmented to the constraints is changed to ZMAX-c • x > 0. 2. When a new feasible solution is found in CHK-IEQ,, this solution has to be tested whether it is better than the solution in the incumbent. 3. The underlining condition [5]: "When a. . < for all i such that £. (s) < 0, x. =0 can be immediately added with an underline to the current partial solution'.'" is changed to "When a. . < for all i such that i. (s) < and c. > 0, x. =0 can be immediately added with an underline to the current partial solution". This is because if c. = 0, then there may exist some feasible completion of { s, j } which has the same objective value as the best feasible completion of (s,-j} has. Thus this change is necessary when we want more than one optimal solution. h. Let Q be the set of the indices of the fixed variables with value 1. Let NCX = Z C When some free variable x. not in Q, is forced to 1 ieQ X J and NCX + c . equals the best value z found so far, there may exist some completion of {s,j} which has the objective function value z. So we do not backtrack when more than one alternative optimal solution is desired. S = AGM-VAR no BACKTRACK < .1 is augmented to the constraints b + Ax > instead of ZMAX-1 - c • x > 2.3 Printing of feasible solutions. The third feature added in ILLIP-2 is that a user can specify that some of the feasible solutions found during the execution of the program be printed. The user provides the program three parameters. One specifies this option and the other two parameters specify which feasible solutions are wanted. When the feasible solutions specified are found, they are printed with their objective function values. How to specify this option is describee in the manual of ILLIP-2 in [12]. To implement this feature we only need one subroutine to print feasible solutions found. 2.k Skip Of Checking Underlining And Pseudo-Underlining Conditions. For some problems (e.g., logical network design problems and traveling salesman problems) pseudo-underlining and underlining conditions are seldom satisfied; then the time spent for checking these conditions is wasted. The fourth feature added in ILLIP-2 is that a user can specify whether the underlining and pseudo-underlining conditions are to be checked or not. The input specifications of this option are described in the manual of ILLIP-2 [12]. In order to do this a special checking routine is added in ILLIP-2. (See the flow charts in [12].) Execution results show that, for logical network design problems, the use of this special routine has reduced computation time by roughly 10$ on the average. 8 CHAPTER 3 MODIFICATIONS OF ILLIP Some other modifications have also been made to ILLIP. 3.1 Input Of Inequalities. The input of inequalities has been simplified even though the input format of ILLIP is not changed. By this change the core storage requirement has been reduced by at least h K bytes and the execution time is reduced. ILLIP first reads inequalities into an array variable INPT of length 2000 and then transfers these inequalities to array variables RWCF, COL, RWPT, RWLT (or CLCF, ROW, CLPT, CLLT) which store the inequalities in the program (the program is shown in [12]). In ILLIP-2, the inequalities are read directly into variables RWCF, COL, RWPT, RWLT (or CLCF, ROW, CLPT, CLLT). k K bytes storage for variable INPT is saved. 3.2 Set-Up Of Initial Partial Solution. Subroutine SINTL, which reads in a partial solution is slightly modified so that it can accept a partial solution with some variables pseudo- underlined. The original ILLIP can not accept a partial solution with variable pseudo-underlined. This is inconvenient when we need to provide some partial solution with variables pseudo-underlined as an initial partial solution. 3.3 Initial Upper Bound. If initial upper bound ZMAX supplied by a user is exactly equal to the optimal value of the problem, ILLIP can not detect this optimal solution and will find the problem to be infeasible. The program is modified so that ILLIP-2 can detect an optimal solution when the initial upper bound supplied is equal to the optimal value of the problem. 3.h Check Of Input Sequence. ILLIP-2 will check the increasing column index sequence of each row (or the increasing row index sequence of each column) in the input of in- equalities. If the sequence is not in increasing order for each row (or column), the program will give a message to a user and stop the execution, since an incorrect sequence of the input of the inequalities will supply the program inequalities different from those of the problem. ILLIP does not check the increasing row sequence (or column sequence). If the inequalities are not pre- pared as stated in [7] (i.e., column sequences or row sequences are not in in- creasing order), the result obtained from ILLIP will not be a correct solution. 3.5 Check Of Augmenting Scheme Number. When a scheme number supplied by a user is different from 1, 2, or 3, ILLIP-2 will assume the scheme number to be 1, give an error message and continue the execution instead of halting execution in ILLIP. 3.6 Inequality-Checking Procedure. The checking procedure used in ILLIP is line checking, i.e., all the inequalities are checked one by one from the first inequality to the I last inequality. This is repeated until no more new free variables are forced to or 1. In ILLIP-2 (FORTRAN version) the chain-checking procedure discussed I in [5] is used, i.e., all the inequalities that must be checked are chained ; together and only these inequalities are checked. When a new condition 10 occurs, some inequalities not in the chain may need be checked again and are added to the chain. When an inequality is checked, it is deleted from the chain. By this way of checking, the time used in exammining which in- equality needs to be checked is saved. For logical network design problems, the use of chain-checking procedure reduces the computation time by 30$. 3-7 Output Printing. The print-out routine in ILLIP is modified such that it can print additional alternative optimal solutions when more than one optimal solution is desired. 3.8 Card Output. The routine SOLPNH in ILLIP that punches out a partial solution is modified such that it also punches out the best feasible solution found so far, if any, and also alternative best feasible solutions if more than one optimal solution is desired. All these solutions and related information which are punched will be used for resuming the next run, when the computation is interrupted. 3.9 Reading-in Of Solutions. The routine SINTL in ILLIP that reads in a partial solution is modified such that it not only reads in a partial solution but also the best feasible solution found so far, if any, and also alternative best feasible solutions if more than one optimal solution is desired. 11 3.10 Printing The Number Of Feasible Solutions. The total number of feasible solutions found during the execution will be counted and will be printed at the end of the execution or at every finite number of iterations specified by a user. 3.11 Optimization Of Source Program. The source program of ILLIP is optimized in ILLIP-2 so that the execution efficiency is improved by $%• 3.12 Core Storage Occupied Ey Variables. Since each PS(l) (NS(l), and YS(l) ) occupies only 2 bytes in ILLIP, it will be overflow when coefficients of inequalities are too large. It is modified in ILLIP-2 that each PS(l) (NS(l), and YS(l)) occupies k bytes. 3.13 Augmentation Schemes. The following is not a modification but it is pointed out that Scheme 3 of AGMT-VAR used in ILLIP is not the same as the one stated in [5], [6], [7]. Scheme 3 used in ILLIP is selection of a free variable x . which maximizes J m Z min (y.(s) + a... 0} + Z a.. 1*0 X 1J i6U 1J among all free variables x., where u = (i|y 1 (s) > 0, yi (s) + a < 0} 12 It is different from what is stated in [5], [6], [7] selection of a free variable x. which maximizes J m Z min {y. (s) + a. ., 0} 3=0 X 1J among all free variables x . . J Computational experiments show that Scheme 3 used in ILLIP is more efficient than Scheme 3 stated in [5], [6], [7] (by 30°/o to 60% for some examples in Chapter k). 13 CHARTER k COMPARISON OF THE FORTRAN AND PL/l VERSIONS OF ILLIP-2. The PL/ I version of ILLIP-2 differs from the FORTRAN version in input format, storage allocation, execution efficiency and procedure of checking inequalities. (1) Input format. In the FORTRAN version the input format is fixed, i.e., each input data has to be punched in some fixed input fields specified by the program. This will take a user more time to prepare this input data. In the PL/l version the input format is not as fixed as that of the FORTRAN version and can be more easily prepared. (2) Storage allocation. In the FORTRAN version, the length of each array variable is fixed. In order that this program can be used to solve big problems (i.e., a large number of variables and a large number of inequalities), each array variable is assigned a sufficiently large length. The user of this version can not change it unless the program itself is modified. When a small problem is to be solved by this version, a lot of core storage for the big array is wasted. The lengths of array variables in the PL/ I version are to be specified by a user at the beginning of the execution of the program. When a small problem is to be solved by the PL/ I version, the user can claim a Ismail array length for each variable and only a small amount of storage is then used. * See Chapter 5 of the Manual of ILLIP-2 [12]. Ik (3) Execution efficiency. Computational results show that the FORTRAN version is more efficient than the PL/ I version. Some problems solved by the FORTRAN version take one third to one fifth of the time it will take when solved by the PL/ I version. The difference is caused by the difference in the compiler efficiencies of the different languages; i.e., the code generated by the FORTRAN compiler is more efficient than the codes generated by the PL/ I compiler. (k) Checking procedure of inequalities. The inequality checking procedure used in the PL/ I version is a sequential checking and the checking procedure used in the FORTRAN version is a chain checking. This is because large scale problems would be solved by the FORTRAN version only and there is no point to speed up the execution of the PL/ I version. 15 CHAPTER 5 SOME COMPUTATIONAL RESULTS In the following tables, Tables 5.1 through 5. 5, each number in each column under 'sec.' shows the time (in seconds) used, and each number in each column under 'ITER.' shows the number of iterations for solving each problem. The computational results are obtained by running the program on an IBM 36o/75I< The compilers used are FORTRAN H with option 2 and PLX. The time indicated in each table includes the initialization time, i/O time, and computation time. Entry * - ' in each table shows that the test was not made. (1) General zero-one linear programming problem. Several general zero-one linear programming problems with different sizes were tested. The coefficients of each problem are randomly generated. The computational results are shown in Table 5.1. (2) Generalized set covering problems. A generalized set covering problem is: n minimize Z c.x. 0=1 3 J n subject to Z a. .x . > 1, for i = l,2,...,m, 0=1 1J J x. = or 1 for j = l,2,...,n, J where a. . = or 1 for i = 1,2,. . .,m, j = 1,2,. ..,n, and c.'s are non-negative integers. Two such problems with different sizes are tested. The coefficients a. . are randomly generated with non-zero density of 0.10. The computational results are shown in Table 5.2. Table 5.1 Computational results of general zero-one linear programming problem. 16 FORTRAN VERSION PL/ 1 VER. NO. OF VAR. NO. OF INE.}. SCHEME ILLIP ILLIP- 2 SINGLE SOL. ILLIP- 2 MULTIPLE SOL. ILLIP- 2 SINGLE SOL. SEC. ITER. SEC. ITER. SEC. ITER. SEC. ITER 15 35 1 2.17 488 1.86 488 1.80 495 - - 2 2.70 488 1.78 488 1-77 495 - - j 2.25 488 1.73 488 1.82 495 8.37 488 k* - - 3.42 718 5.20 1193 - - 12 4 1 0.1+7 25 0.35 25 0.35 25 - - 2 0.40 21 O.32 21 0.38 22 - - 3 o.46 16 0.30 16 0.36 18 0.92 18| 4* - - 0.49 23 0.49 23 - ~ 15 15 1 1.25 227 1.04 227 1.31 287 - - 2 1.32 227 1.18 227 1.25 287 - - 3 1.17 148 0.8 148 O.98 194 - ~ t* - - 2.39 524 - - - - 23 4 1 1.4l 381 1.47 381 1.77 46l - ~ 2 1.68 384 1.52 384 1.95 465 5.75 384 3 1.97 528 1.96 528 2.34 634 - - 80 12 1 - - (49.92) 5773 - - - - 2 - - (50.58) 5773 - - - - J - - (54.34) 5026 - - - " ! * Sc] Mil ieme 4 j Ltiple £ .s the a solution ugment is are j Scheme ?ound . 3 as state id in [5] , [6], [ 1 71. *** This result is provided by George, Bob. The time in parentheses shows only computation time, while the time without parentheses includes the initialization, I/O time, and computation time. 17 Table 5*2 Computational results of generalized set-covering problems. FORTRAN VERSION PL/ 1 VER. [0. OF NO. OF niEQ. SCHEME ILLIP ILLIP- 2 SINGLE SOL. ILLIP-2 MULTIPLE SOL. ILLIP-2 SINGLE SOL. VAR. SEC. ITER. SEC. ITER. SEC. ITER. SEC. ITER. 15 1 1.00 91 0.81 91 1.55 281 - - 2 0.95 91 0.79 91 1.62 28l - - jO 3 1.10 91 0.75 91 1.62 281 6.52 2BT 4* - - 1.84 341 5.52 1283 - - So 25 1 7.80 1703 6.82 1703 10.68 2794 - - 2 8.40 1703 7.43 1703 11.46 2794 - — 3 7.57 1703 7.14 1703 11.08 2794 32.39 1946 k* - - >19-52 >5,000 - - - - See the footnote of Table 5.1. -*■# For multiple solutions. (3) Traveling Salesman Problem. Traveling salesman problem is: n n minimize Z Z d. .x i=l j=l 1J 1J subject to 18 Z x. . = 1 for j = 1,2,. ..,n , i=l ij n Z x. . = 1 for i = 1,2,. ..,n , x. . = or 1 for i = 1,2,. ..,n , J = 1,2, . . . ,n , and Z Z_ x. . > 1 for every s c (1,2,. . . ,n} i€s j£s lt} where d. .'s are given non-negative integers. This problem is reformulated as [8] minimize Z Z d. .x._. ii M li iJ subject to n Z x. . = 1 , j = 1,2,. ..,n , i=l iJ n Z x..=l , i=l,2,...,n , u. - u. + (n-1) x. . < n - 2 , 2 < i I j < n , 19 x. . = or 1 for i = 1,2,. ...n , J = -L j £:, • • . ,n , u. : integer smaller than n - 2, for i - 2,3,...,n . Each variable u. is converted into zero-one variable as stated in Appendix. Three problems were tested. The coefficients d.. were randomly chosen. The computational results were shown in Table 5«3« (h) Logical network design problem. This problem is to find a logic network consisting of a fixed number of NOR gates which realizes a given switching function and minimizes the number of interconnections. The formulation of this problem into zero-one linear programming problem is discussed in [9], [10], [ll]. Three different switching functions of three variables were tested. The computational results are shown in Table 5.k, (5) Comparison of two cases with and without checking underlining and pseudo- underlining conditions. Underlining and pseudo-underlining conditions are seldom satisfied In some types of problems (e.g., logical network design problem and traveling salesman problem). For some other types of problems (e.g., generalized animal covering problem), checking these conditions will greatly reduce computation time. Several tests have been made. The comparison is shown in 'able 5.5. 20 ft OJ • ft cn • ft EH 1 o | 1 1 i 1 i 1 W OJ o H H B ft w H a a ■■^^ ft ir\ ft H ft • C*- ft H CO O ft CO OJ 1 1 i 1 ' 1 . CD • ft OJ H H UA co H O H ft ft as VO OJ cn CO VO o rQ O EH LT\ C- H I [— ft VO o 1 o co H H H OJ OJ cn ro »\ u ft IP- 2 PLE ft a o3 ft H * £ ft EH *PO H UA r— OA UA ft w H ft • H UA VO CO CO H VO a; j^ O • • • I • • 1 H § ft OJ H OJ CO ft d t- o3 CO H H H H OJ OJ oo w A bO , d ft CO CO OJ O VO C3A no o co •H • ft H t- ft O OJ H no o H H s ft EH H o VO o no OJ o o H 0) O O H H H H »\ H H OJ •\ •N r> a3 H CO oj co i ft 7{ VO o fH ft ft H p Pr*l H ft ^ 3 3 UA UA C*- ft [— l>- c— o OJ O H C5 ft H vo ft CO c- t- OJ CM o t— w o t- D— O 00 CO CO OJ o UA +3 & CO ft H H CD OJ i CO A A VO w EH ft cd Ih O ft • - ft 1 OJ H m 1 1 a EH H o vo cn OJ o o M H H H H H OJ •H ft ■P H ft a5 -p ft 3 H UA O- t- o UA UA & • VD UA o co 0J H g O • • • 1 • 1 1 o ft 0O CO OJ o" ON ro CO H H • UA 1 CD @ * * H ft H OJ ro ft H OJ no ft- cn ft O a3 co EH ft O G? t ft- o • ft J- ft- vo O H ft ^ ft O ft u A ua o • £ 1- ft- VO o >7* »=-H ft ° £ • H M 3 vo c— Q O ft H a3 S •H -P ft O CD !> ■H •P 03 C *h CD +3 H 03 O ft CD w CD ft p % O d o3 • >5 O H H £ O +3 W "> fH W •H C ft O •H ..> +3 T5 03 a ^ J3 CD O +3 ft 'H CD 0J U CA CD ft % H W T3 fl c • O 03 H •H • p w UA ^i T3 H fl cd O O rH w o ft CD a? H w H 03 S UA ft •H UA O P • PiO CD O H ft o CD ft PI > o ft •H O O P P 03 ft £ w ^ C CD CD O ft p -H -P H -P 03 ^5 CD H iD o o CO ft- w * * 21 CO K EH O co pq Eh CO W O 1-^ o co g H CO L5 O H O M O fin H (J hH 1 H O P a? P*H C > • W • £^ o ^> s P=H o CO H o a CJ cu to H J- • o 0) CO O VO ON 0O VO CM H O * C— VO CO t- • • m vo CM H O (D * co ^~-s LTN H H O • • C— O CM CM CM ON ON o ON ON 0O H -H/ 0O ON H VO o CD CO H r- CO H o CD CO CO vd o CD CO ON VO • vo -eh o CO LfN CO LTN H cj CD * CO '-^ CO CO LfN t— • • -=t 00 CO VO -H/ -=t" H ON vo H VO CM C- H ct? O •H -P cS 1 O o CD .3 -P o co CO •H CO CD ct3 ft CD ■P id •H -P CD G X CO o id cd o X! •H o •P •H -p T5 3 g o o x CJ -p •H hn ? G •H ^H g o •H H X h -p a) •H ■n >> G 3 w | CD o w T> crt d o 0) to e ft t> -p Ti G

H fi H s o ^J CD Eh crt £ U H CO T3 ft O X ^^ ft CD £ O Eh H bO N "^ ^ pq H G •H g 3 G° CD Ph |25 O crt H CD crt »H G K *H CD H !h M a ho Ph 0) > X a; cd •H tH g crt O G > bo w (D ?h fn CD O 5S Cl3 Eh ft C5 O CO S o H EH H g ft H OO ro LTN o o ft CO OO O LTN S O EH no O C*- 00 H H H H •\ S | P H K S W H 5 w Q * * * C5 g ,. — ., S b • oo cu OJ OA H 1 O _-± VO CO OO ^ O H • • t- ° R 1 CO H vo VO O CO ft W EH Q H 3 rs < CO s o H EH C H B § PC O H CO LA s o H o OJ o LT\ m a EH -H- H o CO S c5 hn H OJ w s H p H fe S; b H J O K S W H P v « S * * * o b • **""N s — v •— "s § o o CO c— CA -=!■ m H o VO CO o p co • • • -H- t^ r-H VO o Eh W b CO v -' H O ft M £ e S 3 ft w o a? N] p^ -Hr -H- IT\ LT\ H • ^ -H- CM H CO g M l>- 1 ft pq o O « OO LT\ O co ps • 2C OJ -H- VO LTN ft o > OJ - ■ o •H crt * ft CD XI -p G O 1 X CO oo •H CO CD X ■B CD crt ft CD X -p G •H -P CD 23 REFERENCES [l] Balinski, M.L. , "Integer Programming: Method, Uses, Computation," Management Science, Vol. 12, No. 3, 1965. 2] Balas, E. , "An Additive Algorithm for Solving Linear Programming With Zero-One Variables," Operations Research, Vol. 13, No. k, pp. 517-5^, 1965. [3] Glover, F. , "A Multiple Phase-Dual Algorithm for the Zero-One Integer Programming Problem," Operations Research, Vol. 13, No. 6, pp. 879- 919, 1965. [k] Geoff rion, A.M., "Integer Programming by Implicit Enumeration and Balas' Method," SIAM Review, Vol. 9, No. 2, pp. I78-I9O, 1967. [5] Ibaraki, T. , T.K. Liu, C.R. Baugh and S. Muroga, "An Implicit Enumeration Program for Zero-One Integer Programming," International Journal of Computer and Information Science, Vol. 1, pp. IO9O-IO96, 1972. [6] Ibaraki, T. , T.K. Liu, C.R. Baugh and S. Muroga, "An Implicit Enumeration Program for Zero-One Integer Programming," Report No. 305, Dept. of Computer Science, Univ. of 111. [7] Liu, T.K. , "A Code for Zero-One Integer Linear Programming by Implicit Enumeration," Report No. 302, Dept. of Computer Science, Univ. of 111., I968. [8] Miller, C.E., A.W. Tucker and R. A. Zemlin, "Integer Programming Formulation of Traveling Salesman Problems," Journal of ACM, Vol. 7, pp. 326- 329, I960. .9] Muroga, S. and T. Ibaraki, "Logical Design of an Optimum Network by Integer Linear Programming - Part I," Report No. 26U, Dept. of Comp. Sci., Univ. of 111., July, 1968. -0] Muroga, S. and T. Ibaraki, "Logical Design of an Optimum Network by Integer Linear Programming - Part II," Report No. 289, Dept. of Comp. Sci., Univ. of 111., Dec. 1968. 1] Muroga, S. and T. Ibaraki, "Design of Optimal Switching Networks by Integer Programming," IEEE TC, pp. 573-582, June, 1972. i|2] Young, M.H., T.K. Liu, C.R. Baugh and S. Muroga, "A Code for Zero-One Integer Programming ILLIP-2," UIUCDCS-R-77-858, Dept. of Comp. Sci., Univ. of 111., April, 1977. LIOGRAPHIC DATA ET 1. Report No. UIUCDCS-R- 77-884 3. Recipient's Accession No. it lc and Subt it le AN IMPLICIT ENUMERATION PROGRAM FOR ZERO- ONE INTEGER PROGRAMMING - ILLIP-2 5. Report Date July 1, 1977 Mirig Huei Young 8- Performing Organization-Re pt. No. utuCTjCS-r- 77-884 •rforming Organization Name and Address Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois 6l801 10. Project/Task/Work Unit No. 11. Contract /Grant No. NSF DCR73- 03 1+21 •ponsoring Organization Name and Address National Science Foundation 1800 G Street, N.W. Washington, D.C. 20550 13. Type of Report & Period Covered Technical 14. i. upplementary Notes I bstracts ILLIP-2 is an improved version of the program ILLIP. This report describes new features added in the ILLIP-2 and how the ILLIP is modified. Comparison of some computational results between the ILLIP-2 and the ILLIP are shown. y Words and Document Analysis. 17a. Descriptors ^ero-one linear programming, implicit enumeration method, partial solution, mderlining, pseudo-under lining, incumbent, backtracking, optimization. *■ entifiers/Open-Ended Terms : - j)SATI Field/Group ^lability Statement -lease unlimited 19. Security Class (This Report) UNCLASSIFIED 20. Security Class (This Page UNCLASSIFIED 21. No. of Pages 27 22. Price TIS-3S (10-70) USCOMM-DC 40329-P71 Brrn A * ICTqb 19) r~ 2 1979