Stack Overflow
Stack Overflow

Questions tagged [branch-and-bound]

Branch and bound is a general technique for finding optimal solutions of various combinatorial and integer programming problems. It entails examining candidates (“branches”), while utilizing knowledge of upper and lower limits (“bounds”) to eliminate sub-trees, to find the optimal solution quicker.

Branch and bound is a general technique for finding optimal solutions of various combinatorial and integer programming problems. It involves partial enumeration, by examining candidates (“branches”), while also utilizing knowledge of upper and lower limits (“bounds”) to eliminate sub-trees.

The B&B technique is widely used in discrete optimization problems where the solution falls in the integer space (Traveling salesman, cutting stock etc.) This method was introduced in 1960.

For further reference: The Wikipedia page on Branch-and-bound (B&B)

114 questions
21
votes
4 answers

Difference between 'backtracking' and 'branch and bound'

In backtracking we use both bfs and dfs. Even in branch and bound we use both bfs and dfs in additional to least cost search. so when do we use backtracking and when do we use branch and bound Does using branch and bound decreases time…
Varun Teja
  • 503
  • 2
  • 6
  • 16
10
votes
3 answers

Is Dynamic 0/1 Knapsack a Total Joke?

I have obtained a proof that would discredit a generally held idea regarding the 0/1 knapsack problem and I'm really having a hard time convincing my self I am right because I couldn't find any thing any where to support my claims, so I am going to…
Amen
  • 1,524
  • 5
  • 22
  • 41
8
votes
2 answers

What are some good resources for learning backtracking, branch-and-bound and dynamic programming algorithms?

CLRS doesn't seem to cover bactracking/branch-and-bound. I tried several resources online, though I get the idead behind these, I am unable to write code for, let's say, Knapsack problem. So, I want something that, may be, takes a problem and…
user1624400
  • 395
  • 4
  • 13
8
votes
4 answers

C++ implementation of knapsack branch and bound

I am trying to a C++ implementation of this knapsack problem using branch and bounding. There is a Java version on this website here: Implementing branch and bound for knapsack I'm trying to make my C++ version print out the 90 that it should,…
user1527877
  • 83
  • 1
  • 1
  • 5
7
votes
2 answers

Packing items into fixed number of bins

I am looking for an algorithm that will solve my problem in the most efficient way. Problem description: I have a list of items (only positive integers are allowed) and fixed number of bins of identical capacity. So far, I thought about…
solitaire
  • 93
  • 1
  • 5
7
votes
3 answers

How to Eliminate Cost-centres in String Taversals and List Comprehensions

I'm implementing a motif finding algorithm from the domain of bioinformatics using Haskell. I wont go into the details of the algorithm other then to say it's branch and bound median string search. I had planned on making my implementation more…
Dave
  • 257
  • 2
  • 7
7
votes
3 answers

TSP - Branch and bound

I'm trying to solve the TSP with Branch and bound algorithm. I must build a matrix with costs but I have this problem: I have city with coordinates x and y. The cost of traveling is ceil(ceil(sqrt((x1-x2)^2+(y1-y2)^2))/v) + days spent in the city. V…
gummmibear
  • 81
  • 1
  • 1
  • 4
7
votes
1 answer

Difference(s) between branch and bound and best-first search

I am studying branch and bound and best-first search for my thesis work but found lots of contradictions on the web about these two concept. First I thought branch and bound only prune the branches ending to high cost solution (using heuristic) and…
Barpa
  • 275
  • 1
  • 3
  • 13
7
votes
2 answers

Can branch and bound algorithms be implemented purely functionally?

General Description of Branch and Bound From Wikipedia's Branch and Bound: This step is called pruning, and is usually implemented by maintaining a global variable m (shared among all nodes of the tree) that records the minimum upper bound seen…
danmcardle
  • 2,079
  • 2
  • 17
  • 25
5
votes
2 answers

Difference between branch & bound (+ extended list) and Dijkstra's Algorithm on Graphs

I was working through http://youtu.be/gGQ-vAmdAOI?t=23m14s when at 23:14 I felt that branch & bound with an "extended list" was very similar to Dijkstra's algorithm. Later on in the lecture when the algorithm is again extended with an admissable…
Sebastian Graf
  • 3,602
  • 3
  • 27
  • 38
5
votes
2 answers

What is the difference between dynamic programming and branch and bound?

I only know that by branch and bound, one can REDUCE the procedure to obtain a solution, but that only helps for problems which have a solution space tree.
chinmay2312
  • 103
  • 1
  • 2
  • 8
5
votes
2 answers

Calculating items included in branch and bound knapsack

Using a branch and bound algorithm I have evaluated the optimal profit from a given set of items, but now I wish to find out which items are included in this optimal solution. I'm evaluating the profit value of the optimal knapsack as follows…
Alex
  • 243
  • 1
  • 7
  • 18
4
votes
1 answer

Branch and bound algorithm implementation

I'd need to implement a branch and bound algorithm to prove the effectiveness of an allocating strategy for storage management in my bachelor thesis. I'm not a programmer, I have some little know-how in C, but I can realize this algorithm can't be…
marcob8986
  • 153
  • 4
  • 12
4
votes
4 answers

branch and bound

Can someone explain the branch and bound search technique for me? I need to find a path with the smallest cost from any start node to an end node of any random graph using branch and bound search algorithm.
mario64
  • 1,517
  • 3
  • 12
  • 12
4
votes
1 answer

Implementing branch and bound for knapsack

I'm having a headache implementing this (awful) pseudo-java code (I wonder: why the hell people do that?) for the b&b knapsack problem. This is my implementation so far, which outputs a maximum of 80 (when it should print 90, for the items on the…
andandandand
  • 21,946
  • 60
  • 170
  • 271
1
2 3 4 5 6 7 8