Branch and Bound Algorithms - Principles and Examples.

1 Branch and Bound Algorithms - Principles and Clausen March 12, 1999 Contents1 B&B - terminology and general Bounding Strategy for selecting next Branchingrule.. Producinganinitialsolution.. 193 Personal Experiences with GPP and 244 Ideas and Pitfalls for B&B PointsforsequentialB&B .. PointsforparallelB&B.. 26 AbstractA large number of real-world planning problems called combinatorialoptimization problems share the following properties: They are optimiza-tion problems, are easy to state, and have a nite but usually very largenumber of feasible solutions. While some of these as the Shortest Pathproblem and the Minimum Spanning Tree problem have polynomial algo-ritms, the majority of the problems in addition share the property that nopolynomial method for their solution is known. Examples here are vehicle Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen, , crew scheduling, and production planning.

2 All of these and Bound (B&B) is by far the most widely used tool for solv-ing large scaleNP-hard combinatorial optimization problems. B&B is,however, an algorithm paradigm, which has to be lled out for each spe-ci c problem type, and numerous choices for each of the components ex-ist. Even then, Principles for the design of e cient B&B Algorithms haveemerged over the this paper I review the main Principles of B&B and illustrate themethod and the di erent design issues through three examples: the Sym-metric Travelling Salesman Problem, the Graph Partitioning problem, andthe Quadratic Assignment discrete optimization problems to optimality is often an im-mense job requiring very e cient Algorithms , and the B&B paradigm is one ofthe main tools in construction of these. A B&B algorithm searches the completespace of solutions for a given problem for the best solution. However, explicitenumeration is normally impossible due to the exponentially increasing numberof potential solutions.

3 The use of bounds for the function to be optimized com-bined with the value of the current best solution enables the algorithm to searchparts of the solution space only any point during the solution process, the status of the solution withrespect to the search of the solution space is described by a pool of yet unexploredsubset of this and the best solution found so far. Initially only one subset exists,namely the complete solution space, and the best solution found so far subspaces are represented as nodes in a dynamically generated searchtree, which initially only contains the root, and each iteration of a classical B&Balgorithm processes one such node. The iteration has three main components:selection of the node to process, Bound calculation, and branching. In Figure 1,the initial situation and the rst step of the process is sequence of these may vary according to the strategy chosen for selectingthe next node to process.

4 If the selection of next subproblem is based on thebound value of the subproblems, then the rst operation of an iteration afterchoosing the node is branching, subdivision of the solution space of the nodeinto two or more subspaces to be investigated in a subsequent iteration. Foreach of these, it is checked whether the subspace consists of a single solution, inwhich case it is compared to the current best solution keeping the best of the bounding function for the subspace is calculated and comparedto the current best solution. If it can be established that the subspace cannotcontain the optimal solution, the whole subspace is discarded, else it is stored inthe pool of live nodes together with it's Bound . This is in [2] called the eager2SS1S2S3S4S1S2S3S4S24(a)(b)(c)S1S4S 21S22S31S32** = does not contain optimal solutionS1S2S3S4S21S22 S23 Figure 1: Illustration of the search space of B& for node evaluation, since bounds are calculated as soon as nodes areavailable.

5 The alternative is to start by calculating the Bound of the selectednode and then Branch on the node if necessary. The nodes created are thenstored together with the Bound of the processed node. This strategy is calledlazy and is often used when the next node to be processed is chosen to be a livenode of maximal depth in the search search terminates when there is no unexplored parts of the solution spaceleft, and the optimal solution is then the one recorded as "current best".The paper is organized as follows: In Section 2, I go into detail with terminol-ogy and problem description and give the three examples to be used , , and then treat in detail the algorithmic components selec-tion, bounding and branching, and Section briefly comments upon methodsfor generating a good feasible solution prior to the start of the search. I thendescribe personal experiences with solving two problems using parallel B&B inSection and , and Section 4 discusses the impact of design decisions on thee ciency of the complete B&B - terminology and general the following I consider minimization problems - the case of maximizationproblems can be dealt with similarly.

