Markowitz and Manne + Eastman + Land and Doig

= Branch and Bound

William Cook

2010 Mathematics Subject Classification: 90C57, 90C10

Keywords and Phrases: Branch and bound, integer programming, traveling salesman problem

The branch-and-bound method consists of the repeated application of a process for splitting a space of solutions into two or more subspaces and adopting a bounding mechanism to indicate if it is worthwhile to explore any or all of the newly created subproblems. For example, suppose we need to solve an integerprogramming (IP) model. A bounding mechanism is a computational technique for determining a value B such that each solution in a subspace has objective value no larger (for maximization problems) than B. For our IP model, the objective value of any dual feasible solution to the linear-programming (LP) relaxation provides a valid bound B. We can compute such a bound with any LP solver, such as the simplex algorithm. The splitting step is called branching. In our IP example, suppose a variable x_{i} is assigned the fractional value t in an optimal solution to the LP relaxation. We can then branch by considering separately the solutions having x_{i} ≤ ⌊t⌋ and the solutions having x_{i} ≥ ⌊t⌋ + 1, where ⌊t⌋ denotes t rounded down to the nearest integer. The two newly created subproblems need only be considered for further exploration if their corresponding bound B is greater than the value of the best known integer solution to the original model.

Branch and bound is like bread and butter for the optimization world. It is applied routinely to IP models, combinatorial models, global optimization models, and elsewhere. So who invented the algorithm? A simple enough question, but one not so easy to answer. It appears to have three origins, spread out over four years in the mid to late 1950s.

As the starting point, the notion of branch and bound as a proof system for integer programming is laid out in the 1957 Econometrica paper “On the solution of discrete programming problems” by Harry Markowitz and Alan Manne [17]. Their description of the components of branch and bound is explicit, but they note in the paper’s abstract that the components are not pieced together into an algorithm.

We do not present an automatic algorithm for solving such problems. Rather we present a general approach susceptible to individual variations, depending upon the problem and the judgment of the user.

The missing algorithmic glue was delivered several years later by Ailsa Land and Alison Doig in their landmark paper “An automatic method of solving discrete programming problems” [12], published in the same journal in 1960. The Land-Doig abstract includes the following statement.

This paper presents a simple numerical algorithm for the solution of programming problems in which some or all of the variables can take only discrete values. The algorithm requires no special techniques beyond those used in ordinary linear programming, and lends itself to automatic computing.

Their proposed method is indeed the branch-and-bound algorithm and their work is the starting point for the first successful computer codes for integer programming. There is a further historical twist however. Sandwiched in between Markowitz-Manne and Land-Doig is the 1958 Harvard Ph.D. thesis of Willard Eastman titled Linear Programming with Pattern Constraints [5]. Eastman designed algorithms for several classes of models, including the traveling salesman problem (TSP). Page 3–5 of his thesis gives the following concise description of the heart of his technique.

It is useful, however, to be able to establish lower-bounds for the costs of solutions which have not yet been obtained, in order to permit termination of any branch along which all solutions must exceed the cost of some known feasible solution.

His methods, too, are early implementations of branch and bound. So Markowitz-Manne or Eastman or Land-Doig? Fortunately there is no need to make a choice: we can give branch-and-bound laurels to each of these three groups of researchers.

1 Markowitz and Manne (1957)

The Markowitz-Manne paper is one of the earliest references dealing with general integer programming. The paper was published in Econometrica in 1957, but an earlier version appeared as a 1956 RAND research paper [16], where the order of the authors is Manne-Markowitz. Even further, George Dantzig’s 1957 paper [1] cites the Manne-Markowitz report as having been written on August 1, 1955. This is indeed at the beginning of the field: Dantzig, Fulkerson, and Johnson’s classic paper on the TSP is typically cited as the dawn of integer programming and it appeared as a RAND report in April 1954 [2].

