Branch-and-Bound and Beyond

BRANCH-AND-BOUND AND BEYOND

Patrick A. V. Hall Department of Mat hematics,

(Division of Computing Science), City University, London, EC1.

Abstract._

The branch-and-bound algorithm is stated in generality, and illustrated by two applications, unidirectional graph search, and reducing a sparse matrix to its minimal band form. The algorithm is then gene ral ised to multiple partitions, applied to bidirectional graph searching for both heuristic and non-heuristic searches, and further extended to ~raph searches and prorl em solving with s :Jbgoals.

1,0 Introduction and Summacr

The branch-and-bound algorithm is a simple technique for the optimisation search for the minimum (or maximum) of a function. It is very basic to artificial intelligence and operations research, and has been repeatedly rediscovered and used in the solution of hard problems. (1,2,6,9) In this paper I shall give a general statement of the algorithm, and then consider the application to reducing a sparse matrix to the band matrix of minimal band-~idth. After this I shall show that the well kno~ graph searching methods (4,5,9) are somewhat dis~uised examples of branch­

and-bound.

This simple branch-and-bound idea will t hen be extended to a more complex optimisation search with multiple starting points, in which form it wi ll be used to solve the bidirectional gr~ph-search problem, givin~ a new unifiei view of existing solut ions, both heuristic and non-heuristic. Fi nally the application of multiple branch-and-bound is further e xtended to cover the use of sub ~oals in gr~ph search and problem solving.

Graph searching as a problem area in artificial intelli ~ence is important because many problems can te represe r. ted as a ~raph which requires a path to be found between two given nodes (J,S,9). Any path between the start and termination nodes would constitute a solution, but a path of minimal length (= number of steps ) can be t ho·;ght of as the most 'elegant' solution, and is often ai~ed for. Hence ::-eneral Problem Solvir.g becomes findin s the shortest path in a graph, which in turn is, as ·.Je s'1all see , a special applic~tion of the branch-and-bound al .;orithm.

However, not all problems are most naturally formulate.j as graph se3.I"c '>es; for ex~ple the travellins salesman problem is expressible as a shortest pat~ problem, but occurs more naturallv as a branch-~nd­ bound aj:Jplicat ion ( 6). Anot".e r example is a match i ng problem in chromosome analysis considered by :~ontonari (7); the natural 'Jay to tackle t.his problem is directly usins tranch-ani-bound, but the author laboriously converts the problem to a ~raph s ~ a.rch and then applies t~e algorithm of Hart, Nilson and ~'phael {S ) . ·

2,0 The Br!l!lch-s.nd-!3o·md Al"orithm

Consider t he problem of minimising a function f in som~ (d iscrete) set X: i.~. f:X-+R and we wish to find x* in X such that f(x·)~f(x) for all x in X. Sup~ose that we 'cave available a func t ion g:2 -R which compu t es a lo\Je r bound for f in a set A:

~(A)~f(x) for all xEA and ACX

We shall also re1uire that when A is a single point a, then

though this can easily be wa i ved s i nce t he algorithm ass umes t he ability to test whether a set comprises a sin~le point,

Informally, describ~d elsew~ere (2(6), t 'ce str,te~ is to divide up (partition] the set X into successively smaller portions, each time only further subdividing t ~e most prom isin ~ subset of X, as measured by g, until eventually a subset ~ontaining a sin~le point is selectei for subdivision, w~ i ch terminates the algorithm with the sinsle point as the minimum.

Definiti0n: a partition )\ of a set X is a set of subsets of X wh i~h are mutually exclusive and exhaustive:

)\= {A 1 , ... ,Am:\c;X,Aif\Aj =)if i "f j,

Formally, the al gorithm is:

START

STEP 1. Set partiti on )\ = {x \ .

ITERATION

STEP 2. Find t he Y in)\ such that g(Y ) m m is minimal, If more than one, choose any of them,

STEP ), If Ym is a set containing a single point, go to TERMINATION, STEP 5.

STEP 4. Partition Ym into Ym 1 , ··· ,Ymn' and remove Ym from , replacing it by Yml'Ym 2 , ··· ,Ymn' Return to Step 2.

TERMINATION

STEP 5. The minimum x* is the contained in Ym' with single point f(x*) = g(Ym ), c