6 The problem is to minimize a functionf(x)ofvariables(x1 xn) over a region offeasible solutions,S:minx2Sf(x)The functionfis called theobjective functionand may be of any type. The setof feasible solutions is usually determined by general conditions on the variables, that these must be non-negative integers or binary, and special constraintsdetermining the structure of the feasible set. In many cases, a set ofpotentialsolutions,P, containingS,forwhichfis still well de ned, naturally comes tomind, and often, a functiong(x) de ned onS(orP) with the property thatg(x) f(x) for allxinS( ) arises naturally. BothPandgare veryuseful in the B&B context. Figure 2 illustrates the situation where S and P areintervals of will use the termssubproblemto denote a problem derived from the orig-inally given problem through addition of new constraints. A subproblem hencecorresponds to a subspace of the original solution space, and the two terms areused interchangeably and in the context of a search tree interchangeably with thetermnode.

7 In order to make the discussions more explicit I use three problemsas examples. The rst one is one of the most famous combinatorial optimizationproblems: the Travelling Salesman problem. The problem arises naturally inconnection with routing of vehicles for delivery and pick-up of goods or persons,4gSPfFigure 2: The relation between the bounding functiongand the objective func-tionfon the setsSandPof feasible and potential solutions of a GBAABC DEFG11242530291501101320H3237172413 0 16303929H1517222520160152318123032301509 2315293739239014211517291823140715172212 152170 Figure 3: The island Bornholm and the distances between interesting sitesbut has numerous other applications. A famous and thorough reference is [11].Example 1: The Symmetric Travelling Salesman Figure 3, a mapover the Danish island Bornholm is given together with a distance table showingthe distances between major cities/tourist attractions.

8 The problem of a bikingtourist, who wants to visit all these major points, is to nd a tour of minimumlength starting and ending in the same city, and visiting each other city exactlyonce. Such a tour is called aHamilton cycle. The problem is called thesymmetricTravelling Salesman problem (TSP) since the table of distances is general a symmetric TSP is given by a symmetricn nmatrixDofnon-negative distances, and the goal is to nd a Hamilton tour of minimumlength. In terms of graphs, we consider a complete undirected graph withnverticesKnand non-negative lengths assigned to the edges, and the goal is todetermine a Hamilton tour of minimum length. The problem may also be statedmathematically by using decision variables to describe which edges are to beincluded in the tour. We introduce 0-1 variablesxij;1 i<j n, and interpretthe value 0 (1 resp.) to mean "not in tour" ("in tour" resp.) The problem is thenminn 1Xi=1nXj=i+1dijxijsuch thati 1Xk=1xki+nXk=i+1xik=2;i2f1; :::; ngXi;j2 Zxij<jZj; Z Vxij2f0;1g;i;j2f1; :::; ng6 ABCDEFGHF igure 4: A potential, but not feasible solution to the biking tourist's problemThe rst set of constraints ensures that for eachiexactly two variables corre-sponding to edges incident withiare chosen.

9 Since each edge has two endpoints,this implies that exactlynvariables are allowed to take the value 1. The sec-ond set of constraints consists of the subtour elimination constraints. Each ofthese states for a speci c subsetSofVthat the number of edges connectingvertices inShas to be less thanjSjthereby ruling out that these form a there are exponentially many of these given constraints determine the set of feasible solutionsS. One obviousway of relaxing this to a set of potential solutions is to relax ( discard) thesubtour elimination constrains. The set of potential solutionsPis then the familyof all sets of subtours such that eachibelongs to exactly one of the subtours ineach set in the family, cf. Figure 4. In Section another possibility is decribed,which in a B&B context turns out to be more subproblem of a given symmetric TSP is constructed by deciding for a sub-setAof the edges ofGthat these must beincludedin the tour to be constructed,while for another subsetBthe edges areexcludedfrom the tour.

10 Exclusion ofan edge (i; j) is usually modeled by settingcijto1, whereas the inclusion of anedge can be handled in various ways as graph contraction. The number offeasible solutions to the problem is (n 1)!=2, which forn= 50 is appr. 3 10622 The following descriptions follow [4, 5].Example 2: The Graph Partitioning Graph Partitioning prob-lem arises in situations, where it is necessary to minimize the number (or weightof) connections between two parts of a network of prescribed size. We consider7 ABCDEFGH10182645371512 Figure 5: A graph partitioning problem and a feasible given weighted, undirected graph G with vertex setVand edge setE,andacost functionc:E!N. The problem is to partitionVinto two disjoint subsetsV1andV2of equal size such that the sum of costs of edges connecting verticesbelonging to di erent subsets is as small as possible. Figure 5 shows an instanceof the problem:The graph partitioning problem can be formulated as a quadratic integerprogramming problem.