Branch and bound

What is Branch and bound?

Branch and bound is one of the techniques used for problem solving. It is similar to the
backtracking since it also uses the state space tree. It is used for solving the optimization
problems and minimization problems. If we have given a maximization problem then we
can convert it using the Branch and bound technique by simply converting the problem
into a maximization problem.

Let's understand through an example.

Jobs = {j1, j2, j3, j4}

41.9M
925
Features of Java - Javatpoint

P = {10, 5, 8, 3}

d = {1, 2, 1, 2}

The above are jobs, problems and problems given. We can write the solutions in two
ways which are given below:

Suppose we want to perform the jobs j1 and j2 then the solution can be represented in
two ways:

The first way of representing the solutions is the subsets of jobs.

S1 = {j1, j4}

The second way of representing the solution is that first job is done, second and third
jobs are not done, and fourth job is done.

S2 = {1, 0, 0, 1}

The solution s1 is the variable-size solution while the solution s2 is the fixed-size
solution.

First, we will see the subset method where we will see the variable size.
First method:

In this case, we first consider the first job, then second job, then third job and finally we
consider the last job.

As we can observe in the above figure that the breadth first search is performed but not
the depth first search. Here we move breadth wise for exploring the solutions. In
backtracking, we go depth-wise whereas in branch and bound, we go breadth wise.

Now one level is completed. Once I take first job, then we can consider either j2, j3 or j4.
If we follow the route then it says that we are doing jobs j1 and j4 so we will not
consider jobs j2 and j3.
Now we will consider the node 3. In this case, we are doing job j2 so we can consider
either job j3 or j4. Here, we have discarded the job j1.

Now we will expand the node 4. Since here we are doing job j3 so we will consider only
job j4.

Now we will expand node 6, and here we will consider the jobs j3 and j4.
Now we will expand node 7 and here we will consider job j4.
Now we will expand node 9, and here we will consider job j4.

The last node, i.e., node 12 which is left to be expanded. Here, we consider job j4.

The above is the state space tree for the solution s1 = {j1, j4}

Second method:

We will see another way to solve the problem to achieve the solution s1.

First, we consider the node 1 shown as below:

Now, we will expand the node 1. After expansion, the state space tree would be
appeared as:

On each expansion, the node will be pushed into the stack shown as below:
Now the expansion would be based on the node that appears on the top of the stack.
Since the node 5 appears on the top of the stack, so we will expand the node 5. We will
pop out the node 5 from the stack. Since the node 5 is in the last job, i.e., j4 so there is
no further scope of expansion.
The next node that appears on the top of the stack is node 4. Pop out the node 4 and
expand. On expansion, job j4 will be considered and node 6 will be added into the stack
shown as below:

The next node is 6 which is to be expanded. Pop out the node 6 and expand. Since the
node 6 is in the last job, i.e., j4 so there is no further scope of expansion.
The next node to be expanded is node 3. Since the node 3 works on the job j2 so node
3 will be expanded to two nodes, i.e., 7 and 8 working on jobs 3 and 4 respectively. The
nodes 7 and 8 will be pushed into the stack shown as below:
The next node that appears on the top of the stack is node 8. Pop out the node 8 and
expand. Since the node 8 works on the job j4 so there is no further scope for the
expansion.

The next node that appears on the top of the stack is node 7. Pop out the node 7 and
expand. Since the node 7 works on the job j3 so node 7 will be further expanded to
node 9 that works on the job j4 as shown as below and the node 9 will be pushed into
the stack.
The next node that appears on the top of the stack is node 9. Since the node 9 works on
the job 4 so there is no further scope for the expansion.
The next node that appears on the top of the stack is node 2. Since the node 2 works on
the job j1 so it means that the node 2 can be further expanded. It can be expanded upto
three nodes named as 10, 11, 12 working on jobs j2, j3, and j4 respectively. There newly
nodes will be pushed into the stack shown as below:

In the above method, we explored all the nodes using the stack that follows the LIFO
principle.

Third method

There is one more method that can be used to find the solution and that method is
Least cost branch and bound. In this technique, nodes are explored based on the cost of
the node. The cost of the node can be defined using the problem and with the help of
the given problem, we can define the cost function. Once the cost function is defined,
we can define the cost of the node.

Let's first consider the node 1 having cost infinity shown as below:

Now we will expand the node 1. The node 1 will be expanded into four nodes named as
2, 3, 4 and 5 shown as below:
Let's assume that cost of the nodes 2, 3, 4, and 5 are 25, 12, 19 and 30 respectively.

Since it is the least cost branch n bound, so we will explore the node which is having the
least cost. In the above figure, we can observe that the node with a minimum cost is
node 3. So, we will explore the node 3 having cost 12.

Since the node 3 works on the job j2 so it will be expanded into two nodes named as 6
and 7 shown as below:
The node 6 works on job j3 while the node 7 works on job j4. The cost of the node 6 is 8
and the cost of the node 7 is 7. Now we have to select the node which is having the
minimum cost. The node 7 has the minimum cost so we will explore the node 7. Since
the node 7 already works on the job j4 so there is no further scope for the expansion.