branch and bound is a problem solving technique

Weekly Must-Reads View All

Ai and healthcare equity: bridging gaps.

AI and Healthcare Equity: Bridging Gaps In today's fast-paced world,

The Boundaries of AI: Legal and Ethical Perspectives

Artificial Intelligence (AI) has become an integral part of our lives, from

Hyperparameter Optimization Techniques

Hyperparameter Optimization: Finding the Perfect Balance for Your Machine

GRU vs LSTM: Comparing Neural Network Architectures

Are you fascinated by the world of artificial intelligence and its applications?

Trending Now View All

Exploring Branch and Bound Technique

Welcome, dear readers, to a fascinating journey into the world of algorithms and problem-solving techniques! In this article, we will embark on a quest to unravel the mysteries of the Branch and Bound technique. Brace yourselves for an enthralling adventure where we will explore the depths of this powerful algorithm and its applications. So, buckle up and get ready to dive into the captivating realm of optimization problems and the magic of Branch and Bound.

The Quest Begins: Introducing Branch and Bound

Let us start our expedition by understanding what exactly Branch and Bound is. In the realm of computer science and optimization, Branch and Bound is a clever and efficient algorithmic technique used to solve various combinatorial optimization problems. It helps us examine a vast space of potential solutions methodically and intelligently, pruning away unpromising paths while searching for the best solution.

The concept behind Branch and Bound is to divide the problem into smaller subproblems, forming a tree-like structure where each branch represents a potential solution. By progressively bounding the search space and systematically exploring promising branches, we can efficiently find an optimal or near-optimal solution.

Think of it as embarking on a treasure hunt. Each branch represents a different path you can take, and at each junction, you assess the potential of finding the treasure. If a path seems unpromising, you discard it and explore other branches that show more potential. This technique allows us to navigate through an enormous solution space, significantly reducing the time and effort required to find the best solution.

Unveiling the Power of Branch and Bound

The true beauty of Branch and Bound lies in its versatility. This powerful technique can be applied to a wide range of optimization problems, including but not limited to:

• Traveling Salesman Problem
• Knapsack Problem
• Graph Coloring Problem
• Integer Linear Programming
• Job Scheduling

By using Branch and Bound, we can tackle these challenging problems and more, providing us with optimal or near-optimal solutions that were previously thought to be out of reach. Imagine being able to find the shortest route for a salesman, efficiently allocate resources in a resource-constrained environment, or optimize job scheduling for maximum efficiency. Branch and Bound makes all of this possible and more.

How Does Branch and Bound Work?

Now that we have a general understanding of Branch and Bound, let us delve deeper into how this technique actually works. The algorithm can be divided into several distinct steps, each playing a crucial role in the overall process:

Step 1: Initialization and Setup

Before we set off on our optimization journey, we need to initialize the necessary variables and data structures. This step involves defining the problem’s constraints, creating data structures to store the problem space, and setting up the initial bounds or objective function values.

Step 2: Branching

Once we have set the stage, it’s time to start branching out and exploring the solution space. We choose a branch and divide the problem into smaller subproblems, narrowing down the potential solution space. Each branch represents a decision or choice that needs to be made. For example, in the Traveling Salesman Problem, each branch may represent a different city to visit next.

Step 3: Bounding

As we navigate through the branches, we need to evaluate their potential and prune away the ones that are unlikely to yield the optimal solution. This is where bounding comes into play. By establishing bounds or estimations on the potential value of each branch, we can discard those that are clearly inferior and focus on exploring the most promising paths.

Step 4: Backtracking

Branch and Bound is not a one-way journey. It involves retracing our steps and exploring additional branches that were previously discarded. This process is known as backtracking. By revisiting unpromising branches, we ensure that we have explored all possible paths and don’t miss out on any potential hidden treasures.

Step 5: Updating Bounds and Solutions

As we progress deeper into the solution space, we may discover better bounds or even find optimal solutions. It is essential to update our bounds and solutions accordingly to refine our search and optimize the exploration process. This step ensures that we don’t miss out on potential improvements while navigating through the tree of branches.

Step 6: Termination

Finally, we reach the end of our expedition. The termination step occurs when we have fully explored the solution space and found the best solution or exhausted all possibilities. At this point, we can conclude our Branch and Bound algorithm, having successfully navigated through the labyrinth of branches and arrived at an optimal or near-optimal solution.

