Open In App

Introduction to Branch and Bound – Data Structures and Algorithms Tutorial

Last Updated : 08 May, 2023
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow

Branch and bound algorithms are used to find the optimal solution for combinatory, discrete, and general mathematical optimization problems.

A branch and bound algorithm provide an optimal solution to an NP-Hard problem by exploring the entire search space. Through the exploration of the entire search space, a branch and bound algorithm identify possible candidates for solutions step-by-step.

There are many optimization problems in computer science, many of which have a finite number of the feasible shortest path in a graph or minimum spanning tree that can be solved in polynomial time. Typically, these problems require a worst-case scenario of all possible permutations. The branch and bound algorithm create branches and bounds for the best solution.

In this tutorial, we’ll discuss the branch and bound method in detail.

Different search techniques in branch and bound:

The Branch  algorithms incorporate different search techniques to traverse a state space tree. Different search techniques used in B&B are listed below:

  1. LC search
  2. BFS
  3. DFS

1. LC search (Least Cost Search):

It uses a heuristic cost function to compute the bound values at each node. Nodes are added to the list of live nodes as soon as they get generated.
The node with the least value of a cost function selected as a next E-node.

2.BFS(Breadth First Search):
It is also known as a FIFO search.
It maintains the list of live nodes in first-in-first-out order i.e, in a queue, The live nodes are searched in the FIFO order to make them next E-nodes.

3. DFS (Depth First Search):
It is also known as a LIFO search.
It maintains the list of live nodes in last-in-first-out order i.e. in a stack.

The live nodes are searched in the LIFO order to make them next E-nodes.

Introduction to Branch and Bound

Introduction to Branch and Bound

When to apply Branch and Bound Algorithm?

Branch and bound is an effective solution to some problems, which we have already discussed. We’ll discuss all such cases where branching and binding are appropriate in this section.

  • It is appropriate to use a branch and bound approach if the given problem is discrete optimization. Discrete optimization refers to problems in which the variables belong to the discrete set. Examples of such problems include 0-1 Integer Programming and Network Flow problems.
  • When it comes to combinatory optimization problems, branch and bound work well. An optimization problem is optimized by combinatory optimization by finding its maximum or minimum based on its objective function. The combinatory optimization problems include Boolean Satisfiability and Integer Linear Programming.

Basic Concepts of Branch and Bound:

â–¸ Generation of a state space tree:

As in the case of backtracking, B&B generates a state space tree to efficiently search the solution space of a given problem instance.

In B&B, all children of an E-node in a state space tree are produced before any live node gets converted in an E-node. Thus, the E-node remains an E-node until i becomes a dead node.

  • Evaluation of a candidate solution:

Unlike backtracking, B&B needs additional factors evaluate a candidate solution:

  1. A way to assign a bound on the best values of the given criterion functions to each node in a state space tree: It is produced by the addition of further components to the partial solution given by that node.
  2. The best values of a given criterion function obtained so far: It describes the upper bound for the maximization problem and the lower bound for the minimization problem.
  • A feasible solution is defined by the problem states that satisfy all the given constraints.
  • An optimal solution is a feasible solution, which produces the best value of a given objective function.
  • Bounding function :

It optimizes the search for a solution vector in the solution space of a given problem instance.

It is a heuristic function that evaluates the lower and upper bounds on the possible solutions at each node. The bound values are used to search the partial solutions leading to an optimal solution. If a node does not produce a solution better than the best solution obtained thus far, then it is abandoned without further exploration.

The algorithm then branches to another path to get a better solution. The desired solution to the problem is the value of the best solution produced so far.

â–¸ The reasons to dismiss a search path at the current node :

(i) The bound value of the node is lower than the upper bound in the case of the maximization problem and higher than the lower bound in the case of the minimization problem. (i.e. the bound value of the ade is not better than the value of the best solution obtained until that node).

(ii) The node represents infeasible solutions, de violation of the constraints of the problem.

(iii) The node represents a subset of a feasible solution containing a single point. In this case, if the latest solution is better than the best solution obtained so far the best solution is modified to the value of a feasible solution at that node.

Types of Branch and Bound Solutions:

The solution of the Branch and the bound problem can be represented in two ways:

  • Variable size solution: Using this solution, we can find the subset of the given set that gives the optimized solution to the given problem. For example, if we have to select a combination of elements from {A, B, C, D} that optimizes the given problem, and it is found that A and B together give the best solution, then the solution will be {A, B}.
  • Fixed-size solution: There are 0s and 1s in this solution, with the digit at the ith position indicating whether the ith element should be included, for the above example, the solution will be given by {1, 1, 0, 0}, here 1 represent that we have select the element which at ith position and 0 represent we don’t select the element at ith position.

