Branch & Bound Algorithm

Branching realization

In a branch & bound algorithm a given subproblem, which cannot be bounded, has to be divided into at least two new restricted subproblems. We do this restriction by determining if two vertices v, w $\in$ V stay in the same partition or are separated into different partitions. We call these two possibilities ``join'' or ``split''. A join is performed by creating a new graph from the original graph: the two vertices v, w $\in$ V, which have to stay in the same partition, are joined into one vertex $\tilde{v}$ with g($\tilde{v}$) = g(v) + g(w). The new edge weights are generated accordingly: $\forall$u $\in$ V $\setminus$ {v, w} : f ({u,$\tilde{v}$}) = f ({u, v}) + f ({u, w}). It is obvious that this new graph has the same CutSize as the original graph with the restriction that v and w have to be in the same partition.

A split of two vertices v, w $\in$ V is performed by removing the commodity with source v and destination w from the general computation of the CutFlow. Instead, this particular flow can be counted into the CutFlow completely. Let S $\subset$ V×V be the set of pairs of vertices which are split. Then we get the following formula for the CutFlow of the MVarMC instance:

$$\geq \sum_{\{v,w\}\in S}^{}$$ CutFlow

$$\sum_{v\in V}^{} \left(\vphantom{ \sum _{w\in V,\{v,w\}\notin S}s(v,w)\cdot g(w)-\bar{s}_{v}(M-g(v))}\right. \sum_{w\in V,\{v,w\}\notin S}^{} \bar{s}_{v}^{} \left.\vphantom{ \sum _{w\in V,\{v,w\}\notin S}s(v,w)\cdot g(w)-\bar{s}_{v}(M-g(v))}\right) \tilde{s}$$

with $\bar{s}_{v}^{}$ : = max_{w $\in$ V,{v, w}$\notin$S}s(v, w), $\tilde{s}$ : = min_{v $\in$ V}${\frac{\bar{s}_{v}}{g(v)}}$, and R : = N - M ^. $\lfloor$${\frac{N}{M}}$$\rfloor$. So in fact in case of the MVarMC instance the split means only a reinterpretation of $\bar{s}_{v}^{}$, while in case of the VarMC and 1-1-MC instance an additional variable s(v, w) is included into the linear program.

Branching Strategy

A crucial point for a good branch & bound algorithm is the branching strategy: In our application this means the decision, which pair of vertices should be used for the join and split in a given situation. We have tried two different strategies. Firstly, we have used the two vertices that are adjacent to that edge, which corresponds to the constraint of the linear program with the maximal dual value. This idea follows the principle that the constraints with maximal dual value are the ones which restrict the solution mostly. Especially by joining this two vertices, the specific edge disappears from the graph and the bound can increase.

The other strategy follows a simple upper bound for the CutFlow of the 1-1-MC instance. We select these two vertices for the branching which increase the simple upper bound mostly.

Theorem 3  
Given a Graph Partitioning problem with graph G, weights g and f, and constants M and p. We use D(v, w) as the length of the shortest path between vertices v and w regarding the edge weights ${\frac{1}{f(e)}}$. Then the maximal lower bound of the 1-1-MC instance is

$${\frac{N(N-M)+R(M-R)}{\frac{2}{\vert E\vert}\sum _{\{v,w\}\in V^{2}}g(v)\cdot g(w)\cdot D(v,w)}}$$.

For our branching strategy we are looking for a pair of vertices which minimizes the term ${\frac{2}{\vert E\vert}}$$\sum_{\{v,w\}\in V^{2}}^{}$g(v) ^. g(w) ^. D(v, w) in the case of a join of the two vertices. Following this strategy the new subproblem created by the join should have a good lower bound. But we have not minded on the split subproblem. Neverthelss, experiments have shown that in the case of p = 2 this branching strategy yields small search tree. In the case of p $\geq$ 3 it is better to restrict the set of candidates to those pairs of vertices which are adjacent. Altogether experiments have shown that the branching strategy based on Theorem 3 yields smaller search trees compared to the strategy basing on the dual values.

Forcing Moves