Benefits and Limitations of Branch and Bound

As with any technique, it is essential to consider both the benefits and limitations of using Branch and Bound. Let’s take a brief look at what makes this algorithm a valuable tool in our optimization arsenal:

• Provides optimal or near-optimal solutions.
• Can be applied to various combinatorial optimization problems.
• Efficiently explores large solution spaces.
• Allows for intelligent pruning and backtracking.

Limitations:

• May suffer from the “curse of dimensionality” in high-dimensional problems.
• Can be computationally intensive for certain problem types.
• Requires careful design and implementation for optimal performance.
• Not suitable for problems with continuous variables or non-linear constraints.

Conclusion: Unleashing the Magic of Branch and Bound

Dear readers, we hope this journey into the realm of Branch and Bound has left you spellbound and eager to explore further. This algorithmic technique has the power to unlock optimal solutions to complex optimization problems, providing us with newfound efficiency and breakthroughs.

Remember, Branch and Bound is not just a mere algorithm; it is a valuable tool in our problem-solving arsenal. Whether you are a computer scientist, an operations researcher, or simply an enthusiast fascinated by the wonders of optimization, Branch and Bound can be your trusted companion on the quest for the optimal.

So, now that we have armed ourselves with the knowledge and understanding of this magical technique, let us set forth and conquer the vast lands of optimization problems. May Branch and Bound guide us through the labyrinth of paths, leading us to the treasures of efficiency and success.

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Save my name, email, and website in this browser for the next time I comment.

Link State vs Distance Vector: Understanding Routing Protocols

Introduction Routing protocols serve as the backbone of computer networks,

• Future Vision

AI in Energy: Paving the Way for Sustainability

AI in Energy: Paving the Way for Sustainability Welcome to the age of artificial

You May Also Like

Elastic search vs. algolia: search solutions.

What’s the Difference Between Elastic Search and Algolia?

Algorithm vs Program: Computer Science Concepts

Algorithm vs Program: Exploring the Differences The World of Computer Science In

Elastic Search vs Splunk: Exploring Data Analysis Tools

Which is Better for Data Analysis: Elastic Search or Splunk?

Flowchart vs. Pseudocode: Algorithm Design

Are you someone who gets easily overwhelmed by complex algorithms and their

• Trending Now
• Foundational Courses
• Data Science
• Practice Problem
• Machine Learning
• System Design
• DevOps Tutorial
• Share Your Experiences
• Coding for Everyone Course

Branch and Bound Algorithm

Learn more about Branch and Bound in DSA Self Paced Course Recent Articles on Branch and Bound

What is Branch and Bound Algorithm?

Branch and bound is an algorithm design paradigm which is generally used for solving combinatorial optimization problems. These problems are typically exponential in terms of time complexity and may require exploring all possible permutations in worst case. The Branch and Bound Algorithm technique solves these problems relatively quickly.

Example to show working of Branch and Bound Algorithm

Let us consider the 0/1 Knapsack problem to understand Branch and Bound.

There are many algorithms by which the knapsack problem can be solved:

• Greedy Algorithm for Fractional Knapsack
• DP solution for 0/1 Knapsack
• Backtracking Solution for 0/1 Knapsack .

Let’s see the Branch and Bound Approach to solve the 0/1 Knapsack problem : The Backtracking Solution can be optimized if we know a bound on best possible solution subtree rooted with every node. If the best in subtree is worse than current best, we can simply ignore this node and its subtrees. So we compute bound (best solution) for every node and compare the bound with current best solution before exploring the node.

Example bounds used in below diagram are, A down can give $315, B down can $275, C down can $225, D down can $125 and E down can $30.

• Branch and Bound | Set 1 (Introduction with 0/1 Knapsack)
• Branch and Bound | Set 2 (Implementation of 0/1 Knapsack)
• Branch and Bound | Set 3 (8 puzzle Problem)
• Branch And Bound | Set 4 (Job Assignment Problem)
• Branch and Bound | Set 5 (N Queen Problem)
• Branch And Bound | Set 6 (Traveling Salesman Problem)
• Learn Data Structure and Algorithms | DSA Tutorial

If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to [email protected]. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above

Please Login to comment...

Similar reads.

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