Markowitz-Manne, or Manne-Markowitz, discuss in detail two specific applications: a production-planning problem and an air-transport problem. A Left: Harry Markowitz, 2000 (Photograph by Sue Clites). Right: Alan Manne (Stanford University News).

fascinating thing is their inclusion of two appendices, one for each of the models, having subsections labeled “Proof” and “Verification” respectively. The “Proofs” consist of branch-and-bound subproblems and the “Verifications” explain why steps taken in the creation of the subproblems are valid.

The general mixed IP model considered by Markowitz-Manne is to maximize a linear function π over a set D(0) wherein some or all variables take on integral values. For a nonempty set S in the same space as D(0), π(S) is defined to be max(π(X) : X ∈ S) if the maximum exists and otherwise π(S) ≡ ∞. Quoting from their paper, Markowitz-Manne lay out the following branch-and-bound framework.

At each step s we have:

(a) a best guess X(s)

(b) one or more sets D_{1}(s), …, D_{K}(s) such that

D(0) ⊃ D_{k}(s) k = 1, …, K,
π(D(0)) = π(D_{1}(s) ∪ D_{2}(s) ⋯ ∪ D_{K}(s) ∪ X(s))

and

(c) polyhedral sets L_{k}(s), such that

L_{k}(s) ⊃ D_{k}(s) k = 1, …, K

Clearly

π( ∪_{k} L_{k}(s) ∪ X(s)) = max (π(L_{1}(s)), …, π(L_{K}(s)), π(X(s)))

≥ π(D(0)) ≥ π(X(s)).

The general strategy is to reduce the size of the sets ∪D_{k} and ∪L_{k}, and to bring together the lower and upper bounds on π(D(0)).

The “best guess” is the currently best-known solution X(s) ∈ D(0). If X(s) is itself not optimal, then the union of the sets D_{k}(s) is known to contain an optimal solution. The sets L_{k}(s) are LP relaxations of the discrete sets D_{k}(s), thus the upper bound

max (π(L_{1}(s)), …, π(L_{K}(s)), π(X(s)))

on the IP objective can be computed via a sequence of LP problems.

In just a few lines, Markowitz-Manne summed up much of the branch-and-bound theory we use today! Indeed, they incorporate the idea of improving the LP relaxations L_{k}(s) from one step to the next, as is now done in sophisticated branch-and-cut algorithms. Moreover, their steps to create subregions D_{k}(s) involve the concept of branching on hyperplanes, that is, splitting a k − 1 level subregion into a number of k-level subregions by enforcing linear equations c(X) = t_{i} for appropriate values of t_{i}.

The “Proof” subsections consist of explicit listings of the sets D_{k}(s) and L_{k}(s) used at each level in the example models, and the “Verifications” subsections explain why the adopted cutting planes are valid and how hyperplanes are used to subdivide subregions into further subregions. These appendices are amazingly complete formal proofs of the optimality of proposed solutions to the two applied problems. It would be beautiful if we could somehow recapture such formal correctness in current computational claims for optimal solutions to large-scale IP models.

Julia Robinson and the TSP

Markowitz and Manne carried out their work at the famed RAND Corporation, home in the 1950s of what was far and away the world’s top center for the study of mathematical optimization. They introduce their general branch-and-bound framework as follows [17].

Our procedure for handling discrete problems was suggested by that employed in the solution of the ‘traveling-salesman’ problem by Dantzig, Fulkerson, and Johnson.

We have already mentioned that the 1954 TSP work of Dantzig et al. is viewed as the dawn of IP research. Their LP-approach to the TSP actually goes back a bit further, to the 1949 RAND report by Julia Robinson [23] and important follow-up studies in the early 1950s by Isidor Heller [8] and Harold Kuhn [9].

Robinson studied an algorithm for the assignment-problem relaxation of the TSP while Heller and Kuhn began investigations of linear descriptions of the convex hull of TSP tours, considering tours as characteristic vectors of their edge sets. In notes from a George Dantzig Memorial Lecture delivered in 2008 [10], Kuhn writes the following concerning his TSP study.