Classification of Branch and Bound Problems:

The Branch and Bound method can be classified into three types based on the order in which the state space tree is searched. 

  1. FIFO Branch and Bound
  2. LIFO Branch and Bound
  3. Least Cost-Branch and Bound

We will now discuss each of these methods in more detail. To denote the solutions in these methods, we will use the variable solution method.

1. FIFO Branch and Bound

First-In-First-Out is an approach to the branch and bound problem that uses the queue approach to create a state-space tree. In this case, the breadth-first search is performed, that is, the elements at a certain level are all searched, and then the elements at the next level are searched, starting with the first child of the first node at the previous level.

For a given set {A, B, C, D}, the state space tree will be constructed as follows :

State Space tree for set {A, B, C, D}

State Space tree for set {A, B, C, D}

The above diagram shows that we first consider element A, then element B, then element C and finally we’ll consider the last element which is D. We are performing BFS while exploring the nodes.

So, once the first level is completed. We’ll consider the first element, then we can consider either B, C, or D. If we follow the route then it says that we are doing elements A and D so we will not consider elements B and C. If we select the elements A and D only, then it says that we are selecting elements A and D and we are not considering elements B and C.

Selecting element A

Selecting element A

Now, we will expand node 3, as we have considered element B and not considered element A, so, we have two options to explore that is elements C and D. Let’s create nodes 9 and 10 for elements C and D respectively.

Considered element B and not considered element A

Considered element B and not considered element A

Now, we will expand node 4 as we have only considered elements C and not considered elements A and B, so, we have only one option to explore which is element  D. Let’s create node 11 for D.

 Considered elements C and not considered elements A and B

 Considered elements C and not considered elements A and B

Till node 5, we have only considered elements D, and not selected elements A, B, and C. So, We have no more elements to explore, Therefore on node 5, there won’t be any expansion.

Now, we will expand node 6 as we have considered elements A and B, so, we have only two option to explore that is element C and D. Let’s create node 12 and 13 for C and D respectively.

Expand node 6

Expand node 6

Now, we will expand node 7 as we have considered elements A and C and not consider element B, so, we have only one option to explore which is element  D. Let’s create node 14 for D.

Expand node 7

Expand node 7

Till node 8, we have considered elements A and D, and not selected elements B and C, So, We have no more elements to explore, Therefore on node 8, there won’t be any expansion.

Now, we will expand node 9 as we have considered elements B and C and not considered element A, so, we have only one option to explore which is element  D. Let’s create node 15 for D.

Expand node 9

Expand node 9

2. LIFO Branch and Bound

The Last-In-First-Out approach for this problem uses stack in creating the state space tree. When nodes are added to a state space tree, they are added to a stack. After all nodes of a level have been added, we pop the topmost element from the stack and explore it.

For a given set {A, B, C, D}, the state space tree will be constructed as follows :

State space tree for element {A, B, C, D}

Now the expansion would be based on the node that appears on the top of the stack. Since node 5 appears on the top of the stack, so we will expand node 5. We will pop out node 5 from the stack. Since node 5 is in the last element, i.e., D so there is no further scope for expansion.

The next node that appears on the top of the stack is node 4. Pop-out node 4 and expand. On expansion, element D will be considered and node 6 will be added to the stack shown below:

Expand node 4

Expand node 4

The next node is 6 which is to be expanded. Pop-out node 6 and expand. Since node 6 is in the last element, i.e., D so there is no further scope for expansion.

The next node to be expanded is node 3. Since node 3 works on element B so node 3 will be expanded to two nodes, i.e., 7 and 8 working on elements C and D respectively. Nodes 7 and 8 will be pushed into the stack.

The next node that appears on the top of the stack is node 8. Pop-out node 8 and expand. Since node 8 works on element D so there is no further scope for the expansion.

Expand node 3

The next node that appears on the top of the stack is node 7. Pop-out node 7 and expand. Since node 7 works on element C so node 7 will be further expanded to node 9 which works on element D and node 9 will be pushed into the stack.

The next node is 6 which is to be expanded. Pop-out node 6 and expand. Since node 6 is in the last element, i.e., D so there is no further scope for expansion.

Expand node 7