• Interview Q

DAA Tutorial

Asymptotic analysis, analysis of sorting, divide and conquer, lower bound theory, sorting in linear time, binary search trees, red black tree, dynamic programming, greedy algorithm, backtracking, shortest path, all-pairs shortest paths, maximum flow, sorting networks, complexity theory, approximation algo, string matching.

Interview Questions

• Send your Feedback to [email protected]

Help Others, Please Share

Learn Latest Tutorials

Transact-SQL

Reinforcement Learning

R Programming

React Native

Python Design Patterns

Python Pillow

Python Turtle

Preparation

Verbal Ability

Company Questions

Trending Technologies

Artificial Intelligence

Cloud Computing

Data Science

Machine Learning

B.Tech / MCA

Data Structures

Operating System

Computer Network

Compiler Design

Computer Organization

Discrete Mathematics

Ethical Hacking

Computer Graphics

Software Engineering

Web Technology

Cyber Security

C Programming

Control System

Data Mining

Data Warehouse

Search anything:

Branch and Bound Technique

Algorithms branch and bound.

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

With this article, you have explained the idea of Branch and Bound Technique, types of Branch and Bound Technique and applications of the technique.

Introduction to Branch and Bound Technique

The algorithm: branch and bound technique.

• Types of Solution

Types of Branch and Bound

Why use branch and bound, problems that can be solved using branch and bound.

The Branch and Bound Technique is a problem solving strategy, which is most commonly used in optimization problems, where the goal is to minimize a certain value. The optimized solution is obtained by means of a state space tree (A state space tree is a tree where the solution is constructed by adding elements one by one, starting from the root. Note that the root contains no element). This method is best when used for combinatorial problems with exponential time complexity, since it provides a more efficient solution to such problems.

In this technique, the first step is to create a function U (which represents an upper bound to the value that node and its children shall achieve), that we intend to minimize. We call this function the objective function. Note that the branch and bound technique can also be used for maximization problems, since multiplying the objective function by -1 coverts the problem to a minimization problem. Let this function have an initial maximum value, according to the conditions of the given problem. Also, let U 0 be the initial value of U . We also calculate a cost function C which will give us the exact value that the particular node shall achieve.

The next question is the order in which the tree is to be searched. For this, there exist multiple types of branch and bound, which we shall discuss in detail later. For now, let us assume that there is a set S consisting of subsets of the given set of values in the order in which they need to be searched.

The algorithm of the branch and bound method for this problem will be as follows:

For each subset s in S, do the following:

• Calculate the value of U(s) .
• If U(s) U 0 , then U 0 = U(s).

In the end, the the subset s for which the current value of U 0 is obtained will be the best solution to the given problem, and the value of the cost function at that node will give us the solution. Here, after each level, the value of U 0 tells us that there shall be a node with cost less than that value.

Types of Solutions

For a branch and bound problem, there are two ways in which the solution can be represented:

Variable size solution : This solution provides the subset of the given set that gives the optimized solution for the given problem. For example, if the we are to select a combination of elements from {A, B, C, D, E} that optimizes the given problem, and it is found that A, B, and E together give the best solution, then the solution will be {A, B, E}.

Fixed size solution : This solution is a sequence of 0s and 1s, with the digit at the i th position denoting whether the i th element should be included or not. Hence, for the earlier example, the solution will be given by {1, 1, 0, 0, 1}.

There are multiple types of the Branch and Bound method, based on the order in which the state space tree is to be searched. We shall now discuss each of these methods in detail. We will be using the variable solution method to denote the solutions in these methods.

FIFO Branch and Bound

The First-In-First-Out approach to the branch and bound problem follows the queue approach in creating the state-space tree. Here, breadth first search is performed, i.e., the elements at a particular level are all searched, and then the elements of the next level are searched, starting from the first child of the first node in the previous level.

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

Here, note that the number assigned to the node signifies the order in which the tree shall be constructed. The element next to the set denotes the next element to be added to the subset. Note that if an element is getting added, it is assumed here that all elements in the set preceeding that element are not added. For example, in node 4, D is getting added. This implies that elements A, B and C are not added.

LIFO Branch and Bound