We were both keenly aware of the fact that, although the complete set of faces (or constraints) in the linear programming formulation of the Traveling Salesman Problem was enormous, if you could find an optimal solution to a relaxed problem with a subset of the faces that is a tour, then you had solved the underlying Traveling Salesman Problem.

It is clear the researchers knew that LP relaxations could be a source of lower bounds for the TSP, but neither Heller nor Kuhn consider the bounding problem as a means to guide a search algorithm such as in branch and bound.

In the case of Robinson’s work, it is tempting to read between the lines and speculate that she must have had some type of enumerative process (like branch and bound) in mind. Why else would she use the title “On the Hamiltonian game (a traveling salesman problem)” for a paper covering a solution method for the assignment problem? It is difficult to guess what she had in mind, but the introduction to the paper suggests she was trying for a direct solution to the TSP rather than an enumerative method through bounding.

An unsuccessful attempt to solve the above problem led to the solution of the following …

The “problem” in the quote is the TSP and the “following” is a description of the assignment problem.

Thus, it appears that early TSP researchers had bounding techniques at their disposal, but were hopeful of direct solution methods rather than considering a branch-and-bound approach.

Bounds and reduced-cost fixing by Dantzig-Fulkerson-Johnson

Dantzig et al. began their study of the TSP in early 1954. Their successful solution of a 49-city instance stands as one of the great achievements of integer programming and combinatorial optimization. But the main body of work did not make use of the LP relaxation as a bounding mechanism. Indeed, the preliminary version [2] of their paper describes their process as follows, where C_{1} denotes the solution set of the LP relaxation, T_{n} denotes the convex hull of all tours through n cities, and d_{ij} is the cost of travel between city i and city j.

What we do is this: Pick a tour x which looks good, and consider it as an extreme point of C_{1}; use the simplex algorithm to move to an adjacent extreme point e in C_{1} which gives a smaller value of the functional; either e is a tour, in which case start again with this new tour, or there exists a hyperplane separating e from the convex of tours; in the latter case cut down C_{1} by one such hyperplane that passes through x, obtaining a new convex C_{2} with x as an extreme point. Starting with x again, repeat the process until a tour x̂ and a convex C_{m} ⊃ T_{n} are obtained over which x̂ gives a minimum of ∑ d_{ij}x_{ij}.

They do not actually solve the LP relaxations in their primal implementation of the cutting-plane method, carrying out only single pivots of the simplex algorithm. Thus they do not have in hand a lower bound until the process has actually found the optimal TSP tour.

In a second part of their paper, however, they work out a method that can take possibly infeasible values for the LP dual variables and create a lower bound B on the cost of an optimal tour. They accomplish this by taking advantage of the fact that the variables in the TSP relaxation are bounded between 0 and 1. The explicit variable bounds correspond to slack and surplus variables in the dual, allowing one to convert any set of dual values into a dual feasible solution by raising appropriately either the slack or surplus for each dual constraint.

Dantzig et al. use this lower bound to eliminate variables from the problem by reduced-cost fixing, that is, when the reduced cost of a variable is greater than the difference between the cost of a best known tour and the value of B then the variable can be eliminated.

During the early stages of the computation, E may be quite large and very few links can be dropped by this rule; however, in the latter stages often so many links are eliminated that one can list all possible tours that use the remaining admissible links.

A general method for carrying out this enumeration of tours is not given, but in [4] an example is used to describe a possible scheme, relying on forbidding subtours. Their description is not a proper branch-and-bound algorithm, however, since the bounding mechanism is not applied recursively to the examined subproblems. Nonetheless, it had a direct influence on Dantzig et al.’s RAND colleagues Markowitz and Manne.

2 Eastman (1958)