Expand node 7

The next node that appears on the top of the stack is node 9. Since node 9 works on element D, there is no further scope for expansion.

The next node that appears on the top of the stack is node 2. Since node 2 works on the element A so it means that node 2 can be further expanded. It can be expanded up to three nodes named 10, 11, 12 working on elements B, C, and D respectively. There new nodes will be pushed into the stack shown as below:

Expand node 2

Expand node 2

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

3. Least Cost-Branch and Bound

To explore the state space tree, this method uses the cost function. The previous two methods also calculate the cost function at each node but the cost is not been used for further exploration.

In this technique, nodes are explored based on their costs, 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.
Now, Consider a node whose cost has been determined. If this value is greater than U0, this node or its children will not be able to give a solution. As a result, we can kill this node and not explore its further branches. As a result, this method prevents us from exploring cases that are not worth it, which makes it more efficient for us. 

Let’s first consider node 1 having cost infinity shown below:

In the following diagram, node 1 is expanded into four nodes named 2, 3, 4, and 5.

Node 1 is expanded into four nodes named 2, 3, 4, and 5

Node 1 is expanded into four nodes named 2, 3, 4, and 5

Assume that cost of the nodes 2, 3, 4, and 5 are 12, 16, 10, and 315 respectively.
In this method, 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 4. So, we will explore node 4 having a cost of 10.

During exploring node 4 which is element C, we can notice that there is only one possible element that remains unexplored which is D (i.e, we already decided not to select elements A, and B). So, it will get expanded to one single element D, let’s say this node number is 6.

Exploring node 4 which is element C

Exploring node 4 which is element C

Now, Node 6 has no element left to explore. So, there is no further scope for expansion. Hence the element {C, D} is the optimal way to choose for the least cost.

Problems that can be solved using Branch and Bound Algorithm:

The Branch and Bound method can be used for solving most combinatorial problems. Some of these problems are given below:

Question

Practice
Introduction with 0/1 Knapsack Link
8 puzzle Problem Link
Job Assignment Problem Link
N Queen Problem Link
Traveling Salesman Problem Link

Advantages of Branch and Bound Algorithm:

  • We don’t explore all the nodes in a branch and bound algorithm. Due to this, the branch and the bound algorithm have a lower time complexity than other algorithms.
  • Whenever the problem is small and the branching can be completed in a reasonable amount of time, the algorithm finds an optimal solution.
  • By using the branch and bound algorithm, the optimal solution is reached in a minimal amount of time. When exploring a tree, it does not repeat nodes.

Disadvantages of Branch and Bound Algorithm:

  • It takes a long time to run the branch and bound algorithm. 
  • In the worst-case scenario, the number of nodes in the tree may be too large based on the size of the problem.

Conclusion

The branch and bound algorithms are one of the most popular algorithms used in optimization problems that we have discussed in our tutorial. We have also explained when a branch and bound algorithm is appropriate for a user to use. In addition, we presented an algorithm based on branches and bounds for assigning jobs. Lastly, we discussed some advantages and disadvantages of branch and bound algorithms.



Previous Article
Next Article

Similar Reads