The Last-In-First-Out approach to this problem follows the stack approach in creating the state space tree. Here, when nodes get added to the state space tree, think of them as getting added to a stack. When all nodes of a level are added, we pop the topmost element from the stack and then explore it. Hence, the state space tree for the same example {A, B, C, D} will be as follows:

Here, one can see that the main difference lies in the order in which the nodes have been explored.

Least Cost-Branch and Bound

This method of exploration uses the cost function in order to explore the state space tree. Although the previous two methods calculate the cost function at each node, this is not used as a criterion for further exploration.

In this method, after the children of a particular node have been explored, the next node to be explored would be that node out of the unexplored nodes which has the least cost. For example, in the previous example, after reaching node 5, the next node to be explored would be that which has the least cost among nodes 2, 3, 4, 5.

The Branch and Bound method is preferred over other similar methods such as backtracking when it comes to optimization problems. Here, the cost and the objective function help in finding branches that need not be explored.

Suppose the cost of a particular node has been determined. If this value is greater than that of U 0 , this means that there is no way this node or its children shall give a solution. Hence, we can kill this node and not explore its further branches. This method helps us rule out cases not worth exploring, and is therefore more efficient.

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

Job Sequencing : Suppose there is a set of N jobs and a set of N workers. Each worker takes a specific time to complete each of the N jobs. The job sequencing problem deals with finding that order of the workers, which minimizes the time taken to complete the job.

0/1 Knapsack problem : Given a set of weights of N objects and a sack which can carry a maximum of W units. The problem deals with finding that subset of items such that the maximum possible weight is carried in the sack. Here, one cannot take part of an object, i.e., one can either take an object or not take it. This problem can also be solved using the backtracking, brute force and the dynamic programming approach.

Traveling Salesman Problem : Here, we are given a set of N cities, and the cost of traveling between all pairs of cities. The problem is to find a path such that one starts from a given node, visits all cities exactly once, and returns back to the starting city.

With this article at OpenGenus, you must have the complete idea of Branch and Bound Technique.

Branch and Bound

I. introduction, ii. illustration on the job assignment problem, iii. the general branch and bound algorithm, iv. criteria for the choice of approximate cost functions, v. implementation of the b&b job assignment algorithm, the general branch and bound algorithm.

Output-Space Outer Approximation Branch-and-Bound Algorithm for a Class of Linear Multiplicative Programs

• Published: 05 June 2024

Cite this article

• Bo Zhang 1 , 2 ,
• Hongyu Wang 3 &
• Yuelin Gao   ORCID: orcid.org/0000-0003-2021-2097 1  

19 Accesses

Explore all metrics

In this study, we investigate a class of linear multiplicative programs with positive exponents. By introducing p additional variables, the original problem is reformulated into an equivalent problem (EP) within the output space. Subsequently, a novel global optimization algorithm is introduced to tackle EP. The algorithm primarily leverages two key techniques. One is the outer approximation technique, which tightens the relaxed feasible region of EP and improves the upper bound by carefully examining suitable feasible points. The other is the branch and bound technique to guarantee the global optimality of the solution. Numerical results confirm the effectiveness and practicality of the proposed algorithm, thereby underscoring its potential for real-world applications.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Data availability

Supporting data for this study are available from the corresponding author, as reasonably requested.

Benson, H.P.: Vector maximization with two objective functions. J. Optim. Theory Appl. 28 , 253–257 (1979)

Article   MathSciNet   Google Scholar  

Bennett, K.: Global tree optimization: a non-greedy decision tree algorithm. Comput. Sci. Stat. 26 , 156–160 (1994)

Google Scholar  

Benson, H.P., Boger, G.M.: Multiplicative programming problems: analysis and efficient point search heuristic. J. Optim. Theory Appl. 94 , 487–510 (1997)

Benson, H.P., Boger, G.M.: Outcome-space cutting-plane algorithm for linear multiplicative programming. J. Optim. Theory Appl. 104 , 301–332 (2000)

Benson, H.P.: Decomposition branch-and-bound based algorithm for linear programs with additional multiplicative constraints. J. Optim. Theory Appl. 126 , 41–61 (2005)

Chen, Y., Jiao, H.: A nonisolated optimal solution of general linear multiplicative programming problems. Comput. Oper. Res. 36 , 2573–2579 (2009)

Dorneich, M.C., Sahinidis, N.V.: Global optimization algorithms for chip layout and compaction. Eng. Optim. 25 , 131–154 (1995)