It is in the realm of the TSP where we find the first explicit description of a branch-and-bound algorithm, namely Eastman’s 1958 Ph.D. thesis. The algorithm is designed for small instances of the asymmetric TSP, that is, the travel cost between cities i and j depends on the direction of travel, either from i to j or from j to i. The problem can thus be viewed as finding a minimum cost directed circuit that visits each city.

In Eastman’s algorithm, the lower bound on the cost of a TSP tour is provided by the solution to a variant of the assignment problem that provides a minimum cost collection of circuits such that each city is in exactly one of the circuits in the collection. If there is only one circuit in the collection, then the assignment problem solves the TSP. Otherwise, Eastman chooses one of the circuits having, say, m edges, then in a branching step he creates m new subproblems by setting to 0, one at a time, each of the variables corresponding to the edges in the circuit.

Eastman describes and illustrates his process as a search tree, where the nodes of the tree are the subproblems.

Willard Eastman (Photograph courtesy of Willard Eastman)

This process can be illustrated by a tree in which nodes correspond to solutions and branches to excluded links. The initial solution (optimal for the unrestricted assignment problem) forms the base of the tree, node 1. Extending from this node are m branches, corresponding to the m excluded links, and leading to m new nodes. Extending from each of these are more branches, corresponding to links excluded from these solutions, and so forth.

This is very similar to how branch-and-bound search is usually viewed today: we speak of the size of the search tree, the number of active tree nodes, etc.

Eastman clearly has a full branch-and-bound algorithm for the TSP and he illustrates its operation on a ten-city example. He also applies his framework to other combinatorial problems, including a transportation model with nonlinear costs and a machine-scheduling model. His work does not include general integer programming, but it is an important presentation of branch-and-bound techniques.

3 Land and Doig (1960)

General mixed integer programming, where only some of the variables are required to take on integer values, is the domain of Land and Doig. Their branchand-bound paper played a large role in the rapid rise of mixed IP as an applied tool in the 1960s and 70s.

Left: Ailsa Land, Banff, 1977 (Photograph courtesy of Ailsa Land). Right: Alison Doig, The Sun, October 21, 1965. (Courtesy of Alison (Doig) Harcourt)

The methods of Markowitz-Manne and Land-Doig are on opposite sides of the algorithmic spectrum: whereas Markowitz-Manne is best viewed as a flexible proof system, Land-Doig is a detailed algorithm designed for immediate implementation. In a memoir [13] published in 2010, Land and Doig write the following.

We were very well aware that the solution of this type of problem required electronic computation, but unfortunately LSE at that time did not have any access to such a facility. However, we had no doubt that using the same approach to computing could be achieved, if rather painfully, on desk computers, which were plentifully available. We became quite skillful at doing vector operations by multiplying with the left hand, and adding and subtracting with the right on another machine! Storage of bases and intermediate results did not present a limitation since it was all simply recorded on paper and kept in a folder.

The reference to “bases” is indicative of the details given in the paper: the description of the general flow of the algorithm is intertwined with its implementation via the simplex algorithm, where the variables taking on fractional values in a solution are known to lie within the set of basic variables in the final simplex iteration.

The Land-Doig algorithm follows the quick outline for IP branch and bound we mentioned in the introduction to this article: use the LP relaxation as a bounding mechanism and a fractional-valued variable as the means to create subproblems. The algorithm differs, however, in the manner in which it searches the space of solutions. Indeed, Land-Doig considers subproblems created with equality constraints x_{i} = k, rather than inequality constraints, at the expense of possibly building a search tree with nodes having more than two child nodes, that is, corresponding to a range of potential integer values k for the branching variable x_{i}.

Besides the nicely automated method, a striking thing about the paper is the computational tenacity of the authors. Although they worked with hand calculators, Land and Doig explored numerous disciplines for running their algorithm, including a variable selection rule that is similar in spirit to current “strong-branching” techniques.

