Recursion, Backtracking and

Branch-and-Bound
Pham Quang Dung and Do Phan Thuan

Computer Science Department, SoICT,

Hanoi University of Science and Technology.

August 15, 2016

1 / 47
 Recursive procedures

A procedure calls itself

Basic cases: the results are computed trivially

1 int fact ( int n ){

2 if ( n <= 1) return 1;
3 return n * fact (n -1);
4 }
5 int C ( int k , int n ){
6 if ( k == n || k == 0) return 1;
7 return C (k -1 ,n -1) + C (k ,n -1);
8 }

2 / 47
Recursion and Memoization
Procedures with the same parameters may be called several times
A procedure with a given set of parameters is triggered for the first
time is executed, and the results will be stored into memory
Later on, if that procedure with the same set of parameters is
triggered, the procedure will not execute. Rather, the results of that
procedure available in the memory will be returned directly
C(3,5)

C(2,4) C(3,4)

C(1,3) C(2,3) C(2,3) C(3,3)

C(0,2) C(1,2) C(1,2) C(2,2) C(1,2) C(2,2)

C(0,1) C(1,1) C(0,1) C(1,1) C(0,1) C(1,1)

3 / 47
 Recursion and Memoization

1 public class Ckn {

2 private int [][] M ;
3 public int C ( int k , int n ){
4 if ( k == 0 || k == n ) M [ k ][ n ] = 1;
5 else if ( M [ k ][ n ] < 0){
6 M [ k ][ n ] = C (k -1 ,n -1) + C (k ,n -1);
7 }
8 return M [ k ][ n ];
9 }
0 public void test (){
1 M = new int [100][100];
2 for ( int i = 0; i < 100; i ++)
3 for ( int j = 0; j < 100; j ++)
4 M [ i ][ j ] = -1;
5
6 System . out . println ( C (15 ,30));
7 }
8 }

4 / 47
Introduction

List all configurations satisfying some given constraints

I permutations
I subsets of a given set
I etc.
A1 , . . . , An are finite sets and X = {(a1 , . . . , an ) | ai ∈ Ai , ∀1 ≤ i ≤ n}
P is a property on X
Generate all configurations (a1 , . . . , an ) having P

5 / 47
Introduction

In many cases, listing is a final way for solving some combinatorial

problems
Two popular methods
I Generating method (not consider)
I BackTracking algorithm

6 / 47
BackTracking algorithm

Construct elements of the configuration step-by-step

Initialization: Constructed configuration is null: ()
Step 1:
I Compute (base on P) a set S1 of candidates for the first position of
the configuration under construction
I Select an item of S1 and put it in the first position

7 / 47
BackTracking algorithm

At Step k: Suppose we have partial configuration a1 , . . . , ak−1

Compute (base on P) a set Sk of candidates for the k th position of
the configuration under construction
I If Sk 6= ∅, then select an item of Sk and put it in the k th position and
obtain (a1 , . . . , ak−1 , ak )
F If k = n, then process the complete configuration a1 , . . . , an )
F Otherwise, construct the k + 1th element of the partial configuration in
the same schema
0
I If Sk = ∅, then backtrack for trying another item ak−1 for the k − 1th
position
0
F If ak−1 exists, then put it in the k − 1th position
F Otherwise, backtrack for trying another item for the k − 2th position, ...

8 / 47
BackTracking algorithm

Algorithm 1: TRY(k)
Construct a candidate set Sk ;
foreach y ∈ Sk do
ak ← y ;
if (a1 , . . . , ak ) is a complete configuration then
ProcessConfiguration(a1 , . . . , ak );
else
TRY(k + 1);

Algorithm 2: Main()
TRY(1);

9 / 47
BackTracking algorithm - binary sequence

A configuration is represented by b1 , b2 , . . . , bn
Candidates for bi is {0, 1}

10 / 47
 BackTracking algorithm - binary sequence