Article   Google Scholar  

Dennis, D.F.: Analyzing public inputs to multiple objective decisions on national forests using conjoint analysis. For. Sci. 44 , 421–429 (1998)

Gleixner, A., Eifler, L., Gally, T., Gamrath, G., Gemander, P., Gottwald, R.L., Hendel, G., Hojny, C., Koch, T., Miltenberger, M., Müller, B., Pfetsch, M-E., Puchert, C., Rehfeldt, D., Schlösser, F., Serrano, F., Shinano, Y., Viernickel, J.M., Vigerske, S., Weninger, D., Witt, J-T., Witzig, J.: The SCIP Optimization Suite. https://www.scipopt.org/index.php/download , v5.0.1 (2017)

Gao, Y., Xu, C., Yang, Y.: An outcome-space finite algorithm for solving linear multiplicative programming. Appl. Math. Comput. 179 , 494–505 (2006)

Gao, Y., Wu, G., Ma, W.: A new global optimization approach for convex multiplicative programming. Appl. Math. Comput. 216 , 1206–1218 (2010)

Jiao, H.: A branch and bound algorithm for globally solving a class of nonconvex programming problems. Nonlinear Anal. 70 , 1113–1123 (2009)

Jiao, H., Wang, W., Yin, J., Shang, Y.L.: Image space branch-reduction-bound algorithm for globally minimizing a class of multiplicative problems. RAIRO-Oper. Res. 55 , 1533–1552 (2022)

Jiao, H., Wang, W., Shang, Y.L.: Outer space branch-reduction-bound algorithm for solving generalized affine multiplicative problems. J. Comput. Appl. Math. 419 , article number: 114784 (2023)

Konno, H., Yajima, Y., Matsui, T.: Parametric simplex algorithms for solving a special class of nonconvex minimization problems. J. Glob. Optim. 1 , 65–81 (1991)

Kuno, T., Yajima, Y., Konno, H.: An outer approximation method for minimizing the product of several convex functions on a convex set. J. Glob. Optim. 3 , 325–335 (1993)

Kuno, T.: Globally determining a minimum-area rectangle enclosing the projection of a higher-dimensional set. Oper. Res. Lett. 13 , 295–303 (1993)

Konno, H., Kuno, T., Yajima, Y.: Global optimization of a generalized convex multiplicative function. J. Glob. Optim. 41 , 47–62 (1994)

Loridan, P.: Necessary conditions for \(\epsilon \) -optimality. Math. Program. Stud. 19 , 140–152 (1982)

Liu, X.J., Umegaki, T., Yamamoto, Y.: Heuristic methods for linear multiplicative programming. J. Glob. Optim. 15 , 433–447 (1999)

Liu, S.Y., Zhao, Y.F.: An efficient algorithm for globally solving generalized linear multiplicative programming. J. Comput. Appl. Math. 296 , 840–847 (2016)

Mulvey, J.M., Vanderbei, R.J., Zenios, S.A.: Robust optimization of large-scale systems. Oper. Res. 43 , 264–281 (1995)

Matsui, T.: NP-Hardness of linear multiplicative programming and related problems. J. Glob. Optim. 9 , 113–119 (1996)

Maranas, C.D., Androulakis, I.P., Floudas, C.A.: Solving long-term financial planning problems via global optimization. J. Econ. Dyn. Control. 21 , 1405–1425 (1997)

Mahmoodian, V., Charkhgard, H., Zhang, Y.: Multi-objective optimization based algorithms for solving mixed integer linear minimum multiplicative programs. Comput. Oper. Res. 128 , 105178 (2021)

Nanda, S.R., Mahanty, B., Tiwari, M.K.: Clustering Indian stock market data for portfolio management. Expert Syst. Appl. 37 , 8793–8798 (2010)

Rau, N., Layard, P., Walters, A.: Microeconomic theory. Economica 47 , 211 (1980)

Ryoo, H.S., Sahinidis, N.V.: Analysis of bounds for multilinear functions. J. Glob. Optim. 19 , 403–424 (2001)

Reza, A.N.: Minimizing the risk in investment projects. Eur. J. Sustain. Dev. 6 , 23–30 (2017)