Clearly the above algorithm does locate the global minimum for any lower bounding function g (providin : only that~ an i f coincide for sets of sin,>le poi nts ) and any partitioninr; pol icy, \ol f: en g compu t es the r;reat .-~st lower bound g·, t he algorithm is most eff icient and make s no un~ecessary partitions; whil e i f g were const~nt for all sets of more than one element, the search would r. ave to ultimately evaluate f ~t every po i nt , makine an exhau,. ti ve search. The3e are t r.e two extreme cases: it is ·1er y re·:dil y seen that for intermediat e ca~~s, if g 1 ~g 2 ~g· then usinr; g 1 mus t r esult in at least as many partitioni ng i t~ rat i ons as usin ~ g 2 ·

Two common properties of lower boun.iing functi0ns are wcrt r. rem··rk i ng on : t hey wil l appear later in graph se~rch ing. These are

• (i) g(A) > g(B) if AC B
• (ii) g(AnB)~ max \g(A) , g (s)}.

The actual lower boundin ~ function g depends upon the particular problem an i in that sense is a 'heuristic func t ion'. The more information about t he problem t hat is used, the closer g approaches t he greatest lower bound g·, the more eff ici ent is the algorithm as outlined above . One could even contemplate using any estimate of the greatest lower bound, recogn is ing that if the bounding condition is violated, a non-optimal sol uti on may be returned , but the error could be no more than the error in the estimator.

In the form given, the algorithm may only find a candidate solution point after considerable searching and branching : in practice this is undesirable since it may be necessary to terminate search early with a suboptimal solution, because of exceeding either storage or time limits . Th i s requires a modification to the basic algorithm to force the search to refine partitions until a possible solution point has been found - and then to continue searching until the minimal point is found; one way to do th i s would be to subtract a depth factor from the bounds to bias the search towards depth . An additional advantage to locating a potential solution point early in the search is that pruning of the search tree is possible, while we acquire the disadvantage of (possibly) more iterations. Note however that we are still guaranteed finding the optimum providing that early termination is not forced upon us.

2.1 Application to Band Matrix Reduction

A sparse matrix is one in which the majority of the elements are zero: these arise in many problems such as engineering structural analysis.(lO) Storing sparse matrices in the usual way is wasteful; one solution is to store only the non-zero elements, for example by using hashing methods.(6) This leads to special numerical techniques.(lO) A preferred solution would be to reduce the matrix by row and column permutations to a band matrix (i.e. a matrix in which all non-zero elements lie in some band close to the diagonal), for which only the band elements need be stored: the advantage is then that standard and efficient numerical techniques are applicable . The reduction to a band matrix is normally carried out by ad hoc methods, by skilled humans prior to computer runs: what is desired is a guaranteeable method for performing this reduction. The branch­ and-bound algorithm proved ideal.

For an n by n matrix, there are (n!) 2 possible configurations, and exhaustive searches are untenable. The technique used was to partition by row or column selection. Assuming for the moment that the lower bound function g is available (this will be outlined later), then the first partition of the totality of possible configurations is to consider the n possible selections of particular columns of the original matrix for the first position in the reduced matrix. Among these n subsets, the one with smallest lo10er bound is selected, and the n possible selections of rows for the first position of the reduced matrix considered. Among the resulting 2n-l subsets that with minimal lower bound is selected for row or column partition as appropriate, and so on, for a minimum of 2n partitions.

The lower bound function computes a bes t possible bandwidth for a partially determined mat rix (with the first m columns fixed and the first m or m-1 rows fixed) as the maximum of the following : (i) for the fixed portion at top left; count from the diagonal of the fixed portion along the rows and col umns to locate the last non-zero .element ; within the fixed portion (m by m or m by m-1) the elements are fixed, while beyond the fixed portion i t is assumed th at the non-zero elements could be positioned immediately following the fixed columns or rows . Repeat this for each row and column within the fixed portion, taking the maxi mum count found.

(ii) for the unfixed portion at bottom right; count the number of e lements in each r010 and colUITU1 and assume that these could be placed symmet rically about the diagonal - hence bound to bandwidth here is maximum of r (count + 1) /2] where (I] means the integer part of I.

Figure 1 illustrates the method for a 4 by 4 matrix of bandwidth 2. Figure 1 (a) shows the original matrix and Figure 1 (b) illustrates in tree fora the complete search. Each node is labelled with the value of the lower bound function g, and the matrix to date; the elements whose positions are fixed appear in the upper left-Qand submatrix marked with thick linea. The search for the next node to develop selects, when more than one node has the minimal value, that node nearest the bottom of the tree. Each level of the tree is labelled to show what develo!JIIent is being made, which row or column is being fixed: each branch of the tree is labelled to indicate which row or column in the original matrix is the one tl:at is being fixed in the position indicate for the whole level.