1 public class ListingBinary {
2 private int [] a ;
3 private int n ;
4 private void TRY ( int i ){
5 for ( int v = 0; v <= 1; v ++){
6 a[i] = v;
7 if ( i == n -1){
8 for ( int j = 0; j < n ; j ++) System . out . print ( a [ j ]);
9 System . out . println ();
0 } else {
1 TRY ( i +1);
2 }
3 }
4 }
5 public void list ( int n ){
6 this . n = n ;
7 a = new int [ n ];
8 TRY (0);
9 }
0 public static void main ( String [] args ) {
1 ListingBinary LB = new ListingBinary ();
2 LB . list (4);
3 }
4
5 } 11 / 47
BackTracking algorithm - combination

A configuration is represented by (c1 , c2 , . . . , ck )

I dummy c0 = 1
I Candidates for ci being aware of hc1 , c2 , . . . , ci−1 i:
ci−1 + 1 ≤ ci ≤ n − k + i, ∀i = 1, 2, . . . , k

12 / 47
BackTracking algorithm - combination

Algorithm 3: TRY(i)
foreach v = ci−1 + 1, . . . , n − k + i do
ci ← v ;
if i == k then
printConfiguration();
else
TRY(i + 1);

Algorithm 4: MainCombinationGeneration(n, k)
c0 ← 0;
TRY(1);

13 / 47
BackTracking algorithm - permutation

A configuration: p1 , p2 , . . . , pk
Candidates for pi being aware of hp1 , p2 , . . . , pi−1 i:
{1, 2, . . . , n} \ {p1 , p2 , . . . , pi−1 }
Use an array of booleans for making values used b1 , b2 , . . . , bn
I bv = 1, if value v is already used (appear in p1 , p2 , . . . , pi−1 )
I bv = 0, otherwise

14 / 47
BackTracking algorithm - permutation
Algorithm 5: TRY(i)
foreach v = 1, . . . , n do
if visited[v ] = FALSE then
pi ← v ;
visited[v ] ← TRUE ;
if i == n then
printConfiguration();
else
TRY(i + 1);
visited[v ] ← FALSE ;

Algorithm 6: MainPermutationGeneration(n, k)
foreach v = 1, . . . , n do
visited[v ] ← FALSE ;
TRY(1);
15 / 47
BackTracking algorithm - Linear integer equation

Solve the linear equations in a set of positive integers

x1 + x2 + · · · + xn = M

where (ai )1≤i≤n and M are positive integers

Partial solution (x1 , x2 , . . . , xk−1 )
m = k−1
P
i=1 xi
A=n−k
M =M −m−A
Candidates of xk is {v ∈ Z | 1 ≤ v ≤ M}

16 / 47
BackTracking algorithm - Linear Integer Equation
Algorithm 7: TRY(i)
if i = n then
M ← M −f;
M ← M −f;
else
M ← M − f − (n − i);
M ← 1;
foreach v = M, . . . , M do
xi ← v ;
f ← f + v;
if i == n then
printConfiguration();
else
TRY(i + 1);
f ← f − v;

Algorithm 8: MainLinearEquation(n, M)
f ← 0;
TRY(1);

17 / 47
BackTracking algorithm - n-queens problem

Problem: Place n queens on a chess board such that no two queens

attack each other
Solution model: (x1 , x2 , . . . , xn ) where xi represents the row on which
the queen in column i is located
Constraints:
I xi 6= xj , ∀1 ≤ i < j ≤ n
I |xi − xj | =6 |i − j|, ∀1 ≤ i < j ≤ n

18 / 47
BackTracking algorithm - n-queens problem
Algorithm 9: Candidate(v , i)
foreach j = 1, . . . , i − 1 do
if xj = v ∨ |xj − v | = |j − i| then
return FALSE;
return TRUE;

Algorithm 10: TRY(i)