Shao, L., Ehrgott, M.: Primal and dual multi-objective linear programming algorithms for linear multiplicative programmes. Optimization 65 , 415–431 (2016)

Shen, P.P., Huang, B.D., Wang, L.F.: Range division and linearization algorithm for a class of linear ratios optimization problems. J. Comput. Appl. Math. 350 , 324–342 (2019)

Shen, P.P., Wang, K., Lu, T.: Outer space branch and bound algorithm for solving linear multiplicative programming problems. J. Glob. Optim. 78 , 453–482 (2020)

Wang, C.F., Liu, S.Y.: A new linearization method for generalized linear multiplicative programming. Comput. Oper. Res. 38 , 1008–1013 (2011)

Wang, C.F., Bai, Y.Q., Shen, P.P.: A practicable branch-and-bound algorithm for globally solving linear multiplicative programming. Optimization 66 , 397–405 (2017)

Wang, C.F., Deng, Y.P., Shen, P.P.: A novel convex relaxation-strategy-based algorithm for solving linear multiplicative problems. J. Comput. Appl. Math. 407 , 114080 (2022)

Youness, E.A.: Level set algorithm for solving convex multiplicative programming problems. Appl. Math. Comput. 167 , 1412–1417 (2005)

Zhang, B., Gao, Y.L., Liu, X., Huang, X.L.: Output-space branch-and-bound reduction algorithm for a class of linear multiplicative programs. Mathematics 8 , article number: 315 (2020)

Zhang, B., Gao, Y.L., Liu, X., Huang, X.L.: An outcome-space-based branch-and-bound algorithm for a class of sum-of-fractions problems. J. Optim. Theory Appl. 192 , 830–855 (2022)

Zhang, B., Gao, Y.L., Liu, X., Huang, X.L.: Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problems. J. Glob. Optim. 86 , 61–92 (2023)

Download references

Acknowledgements

We would like to thank three anonymous referees for their constructive criticism and helpful comments, which enabled us to improve the original manuscript.

This research is supported by the National Natural Science Foundation of China under Grant (Grant Numbers 12301401, 41962016), Construction Project of first-class subjects in Ningxia higher Education (Grant Number NXYLXK-2017B09), Basic discipline research projects supported by Nanjing Securities (Grant Number NJZQJCXK202201) and the Construction Project of first-class subjects in Hydraulic Engineering (Grant Number NXYLXK2021A03).

Author information

Authors and affiliations.

Ningxia Province Key Laboratory of Intelligent Information and Data Processing, North Minzu University, Yinchuan, 750021, People’s Republic of China

Bo Zhang & Yuelin Gao

School of Mathematics and Statistics, Ningxia University, Yinchuan, 750021, People’s Republic of China

School of Civil and Hydraulic Engineering, Ningxia University, Yinchuan, 750021, Ningxia, People’s Republic of China

Hongyu Wang

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Yuelin Gao .

Additional information

Communicated by Luis Zuluaga.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Zhang, B., Wang, H. & Gao, Y. Output-Space Outer Approximation Branch-and-Bound Algorithm for a Class of Linear Multiplicative Programs. J Optim Theory Appl (2024). https://doi.org/10.1007/s10957-024-02461-y

Download citation

Received : 19 September 2022

Accepted : 18 May 2024

Published : 05 June 2024

DOI : https://doi.org/10.1007/s10957-024-02461-y

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Global optimization
• Linear multiplicative program
• Branch-and-bound
• Outer approximation

Mathematics Subject Classification

• Find a journal
• Publish with us
• Track your research

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures
• Introduction to Knapsack Problem, its Types and How to solve them

Fractional Knapsack

• Fractional Knapsack Problem
• Fractional Knapsack Queries
• Difference between 0/1 Knapsack problem and Fractional Knapsack problem

0/1 Knapsack

• 0/1 Knapsack Problem
• Printing Items in 0/1 Knapsack
• 0/1 Knapsack Problem to print all possible solutions
• 0-1 knapsack queries

0/1 Knapsack using Branch and Bound

• 0/1 Knapsack using Least Cost Branch and Bound
• Unbounded Fractional Knapsack
• Unbounded Knapsack (Repetition of items allowed)
• Unbounded Knapsack (Repetition of items allowed) | Efficient Approach
• Double Knapsack | Dynamic Programming

