*** PRELIMINARY DRAFT ***
Finding Embedded Network Rows
in Linear Programs II: Augmentation Heuristics
by Robert E. Bixby and Robert Fourer
1. INTRODUCTION
In the first half of this paper (Bixby and Fourer 1987) we
considered heuristic algorithms that extract large subsets of network
flow equations from the constraints of a linear program. We now turn to
algorithms that try to enlarge any such embedded network subsets that
have been found.
Our study of these *augmentation* heuristics is naturally intended
to determine whether a significant improvement can be made to the
results of the extraction heuristics. We also want to consider what the
best overall strategy might be for embedded network detection. We
evaluate a strategy by its efficiency (the amount of computing time it
requires) and by its effectiveness (the size of the network that it
finds). Thus we might find, for example, that some efficient extraction
heuristic is not particularly effective when used alone, but is
competitive in combination with an efficient augmentation heuristic.
The augmentation methods that we consider are designed to operate
efficiently on the same row-list and column-list data structures as the
extraction methods. All can be regarded as *exchange* heuristics: at
each successful step, they delete one row from the current embedded
network, and insert one or more currently non-network rows. They differ
in how they go about finding the deletions and insertions:
The *deletion-driven* approach first picks a network row that might
be deleted, then determines whether one or more non-network rows
might be inserted as a result. This is the most expensive method,
but it has the possible advantage of maintaining a certain
maximality of the embedded network after every step.
The *insertion-driven* approach first picks a non-network row that
might be inserted, then determines whether its insertion can be
made possible by the deletion of at most one network row. The
steps of this method are less expensive, but do not maintain
maximality.
A *hybrid* approach attempts to combine the best features of the
preceding two. Each step starts out insertion driven; but if both
an insertion and a deletion are made, then further non-network rows
are inserted if possible. Thus maximality is maintained as in a
deletion driven step, at some extra cost.
A single pass tries either all network rows (one at a time) as
candidates for deletion, or all non-network rows as candidates for
insertion. The algorithm consists of a series of passes, stopping when
there appears to be no further progress in augmenting the embedded
network.
Our extensive computational tests show that the exchange heuristics
frequently do accomplish a significant augmentation of previously
extracted networks, at a reasonable increase in cost. The largest
augmentations occur, predictably, when a relatively poor network has
been extracted; thus, at the least, the behavior of an exchange method
serves as a good indicator of network quality. In fact, for four of our
nine test problems, the largest network is found *only* by runs that
employ exchange heuristics. In all cases, moreover, a greater
proportion of network extraction implementations find best or near-best
networks when they are followed by exchange heuristics.
The remainder of this introduction briefly reviews concepts and
terminology from part I. Sections 2, 3 and 4 then introduce deletion-
driven, insertion-driven and hybrid exchange, respectively. Section 5
compares effectiveness (network size) and efficiency (run time) of these
methods.
Section 6 presents our conclusions drawn from the runs in both
parts of this paper. ...
Preliminaries
As in the first half of this paper, we are concerned a linear program
(LP) of m constraints in n bounded variables:
{ <= }
sum_{j=1}^n aij xj { = } bi, i = 1,...,m
{ >= }
lj <= xj <= uj, j = 1,...,n
The coefficients of the constraints define an m x n matrix, A.
Following some scalings and other manipulations of A, we identify a
subset I within {1,...,m} of "+-1 rows": for each i in I and any j =
1,...,n, aij is either +1, -1 or 0. We speak of the nonzero values in a
row or column as its *elements*, and say that a row i and a column j
*intersect* if aij /= 0.
For purposes of this paper, an *embedded network* is defined to be
a subset of the rows of A such that each column contains at most one +1
and one -1 within that subset, and is otherwise all zeroes within that
subset. Equivalently, a subset N within I describes an embedded network
if, for all j = 1,...,n, there is at most one i1 in N with ai1j = +1,
and there is at most one i2 in N with ai2j = -1. Once N has been
identified, the LP can be interpreted as imposing conservation of flow
at the nodes of a certain network (defined by the rows i in N) plus
other conditions on the flows (as specified by the rows i notin N).
Any +-1 row remains a +-1 row when it is multiplied through by -1.
The operation of scaling by -1, or *reflection*, necessarily changes the
balance of +1 and -1 elements in certain columns of A. Thus all of our
methods provide for optional reflection of any rows i in I.
All of the methods described in the first half of this paper find
an embedded network that is *maximal*, in the sense that it cannot be
enlarged by merely appending any one non-network row (or its
reflection). There can be many maximal embedded netowrks in this sense
for a given LP, and their size can vary considerably. To find larger
maximal subsets we consider, in this second half of the paper, methods
that delete a row from N in the hope of adding two or more rows
(possibly reflected) from I \ N.
We use the same data structures as before, including both row-wise
and column-wise lists of the elements of A. Our tests, applied to the
nine linear programs introduced in part I, attempt to augment the
networks produced by 11 of our extraction heuristics. We have chosen
these 11 because they are representative of all we have tested, and give
a range of different networks; they are listed in Table 1-1, along with
the abbreviations by which they are identified in subsequent tables.
Abbrev Method of network extraction
------ ----------------------------------------------------
RD/U Row-scanning deletion, with updating of penalties;
rows with initial penalty zero are set aside
RD/N Row-scanning deletion, without updating of penalties
CD/UI Column-scanning deletion, using row counts;
columns scanned in order of increasing count
CD/UD Column-scanning deletion, using row counts;
columns scanned in order of decreasing count
CD/UB Column-scanning deletion, using row counts;
columns scanned backwards through data structure
CD/NI Column-scanning deletion, not using row counts;
columns scanned in order of increasing count
CD/ND Column-scanning deletion, not using row counts;
columns scanned in order of decreasing count
CD/NF Column-scanning deletion, not using row counts;
columns scanned forwards through data structure
CD/NB Column-scanning deletion, not using row counts;
columns scanned backwards through data structure
RA/I Row-scanning addition;
rows scanned in order of increasing count
RA/F Row-scanning addition;
rows scanned forwards through data structure
Table 1-1. Abbreviations for embedded-network extraction heuristics,
used in subsequent tables. Further description of all methods are given
in part I of this paper (Bixby and Fourer 19xx).
2. DELETION-DRIVEN EXCHANGE
Any operation that enlarges a maximal network must delete or
reflect at least one row from the network subset. Perhaps the simplest
such operation is begun by arbitrarily deleting some network rows, after
which as many non-network rows as possible are inserted. If the number
of insertions exceeds the number of deletions, a larger maximal network
has been found.
Since the choice of rows to delete is the major decision of a step,
we refer to this kind of method as *deletion-driven* exchange. We
describe below an efficient version that makes just one deletion per
step. A statement and discussion of the algorithm is followed by some
comments on its implementation and a summary of computational results.
Principles
Suppose that some row is provisionally deleted from the maximal
embedded network subset N. Then we can attempt to insert rows from I \
N, much as in the resinsertion algorithm described by part I of this
paper (Bixby and Fourer 198x). If no insertions are possible, we can
cancel the deletion and try a different one. Otherwise, we have found a
new maximal network that is either the same size as the old one (if only
a single row could be inserted) or larger than the old one (if two or
more rows could be inserted).
Since we have no information in advance about which rows would be
best to delete, we consider each one in turn. Thus a single pass of the
algorithm carries out one attempted-deletion step for each t in N. If a
pass causes any change in N, then another pass may be begun.
As in part I, we let cj+ and cj- be the numbers of +1's and -1's in
column j within the rows of N; since N is a network, these counts can
only be 0 or 1. We let J within {1,...,n} be the subset of columns that
are relevant to the existence of an embedded network. Then the
algorithm can be stated precisely as follows:
Deletion-driven exchange
------------------------
Repeat as long as desired:
Repeat for each t in N:
For each atj = +1, set cj+ <- 0;
for each atj = -1, set cj- <- 0.
Repeat for each i in I \ N:
If cj+ = 0 for all aij = +1, j in J; and
cj- = 0 for all aij = -1, j in J:
Insert row i: N <- N union {i}.
For each aij = +1, j in J: set cj+ <- 1.
For each aij = -1, j in J: set cj- <- 1.
If cj+ = 0 for all aij = -1, j in J; and
cj- = 0 for all aij = +1, j in J:
Reflect and insert row i: N <- N union {i}.
For each reflected aij = +1, j in J: set cj+ <- 1.
For each reflected aij = -1, j in J: set cj- <- 1.
If any row has been inserted:
If cj+ = 0 for all atj = -1, and cj- = 0 for all atj = +1:
Reflect row t.
For each reflected aij = +1, j in J: set cj+ <- 1.
For each reflected aij = -1, j in J: set cj- <- 1.
Else delete row t: N <- N \ {t}.
Otherwise, cancel the deletion:
For each atj = +1, set cj+ <- 1;
for each atj = -1, set cj- <- 1.
Since every possible insertion is tried when t is deleted, N remains a
maximal network after every step. It is essential to attempt
reinsertion of the reflection of t at some point during the step, since
otherwise maximality could be lost. In our versions we place this
attempt at the end of the inner loop, so that a step cannot merely
reflect row t without also inserting some other rows.
The algorithm allows row t to remain deleted even if only one row
can be inserted. In such a case the maximal network is changed but not
enlarged. We permit such operations mainly for the sake of efficiency;
we do not want to have to cancel both an insertion and a deletion at
some steps. Numerous deletions and insertions may also tend to
"shuffle" the network in ways that make augmentation more likely at
later steps, and our computational experiments show some evidence for
this.
The algorithm could also be generalized so that it tries deleting
more than one row at each step. However, since N is large in any
worthwhile application, the cost of trying even all possible pairs of
deletions is prohibitive; some kind of sampling would have to be used.
Moreover, if two deletions were followed by only one insertion, there
would be no way in general to avoid the work of cancelling both the
insertion and the deletions.
Implementation
We consider first the details of the innnermost loop, which
attempts an insertion for each non-network row. The work involved
depends on the size of I \ N, which is fairly small if the LP indeed has
a significant embedded network. We can reduce the work further,
however, by observing that the deletion of row t from a maximal network
cannot permit the insertion of row i unless these rows intersect some
common column. Since typical coefficient matrices are very sparse, only
a fraction of the rows in I \ N need intersect a common column with t.
We thus implement the inner loop by scanning each column j in J
such that atj /= 0. For each aij /= 0, we check whether i in I \ N, and
if so we attempt to insert row i. These are fast operations using the
row-list and column-list data structures. Even so, we wish to avoid
attempting the insertion of row i more than once, if it intersects more
than one column in common with row t. To this end, we maintain an array
YMARKR(i), initialized to zero for i in I \ N, and a distinguished
positive integer MARKER. We allow the insertion of row i to be
attempted only if YMARKR(i) does not equal MARKER; after an attempted
insertion we set YMARKR(i) = MARKER to prevent repetitions. A new value
of MARKER is used at each new deletion of a row t, so that YMARKR need
never be reinitialized in the course of the algorithm.
The middle loop scans rows 1,2,...,m and attempts deleting each one
that lies in N. This is a very efficient arrangement, although it does
mean that, on occasion, a row that has been inserted may be deleted at
the same pass.
The only question of implementation for the outer loop is the
choice of termination criterion. In the interest of finding large
networks, we continue this loop until further augmentation seems very
unlikely. Specifically, we stop only when a pass has made no deletions
(so that N has not changed) or when two consecutive passes have failed
to augment N.
Since arrays of the quantities cj+ and cj- are maintained in some
form by all the network extraction heuristics, the only new setup cost
for augmentation is the initialization of YMARKR. Cleanup costs for
bookkeeping arrays are unaffected.
Test results
Since we applied deletion-driven exchange to 99 networks in all --
as extracted by eleven different heuristics from to nine different LPs -
- our raw data is voluminous. Representative results for one linear
program, GIFFPINC, are shown in Table 2-1. Results for the CD/UB and
CS/NB runs are not shown, because they were the same as for the CD/UD
and CS/ND runs, respectively. (Apparently scanning columns backwards
through the data structure achieves the same thing as scanning them by
decreasing count.)
As in part I, we use the number of non-network rows (the size of I
\ N) to compare effectiveness of heuristics. The networks found by
extraction alone range from 77 to 109 non-network rows, and the
augmentations due to exchange range from 6 to 20. As one would expect,
there tends to be a greater augmentation when I \ N is larger to begin
with, although there are clear exceptions to this trend.
For GIFFPINC, the first pass of the exchange heuristic always
accomplishes the greatest augmentation. The second pass sometimes adds
a few rows, as many as 4 in one case, but there is virtually no
augmentation accomplished in later passes.
The time per pass is uniformly about 0.15 seconds. This compares
with times of 0.06 to 0.14 for the network detection, and up to 0.03
seconds for setup preceding the first exchange pass. Evidently the cost
of a pass is significant relative to the overall cost of network
detection. Our observations about effectiveness of sucessive passes
suggests that only one or two passes should be run if efficiency is a
concern.
Similar observations can be made the other eight test problems, but
we defer additional summary statistics to Section 5, which compares all
of the exchange heuristics.
Rows Pass
------------- --------------------------------
Bef Gain Aft 0 1 2 3 4 5
RD/U 109 16 93 Del 115 126 134 122 120 120
Ins 6 137 138 123 120 120
Time 0.13 0.16 0.14 0.14 0.14
RD/N 109 20 89 Del 120 184 124 118 118
Ins 11 201 127 118 118
Time 0.14 0.17 0.13 0.14
CD/UI 87 8 79 Del 87 122 121 120
Ins 0 130 121 120
Time 0.14 0.16 0.16
CD/UD 94 11 83 Del 112 138 111 110
Ins 18 149 111 110
Time 0.14 0.16 0.14
CD/UB 94 11 83 Del 112 138 111 110
Ins 18 149 111 110
Time 0.15 0.14 0.14
CS/NI 92 17 75 Del 92 139 115 114
Ins 0 156 115 114
Time 0.16 0.16 0.14
CS/ND 77 6 71 Del 80 136 133 129 128
Ins 3 141 134 129 128
Time 0.15 0.14 0.15 0.15
CS/NF 109 20 89 Del 129 184 124 118 118
Ins 20 201 127 118 118
Time 0.15 0.14 0.16 0.14
CS/NB 77 6 71 Del 80 136 133 129 128
Ins 3 141 134 129 128
Time 0.16 0.16 0.15 0.14
RA/I 104 12 92 Del 104 108 126 120 118 118
Ins 117 128 121 118 118
Time 0.14 0.14 0.15 0.14 0.15
RA/F 91 9 82 Del 91 151 132 128 128
Ins 159 133 128 128
Time 0.15 0.17 0.15 0.15
Table 2-1. Examples of deletion-driven exchange, applied to the GIFFPINC
model. For each extraction heuristic listed at left, the first three
columns show the number of non-network rows before exchange, the number of
rows added to the network by the exchange heuristic, and the number of
non-network rows after exchange.
Subsequent columns provide more details. Under "pass 0" are the number of
rows initially deleted (or not added) by the extraction method, and the
number of rows added by simple reinsertion. Then the numbers of deletions
and insertions, and the timings, are given for each pass of the exchange
method.
3. INSERTION-DRIVEN EXCHANGE
Rather than pick a network row to delete and then look for non-
network rows to insert, we can pick an insertion and look for deletions.
The resulting *insertion-driven* exchange method promises to be less
costly than the deletion-driven approach, because it scans the
relatively few non-network rows at each pass.
As in the preceding section, we present and discuss the algorithm
in general terms, then describe the particulars of an efficient
implementation and show some computational results.
Principles
Suppose that we have a network subset N, and that we want to insert
a non-network row i from I \ N. The simple reinsertion heuristic (from
part I of this paper) just checks to see whether row i "conflicts" with
any row in N; if not, it inserts i. The insertion-driven exchange
heuristic also checks, however, whether i conflicts with just one row t
in N, and if so it deletes t from N and inserts i. The same check is
made for the reflection of i.
By analogy with the deletion-driven heuristic, a step comprises the
attempt to insert one row, and a pass consists of one step for each non-
network row. We cannot give a precise description of the algorithm,
however, in terms of the cj+ and cj- previously used. These values can
tell us, in effect, how many elements of row i in I \ N cause conflicts
with network rows, but they do not indicate whether all the conflicts
are with the *same* row.
We are thus led to define values that indicate not only whether
each column has a +1 or -1, but where these elements lie:
c^j+ = 0 if column j has no +1 element within the rows of N
t if column j has a +1 element in row t in N
c^j- = 0 if column j has no -1 element within the rows of N
t if column j has a -1 element in row t in N
The algorithm can then be outlined as follows:
Insertion-driven exchange
-------------------------
Repeat as long as desired:
Repeat for each i in I \ N:
If there exists an index t (possibly 0) such that
c^j+ = 0 or t for all aij = +1, j in J; and
c^j- = 0 or t for all aij = -1, j in J:
If t /= 0, delete row t: N <- N \ {t}.
For each atj = +1, j in J: set c^j+ <- 0.
For each atj = -1, j in J: set c^j- <- 0.
Insert row i: N <- N union {i}.
For each aij = +1, j in J: set c^j+ <- i.
For each aij = -1, j in J: set c^j- <- i.
If there exists an index t (possibly 0) such that
c^j- = 0 or t for all aij = +1, j in J; and
c^j+ = 0 or t for all aij = -1, j in J:
If t /= 0, delete row t: N <- N \ {t}.
For each atj = +1, j in J: set c^j+ <- 0.
For each atj = -1, j in J: set c^j- <- 0.
Reflect and insert row i: N <- N union {i}.
For each reflected aij = +1, j in J: set c^j+ <- i.
For each reflected aij = -1, j in J: set c^j- <- i.
The case t = 0 corresponds to a simple insertion that augments N by one.
When t > 0 an exchange is made, and N stays the same size.
Clearly this algorithm does not maintain maximality of N. After an
exchange step, further insertions may become possible; but these
insertions will not be discovered, if at all, until subsequent steps,
possibly at the next pass. We think of the algorithm as "shaking up"
the set N in the hope that additional rows will find their way into it.
Since no step deletes a row without inserting one, the size of N can
only stay the same or increase from pass to pass.
Since the algorithm does not keep the network maximal, there is no
reason to start it with a maximal network. Consequently, following the
extraction heuristics based on deletion, we do not apply the insertion-
only heuristic (as in part I) before proceeding to insertion-driven
exchange. We do always apply the insertion-only heuristic *after*
insertion-driven exchange, however, so that the final network found is
maximal.
Implementation
The efficiency of insertion-driven deletion depends upon fast
execution of the inner loop, which we consider first. We then briefly
indicate how data required by the algorithm can be set up.
The first principal part of the inner loop determines whether row i
or its reflection can be inserted, and if so what row t (if any) must be
deleted to make the insertion possible. We carry this out in a single
scan of the row's elements, based on the same concept of a series of
"states" that was employed in our column-scanning deletion heuristics
(Bixby and Fourer 198x). As the algorithm is about to examine the next
element of row i, its current state is determined by the numbers of
conflicts that it has already found between the row -- unreflected or
reflected -- and the network. The relevant states are:
0 conflicts unreflected, 0 conflicts reflected
1 conflict unreflected, 0 conflicts reflected
0 conflicts unreflected, 1 conflict reflected
1 conflict unreflected, 1 conflict reflected
>=2 conflicts unreflected, 0 conflicts reflected
0 conflicts unreflected, >=2 conflicts reflected
>=2 conflicts unreflected, 1 conflict reflected
1 conflict unreflected, >=2 conflicts reflected
To make the scan fast, we have a separate block of code for processing
elements under each state. As soon as row i is found to conflict with
two different network rows when unreflected and two different rows when
reflected, we can terminate the scan and abandon the attempt at
insertion. Since non-network rows tend to be the ones that have
relatively many elements (and hence relatively many conflicts) we expect
a significant saving in avoiding a full scan of every non-network row.
The remainder of the inner loop makes any indicated deletion and
insertion. If either row i or its reflection can be inserted, we
naturally give preference to whichever does not require a deletion; if
neither requires a deletion, we insert the row unreflected (as in the
resinsertion algorithm described by part I of this paper). Finally, the
situation is more difficult when the choice is between inserting i
unreflected while deleting a row, and inserting i reflected while
deleting some other row. Preliminary tests showed that although the
resolution of this choice was significant -- in once case it made a
difference of over 20 rows to the size of the network eventually found -
- there was no way to consistently predict whether the row should be
inserted reflected on unreflected. Thus in our final tests we resorted
to making the choice randomly.
To scan I \ N for the inner loop, we use a circularly linked list
of non-network rows. When a deletion heuristic has been used for
network extraction, this list initially contains the rows in the reverse
of their order of their deletion. The circular linking contributes to
the efficiency of the inner loop, by allowing the head to be updated
just like any other element. In the case of an exchange, the deleted
row takes the inserted row's position in the list. Thus any deleted
rows cannot be reinserted until the following pass; an inserted row may
be deleted as the result of another insertion later in the same pass,
however.
The termination criterion for the outer loop is the same as in the
deletion-driven exchange.
Initialization of the arrays that hold c^j+ and c^j- is a
potentially major setup cost. The actual cost varies, however,
according to the type of extraction heuristic used:
Row-scanning deletion: There is no efficient way to determine c^j+
or c^j- as the deletions progress. We set them up from scratch
afterwards, by scanning each network row.
Column-scanning deletion: We tentatively set c^j+ and c^j- when
the deletion heuristic scans column j. Afterwards we make
The details are much the same as for the setup of cj+ and cj- after
colunm-scanning deletion (Bixby and Fourer 198x).
Row-scanning addition: The maintenance of cj+ and cj- is an
essential part of the addition heuristic's implementation. A few
simple changes permit the use of c^j+ and c^j- instead, at no
greater expense.
The initial linked list of non-network rows is cheaply set up during any
of the extraction heuristics, and very small amount of additional work
serves to make it circular.
Test results
Table 3-1 shows representative data for the insertion-driven method
applied to GIFFPINC. The sizes of the networks prior to the first pass
are generally somewhat larger than in Table 2-1, because simple
reinsertion is applied before deletion-driven exchange but not before
insertion-driven exchange, as explained above. Ultimately the sizes of
the networks are comparable; the insertion-driven results show smaller
networks in most, but not all, cases.
As might be expected, the insertion-driven exchanges can continue
for relatively many passes. In one case, augmentations are observed in
every pass through the ninth. Fairly large augmentations are recorded
in the first and second passes, and augmentations as large as three rows
are seen in the sixth and seventh passes.
Also as expected, however, the cost per pass is quite low. The
average is only about 0.025 seconds, with a slight tendency toward
higher cost at earlier passes. Thus it seems reasonable to keep
executing passes until no progress is observed.
Rows Pass
-------- ---------------------------------------------------
Gain Aft 0 1 2 3 4 5 6 7 8 9 10 11 12
RD/U 21 94 Del 115 95 93 84 83 81 78 77 76 76 77
Ins 99 100 89 84 81 80 78 77 76 77 0
Time .03 .02 .03 .03 .02 .02 .02 .02 .02 .03 .01
RD/N 27 93 Del 120 98 93 90 85 84 81 78 76 77 73 74
Ins 107 101 91 86 86 82 81 77 78 73 74 0
Time .03 .03 .02 .04 .03 .03 .02 .02 .02 .02 .02 .02
CD/UI 12 75 Del 87 80 66 68 66 65 63 62 61 60 62
Ins 83 70 69 66 66 63 63 62 60 62 1
Time .03 .03 .02 .02 .02 .01 .03 .02 .01 .03 .01
CD/UD 27 85 Del 112 93 71 75 72 71 71 71
Ins 106 81 78 72 72 71 71 0
Time .04 .02 .02 .02 .02 .02 .02 .01
CD/UB 27 85 Del 112 93 71 75 72 71 71 71
Ins 106 81 78 72 72 71 71 0
Time .03 .03 .03 .02 .02 .02 .02 .01
CS/NI 10 82 Del 92 84 75 77 76 74 75
Ins 92 76 77 77 74 75 0
Time .03 .03 .03 .03 .03 .02 .01
CS/ND 10 70 Del 80 77 73 71 67 67 67
Ins 80 76 72 70 67 67 0
Time .03 .02 .01 .03 .01 .03 .01
CS/NF 38 91 Del 129 101 93 86 86 79 75 70 70 70 68
Ins 118 102 87 87 83 78 71 72 70 68 0
Time .04 .02 .02 .04 .02 .02 .02 .02 .02 .02 .01
CS/NB 10 70 Del 80 77 73 71 67 67 67
Ins 80 76 72 70 67 67 0
Time .03 .02 .01 .03 .02 .01 .01
RA/I 11 93 Del 104 88 82 76 76 77 77
Ins 89 90 77 77 77 77 0
Time .04 .02 .03 .03 .02 .02 .01
RA/F 3 88 Del 91 79 76 77 76 76
Ins 80 76 78 76 76 1
Time .02 .02 .02 .03 .03 .01
Table 3-1. Examples of insertion-driven exchange, applied to the
GIFFPINC model. The format follows that of Table 2-1, but the number of
rows listed as deleted under "pass 0" is exactly equal to the number of
non-network rows just before the exchange heuristic is applied. We do
not make a simple reinsertion of rows until the last pass of insertion-
driven exchange.
4. HYBRID EXCHANGE
As a third alternative, we consider an approach that is designed to
combine the best features of the previous two. This *hybrid* method
offers relatively efficient passes like insertion-driven exchange, but
maintains optimality like deletion-driven exchange.
The organization of this section is the same as that of the
preceding ones.
Principles
Our hybrid approach proceeds just like the insertion-driven method,
until it encounters a step at which one row is inserted and another is
deleted. It then makes a subsidiary pass to determine immediately
whether any further non-network rows can be inserted.
In terms of the quantities c^j+ and c^j- previously defined, this
algorithm can be outlined as follows:
Hybrid exchange
---------------
Repeat as long as desired:
Repeat for each i in I \ N:
If there exists an index t (possibly 0) such that
c^j+ = 0 or t for all aij = +1, j in J; and
c^j- = 0 or t for all aij = -1, j in J:
If t /= 0, delete row t: N <- N \ {t}.
For each atj = +1, j in J: set c^j+ <- 0.
For each atj = -1, j in J: set c^j- <- 0.
Insert row i: N <- N union {i}.
For each aij = +1, j in J: set c^j+ <- i.
For each aij = -1, j in J: set c^j- <- i.
If t /= 0,
Repeat for each i' in I \ N:
If c^j+ = 0 for all ai'j = +1, j in J; and
c^j- = 0 for all ai'j = -1, j in J:
Insert row i': N <- N union {i'}.
For each ai'j = +1, j in J: set c^j+ <- i'.
For each ai'j = -1, j in J: set c^j- <- i'.
If c^j- = 0 for all ai'j = +1, j in J; and
c^j+ = 0 for all ai'j = -1, j in J:
Reflect and insert row i': N <- N union {i'}.
For each reflected ai'j = +1, j in J: set c^j+ <- i'.
For each reflected ai'j = -1, j in J: set c^j- <- i'.
If there exists an index t (possibly 0) such that
c^j- = 0 or t for all aij = +1, j in J; and
c^j+ = 0 or t for all aij = -1, j in J:
*Proceed as above, but inserting reflected row i.*
Although the algorithm's statement has become quite long, it retains the
efficiencies of insertion-driven deletion. A pass examines only each
row in the relatively small set I \ N. A fast scan of row i in I \ N
suffices to determine whether it can be inserted and whether some row t
can be deleted. The extra work occurs when some row t is deleted, at
which point the algorithm must determine whether more rows can be
inserted as a result; in effect, the latter part of a deletion-driven
exchange step is appended to the insertion-driven step.
The hybrid exchange algorithm need not be started at a maximal
network. As soon as any row t is deleted, the reinsertion of rows i'
makes the network maximal, and it remains maximal at every step
thereafter. (If no rows are deleted, then a pass of this algorithm is
the same as a pass of simple reinsertion, and the network must be
maximal at the end of the pass.)
Implementation
Our realization of this method is also a hybrid. The
implementation of insertion-driven exchange is adopted for the setup,
for scanning the circularly linked list of non-network rows, and for
finding row t. The implementation of deletion-driven exchange
contributes the code for determining whether deletion of row t permits
other rows i' to be inserted. Thus the scanning of matrix elements at a
step involves, at most, the row i, the columns that intersect row t, and
all or part of the rows that interect such columns.
The extra reinsertions do pose a problem for the maintenance of the
linked list. When row i' is inserted, we do not know where it appears
in the list; we would have to search through the list in order to remove
it immediately. Instead, we mark i' as "inserted but not yet recorded"
(making use of the array that keeps the network status of all rows).
Eventually i' is encountered in the course of scanning the list -- at
some later step, in either the current or the next pass; then it is
removed from the list, and its status can be changed to "inserted and
recorded."
Test results
Table 4-1 collect data from the application of hybrid exchange to
GIFFPINC. The results resemble those for insertion-driven deletion, but
with the expected differences.
With respect to both the number of passes and the concentration of
augmentations in the first or second pass, hybrid exchange tends to lie
midway between the insertion-driven and deletion-driven methods. Total
augmentations are quite close to the totals for insertion-driven
exchange, but are not consistently either greater or less.
Average time per pass is about 0.042 seconds. Thus the extra
insertion loop in a hybrid exchange step nearly doubles the cost, but
still leaves it much cheaper than a deletion-driven exchange set.
Rows Pass
-------- ---------------------------------------
Gain Aft 0 1 2 3 4 5 6 7 8 9
RD/U 23 92 Del 115 92 81 72 70 67
Ins 102 91 75 70 67
Time .04 .06 .03 .04 .05
RD/N 29 91 Del 120 94 77 73 69 70 68 68 68 66
Ins 114 81 75 69 71 69 69 68 66
Time .06 .05 .05 .04 .04 .03 .05 .04 .03
CD/UI 10 77 Del 87 80 66 68 66 65 61 62
Ins 86 67 69 66 67 61 62
Time .04 .03 .05 .03 .03 .05 .03
CD/UD 29 83 Del 112 93 70 70 63 66
Ins 117 72 73 63 66
Time .06 .03 .05 .05 .03
CD/UB 29 83 Del 112 93 70 70 63 66
Ins 117 72 73 63 66
Time .05 .05 .04 .03 .04
CS/NI 10 82 Del 92 84 73 74
Ins 94 73 74
Time .04 .04 .03
CS/ND 10 70 Del 80 77 73 71 69 69
Ins 82 76 73 69 69
Time .05 .03 .04 .03 .04
CS/NF 34 95 Del 129 100 89 80 80 78 78 75 72
Ins 123 98 80 81 78 79 75 72
Time .06 .05 .04 .05 .05 .05 .04 .04
CS/NB 10 70 Del 80 77 73 71 69 69
Ins 82 76 73 69 69
Time .04 .03 .04 .03 .04
RA/I 11 93 Del 104 88 79 73 73 77 76
Ins 94 83 73 74 77 76
Time .05 .04 .05 .05 .05 .05
RA/F 6 85 Del 91 78 72 73 71 71 71
Ins 81 72 75 72 71 71
Time .05 .03 .04 .04 .03 .05
Table 4-1. Examples of hybrid exchange, applied to the GIFFPINC model.
The format is the same as in Table 3-1.
5. COMPARISONS
The deletion-driven, insertion-driven and hybrid exchange methods
can now be compared with each other, and with the option of no exchange
as in part I. Detailed data are collected in tables A-1, A-2 and A-3 of
Appendix A. Briefer summary tables are included with the commentary
below, which considers first first effectiveness and then efficiency.
Effectiveness
All three of the exchange heuristics do succeed in substantially
augmenting the embedded network in a large majority of cases. For a
given linear program, the augmentations are generally greatest when the
extracted network is smallest. Thus the various extraction heuristics
tend to differ less in effectiveness after they have been followed by
augmentation. The extreme example of this phenomenon is SHIP12L, which
is reduced to 97 non-network rows by any exchange heuristic, no matter
what was found by the previous extraction heuristic.
Table 5-1 gives an idea of how the three exchange methods compare
in effectiveness with each other, and with the option of no exchange.
Each combination of an LP and an extraction heuristic can be regarded as
a single *case*, for which our tests yield four networks: one using
each exchange method, and one using only simple reinsertion as in part
I. We arbitrarily consider a network to be "nearly best" for a given
case if it is within two rows of the largest found for that case. The
first line of Table 5-1 shows, for each LP, the number of cases (out of
11) in which simple reinsertion found a "nearly best" network. The
following three lines show the numbers of cases in which the "nearly
best" network was found by each of the exchange methods.
------------------------------------------------------------------------
G G S
I R S S T
E F E C H S A
N F E A S I I N
E P N P G C P E D
R I B I R R 1 R A
Number of G N E E 2 S 2 R T
near-best runs: Y C A S 5 8 L A A
---------------
No exchange 0 0 0 4 2 0 5 3 3
Insertion exch 8 8 10 11 3 9 11 11 11
Hybrid exch 7 8 9 11 2 8 11 5 10
Deletion exch 10 10 9 11 10 11 11 6 9
Table 5-1. Comparative effectiveness of exchange heuristics. Each
column shows the number of test runs (out of 11) in which different
exchange options performed "near-best" -- within two rows of the best
option -- for a given test problem. See text for further explanation.
------------------------------------------------------------------------
The data suggest that all three exchange methods are preferred in
most cases to simple reinsertion, and that among the three methods there
is some tendency for deletion-driven exchange to give larger networks.
However, for seven of the nine LPs, all exchange methods found some of
the best networks in a large proportion of cases; for PIES and SHIP12L,
the sizes of the networks do not differ by more than two rows in any
case. The only exceptions to this pattern are SCAGR25, for which
deletion-driven exchange works best and finds the smallest possible
network almost every time, and SIERRA, for which insertion-driven
exchange is preferred.
Table 5-2 shows the largest networks from Table A-1, over all
cases, both before and after augmentation. For four of the test
problems (ENERGY, GIFFPINC, GREENBEA and SCRS8) the use of exchange
methods permits a reduction of at least about 10% in the number of non-
network rows. For the other five problems, however, at least one
extraction heuristic finds just as large an embedded network by itself.
------------------------------------------------------------------------
G G S
I R S S T
E F E C H S A
N F E A S I I N
E P N P G C P E D
R I B I R R 1 R A
Fewest G N E E 2 S 2 R T
non-network rows: Y C A S 5 8 L A A
----------------
Without exchange 71 77 48 61 49 23 97 343 56
With exchange 63 70 37 61 49 20 97 343 56
Table 5-2. Overall effectiveness of exchange heuristics. Each column
shows the smallest number of non-network rows achieved by use of
extraction methods alone, and by use of extraction plus exchange.
------------------------------------------------------------------------
The exchange heuristics should not be dismissed as superfluous for
some LPs, however, merely because certain runs do as well without them.
It is only in retrospect, when all the tests have been run, that an
extraction heuristic can be seen to yield the largest network. If we
imagine running the tests one at a time, then the results of the
exchange offer a valuable guide to the quality of the resulting network.
A large augmentation often indicates that the resulting network is
mediocre, and hence that further runs should be tried. At the other
extreme, when the exchange methods fail to augment the network at all,
then one of the largest possible networks has most likely been found,
and further runs can be avoided.
Efficiency
The running times of the exchange methods are harder to analyze,
because they depend on several factors: cost per setup, cost per
exchange pass, and number of exchange passes. We discuss each of these
in turn, and then offer a comparison of total timings for the most
effective runs.
The relative setup times for the exchange heuristics, as shown in
Table A-2, are consistent with the descriptions in Sections 2-4. The
greatest time is taken to set up for insertion-driven or hybrid exchange
after row-scanning deletion, where a full scan of network elements is
necessary to initialize c^j+ and c^j-. In contrast, the setup for
deletion-driven exchange after row-scanning deletion is negligible,
since the necessary information is already available. Following column-
scanning deletion, all exchange methods require about the same time to
fix up c^j+ or cj+ and c^j- or cj-; and no substantial setup is required
by any exchange method after row-scanning addition. In all cases, the
setup time for exchange is a small fraction of the time required to set
up and execute the preceding extraction heuristic.
Computation times are about the same for each pass of an exchange
method. Thus Table A-2 gives just the average time per pass.
Predictably, the times are always much the highest for deletion-driven
exchange; often the cost of each pass is half or more of the extraction
cost. The times are always the lowest for insertion-driven exchange,
where the cost per pass is usually only a small proportion of the cost
of extraction. Hybrid exchange naturally falls somewhere in the middle,
but is generally closer to the insertion-driven method.
Table A-3 compares numbers of passes. There is a consistent
tendency for deletion-driven exchange to require the fewest passes and
for insertion-driven exchange to require the most, although the pattern
is different in specific cases. The total cost of carrying out an
exchange method could thus be viewed as involving a tradeoff between
number of passes and cost per pass; a method that is lower in one tends
to be higher in the other.
This situation is more complicated, however, because we keep
executing passes until the chance of further augmentation seems very
low. In particular, virtually all runs terminate because two
consecutive passes insert and delete the same number of rows. As a
result, there are two passes at the end of a run that can be considered
superfluous, at least in retrospect. (A few SIERRA runs stop after one
superfluous pass that makes no insertions and deletions at all.)
Interpreted in this light, the counts in Table A-3 suggest that
deletion-driven exchange will achieve most of its augmentation in just
one or two of its expensive passes; this confirms what the more detailed
data for GIFFPINC has already indicated in Section 2. Insertion-driven
exchange, by contrast, can require an unpredictably large number of
passes. Since each pass is inexpensive, however, our conservative
criterion for termination of a run seem appropriate. The situation for
hybrid exchange lies somewhere in the middle.
In evaluating the overall efficiency of exchange methods,
therefore, we consider each of the following possibilities:
Simple reinsertion with no exchange
Insertion-driven exchange with conservative termination
Hybrid exchange with conservative termination
Hybrid exchange terminating after 2 passes
Deletion-driven exchange terminating after 2 passes
Deletion-driven exchange terminating after 1 pass
Table 5-3 summarizes all of the "best" runs that result. Among all runs
that found the largest network, we show the one that took the least
time. We also show runs that found the largest network in nearly the
least time (generally within 10%), and runs that found almost as large a
network in less time.
------------------------------------------------------------------------
Heuristic
-----------------
Time Out Extract Exchange
ENERGY 1.43 63 RD/N Del/1
GIFFPINC 0.17 72 CD/NB Hyb/2
0.23 70 CD/NB Ins/inf
GREENBEA 1.11 39 RD/N Hyb/2
1.13 37 RD/N Ins/inf
PIES 0.16 62 RA/F Ins/inf
0.19 61 CD/UI --
0.19 61 CD/UB --
SCAGR25 0.02 49 RA/F --
SCRS8 0.06 20 RA/F Hyb/2
0.07 20 RA/F Hyb/inf
0.08 20 RA/F Ins/inf
SHIP12L 0.71 97 RA/F Ins/inf
0.74 97 RD/N --
0.76 97 CD/UB --
SIERRA 0.36 343 CD/UI --
STANDATA 0.13 56 CD/UB --
Table 5-3. Summary of best runs. For each test problem we show the
combination of heuristics that took the least time to find the largest
network. We also show some combinations that did nearly as well.
The last column indicates the exchange option (if any) as explained in the
text. Ins/inf and Hyb/inf denote insertion-driven and hybrid exchange with
the conservative termination criterion. Hyb/2 is 2 passes of hybrid
exchange, and Del/1 is one pass of deletion-driven exchange.
------------------------------------------------------------------------
The overall impression given by the table is that many different
methods have their place. Among the extraction heuristics, row-scanning
deletion without updated penalties appears 3 times. (Strangely, the
version that does update penalties -- which has been most extensively
studied prior to our work [] -- does not appear at all.) Column-
scanning deletion appears 5 times in various versions, and row-scanning
addition working forwards appears 4 times.
Among the exchange heuristics, the table shows largely insertion-
driven exchange and 2-pass hybrid exchange. Deletion-driven exchange,
with its high cost per pass, gives best results only for ENERGY. Four
LPs require an exchange method to get the best results, as previously
noted, and three get best results without an exchange method. In the
cases of PIES and SHIP12L do very well using the especially simple
combination of row-scanning addition and insertion-driven exchange, even
though certain more sophisticated extraction heuristics can do
comparably without exchange.
We could perhaps change these conclusions somewhat by broadening
our definition of "nearly best", by considering additional termination
criteria for exchange methods, or by making further runs using other
variants of the extraction heuristics. However, the lessons to be drawn
from the results would be much the same; we discuss this issue further
in the concluding remarks of Section ?.
6. CONCLUSIONS
...
Effectiveness of embedded network detection
Figure 6-1 summarizes the steps by which the original LP rows have
been pared down to the network subset N. We have described in part I of
this paper (Bixby and Fourer 19xx) the first three steps, which remove
rows of the following kinds:
Trivial rows, such as ones that are nonconstraining or that have
fewer than two elements.
Certain "generalized bounding" rows that can be appended to any
network after at most a simple linear transformation.
Rows that cannot be transformed through scaling so that all their
elements are +1 or -1.
The resulting +-1 rows are subjected to the network extraction and,
optionally, augmentation heuristics, which remove additional non-network
rows. The table shows the largest networks that result, as reported in
the previous section.
---------------------------------------------------------------------
G G S
I R S S T
E F E C H S A
N F E A S I I N
E P N P G C P E D
R I B I R R 1 R A
G N E E 2 S 2 R T
Rows: Y C A S 5 8 L A A
------------
Total 2263 617 2400 663 472 491 1165 1228 468
Trivial 28 27 85 9 2 26 327 1 2
Bounding 394 0 53 8 129 16 0 0 39
Unscaled 516 0 1299 368 98 136 8 0 76
+-1 325 590 963 278 243 313 830 1227 351
Non-network 63 70 37 61 49 20 97 343 56
Network 1262 520 926 217 194 293 733 884 295
Table 6-1. Summary of the network-finding process. Trivial,
generalized bounding and unscaleable rows are set aside to yield the
subset of +-1 rows. The enough non-network rows are set aside to
produce a network subset. All table entries show the numbers of rows in
the various categories; non-network counts are taken from the best runs
in Table 5-3.
---------------------------------------------------------------------
In assessing the sizes of the networks we ignore the trivial rows,
which could have been removed in any case. Thus the effective
percentage of network rows, as shown in Table 6-2, is the number of rows
found by the heuristics plus the number of generalized bounding rows,
divided by the number of nontrivial rows.
---------------------------------------------------------------------
G G S
I R S S T
E F E C H S A
N F E A S I I N
E P N P G C P E D
R I B I R R 1 R A
Nontrivial G N E E 2 S 2 R T
Rows: Y C A S 5 8 L A A
------------
Total 2235 590 2315 654 470 465 838 1227 466
Network 1656 520 979 225 323 309 733 884 334
(%) 74% 88% 42% 34% 69% 66% 87% 72% 72%
Upper bound 1669 522 982 228 323 310 768 956 348
(%) 75% 88% 42% 35% 69% 67% 92% 78% 75%
Gap 13 2 3 3 0 1 35 72 14
(%) 1% 0% 0% 0% 0% 0% 4% 6% 3%
Table 6-2. Effectiveness of network-finding. The first line gives the
number of nontrivial LP rows, as implied by Table 6-1. The rest of the
table gives the following information, in both absolute numbers of rows
and as a percentage of nontrivial rows: the size of the largest network
we found (including generalized bound rows); the Brown and Wright (19xx)
upper bound on network size; and the difference between network size and
the bound.
---------------------------------------------------------------------
The GIFFPINC and SHIP12L problems, which can be scaled to have
virtually all elements either +1 or -1, are about 7/8 network rows.
Five of the other LPs have a network proportion between about 2/3 and
3/4, under varying circumstances. The SIERRA problem, based on a two-
commodity flow model, is +-1 scaleable but has many rows that cannot be
included in a network. A combination of factors influence ENERGY, PIES,
SCAGR25 and SCRS8; they have generalized bounding rows, reasonably many
+-1 rows, and a fairly high proportion of network rows within the +-1
subset. Only GREENBEA and PIES are fewer than 1/2 network rows, in both
cases because fewer than half the rows could be scaled.
We can also compute upper bounds on the sizes of the embedded
networks, using a fast implementation of a method described by Brown and
Wright (19xx). Table 6-2 shows these bounds, as well as the differences
between the bounds and the largest networks. For five of the LPs, our
network subsets must be at most a few rows short of optimality, relative
to the set of +-1 rows that we have employed. The other networks may
fall short of optimality by a few percent.
Efficiency of embedded network detection
Timings for the process of finding an embedded network are
summarized in Table 6-3. First we show the times for reduction (removal
of trivial and generalized bound rows) and for scaling. Then two
network detection times are given: the smallest time needed to find the
best network (from Table 5-x) and the largest time taken by any
combination of extraction and augmentation methods.
---------------------------------------------------------------------
G G S
I R S S T
E F E C H S A
N F E A S I I N
E P N P G C P E D
R I B I R R 1 R A
G N E E 2 S 2 R T
Timings: Y C A S 5 8 L A A
------------
Reduction 0.61 0.08 0.49 0.16 0.07 0.12 0.26 0.11 0.08
Scaling 6.28 0.09 7.52 1.84 0.29 0.53 1.46 0.24 0.46
Detection (min) 1.43 0.23 1.13 0.19 0.02 0.06 0.71 0.36 0.13
(max) 4.04 0.87 4.26 0.87 0.41 0.75 5.15 1.92 0.66
Table 6-3. Efficiency of network finding. The first two lines give the
timings from part I (Bixby and Fourer 19xx) for removal of trivial and
generalized bound rows, and for scaling to increase the number of +-1
rows. The remaining lines show the minimum total detection time for the
best network, from Table 5-3, and the maximum detection time for any of
the runs represented in part II.
---------------------------------------------------------------------
If we think in terms of applying a single best combination of
heuristics to an LP, then the results suggest that scaling is likely to
be the dominant cost. In most cases the scale time is substantially
greater than the best detection time. The only exceptions are GIFFPINC
and SIERRA, which can be scaled completed by a simple myopic algorithm
as explained in part I.
If we envision experimenting with a variety of heuristics, however,
then the results suggest that the cost of detection will be dominant.
Reduction and scaling will have to be run only once. The cost of
repeated detection runs will add up, especially if some produce timings
closer to the maximums than to the minimums.
Generally we would recommend the latter approach, comparing various
runs, when an embedded network is being sought in an LP for the first
time. Later, runs on substantially similar versions of the same LP
could use just the best combination of extraction and augmentation.
Thus the cost of detection would be greatest in the initial stages of
experimentation, while scaling would come to dominate in the subsequent
"production" runs.
We note two factors that may modify this analysis. First, the
scaling itself involves a sequence of heuristics, as described in part
I; possibly its cost can also be reduced when we know that it will be
applied repeatedly to versions of the same LP. Second, if we are
willing to settle for an embedded network with gains -- in which each
column can be scaled to have at most a +1 element and a negative element
-- then we can dispense with the scaling to +-1 rows.
Implications for solving linear programs
[results of tests with embedded-network simplex codes]
Implications for finding embedded structures
[recommended use of our heuristics]
[possibilities for extensions -- more transformations, etc.]
[conclusions about heuristics for this kind of problem in general]