foreach v = 1, . . . , n do
if Candidate(v , i) then
xi ← v ;
if i == n then
Solution();
else
TRY(i + 1);

Algorithm 11: MainQueen(n)

TRY(1);

19 / 47
BackTracking algorithm - n-queens problem - refinement

Use arrays for marking forbidden cells

I r [1..n]: r [i] = false if the cells on row i are forbidden
I d1 [1 − n..n − 1]: d1 [q] = false if cells (r , c) s.t. c − r = q are forbiden
F in Java, indices of elements of an array cannot be negative (i.e., indices
are 0, 1, ...). Hence making a deplacement: d1 [q + n − 1] instead of
d1 [q]
I d2 [2..2n − 2]: d2 [q] =false if cells (r , c) s.t. r + c = q are forbiden

20 / 47
BackTracking algorithm - n-queens problem - refinement

Algorithm 12: TRY(i)

foreach v = 1, . . . , n do
if r [v ] ∧ d1 [i − v ] ∧ d2 [i + v ] then
xi ← v ;
r [v ] ← FALSE;
d1 [i − v ] ← FALSE;
d2 [i + v ] ← FALSE;
if i = n then
Solution();
else
TRY(i + 1);
r [v ] ← TRUE;
d1 [i − v ] ← TRUE;
d2 [i + v ] ← TRUE;

21 / 47
BackTracking algorithm - n-queens problem - refinement

Algorithm 13: MainQueenRefine(n)

foreach v = 1, . . . , n do
r [v ] ← TRUE;
foreach v = 1 − n, . . . , n − 1 do
d1 [v ] ← TRUE;
foreach v = 2, . . . , 2n do
d2 [v ] ← TRUE;
TRY(1);

22 / 47
Combinatorial Optimization Problems

z = min {f (x) : x ∈ X }
Applications
I Vehicle Routing
I Scheduling
I Timetabling
I Bin Packing
I Resource allocations
I ...

23 / 47
Generic schema of Branch and Bound

Branch-and-Bound splits the given problem into smaller and smaller

subproblems until they become easy to solve (Branching)
S
I X is splited into subsets X1 . . . , Xk (k ≥ 2) such that i=1,...,k Xi = X
I Recursive application of splitting defines a tree structure: search tree
(each node is a subset of X )
Normally, the size of the search tree is too large (exponential)
Bounding
I For each set Xi (∀i = 1, . . . , k)
F z i = min {f (x) : x ∈ Xi }
F compute z i and z i respectively the lower bound and upper bound of z i :
zi ≤ zi ≤ zi
I If there exist i 6= j s.t. z i ≤ z j , then the set Xj can be removed from
the search space since z j ≥ z i (no need to explore Xj )
I Suppose that z ∗ is incumbent (best solution found so far). If z i ≥ z ∗ ,
then Xi can be removed (no need to explore Xi since z ∗ ≤ z i ≤ z i )

24 / 47
Generic schema of Branch and Bound - example

25 / 47
Generic schema of Branch and Bound algorithms
(minimization problems)
Algorithm 14: TRY(k)
Construct a candidate set Sk ;
foreach y ∈ Sk do
ak ← y ;
if (a1 , . . . , ak ) is a complete configuration then
if f (a1 , . . . , ak ) < z ∗ then
z ∗ ← f (a1 , . . . , ak );
else
if z(a1 , . . . , ak ) < z ∗ then
TRY(k + 1);

Algorithm 15: Main()

z ∗ ← +∞;
TRY(1);
26 / 47
Traveling Salesman Problem
Given a list of n cities with pairwise distances
Find the shortest route that visits each city exactly once and returns
to the origin city
x = (x1 , . . . , xn ), route is x1 → x2 → · · · → xn → x1
f (x) = c(x1 , x2 ) + c(x2 , x3 ) + · · · + c(xn , x1 )
5
4 3
2
4 1
7
1 2
3
 