FIGURE 1. The application of Branch-and-bound to reducing a sparse matrix to its minimal band matrix form.

(a) the original matrix

(b) the search tree: branches are labelled vith the row or column of the original being fixed in the position shown at the left; nodes are labelled with the bound, and the fi:md portion in the upper left marked off.

The algorithm as actually implemented (in Algol ) uses a depth forcing initial search (as discussed previously) so that suboptimal results could he returned on exceeding storage hounds. Search length has been found to be very dependent upon the particular matrix, varying from searches direct to goal (as in the example) to searches where only suboptimal (but acceptable)

solutions could be found .

3 .0 Graph Searching as Branch-and-Bound

ll'e shall no~> examine graph searching and appl y the preceding algorithm to its solution. We wish to find the shortest route between two nodes s and t in a graph, such as that illustrated in Figure 1.

We shall define a weighted directed ~as an ordered set ( /1: ,1',~> ) where t\ is the set of nodes of the graph; E is a set of ordered pairs of nodes which we call the edges of the graph, sa1ing that an edge (a,b ) goes from node a to node b ; and w is the weight or length function, mapping E to the non-negative real numbers , saying that w(a,b ) is the length of edge (a,b).

We define a path or route between two

nodes s and t as a sequence-or-nodes

and define the length of this path as

The set X to be searched is the set of all possible loop- free routes from s to t, and the subsets of routes which will be used in partitions of X will be those which start at s and have an initial part in common. The function g will give the length of the path in common - all routes in the set must obviously be at least that long . Partitioning will be by extending the initial path by one edge for all possible edges eliminating those which introduce loops : each of these extended initial paths defines a subset of the refined partition. A subset of the partition comprises a single point when the defining initial path extends from s all the way to t.

With these definitions, the graph search becomes a branch-and-bound problem, and the search of a simple graph is illustrated in Figure 2. In part (a) the graph is shown, a directed graph with edge weights as labelled . The search process is shown in part (b)~ subsets of the part1 t1on are named by the path that i s common (thus <sac> is the set of all paths starting at s going through a and then c and finally ending at t). The search starts with the partition consisting of the single set <s > of all possible routes from s to t. This is then partitioned into two subsets, <sa> all those routes from s through a to t and <sb> all those routes from s through b to t . These have bounds 1 and 2 respectively. The min i mum of these is selected for further refinement, and thus <sa> is refined to <sac> and ··sad> with bounds 6 and 7 respectively . And so on until stage 8 where the search for partltlonsubset of minimum bound g finds <sbct > which contains a single point which is therefore the minimum. Part (c) of Figure 2 shows the search process displayed as a tree with nodes labelled inside by subset and outside by bound. The sequence in which the tree nodes are developed (i.e. subset s partitioned) is in ascend i ng order of bound , with development from left to r i ght where nodes have equal bound.

This search procedure is almos t the Dijkstra (4 ) graph search method, excepting that some redundant routes are eliminated in the Dijkstra method - for example , having two sets of routes with initial parts endi ng in c (i.e. <sac> and <sbc>) is wasteful and only that of small bound <sbc> need be retained after stage 4 : effect i vely one is coarsening the partition by forming the union of the two sets, and computing the union bound from g(AV B)= min (g(A) ,g (B)). 1\ote that this pruning is also retroactive in the sense that some unions would occur between a new subset and one that was previously partitioned (for example between <sacd> and <shed>), but in this case cannot change the earlier bound (of <shea>) since g has the monotonic property g(A) ~ g(B) if A~ B.

The branch-and-bound algorithm can further be extended to heuristic graph search in a way comparable to the extension of the Dijkstra Algorithm.(6,9) Suppose that we possess a heuristic function h(x,y) which estimates the distance through the graph from node x to node y. If h(x,y) ~ d(x,y ) where d(x,y) is the 'true' minimal distance through the graph from x toy, then using

the bounding function

(formed from the length of the part in common plus the estimate of the. distance left to go) gives a lower bound for the set of all paths initially along <s ..· x> and thence tot .

Using this g in the branch-and-bound algorithm applied to graph search leads to a ~uided search, guaranteed to return the m)nimum. Again irrelevant repetitions can be eliminated - if two partial paths have a common end point, one can coarsen the partition as in the non-heuristic case, but there is a note of caution: retroactive coarsening could prune a branch of the tree and not the new leaf, unless the monotonicity property holds for g. This is the "consistency condition" of Hart et al,(6) and allows a 'tidy' algorithm, but in no way affects the correctness of the solution obtained.

