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