0 3 7 4
 
 3 0 1 2 
c = 

 7 1 0 5 

4 2 5 0
27 / 47
Traveling Salesman Problem - Simple Branch-and-Bound

A subproblem
I Correspond to a prefix of the solution: x1 , x2 , ..., xk
I Lower bound:
z(x1 , ..., xk ) = c(x1 , x2 ) + ... + c(xk−1 , xk ) + (n − k + 1) ∗ cmin where
cmin is the minimum element of the cost matrix (exclusive elements of
the diagonal)
I Recursive procedure extend(hx1 , ..., xk−1 i) will extend current partial
solution

28 / 47
Traveling Salesman Problem - Simple Branch-and-Bound
Algorithm 16: TRY(k)
Input: k: the index of k th city to be visited
n, c, x, f ∗ , f , visited are global variables
Output: Extend current partial solution x1 , . . . , xk−1 by assigning a value to xk
foreach v = 1, . . . , n do
if visited[v ] = FALSE then
xk ← v ;
visited[v ] ← TRUE ;
f ← f + c(xk−1 , xk );
if k = n then
if f + c(xn , x1 ) < f ∗ then
f ∗ ← f + c(xn , x1 );
else
z ← f + (n − k + 1) ∗ cmin;
if z < f ∗ then
TRY(k + 1);

f ← f − c(xk−1 , xk );
visited[v ] ← FALSE ;

29 / 47
Traveling Salesman Problem - Simple Branch-and-Bound

Algorithm 17: MainSimpleBBTSP(n, c)

Input: n, c: number of cities n and distance matrix c
x, f ∗ , f , visited are initialized as global variables
Output: The length of the shortest tour
foreach v = 1, . . . , n do
visited[v ] ← FALSE ;
f ∗ ← ∞;
f ← 0;
x1 ← 1;
visited[x1 ] ← TRUE ;
TRY(2);
return f ∗ ;

30 / 47
Traveling Salesman Problem - Second Branch-and-Bound

Lower bound
I A Tour is associated with a set S of n cells of the cost matrix in which
each row, column of the cost matrix contain exactly one element of S.
I Hence the optimal Tour does not change if we subtract each cell of a
given row (or column) with a same value.
I Algorithm reduce will compute the lower bound of the optimal tour

31 / 47
Traveling Salesman Problem

Algorithm 18: reduce(C)

1..k is the size of the cost matrix C ;
S ← 0;
foreach i ∈ 1..k do
minRow ← minimum value of row i of C ;
if minRow > 0 then
foreach j ∈ 1..k do
C [i][j] = C [i][j] − minRow ;
S ← S + minRow ;

foreach j ∈ 1..k do
minCol ← minimum value of column j of C ;
if minCol > 0 then
foreach i ∈ 1..k do
C [i][j] = C [i][j] − minCol;
S ← S + minCol;

return S;

32 / 47
Traveling Salesman Problem - Branching

Select an arc (u, v ) for branching (computed by bestEdge below)

I Tours contain (u, v )
F Remove row u and column v
F Set C [v ][u] = ∞
F If u is a terminating node of a path hx1 , x2 , ..., ui and v is a starting
node of a path hv , y1 , ..., yk i, then C [yk ][x1 ] = ∞ to prevent sub-tour
I Tours do not contain (u, v )
F Set C [u][v ] = ∞

33 / 47
Traveling Salesman Problem - Branching

When the reduced matrix has size 2 × 2

a. admit (u, w ) and (v , x) b. admit (u, x) and (v , w )

34 / 47
Traveling Salesman Problem - Branching

Algorithm 19: bestEdge(C)

1..k is the size of the cost matrix C ;
best ← −∞;
foreach i ∈ 1..k do
foreach j ∈ 1..k do
if C [i][j] = 0 then
minRow ← smallest element of row i which is different from C [i][j];
minCol ← smallest element of column j which is different from C [i][j];
total ← minRow + minCol;
if total > best then
best ← total;
selRow ← i;
selCol ← j;

