# Full text of "A heuristic for constructing surrogate constraints for the linear zero-one integer programming problem"

## See other formats

RESEARCH REPORTS DIVIS NAVAL POSTGRADUATE SC MONTEREY, CALIFORNIA 9 NPS55-82-009 NAVAL POSTGRADUATE SCHOOL Monterey, California A HEURISTIC FOR CONSTRUCTING SURROGATE CONSTRAINTS FOR THE LINEAR ZERO- ■ONE INTEGER PROGRAMMING PROBLEM by Frank R. Giordano February 19 8 2 Approved for public release; distribution unlimited Prepared for: Naval Postgraduate School Monterey, ca 9 39 40 FEDDOCS D 208.14/2: NPS-55-82-009 DUDLEY KNOX LIBRARY NAVAL POSTGRADUATE SCHOOL MONTEREY, CA 93943-5101 NAVAL POSTGRADUATE SCHOOL MONTEREY, CALIFORNIA Rear Admiral J. J. Ekelund David A. Schrady Superintendent Acting Provost Reproduction of all or part of this report is authorized. UNCLASSIFIED SECURITY CLASSIFICATION OF THIS PAGE "Then Data Entered) REPORT DOCUMENTATION PAGE READ INSTRUCTIONS BEFORE COMPLETING FORM I. REPORT NUMBER NPS55-82-009 2. GOVT ACCESSION NO. 3. . RECIPIENT'S CATALOG NUMBER 4. TITLE (and Subtitle) A HEURISTIC FOR CONSTRUCTING SURROGATE CONSTRAINTS FOR THE LINEAR ZERO-ONE INTEGER PROGRAMMING PROBLEM 5. TYPE OF REPORT 4 =ERIOD COVEREO Technical 6. PERFORMING ORG. REPORT NUMBER 7. AUTHOR)"*; Frank. R. Giordano 8. CONTRACT OR GRANT NUMBE a '»v 9. PERFORMING ORGANI ZATICN NAME AND ADDRESS Naval Postgraduate School Monterey, CA 93940 10. PROGRAM ELEMENT. PROJECT, TASK AREA 4 WORK UNIT NUMBERS II. CONTROLLING OFFICE NAME AND ADDRESS 12. REPORT OATE February 1982 13. NUMBER OF PAGES 19 14. MONITORING AGENCY NAME 4 lOORESSCH different from Controlling Office) IS. SECURITY CLASS, 'of thta report) UNCLASSIFIED IS«. DECLASSIFICATION.' DOWN G R AOI N I SCHEDULE IS. DISTRIBUTION ST ATEMEN T (ol thla Report) Approved for public release; distribution unlimited, 17. DISTRIBUTION STATEMENT (of the abatract entared In Block 20, If dlffarant from Report) IB. SUPPLEMENTARY NOTES 19. KEY WORDS (Continue on raveraa elda If naeaeeary and Identify by olocx number) 20. ABSTRACT Continue on ravarea elda If naeaeeary and Identity by block number) In this report the author presents a heuristic for constructing surrogate con- straints to be used for the solution of the linear zero-one integer problem. Using the heuristic the author was able to build surrogate constraints with strength comparable to the dual multiplier surrogate in one-tenth the time. DD i JAN 7 j 1473 COITION Of I NOV 88 IS OBSOLETE S/N 0102-014- 4801 UNCLASSIFIED SECURITY CLASSIFICATION OF THIS "AGE (When Data Interadl 1 . BACKGROUND 1.1 DEFINITIONS Given the binary linear integer programming problem Minimize {cx|Ax<_b, x=(0,l)} (1 where A is an m by n matrix, a surrogate constraint for prob- lem (1) is defined as follows: u(b-Ax) > 0, u = (u,,u ,...,u ), u > 0. (2) — 12m — We will also find it convenient to define a corresponding one-constraint (knapsack) surrogate problem: Minimize (cx|u(b-Ax) 0, u >_ , x = (0,1)}. (3 1.2 PROPERTIES Because the vector u implies that the solution set to inequality (2) contains the solution set to (1), we have the following properties: 1. If x* is a feasible solution to (1) it is also feasible to (2) and (3) . 2. If the surrogate constraint (2) has no feasible solution, then neither does the original problem (1) • 1.3 USES Surrogate constraints are used in conjunction with implicit enumeration algorithms (e.g., Balas) in several ways. Each vertex in an enumeration tree represents a restriction of problem (1). Problems (1), (2) and (3) can be written in explicit terms of the restriction being studied by substitution of the variables assigned values by the restriction. If it can be shown that a surrogate constraint corresponding to a vertex has no feasible solution (completion) , then the vertex being studied can be fathomed by Property (2) . If the vertex cannot be fathomed, Property (1) allows the surrogate to be appended to the constraint set as a valid constraint to be used with the implicit enumeration tests to identify promising variables for further exploration. Further, if the solution to Problem (3) corresponding to the vertex restriction is known, it provides an upper bound on the original problem (1) if it is feasible for (1) or a lower bound on the vertex restriction if it is infeasible for (1) . 1.4 STRENGTH OF SURROGATES In order to choose u > 0, Glover [1965] defined surrogate 1 2 u (b-Ax) > to be stronger than u (b-Ax) > if 1 . Min {cx|u (b-Ax) >_ , x= (0,1)} > Min {cx|u (b-Ax) > 0, x = (0,1 for u 1 , u 2 > 0. (4) This definition states that if the corresponding surrogate knapsack problems (3) are resolved, the surrogate resulting in the more restrictive lower bound to problem (1) is stronger Essentially, that surrogate eliminating more solutions (as measured by the objective function) is the stronger. This is intuitively appealing since by Property (1) the surrogate cannot eliminate any feasible solutions to the original prob- lem. Thus by this definition we should choose u as follows: Max Min {cxju(b-Ax) ^ 0} (5) u>0 x=(0,l) Unfortunately (5) is difficult to solve for general cases, although Glover [1965] has studied the two constraint case. An approximation to (5) can be made by relaxing the integer restriction on x, i.e., choose u > satisfying Max Min (cxju(b-Ax) >_ 0} (6) u>0 0<x<l In a previous report the strength of the approximation (6) as measured by (4) was studied, Giordano [1982] . In this report we will present an alternative approximation to (5) and com- pare both the strength and speed of the alternative approxi- mation to the approximation suggested by (6) . 2. THE DUAL MULTIPLIER SURROGATE 2.1 DEFINITION The advantage of the relaxation to (6) is that it can be resolved optimally yielding u = v where v are the dual variables to the linear programming (LP) relaxation of (1) . Thus at any given vertex restriction, after substituting the variables assigned values, the LP written in terms of the re- maining free variables may be resolved and the optimal values of the dual variables used as weights to form a surrogate constraint. A surrogate so formed is called a dual multiplier surrogate. 2.2 PROPERTIES/USES As with all surrogates, if it can be shown that the dual multiplier surrogate has no feasible solution then the vertex can be fathomed. This test can be strengthened by requiring that the solution to the surrogate constraint also improve the current upper bound on problem (1) , Geoff rion [19 69] . After resolving the corresponding LP for the dual variables, the value of the free variables may be used to solve the LP relaxa- tion of (3) directly. Note in this case when solving for the dual variables we are solving the LP relaxation of (1) corres- ponding to the vertex restriction. If the values of the free variables are integer, problem (1) has been solved for that vertex and a new upper bound on the original problem has been obtained. If the values are fractional, then a lower bound for the vertex is obtained. If desired, heuristics may be applied to the fractional values to identify promising varia- bles for branching. 2.3 COMPUTATIONAL ADVANTAGES The dual multiplier surrogate has been widely used in conjunction with implicit enumeration algorithms and research has been conducted on frequency of use, maximum number of constraints to carry forward, and related matters. It is interesting to note the effect of the use of the dual multi- plier surrogate on the problem set studied, which includes 18 problems with up to 50 variables and up to 10 constraints. Seventeen of the problems required a total of 552.36 CPU seconds (CDC 6500) using a Balas Algorithm with heuristics. The same Balas Algorithm employing a dual multiplier surrogate generated every eight iterations and carrying a maximum of four surrogates forward solved the 17 problems in 32.15 CPU seconds. Problem 18, consisting of 50 variables and 5 con- straints, had not been solved optimally after 5631 CPU seconds using the Balas Algorithm but was solved optimally in 6.4 7 seconds when the surrogate was added. The results are sum- marized in Table 1, which is found at the end of this report. 2.4 OBSERVATIONS The dual multiplier surrogate has been a very significant contribution to implicit enumeration. Nevertheless, there are disadvantages inherent in the dual multiplier surrogate when applied to large problems. A linear program must be solved at each vertex at which a surrogate constraint is to be formed. As problems with larger numbers of variables are considered, not only does the size of the corresponding LP's increase, but more importantly, the number of vertices grows exponentially Since one of the primary advantages of the Balas Algorithm is that it is additive computationally, the necessity of solving the LP's should be investigated. Note that the necessity to solve the LP's makes the integer programming problem more sensitive to the number of constraints than is otherwise the case. Ideally one would like to build a surrogate with strength and computational advantages comparable to the dual multiplier surrogate but requiring less computation time. 3. AN ALTERNATIVE METHOD FOR CONSTRUCTING SURROGATE CONSTRAINTS Definition (4) suggests an alternative strategy for con- structing surrogates. Given an initial surrogate a stronger surrogate can be constructed by making the optimal solution to the current surrogate knapsack problem infeasible for the new surrogate constraint while continuing to eliminate less optimal solutions. The process iterates until a stronger surrogate can no longer be constructed. Such an iterative procedure was developed when the strength of surrogates was investigated, Giordano [1982]. In the referenced report, the initial surrogate was the dual multiplier surrogate and each surrogate knapsack problem was resolved for an optimal solu- tion using a Balas Algorithm. To develop a quick heuristic for constructing surrogates, two major problems must be resolved. First an alternative method for forming the initial surrogate must be developed since solving the corresponding LP at each vertex is computationally costly. Secondly, an alternative process for solving the surrogate knapsack problems must be incorporated to avoid the computation time involved in the Balas Algorithm We will review the procedure for iterating to a best surro- gate, investigate alternative methods for forming the initial surrogate, present an approximation technique for resolving the surrogate knapsack problems, and compare the formation time and strength of the heuristically generated surrogate with the dual multiplier surrogate. 4 . ITERATING TO A BEST SURROGATE 4.1 AN ALGORITHM Let us define for the current surrogate: x : the optimal solution to the current surrogate knapsack problem, u*: the weight of the ith constraint in the current 1 surrogate s.: the slack x allows in the ith constraint. S*: 7 u*s*: the slack x* allows in the current 4 i i surrogate. Similarly, for the new surrogate let: u! : the weight of the ith constraint in the new surrogate . SI: V u.' s*: the slack x* would allow in the new o r i i i surrogate. Let * u; 1 1 The purpose of a. is to increase the weight of the constraints violated by x and 9 is a parameter to insure x* becomes infeasible for the new surrogate. Choosing * a . = s . l l and 9 = (S*/£ s* 2 ) + .05 a new surrogate is generated and combined with the previous surrogate, weighting the previous surrogate 75%. If a suc- cessive surrogate fails to be stronger than its predecessor, £ = .05 above is halved and che process repeated. If a surrogate fails to improve after three reductions, the proc- ess terminates with the previous surrogate judged 'best'. 4 .2 COMPARING THE STRENGTH OF SURROGATES The strength of a surrogate is measured by the optimal solution to the corresponding knapsack problem. To compare various surrogates the following measure proved convenient: percent convergence = | z ' - z" | / j z ' - z where: z~: objective function value of the optimal solution to problem (1) . z': objective function value of the optimal solution to the continuous relaxation to (1) . z": objective function value of the optimal solution to (3) for the surrogate in question. The percent convergence heuristically measures the number of infeasible solutions between the continuous and integer optimum solutions to (1) that a particular surrogate effec- tively eliminates and is an indication of the relative strength of two surrogates. 4.3 RESULTS Of the 13 problems considered, the solution to the dual multiplier surrogate knapsack problem solves the original prob- lem directly in 7 cases. In the remaining 11 cases, it is possible to build a stronger surrogate in 9 cases. The im- provement in most instances is substantial. In fact, the best surrogate obtained solves an additional 4 problems. The results are summarized in Table 2, which is located at the end of the report. 5. THE INITIAL SURROGATE 5.1 METHODS TESTED Three alternative methods for forming the initial surro- gate were tested: 1. Simply adding the original constraints. 2. Averaging the original constraints. 3. Weighting each of the original constraints according to the right hand side. 9 5.2 DISCUSSION The advantage of Method 1 is that it is a simple way of getting started. Method 2 attempts to prevent the initial surrogate from becoming so large that it compromises the weighting scheme developed in 4.1 when forming subsequent surrogates. Method 3 attempts to exploit the format of the problem for the vertex being studied. In the Balas format, the problem is better than optimal with all variables at the zero level. Variables are raised to the one level only to cure inf easibility . For violated constraints, the current right hand side represents the inf easibility which must be "cured". Using Method 3, the initial surrogate is formed weighting each violated constraint according to its relative inf easibility . Various normalization schemes were tested to insure a unit of slack in each constraint means approximately the same thing. 5.3 RESULTS For the problem set tested, Method 2 generally produces the best results. Although the initial surrogate is normally not as strong as the dual multiplier surrogate, the process quickly converges to a "best" surrogate. Since the initial surrogate is not as strong as the dual multiplier surrogate, some loss of strength is experienced. The best surrogate using the dual multiplier surrogate as the initial surrogate is equaled in 12 of the 18 problems tested. More importantly, the best surrogate generated using Method 2 above equals or 10 improves the strength of the dual multiplier surrogate in 15 of the 18 cases. The results are summarized in Table 2. 6 . SOLVING THE SURROGATE KNAPSACK PROBLEMS 6 .1 AN APPROXIMATE ALGORITHM Consider the knapsack problem: Minimize {7 (-ex.) IT a.x. < b, x. = or 1} . j 3 3 fj 3 3 ~ 3 By preassigning values for x. where c. and a. differ in sign and substituting x. = 1-x! for the remaining variables where c. and a. are both negative, the above problem can be reduced to a form with all c., a., and b positive. Arrange the indices of x. such that c,/a, > c~/a > . . . > c /a . We will refer 3 11—22— — nn to c./a. as the knapsack ratio for x.. Find p the least integer (0 p n) such that a. b. Beginning with j<p ] r = p increment r by unit steps to n, adding each a to p-1 r 1 a, if and only if the resultant cumulative sum is less than k=l K or equal to b. Then the approximate solution is given by . (" if j < p or if a. is added to the summation x . 0, otherwise. This algorithm arranges the variables in such a manner that the more attractive variables are elevated to level one before inf easibility occurs, Taha [1975]. 11 6.2 INCORPORATING THE APPROXIMATE KNAPSACK ALGORITHM Since, in the algorithm presented in 4.1, it is only necessary that a subsequent surrogate be relatively stronger than a previous surrogate, approximate measurements of their strengths should be sufficient. When the approximate algor- ithm is incorporated, the desired speed is obtained, some loss in strength in the 'best' surrogate is experienced, fewer iterations are required to converge, and the probability of finding a feasible solution to the original problem in- creases. Part of the loss in strength of the best surrogate is due to terminating the process when a feasible solution to the original problem is found. For example, in Problem 4, the approximate solution to the best surrogate constructed solves the original problem. Since the approximate solution to a surrogate constraint is greater (minimization) than the exact solution, such a solution poses a greater restriction on the subsequent surro- gate. This reduces the number of iterations required to obtain a best surrogate and reduces the probability of building stronger surrogates in the vicinity of the best surrogate, since no surrogate can be constructed 'between' the current surrogate and the approximate solution to the current surrogate The fact that the approximate solution is greater than the exact solution to the surrogate also explains the increase in the number of feasible solutions to the original problem found. The computational advantage of using these feasible solutions in the Balas Algorithm will be subsequently discussed. 12 6.3 RESULTS In the 18 problems tested, the best surrogate obtained equals the dual multiplier surrogate in 10 cases, is stronger in 4 cases, and weaker in 4 cases. Thus the two surrogates are roughly equivalent in strength. However, the heuristically determined best surrogate is formed in a total of .89 seconds for the problem set compared with 9.19 seconds for the dual multiplier surrogate. The results are summarized in Table 2. 7. ANALYSIS OF ANCILLARY INFORMATION 7.1 TERMINATION OF ALGORITHM The algorithm presented in 4.1, modified to incorporate Method 2 for generating an initial surrogate and the approxi- mate technique for resolving the surrogate knapsack problems, terminates under the following conditions: 1. Stronger surrogates can no longer be constructed. 2. A feasible solution to the original problem has been found. Upon termination, one always has a solution which is a lower bound for the vertex. The best surrogate formed is a weighted combination of the original constraints which more heavily weights those constraints which, in some sense, are critical. The final set of knapsack ratios thus represents the attrac- tiveness of the variables with respect to the critical con- straints. One can take advantage of this situation to attempt to find feasible solutions to the original problem. 13 7.2 FINDING FEASIBLE SOLUTIONS When the algorithm terminates due to condition 1, one knows which constraints were violated by the solution to the best surrogate. Depending on the format (e.g., Balas) and type of problem considered (e.g., set covering), one may be able to raise additional variables to the one level in order to satisfy the violated constraints. The last set of knapsack ratios can be used to determine the order of raising additional variables to the one level. For the 18 problems studied, it is possible to quickly find a feasible solution to the original problem. To get an indication of the effect of a feasible solution on the total computation time, the algorithm employing a dual multiplier surrogate every eight iterations carrying forward a maximum of four surrogates (2.3) was again used. The only difference was than an initial solution to use as a bound was provided. The 18 problems tested requires 38.62 seconds to resolve without the bounds and 19.97 seconds with the bounds. A total of .26 seconds of additional time is re- quired to find feasible solutions for those problems in which a feasible solution is not determined while iterating to a best surrogate. The results are summarized in Table 1. 7.3 HISTORY OF VARIABLES AND CONSTRAINTS When iterating to a best surrogate, one may use index sets to record which variables are at the one level in the solutions to the various surrogates. This information can be used to attempt to find a feasible solution or for developing 14 a heuristic for branching in the Balas Algorithm. If addi- tional information on the variables is desired, the exact solution to the LP relaxation of (3) is immediately available once the knapsack ratios have been determined [Dantzig, 1957], Similarly, one can use an index set to record which of the original constraints are violated while iterating to a best surrogate. This information can be used advantageously in the Balas Algorithm. 8. CONCLUSIONS Using the heuristic procedure developed in this paper it is possible to generate surrogates of strength comparable to the dual multiplier surrogate in less than 10% of the time required to form the dual multiplier surrogate. Because of the way the surrogates are formed, one would expect that the time required to converge to a best surrogate would behave well as the size of the problem increases. The results of the experimentation conducted suggest the following research: 1. Develop an algorithm which employs the heuristically generated surrogate in a manner analogous to the dual multiplier surrogate. 2. Develop heuristics for exploiting the ancillary information developed when iterating to a best surrogate. 3. Adapt the procedure to the general integer problem. 15 9 . ACKNOWLEDGMENTS I am deeply indebted to Professor Fred Glover, University of Colorado, and Professor Hamdy Taha, University of Arkansas, for contributing essential ideas throughout the conduct of this research. I would also like to thank Professor Frank Grange, Colorado School of Mines, who provided the problem set and Professor Gerald Brown, Naval Postgraduate School, for his valuable suggestions and assistance in presenting the results. 16 TABLE 1 EFFECT OF A DUAL MULTIPLIER SURROGATE AND AN INITIAL STARTING SOLUTION ON THE SOLUTION TIMES OF A BALAS ALGORITHM J 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 SUM 6 5 6 10 6 4 8 2 10 10 14 3 15 10 20 10 25 2 28 10 28 28 28 28 28 28 39 50 537 4,134 1,882 2,772 98,960 37,407 4,127 6,155 167 12,462 142,019 131,637 99,647 122,505 100,433 131,355 10,672 17,007 370 3,800 1,800 2,600 98,500 35,777 4,015 6,120 148 12,400 141,278 130,883 95,677 119,337 98,796 130,623 10,618 16,537 0.10 0.14 0.07 0.07 0.28 0.56 0.76 6.28 0.35 107.26 5.68 11.14 9.58 1.13 15.97 12.68 380.81 (>5631) 0.12 0.19 0.12 0.07 0.43 0.32 0.99 0.83 0.39 3.57 2.39 3.85 2.91 0.77 4.13 2.13 8.94 6.47 0.11 0.14 0.08 0.09 0.36 0.19 0.89 0.59 0.37 1.11 0.43 0.49 1.57 1.08 0.40 0.44 5.29 6.34 0.01 0.01 0.01 0.03 0.02 0.04 0.01 0.02 0.03 0.04 0.04 368 3,700 1,800 2,600 83,369 35,777 3,245 6,010 112 12,150 139,508 129,773 83,368 104,689 98,796 129,723 10,077 12,753 (>6183) 38.62 19.97 0.26 o< M 4J G •H 03 u -u CO a 4-4 O I* -a u q 3 4-1 o -I c 5 g en IS ■H (Tj co id 3 >1 g "a -p O 5 8 -0 a I ■H H 3 g a) -G -«-> +J 03 US* o h rtj co .H -H 03 rH - +J si G 10 T3 If ■H 3 •H CO I-l 03 O a) rf3 03 CO 73 03 G ^H 03 05 CQ 0) 4-) - 03 G 5 2 3 ~> ^ en— i CO O 03 §G^ 4J J* en 5 03 -P d) 4-i .G -H "3 2 G O w a i W "3 ■H ~J •H H a CO 17 TABLE 2 COMPARISON OF THE DUAL MULTIPLIER AND HEURISTIC SURROGATES h 1 5 5 167 5 100 100 100 0.12 0.01 2 6 10 334 100 100 100 100 0.21 0.04 3 6 4 82 100 100 100 100 0.14 0.02 4 8 2 172 42 100 100 100 0.12 0.01 5 10 10 46 100 100 100 100 0.36 0.01 6 14 3 1,630 100 100 100 100 0.23 0.01 7 15 10 112 20 65 65 65 0.49 0.07 3 20 10 35 100 100 100 100 0.68 0.05 9 25 2 19 16 74 58 * 0.34 0.05 10 28 10 62 35 35 ** ** 0.98 0.10 11 28 2 741 64 100 64 64 0.41 0.05 12 28 2 754 100 100 100 100 0.40 0.04 13 28 2 3,970 44 44 22 22 0.38 0.07 14 28 2 3,168 45 59 45 45 0.43 0.05 15 28 2 1,637 100 100 100 100 0.36 0.02 16 28 2 732 85 100 100 85 0.39 0.06 17 39 5 54 19 20 17 *** 0.96 0.12 18 50 5 47 19 87 87 38 1.17 0.11 SUM 9.19 0.89 en CD r-i ■a •H I 4-1 o ill! 4-1 *■* 5 4-> T3 > 4-> H x: o o * -8 3 ! a) a 4-1 q, I ° ° > -p cy oJ cd 3 rj> a) Ja -h <y i — r \j a s . a) cd £ 4J 4-1 o cd 3 U c/} § M Cn CD a h 83 S3 4J T3 >, 4-1 +3 -H o £ 4J o w <u -H o a u 2 4-> 3 a) fT3 o If W 4J I 0) en 4-i £ 0) 03 4J 4-i a c °al oj o C 4J 4J 03 en » 7T Solution to best surrogate surrogate was 164 . H 2 £ a c 4h £ -d S 03 cn flg cd +3 4-1 a 03 S |l U3 y -h i q 03 5 Q 2 1 &| 81 .5£ Cn CD o M C 4-1 0) -H > 03 CN S 4-> 8 -8 -8 P CD 4-1 •H o3 cn rH CD 03 4-> 03 AS m o 03 3 .13 H 03 CD •H 4J 4-> OJ ■31 2 03 CD CD +3 w 1 , , Cfl U 1 75 33 s w n D 4-1 6 "8 CD •3 CD 03 Cn was 191 while solution to dual raultiplier ** Solution to best surrogate multiplier surrogate was 12,440, was 12,470 while solution to dual *** Solution to best surrogate multiplier surrogate was 10,662. was 10,774 while solution to dual 18 BIBLIOGRAPHY 1. Balas E. "An Additive Algorithm for Solving Linear Programs With Zero-One Variables", Operations Research / 13. (1965) , 517-546. 2. Balas, E. "Discrete Programming by the Filter Method", Operations Research , 15. (1967), 915-957. 3. Dantzig, G.B. "Discrete Variable Extremum Problems", Operations Research , 5. (1957), 266-277. 4. Garfinkel, R.S., and G.L. Nemhauser. Integer Programming . Wiley, 1972. 5. Geoffrion, A.M. "An Improved Implicit Enumeration Approach for Integer Programming", Operations Research , 17. (1969) , 437-454. 6. Giordano, F. "The Strength of Surrogate Constraints for the Linear Zero-One Integer Programming Problem", Naval Postgraduate School Technical Report , NPS55-082-008 , February 19 82. 7. Glover, F. "A Multiphase-Dual Algorithm for the Zero- One Integer Programming Problem", Operations Research , 13. (1965) , 879-919. 8. Glover, F. "Surrogate Constraints", Operations Research , 16. (1968) , 741-749. 9. Taha, H.A. Integer Programming: Theory, Applications, and Computations. Academic Press, 1975. 19 DISTRIBUTION LIST NO. OF COPIES Library, Code 014 2 4 Naval Postgraduate School Monterey, CA 9 3940 Dean of Research 1 Code 012A Naval Postgraduate School Monterey, CA 9 3940 Library, Code 5 5 2 Naval Postgraduate School Monterey, CA 9 3940 Professor F. R. Giordano 48 Code 53Gi Naval Postgraduate School Monterey, CA 9 39 40 Defense Technical Information Center ATTN: DTIC-DDR Cameron Station Alexandria, Virginia 22314 DUDLEY KNOX LIBRARY - REbt * H '-' 1 n "r il | 5 6853 01068016 8