A note on difference of emphasis between the approach here, and the more standard approach (6,9) to graph search, mu.st be made to avoid confusion . We have seen above that in part1t1ons, sets defined by p&rtial paths with common end points should in the interests of efficiency be united : the important parameter of the subset is the terminal node of the common initial path . In the standard approach the emphasis is upon the nodes, with the common paths defined implicitly by some form of chaining. The search for the minimum for next branching is ever the node set, restricting the search to a subset of nodes which are "open" or "visited" with the consi s tency condition ensuring that previously "closeJ" or "developed" nodes do not need to be re-opened . Relating this terminology to our viewpoint, the open nodes are those at the end of a common path for some set in the partition, and these become closed when the corres­ ponding subset is selected for subdivision.

The approach to graph search given here, and the standard approach, lead to the same algorithms: the approach via branch-and-bound serves to add fresh insight into the ~oo· orkings of unidirectional graph searches. Later, in more complex searches , the branch-and-bound approach will full y justify itself with the generation of powerful new algorithms.

4.0 Multiple Branch-and-Bound

The natural extension of the branch­ and-bound algorithms discus s ed in secti on 2 is to us e more than one partition, refining each partition in turn (or in some arbitrary order) . At each stage of the search we would have an effective partition on the set of the product of the separate partitions:

Definiti on : gi ven a set of partitions ~ 1 , ~ , , . .. , ~ we shall define a product partiti on a~

The algorithm fo llo~oo· s, again m1nim1s1ng a function f on a set X, using as an aid a lower bound function g and a ne~oo· function q. The minimum will be located in a subset of the product partition, and since this gro"'s much more rapidly than the individual component partitions, the actual search would be expected to be considerably more efficient.

As previousl y, g 2x -· R is defined by

g(A) f(x ) for all x in A, and IIC X

and g ( ( a }) f(a) for all a in X.

In addition we are given a "combination" function q such that

where g*(A) is the greatest lower bound o~ f in A and where ~l····· ~n are partitions that we will progressively refine . We shall denote by mi, the minimum g(A) for A in ~i:

Two parameters x· and mr-; "'i 11 be us ed to record the best point found so far .

START

STEP 1 . Set mN=~,and ~. = { X } ) and m.=g(X) for all j .

ITERATION

STEP 2. further refinement.

STEP 3.

)

Choose any of then . for )

Suppose that "s selected :

3 . 1. Select Ym € · s such that g(Ym) is minimal . If more than one , choose any of them.

3 . 2. Partition Ym into Ym l ,Ym; ·· . . ,Ymk·

3.3 . In r s.

• 3 . 4. Check ~oo· hether Ymi f'l Z i s a singl e point x for all i=l, . . . ,1. and : E ~ s

(where o: is the product 5

partition of alI the sepa rat e partitions other than · 5 )

If it is,then evaluate f (x) and if f(x) < ~I\ then change ~! \ to f(x) and x* to x .

3. 5 . Update m~ to t~e minimum of the g(Y) . for Y.: · 5 .

STEr 4 . If '11\ ' C)(m 1 ,m; , . . . · ~) then and hence

Note that while partitioning and associated searches occur for the i ndividual partions ni, the minimum is identified by reference to the product partition n. The terminating condition is encountered by virtue of the properties of g and q.

Note that Step 3.5 and Step 4 could be replaced by directly testing at a modified STEP 4 whether MIN > g(Z) for all Z in the product partition n. The usefulness of the function q is that it obviates this necessity and introduces a radical improve­ ment in efficiency over this more naive approach. The simplest form for q, always possible, is q(x1, ... ,~) = max(x1, ... ,xn); but as we shall see, other functions are also possible.

4 . 1 Application to Bidirectional Graph Searching

The bidirectional graph searching problem (9) can be very naturally solved

repeat from STEP 2 : otherwise,

terminate with STEP 5.

TERt-1INATION

The choice of partition to refine at Step 2 is entirely arbitrary, and could be random, or each in turn, or always choosing the one with fewest members. We could even always choose the same partition, in which case we obtain a variation of the simpler algorithm of section 2.

That this algor)thm does indeed return a minimum point follows from the observation that the algorithm terminates

