(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

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

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