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

HEURISTIC FOR CONSTRUCTING

SURROGATE

CONSTRAINTS FOR THE LINEAR

ZERO-

■ONE

INTEGER PROGRAMMING PROBLEM

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 NUMBEa'»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 7j 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,,u0,...,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 >_ 0 , x = (0,1)}. (3

1.2 PROPERTIES

Because the vector u 0 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) > 0 to be stronger than u (b-Ax) > 0 if

1 .

Min {cx|u (b-Ax) >_ 0 , x= (0,1)} > Min {cx|u (b-Ax) > 0, x = (0,1

for u1, u2 > 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 > 0 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

surrogate

s.: the slack x allows in the ith constraint.

S*: 7 u*s*: the slack x* allows in the current
0 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

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.

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

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. = 0 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~/a0 > . . . > 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].

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.

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.

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

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.

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.

TABLE 1

EFFECT OF A DUAL MULTIPLIER SURROGATE AND
AN INITIAL STARTING SOLUTION ON THE
SOLUTION TIMES OF A BALAS ALGORITHM

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.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.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

G
•H

03
u
-u

4-4
O

-a

u q

3 4-1
o

-I
c

g en

■H (Tj

co
id

>1
g

"a -p

O 5

-0

a
I

■H

g a)
-G -«->

+J 03

US*

o h
rtj co

.H -H

03 rH

- +J

10 T3

■H

•H CO
I-l 03

O a)

rf3 03
CO 73

03 G

^H 03
05

CQ 0)

4-)

- 03

^ en— i

CO O 03

§G^

en 5

03 -P
d) 4-i

.G -H

"3
■H
~J
•H

TABLE 2

COMPARISON OF THE DUAL MULTIPLIER
AND HEURISTIC SURROGATES

167

100

0.12

0.01

334

100

0.21

0.04

100

0.14

0.02

172

100

0.12

0.01

100

0.36

0.01

1,630

100

0.23

0.01

112

0.49

0.07

100

0.68

0.05

0.34

0.05

0.98

0.10

741

100

0.41

0.05

754

100

0.40

0.04

3,970

0.38

0.07

3,168

0.43

0.05

1,637

100

0.36

0.02

732

100

0.39

0.06

***

0.96

0.12

1.17

0.11

SUM

9.19

0.89

r-i

■a

•H

4-1

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

4J T3 >,
4-1 +3 -H

o £ 4J

o w

<u -H

o a u

2 4-> 3

a) fT3 o

0 W

4J I 0)

en 4-i £

0) 03 4J

4-i a c

°al

oj o C

4J 4J

03 en

Solution to best surrogate
surrogate was 164 .

H 2 £

a c 4h

£ -d

S 03 cn

flg

cd +3

4-1 a
03 S

y -h

i q

03 5

Q 21
&|

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

CD 03
4->
03 AS

m o
0 03

3 .13

03 CD

•H 4J

4-> OJ

■31

CD CD
+3 w

, ,

Cfl

U 1

4-1

CD 0

•3 CD

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

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.

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'-'1n"ril|

5 6853 01068016 8

Internet Archive Audio

Featured

Top

Images

Featured

Top

Software

Featured

Top

Books

Featured

Top

Video

Featured

Top

Mobile Apps

Browser Extensions

Archive-It Subscription

Save Page Now

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

See other formats