Some Problems of Knapsack problem

• Partition problem | DP-18
• Count of subsets with sum equal to X
• Length of longest subset consisting of A 0s and B 1s from an array of strings
• Breaking an Integer to get Maximum Product
• Find minimum number of coins to make a given value (Coin Change)
• Count all combinations of coins to make a given value sum (Coin Change II)
• Maximum sum of values of N items in 0-1 Knapsack by reducing weight of at most K items in half

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 at all [It is not possible to put a part of an item into the bag.

Input: N = 3, W = 4, v[] = {1, 2, 3}, w[] = {4, 5, 1} Output: 3 Explanation: There are two items which have weight less than or equal to 4. If we select the item with weight 4, the possible profit is 1. And if we select the item with weight 1, the possible profit is 3. So the maximum possible profit is 3. Note that we cannot put both the items with weight 4 and 1 together as the capacity of the bag is 4. Input: N = 5, W = 10, v[] = {40, 50, 100, 95, 30}, w[] = {2, 3.14, 1.98, 5, 3} Output: 235

Branch and Bound Algorithm:

Branch and bound is an algorithm design paradigm which is generally used for solving combinatorial optimization problems. These problems typically exponential in terms of time complexity and may require exploring all possible permutations in worst case. Branch and Bound solve these problems relatively quickly. 

Firstly let us explore all approaches for this problem.

1. 0/1 Knapsack using Greedy Approach :

A Greedy approach is to pick the items in decreasing order of value per unit weight. The Greedy approach works only for fractional knapsack problem and may not produce correct result for 0/1 knapsack .

2. 0/1 Knapsack using Dynamic Programming (DP) :

We can use D ynamic P rogramming ( DP ) for 0/1 Knapsack problem . In DP, we use a 2D table of size n x W. The DP Solution doesn’t work if item weights are not integers .

3. 0/1 Knapsack using Brute Force:

Since DP solution doesn’t always work just like in case of non-integer weight, a solution is to use Brute Force. With n items, there are 2n solutions to be generated, check each to see if they satisfy the constraint, save maximum solution that satisfies constraint. This solution can be expressed as tree.

0/1 Knapsack using Brute Force

4. 0/1 Knapsack using Backtracking :

We can use Backtracking to optimize the Brute Force solution. In the tree representation, we can do DFS of tree. If we reach a point where a solution no longer is feasible, there is no need to continue exploring. In the given example, backtracking would be much more effective if we had even more items or a smaller knapsack capacity.

0/1 Knapsack using Backtracking

5. 0/1 Knapsack using Branch and Bound:

The backtracking based solution works better than brute force by ignoring infeasible solutions. We can do better (than backtracking) if we know a bound on best possible solution subtree rooted with every node. If the best in subtree is worse than current best, we can simply ignore this node and its subtrees. So we compute bound (best solution) for every node and compare the bound with current best solution before exploring the node.

How to find bound for every node for 0/1 Knapsack?

The idea is to use the fact that the Greedy approach provides the best solution for Fractional Knapsack problem. To check if a particular node can give us a better solution or not, we compute the optimal solution (through the node) using Greedy approach. If the solution computed by Greedy approach itself is more than the best so far, then we can’t get a better solution through the node.

Follow the steps to implement the above idea:

• Sort all items in decreasing order of ratio of value per unit weight so that an upper bound can be computed using Greedy Approach.
• Initialize maximum profit, maxProfit = 0 , create an empty queue, Q , and create a dummy node of decision tree and enqueue it to Q . Profit and weight of dummy node are 0 .
• Extract an item from Q . Let the extracted item be u .
• Compute profit of next level node. If the profit is more than maxProfit , then update maxProfit .
• Compute bound of next level node. If bound is more than maxProfit , then add next level node to Q .
• Consider the case when next level node is not considered as part of solution and add a node to queue with level as next, but weight and profit without considering next level nodes. 

Below is the implementation of above approach:

Time Complexity: O(2 N ) Auxiliary Space: O(N)

Branch and bound is very useful technique for searching a solution but in worst case, we need to fully calculate the entire tree. At best, we only need to fully calculate one path through the tree and prune the rest of it. 

Please Login to comment...

Similar reads.

• Branch and Bound

Improve your Coding Skills with Practice

What kind of Experience do you want to share?