Following the subproblems in the search tree, there are some situations where pairs of vertices can be forced to be split or joined. Firstly, if $\exists$v $\in$ V : g(v) = M this vertex v can be split from all other vertices, since a vertex with weight M corresponds to a partition with maximal size. Secondly, if $\exists$v, w $\in$ V,{v, w}$\notin$S : N + g(v) - g(w) - $\sum_{u\in V,\{v,u\}\in S}^{}$g(u) < N - (p - 1)M then we can join the vertices v and w, since otherwise vertex v has no possibility to become part of a correct partition. Thirdly, looking at the graph G_S : = (V, S): if this graph has two clique subgraphs with p vertices which match in exactly p - 1 vertices, then the two remaining vertices can be joined. The last possibility for forcing a join bases on a given solution of a Multicommodity Flow instance:

Lemma 2  
Given a Graph Partitioning problem with graph G and edge weights f and a Multicommodity Flow problem with this graph, congestions c : E $\rightarrow$ I   R, maximal congestion C and CutFlow CF. An improving solution for the Graph Partitioning problem with CutSize at most L is searched. Then the vertices v, w with {v, w} = e $\in$ E can be joined if

$${\frac{CF+(C-c(e))\cdot f(e)}{C}}$$ > L.

This possibility for forcing a join is extremely helpfully if the bounds are close to a given feasible solution and the graph is somehow irregular such that there are edges which are not loaded with the maximal congestion.

Experiments

As there are a lot of good heuristics for the Graph Partitioning problem, it is easy to get a good feasible solution at the beginning of the branch & bound procedure. We use the Party library [15] for this purpose. As in most cases the solution from the heuristic is optimal, we do not matter about any best first search but use simple depth first search. The PCx code is used for the solution of the linear programs. We have adapted the code such that the interior point method stops if the primary solution is good enough to bound the actual subproblem or if the dual solution shows that we cannot bound the actual subproblem.

In Table 2 a comparison of our branch & bound algorithm with the results from Karisch et al. [10], for our knowledge the best actual code, are presented. The results in [10] are performed on a HP 9000/735 system. The ``#B'' column gives the number of search nodes in the branch&bound tree, the time is given in hh:mm:ss. The missing values for some graphs of the 1-1-MC and VarMC instances result from runs we have stoped after a time overflow. For the problems with the DeBruijn graphs we have utilized two specific properties: Firstly, every bisection of the DeBruijn graph has an even CutSize; Karisch has used this for the DB7, also. Secondly, symmetrical parts of the search tree, which result from four automorphisms of the DeBruijn graph, are cut of; this decreases the search tree of the DB8 by a factor of about two. Finally, we want to remark that our approach has solved the bisection problem of the DeBruijn graph with dimension 8 for the first time at all.

Table 2: Results of the branch & bound algorithms

Graph	1-1-MC		VarMC		MVarMC		Karisch
	Time	#B	Time	#B	Time	#B	Time	#B
m4	-	-	-	-	1	1	1	1
ma	-	-	-	-	2	1	3	1
me	1	1	2	1	2	1	4	1
m6	7	11	5	1	10	1	37	1
mb	3	1	6	1	8	1	28	1
mc	2:41	56	7	1	10	1	46	1
md	3	1	8	1	9	1	29	1
mf	5	1	13	1	13	1	24	1
m1	-	-	-	-	21	1	18:15	15
m8	27	1	15	1	29	1	5:21	1
cb30	3	23	3	21	0	1	2	1
cb45	37	77	46	76	4	1	7	1
cb47_99	1:49	238	2:34	237	10	7	10	1
cb47_101	22	53	22	40	7	3	1:52	35
cb61	2:19	78	3:38	72	42	6	20	1
DB5	0	1	0	1	0	1	6	3
DB6	11	5	5	1	7	1	7:49	55
DB7	28:10	44	25	1	1:12	1	8:53:20	195
DB8
ex36a			22:19	197	41:04	197	3	1
ex36d			45:44	101	40:30	101	11	3

Conclusions from the experiments

• The MVarMC instance is definitely the best one for the branch & bound algorithm from the three Multicommodity Flow instances.
• Concerning the tested real world applications our approach delivers equally results compared with the results from Karisch. For the DeBruijn graphs our approach is in orders of magnitude better than Karischs approach. This is the other way around for the randomly generated dense ``ex'' problems.

So we conclude that our approach is quite good for more ``sparse'' and ``regular'' graphs while it is less good for ``dense'' graphs. In most applications of the Graph Partitioning problem, e.g. circuit layout or load balancing, the graphs are relatively ``sparse'' and ``regular'', in fact. So our approach is well suited for these applications.