Land was also involved in very early work on the TSP, writing a paper with George Morton in 1955 [19], but combinatorial problems are not considered in the Land-Doig paper. In an email letter from June 9, 2012, Land confirmed that at the time she had not considered the application of branch and bound to the TSP.

I only got involved in applying B&B to the TSP when Takis Miliotis was doing his PhD under my supervision.

The thesis work of Miliotis [18] was carried out in the 1970s and Land herself authored a computational TSP paper in 1979 [11], but there is no direct connection between Eastman’s work at Harvard and the Land-Doig algorithm for general integer programming.

4 Coining the term branch and bound

The concise and descriptive name “branch and bound” has likely played a role in unifying the many diverse implementations of the algorithmic framework. On this point, however, our three pioneering teams cannot take credit. Markowitz and Manne modestly refer to their process as “a general approach” or “our method”. Eastman called his algorithm “the method of link exclusion” in reference to the fact that his branches are determined by excluding certain edges, that is, by setting the corresponding variables to the value zero. Land and Doig provide the following discussion of their procedure’s name [13].

We did not initially think of the method as ‘branch and bound’, but rather in the ‘geometrical’ interpretation of exploring the convex feasible region defined by the LP constraints. We are not sure if ‘branch and bound’ was already in the literature, but, if so, it had not occurred to us to use that name. We remember Steven Vajda telling us that he had met some French people solving ILPs by ‘Lawndwa’, and realizing that they were applying a French pronunciation to ‘Land-Doig’, so we don’t think they knew it as branch and bound either.

It was John Little, Katta Murty, Dura Sweeney, and Caroline Karel who in 1963 coined the now familiar term. Here are the opening lines from the abstract to their TSP paper [15].

A ‘branch and bound’ algorithm is presented for solving the traveling salesman problem. The set of all tours (feasible solutions) is broken up into increasingly small subsets by a procedure called branching. For each subset a lower bound on the length of the tours therein is calculated. Eventually, a subset is found that contains a single tour whose length is less than or equal to some lower bound for every tour.

In a recent note [20], Murty further pinpointed the naming of the algorithm, giving credit to his coauthor Sweeney.

Later in correspondence John Little told me that one of his students at MIT, D. Sweeney, suggested the name “Branch and Bound” for the method …

So while the origin of the algorithm is complicated, the origin of the name is at least clear!

5 Branch-and-cut algorithms

The Markowitz-Manne framework includes the idea of improving an LP relaxation L_{k}(s) of a subproblem by the addition of linear inequalities satisfied by all solutions in D_{k}(s). This incorporates into branch and bound the technique that was so successful in the Dantzig et al. TSP study. In fact, the Markowitz-Manne paper may contain the first published use of the term “cutting plane” to refer to such valid linear inequalities.

We refer to (3.7) as a cutting line (when N > 2, a cutting plane).

Cutting planes, of course, appear in the starring role in the 1958 integerprogramming algorithm of Ralph Gomory [6], but the idea did not work its way into the Land-Doig computational procedure. Concerning this, Ailsa Land and Susan Powell [14] make the following remark in a 2007 paper.

While branch and bound began to be built into computer codes, the cutting plane approach was obviously more elegant, and we spent a great deal of time experimenting with it. (…) Work was done, but it was not published because as a method to solve problems branch and bound resoundingly won.

The combination of branch-and-bound and cutting planes, as outlined in Markowitz-Manne, eventually became the dominant solution procedure in integer programming and combinatorial optimization. The first big successes were the 1984 study of the linear-ordering problem by Martin Grötschel, Michael Jünger, and Gerhard Reinelt [7] and the late 1980s TSP work by Manfred Padberg and Giovanni Rinaldi [21, 22],

It was Padberg and Rinaldi who coined the term branch and cut for the powerful combination of the two competing algorithms. Land and Powell conclude their 2007 paper with the fitting statement “It is gratifying that the combination, ‘branch and cut’, is now often successful in dealing with real problems.”