when first

from which we deduce

from the definition of the mi's. from the definition of q Hence

using the multiple branch-and-bound algorithm. Two partitions would be used, generated from partial paths anchored at either end: thus one partition is determined by subsets defined by common initial paths, (as in the Dijkstra search) while the other partition is determined by subsets defined by common final paths. Two subsets (one from each partition) intersect in a point when they both have the same extreme point on their defining partial paths. Heuristic and non-heuristic searches differ both in the lower bound function used (the function g) and in the way these combine on inter­ section (the function q). This double distinction is important. The general bidirectional graph-search will be detailed below, before proceeding further: refine­ ments of efficiency will be overlooked in the interests of clarity, and as in the unidirectional form, unnecessary partial paths will be retained .

The problem is to find the shortest path through a graph from node s to node t. The set to be searched is all possible loop-free paths starting at s and terminating at t. We shall call the two partitions ns and nt and label the elemental subsets of the partitions by the partial paths defining them (as we did previously in section 2.1). X will have two representa­

tions as <s> and <t >.

START

ITERATION

STEP 2. Choose to refine either 1Ts or nt.

STEP 3. Suppose that ns were chosen : a symmetrical set of steps would be done if nt were chosen.

3 .1. Find the set <s . . . x> inns such that g(<s ... x>) is minimal. If there are more than one, choose any of them.

3 . 2. Partition <s ... x> by finding all the successors YJ···· ,yk of node x (i.e. all nodes connected by a single edge from x) but rejecting all successors y on the path s . . . x, and form sets <s ... xyJ >, .. . ,<s ... xyk>·

1. Replace <s ... x> by <s ... xy 1>, <s ..· xy2>, .. ,<s ... xyk>.
2. The previous step will have produced a lot of new single point sets in the product partition ns x nt. Search all additions tons x nt (i.e. search the set <s ... xyi > 1'\ Z for all i=l, ... ,k and all Z c nt) to see whether these are single points (the matching of the last symbol in the label of the set of ns with the first symbol of the label for the set of nt determines this) and if the intersection is a single point <s ... X)'i ... t>, if f(<s ... xn ... t >) <MIN update Ml~ and x· respectively to f( <s ... xyi ... t >) and <s ... xyi ... t >.
3. Update ms to the minimum of g(Y)forY£ ns.
4. STEP 4. If Ml~ > q(ms,mt) then repeat from STEP 2.

STEP 5. x· is path of minimal length ~11~.

Heuristic and non-heuristic search have the following particular bounding functions g and q:

(1) Non-heuristic

The bounding function g is the length of the common path

The combination function q is given by

The intersection of two sets implies having t~-· o partial paths (one from each set) which must be common to all paths in the intersection set (note that our sets arc such that one path cannot be included in the other) : hence one can compute a bound for the intersection simply as the total length of path common to all paths in the set.

(2) Heuristic

The bounding function g is given by

where h(a,b) is the heuristic estimator of the minimal path length from a to b, and must underestimate. For the one partition x 0 = s and for the other partition Xm = t. The combination function is given by

The usual form of these algorithms includes an extra coarsening of the partition at Step 3.3, removing redundant sets as in the unidirectional case.. Two different sets with labels matching at beginning and end need not both be retained, only that with shorter defining path being needed . The resulting algorithms for bidirectional graph searching are similar to existing ones. (9). The heuristic form is almost identical to the general algorithm VGHA of Ira Poh l (9), but our non-heuristic form is neither a simple specialisation of VGHA with h(x, y) = 0, nor a restatement of Pohl 's VGA, but is something of a marriage of the !low. The heuristic and non-heuristic cases have in t he past been tackled separately : here they are united in a single general algorithm.

That our algorithms work follows from the fact that they are particular cases of the multiple branch-and-bound algorithm : there is no need to worry about the subtle termination conditions that have proved troublesome in the more conventional approaches. (9)

4.2 Graph searches with subgoals

In graph searching, why should we stop at a mere two partitions? We can introduce further partitions by choosing a point as a possible intermediate node, and then in addition conduct further explorations from there. This in problem solving is the setting up of subgoals . No matter what the number of subgoals, whether these are added to during search, whether they are in some ~ense parallel or sequential (i.e. whether they are alternatives, or whether the solution path is thought likely to pass through them both), the algorithm will be the same. Further, the search can be heuristically guided or not, using the funct1ons g and q as previously given .

' /

'

The algorithm will be the full multiple branch-and-bound version of the previous bidirectional graph search, but with one generalisation. All except one of the partitions will be permitted to be partial, by which we shall understand that while the sets of the individual partitions must still be disjoint, they need not necessarily unite to the complete set; the appropriate generalisation of the product partition will be

if ni is partial }.