Applications, Advantages and Disadvantages of Branch and Bound Algorithm
Branch and bound algorithm is a method used in computer science to find the best solution to optimization problems. It systematically explores all potential solutions by breaking the problem down into smaller parts and then uses limits or rules to prevent certain parts from being considered. Applications of Branch and Bound:Combinatorial Optimizati
2 min read
Generate Binary Strings of length N using Branch and Bound
The task is to generate a binary string of length N using branch and bound technique Examples: Input: N = 3 Output: 000 001 010 011 100 101 110 111 Explanation: Numbers with 3 binary digits are 0, 1, 2, 3, 4, 5, 6, 7 Input: N = 2 Output: 00 01 10 11 Approach: Generate Combinations using Branch and Bound : It starts with an empty solution vector.Whi
6 min read
Difference between Backtracking and Branch-N-Bound technique
Algorithms are the methodical sequence of steps which are defined to solve complex problems. In this article, we will see the difference between two such algorithms which are backtracking and branch and bound technique. Before getting into the differences, lets first understand each of these algorithms. Backtracking: Backtracking is a general algor
4 min read
Branch and Bound meaning in DSA
Branch and bound is an algorithmic technique used in computer science to solve optimization problems. Branch and bound is a systematic way of exploring all possible solutions to a problem by dividing the problem space into smaller sub-problems and then applying bounds or constraints to eliminate certain subproblems from consideration. Characteristi
3 min read
Implementation of 0/1 Knapsack using Branch and Bound
Given two arrays v[] and w[] that represent values and weights associated with n items respectively. Find out the maximum value subset(Maximum Profit) of v[] such that the sum of the weights of this subset is smaller than or equal to Knapsack capacity Cap(W). Note: The constraint here is we can either put an item completely into the bag or cannot p
15+ min read
Traveling Salesman Problem using Branch And Bound
Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible tour that visits every city exactly once and returns to the starting point. For example, consider the graph shown in figure on right side. A TSP tour in the graph is 0-1-3-2-0. The cost of the tour is 10+25+30+15 which is 80.We have discuss
15+ min read
0/1 Knapsack using Least Cost Branch and Bound
Given N items with weights W[0..n-1], values V[0..n-1] and a knapsack with capacity C, select the items such that:   The sum of weights taken into the knapsack is less than or equal to C.The sum of values of the items in the knapsack is maximum among all the possible combinations.Examples:   Input: N = 4, C = 15, V[]= {10, 10, 12, 18}, W[]= {2, 4,
15+ min read
Branch and Bound Algorithm
The Branch and Bound Algorithm is a method used in combinatorial optimization problems to systematically search for the best solution. It works by dividing the problem into smaller subproblems, or branches, and then eliminating certain branches based on bounds on the optimal solution. This process continues until the best solution is found or all b
1 min read
N Queen Problem using Branch And Bound
The N queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The backtracking Algorithm for N-Queen is already discussed here. In a backtracking solution, we backtrack when we hit a dead end. In Branc
15+ min read
Why do we use branch and bound algorithm?
The Branch and Bound algorithm is used to solve optimization problems where the goal is to find the best solution out of all possible solutions. It is efficient as it eliminates the need to check all solutions by ruling out those that cannot possibly lead to the best solution. What is Branch and Bound Algorithm?The Branch and Bound algorithm is a m
3 min read
Job Assignment Problem using Branch And Bound
Let there be N workers and N jobs. Any worker can be assigned to perform any job, incurring some cost that may vary depending on the work-job assignment. It is required to perform all jobs by assigning exactly one worker to each job and exactly one job to each agent in such a way that the total cost of the assignment is minimized. Let us explore al
15+ min read
Which strategy can be used to solve branch and bound problem?
Branch and Bound problem can be solved using different strategies such as Least Cost (LC) Search, Breadth-First Search (BFS) and Depth-First Search (DFS). These strategies help traverse the state space tree effectively, ensuring optimal solutions. Branch and bound is a problem-solving technique used in optimization problems to find the best possibl
2 min read
0/1 Knapsack using Branch and Bound
Given two arrays v[] and w[] that represent values and weights associated with n items respectively. Find out the maximum value subset(Maximum Profit) of v[] such that the sum of the weights of this subset is smaller than or equal to Knapsack capacity W. Note: The constraint here is we can either put an item completely into the bag or cannot put it
15+ min read
Introduction to Rolling Hash - Data Structures and Algorithms
A rolling hash is a hash function that is used to efficiently compute a hash value for a sliding window of data. It is commonly used in computer science and computational biology, where it can be used to detect approximate string matches, find repeated substrings, and perform other operations on sequences of data. The idea behind a rolling hash is
15+ min read
Does a Data Scientist/Machine Learning Engineer require in depth knowledge of Data Structures and Algorithms?
In today's world, data scientists and machine learning engineers play a crucial role in analyzing data and building intelligent systems. As technology continues to advance, the demand for these experts is growing rapidly. Real-world data problems are complex, requiring strong skills in handling data and creating efficient algorithms. In this articl
10 min read
Lower bound for comparison based sorting algorithms
The problem of sorting can be viewed as following. Input: A sequence of n numbers <a1, a2, . . . , an>. Output: A permutation (reordering) <a'1, a'2, . . . , a'n> of the input sequence such that a'1 <= a'2 ..... <= a'n. A sorting algorithm is comparison based if it uses comparison operators to find the order between two numbers. C
7 min read
Need of Data Structures and Algorithms for Deep Learning and Machine Learning
Deep Learning is a field that is heavily based on Mathematics and you need to have a good understanding of Data Structures and Algorithms to solve the mathematical problems optimally. Data Structures and Algorithms can be used to determine how a problem is represented internally or how the actual storage pattern works & what is happening under
6 min read
Why Data Structures and Algorithms are "Must Have" for Developers and Where to learn them : Answered
With advancement and innovation in technology, programming is becoming a highly in-demand skill for Software Developers. Everything you see around yourself from Smart TVs, ACs, Lights, Traffic Signals uses some kind of programming for executing user commands. In order to be irreplaceable, one must always be efficient. Data Structures and Algorithms
4 min read
Data Structures and Algorithms Online Courses : Free and Paid
Data Structures and Algorithms is one of the most important skills that every computer science student must-have. It is often seen that people with good knowledge of these technologies are better programmers than others and thus, crack the interviews of almost every tech giant. Now, you must be thinking to opt for a quality DSA Course to build
7 min read
Data Structures and Algorithms | Set 36
Que - 1. The function shiftNode() which takes as input two linked lists- destination and source. It deletes front node from source and places it onto the front of destination. Choose the set of statements which replace X, Y, Z in given function. void shiftNode(struct node** destRoot, struct node** srcRoot) { // the front of source node struct node*
4 min read
Data Structures and Algorithms | Set 37
Que - 1. For 8 keys and 6 slots in a hashing table with uniform hashing and chaining, what is the expected number of items that hash to a particular location. (A) 2.33 (B) 0.75 (C) 1.33 (D) 2 Solution: Probability that key1 ends up in slot 1 = 1/6 Probability that key2 ends up in slot 1 = 1/6 Probability that key3 ends up in slot x = 1/6 Probabilit
4 min read
Difference between Data Structures and Algorithms
What are Data Structures and Algorithms? Data structures and algorithms are two interrelated concepts in computer science. Data structures refer to the organization, storage, and retrieval of data, while algorithms refer to the set of instructions used to solve a particular problem or perform a specific task. Applications of Data Structures and Alg
2 min read
Are Data Structures and Algorithms important for Web Developers?
Web development is constantly changing, and new languages, technologies, and tools are emerging to help developers create engaging and functional web applications. Despite these additions, some basic concepts remain the same no matter what kind of development we are talking about, what language we’re using, or what platform we’re working on. Two of
7 min read
Walk-Through DSA3 : Data Structures and Algorithms Online Course by GeeksforGeeks
This is a 10 weeks long online certification program specializing in Data Structures & Algorithms which includes pre-recorded premium Video lectures & programming questions for practice. You will learn algorithmic techniques for solving various computational problems and will implement more than 200 algorithmic coding problems. This course
5 min read
Live Classes for Data Structures and Algorithms: Interview Preparation Focused Course
Engineers have the power to change the world by solving real-world problems but underneath its DSA that plays a crucial role in solving all the problems we are surrounded with. These all are the reasons people from all age groups love to move towards programming and want to learn it. Also, all the major tech companies (Google, Microsoft, Amazon, Fa
4 min read
Best Data Structures and Algorithms Books
Data Structures and Algorithms is one of the most important skills that every Computer Science student must have. There are a number of remarkable publications on DSA in the market, with different difficulty levels, learning approaches and programming languages. In this article we're going to discuss a summary of top 10 Best Data Structures and Alg
9 min read
Is Data Structures and Algorithms Required for Android Development?
Android development is a rapidly evolving field, with new technologies and tools constantly emerging. One question that often arises is whether a solid understanding of data structures and algorithms is necessary for Android developers. In this article, we will explore the importance of data structures and algorithms in software development, their
4 min read
Understanding "Efficiency" when working with Data Structures and Algorithms
What is Efficient Programming?Efficient programming is programming in a manner that, when the program is executed, uses a low amount of overall resources pertaining to computer hardware.  Practicing to create a small file size and low resource algorithm results in an efficient program. Below are some important concepts you should know to understand
8 min read
Learn DSA with Python | Python Data Structures and Algorithms
This tutorial is a beginner-friendly guide for learning data structures and algorithms using Python. In this article, we will discuss the in-built data structures such as lists, tuples, dictionaries, etc, and some user-defined data structures such as linked lists, trees, graphs, etc, and traversal as well as searching and sorting algorithms with th
15+ min read
What to do if I get stuck in Data Structures and Algorithms (DSA)?
Learning Data Structures and Algorithms is like a big adventure where you explore various techniques that tell us how to solve complex problems in computer science. It's like solving a puzzle where you might not be sure what piece goes where. Thus there are times when you might feel stuck while learning DSA. This blog will help to overcome those di
4 min read
three90RightbarBannerImg