References

[1] Dantzig, G. B. 1957. Discrete-variable extremum problems. Operations Research 5, 266–277.

[2] Dantzig, G., R. Fulkerson, S. Johnson. 1954. Solution of a large scale traveling salesman problem. Technical Report P-510. RAND Corporation, Santa Monica, California, USA.

[3] Dantzig, G., R. Fulkerson, S. Johnson. 1954. Solution of a large-scale traveling-salesman problem. Operations Research 2, 393–410.

[4] Dantzig, G. B., D. R. Fulkerson, S. M. Johnson. 1959. On a linearprogramming, combinatorial approach to the traveling-salesman problem. Operations Research 7, 58–66.

[5] Eastman, W. L. 1958. Linear Programming with Pattern Constraints. Ph.D. Thesis. Department of Economics, Harvard University, Cambridge, Massachusetts, USA.

[6] Gomory, R. E. 1958. Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society 64, 275–278.

[7] Grötschel, M., M. Jünger, G. Reinelt. 1984. A cutting plane algorithm for the linear ordering problem. Operations Research 32, 1195–1220.

[8] Heller, I. 1953. On the problem of the shortest path between points. I. Abstract 664t, Bulletin of the American Mathematical Society 59, 551.

[9] Kuhn, H. W. 1955. On certain convex polyhedra. Abstract 799t, Bulletin of the American Mathematical Society 61, 557–558.

[10] Kuhn, H. W. 2008. 57 years of close encounters with George. George Dantzig Memorial Site. INFORMS. Available at http://www2.informs.

org/History/dantzig/articles_kuhn.html.

[11] Land, A. 1979. The solution of some 100-city travelling salesman problems. Technical Report. London School of Economics, London, UK.

[12] Land, A. H., A. G. Doig. 1960. An automatic method of solving discrete programming problems. Econometrica 28, 497–520.

[13] Land, A. H., A. G. Doig. 2010. Introduction to An automatic method of solving discrete programming problems. In: Jünger et al., eds. 50 Years of Integer Programming 1958–2008. Springer, Berlin. 105–106.

[14] Land, A. H., S. Powell. 2007. A survey of the operational use of ILP models. K. Spielberg, M. Guignard-Spielberg, eds. History of Integer Programming: Distinguished Personal Notes and Reminiscences. Annals of Operations Research 149, 147–156.

[15] Little, J. D. C., K. G. Murty, D. W. Sweeney, C. Karel. 1963. An algorithm for the traveling salesman problem. Operations Research 11, 972–989.

[16] Manne, A. S., H. M. Markowitz. 1956. On the solution of discrete programming problems. Technical Report P-711. RAND Corporation, Santa Monica, California, USA.

[17] Markowitz, H. M., A. S. Manne. On the solution of discrete programming problems. Econometrica 25, 84–110.

[18] Miliotis, P. 1978. Using cutting planes to solve the symmetric travelling salesman problem. Mathematical Programming 15, 177–188.

[19] Morton, G., A. H. Land. 1955. A contribution to the ‘travelling-salesman’ problem. Journal of the Royal Statistical Society, Series B, 17, 185–194.

[20] Murty, K. G. 2012. The branch and bound approach: a personal account.

Available at http://www-personal.umich.edu/~murty/B&BHistory.pdf.

[21] Padberg, M., G. Rinaldi. 1987. Optimization of a 532-city symmetric traveling salesman problem by branch and cut. Operations Research Letters 6, 1–7.

[22] Padberg, M., G. Rinaldi. 1991. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review 33, 60–100.

[23] Robinson, J. 1949. On the Hamiltonian game (a traveling salesman problem). Research Memorandum RM-303. RAND Corporation, Santa Monica, California, USA.

William Cook

School of Industrial and Systems Engineering Georgia Institute of Technology USA

                 bico@gatech.edu