Note that rr is not necessarily a partition since its component subsets are not necessarily disjoint . But this does not matter , and using this rr at Step 3. 4 gives the required algorithm.

To illustrate this algorithm, Figure 3 displays the search of the graph of Figure 2(a) working forwards from s, backwards from t, and backwards from a single subgoal c. Note that the subgoal only helped here because it was on the solution path: the saving is small, because the problem is small . The advantages of the extension to subgoals will only be apparent on large problems, and especially where looking for any path, when the fortuitous choice of the subgoal on the minimal path is not necessary .

To obtain some insight into the savings possible with subgoals, let us analyse a special class of graphs . Let us define a binary tree as a graph in which all nodes have exactly two edges entering them and two edges leaving them; all edges have unit weight and there are no loops. Trees must hence have infinitely many nodes. Two examples are shown in Figure 4. (Note that we are not intending rooted trees here . )

In a binary tree, starting at a points there are exactl y zk paths of length k. There may be zk or less nodes at distance k, depending on whether paths converge or not . Suppose that we are required to search a binary tree for a route between two nodes, s and t, of minimal distance K apart (there may well be routes of length greater than K as we 11). 1\e ~hall consider onl y non-heuristic searches with each partition taken in turn, and no coarsening to remove redundant paths . Then a unidirectional search wi 11 undergo between 2K-l and 2K iterations.

Simple bidirectional search will [K/2) -1 [K/2 ) + 1 undergo between 2.2 and 2. 2 iterations, where [K/2) means the i ntegral part of K/2.

If we have a bidirectional subgoal (i.e . a subgoal searched in both directions, thus defining a pair of partitions) situated halfway along a minimal path , t~? 4 Y~ber of itefat!Q~l will be between _4.2l and 4.2 K/ l . In general w1th n-1 bidirectional subgoals at equal distances along the same minim~l ~at~ 1 the search wi ll+ involve between 2n.2tK/ nj and 2n.2[K/ 2n) 1 iterations. An arbitrary set of n-1 bidirectional subgoals cannot be better than this last case, but cannot be worse than for n times the figure for simple bidirecti ona l search. A graphical comparison is gi ven in Figure 5, for the case K = 100 .

The use of subgoals in problem solving is a gamble, for you may take longer to solve the problem, but you may well save dramatically: however, you cannot as a result fail completel y if the subgoals are used within the frameo; or k of a multiple branch-and-bound algorithm, for if all else fails, the search must succeed as a unidirectional search .

2....9_ References

1. Barrow,P.,C·, and Popplestone 1 P...J, 1 "Relational Descriptions in Picture Processing", Dept. of Machine Intelligence and Perception, Univ. of Edinburgh, July 19?0.
2. ~stall 1P .M., "Tree searching methods with an application to a network design problem" , Machine Intelligence 1, pp65-87. Oliver & Boyd , Edinburgh. 1967
3. Doran,J,,"An approach to autcmatic problem­ solving", Opus sit, pp1('5-123. 1967
4. Dijkstra,E.,"A note on two problems in connec­ tion with graphs", Numerische Mathematik, 1, pp269-271. 1959. -
5. Hart,P.,Nilsson,N ·· 1. and Raphael,F., "A formal basis for the heuristic determination of minimum cost paths" 1 1!:1£. 1 ~, pp 1 C0-1 C 7, July 1968.
6. Lawler ,E.l .· and Wood,D.E,, "Branch-ar.d-1:-ound mett:ods: a survey", !!>erations Research ,11., pp699-719. 1966. -
7. Hontanari 1 l'go,"Heuristically guided search and chrcmosome matching", ArHficial Intelliger..ce, 1, pp227-245. 1970.
8. ""Morris ,R. "Scatter Storage Techniques" , Cornr:, ACM,l1,1,pp33-44,Jan,J9~8.
9. Pohl;Ira, "Bi-directional and Heuristic Search in Path Problems", Stanford Lir.ear Accelerator Centre Report 104, May 1969.
10. Tewarson,R.P., "Ccmputation with Sparse Matrices", SIAM Review,H,4,rp527- :1.4. l 0 7C.