return (selRow , selCol)

35 / 47
Traveling Salesman Problem

a. Original Cost matrix b. Reduced matrix

36 / 47
Traveling Salesman Problem

Set of Tours is divided into 2 cases:

37 / 47
Traveling Salesman Problem

Set of Tours containing (6,3) is divided into 2 cases:

38 / 47
Traveling Salesman Problem

Set of Tours containing (6,3), (4,6) is divided into 2 cases:

39 / 47
Traveling Salesman Problem

Set of Tours containing (6,3), (4,6), (2,1) is divided into 2 cases:

40 / 47
Traveling Salesman Problem

Set of Tours containing (6,3), (4,6), not (2,1) is divided into 2 cases:

41 / 47
Traveling Salesman Problem

Set of Tours containing (6,3), (4,6), (5,1), not (2,1)

is divided into 2 cases:

Finally, the best Tour has cost 104

42 / 47
Branch-and-Bound: MaxClique
Description
I Input: undirected graph G = (V , E ),
I Subgraph: Let G (S) be the graph (S, ES ) in which
ES = {(u, v ) | u, v ∈ S ∧ (u, v ) ∈ E }. G (S) is called subgraph induced
by S (∀S ⊆ V )
I Output: maximal complete subgraph (or clique) of G
Branch-and-Bound
I Partial solution Q: set of nodes, two nodes of Q are adjacent
I Candidate nodes Cand for expansion: each node of Cand is adjacent
with all nodes of Q
I Upper Bound
F ∆ is the number of colors used to color nodes of Cand such that two
adjacent nodes u, v ∈ Cand must be colored by different colors.
F The size of every complete subgraph of G (Cand) is less than or equal
to ∆
F |Q| + ∆ is the upper bound of the size of cliques expanded from Q
F If |Q| + ∆ ≤ |Qmax|, then do not expand Q

43 / 47
Branch-and-Bound: MaxClique

Algorithm 20: MaxClique(G = (V , E ))

Input: Graph G = (V , E )
Output: Maximal complete subgraph of G
Qmax ← {};
Q ← {};
Cand ← list of nodes of V ;
∆ ← Sort(Cand);
Expand(Cand);
return Qmax;

44 / 47
Branch-and-Bound: MaxClique

Algorithm 21: Expand(Cand)

Input: Sorted List of candidates Cand, G = (V , E ) and Q, Qmax are global variables
Output: Expanding the partial solution Q
foreach i = 0, . . . , lenght(Cand) − 1 do
u ← Cand[i];
Q ← Q ∪ {u};
if |Q| > |Qmax| then
Qmax ← Q;
Cand 0 ← {v ∈ Cand | v 6= u ∧ (u, v ) ∈ E };
∆ ← Sort(Cand 0 );
if |Q| + ∆ > |Qmax| then
Expand(Cand 0 );
Q ← Q \ {u};

45 / 47
Branch-and-Bound: MaxClique
Algorithm 22: Sort(Cand)
Input: Sort the List of candidates Cand
Output: Updated Cand and return the number classes
maxNo ← 0;
C1 ← {};
foreach u ∈ Cand do
k ← 1;
while ∃v ∈ Ck | (u, v ) ∈ E do
k ← k + 1;
if k > maxNo then
maxNo ← k;
Ck ← {};
Ck ← Ck ∪ {u}
L ← [];
foreach k = 1, . . . , maxNo do
foreach v ∈ Ck do
L ← L :: v ;

foreach i = 0, . . . , length(L) − 1 do
Cand[i] ← L[length(L) − i − 1];
return maxNo;

46 / 47
Exercises

Nurses Scheduling
Balanced Courses Assignment
Packing 2D rectangle items into the container
MaxClique
Networks analysis (count number of k-paths on a graph, a tree)

47 / 47