Questions tagged [branch-and-bound]
The branch-and-bound tag has no usage guidance.
30
questions
1
vote
0
answers
59
views
Bounding function for Travelling Salesman Problem
I have been studying the Branch and Bound paradigm. I came across an approach to solve the Travelling Salesman Problem using branch and bound where a specific kind of bounding function was used. I've ...
- 11
0
votes
0
answers
18
views
Branch and bound defining a estimated cost
How can I define a valid $\hat{C}$ for a job assignment problem where I have $n$ jobs and always $3$ employees, where the cost of an employee doing a job is defined as $C_{ij}$ and no employee can do ...
- 121
1
vote
1
answer
126
views
pruning branch and bound
I am working on a branch and bound problem and I was wondering if it is correct to prune the node with z = 21.667 and if so, how do we know that we will not get a better solution if we branch on this ...
- 13
3
votes
0
answers
1k
views
Backtracking vs Branch-and-Bound
I'm getting a bit confused about the three terms and their differences: Depth-First-Search (DFS), Backtracking, and Branch-and-Bound.
What confuses me:
Stack Overflow: Difference between '...
- 2,350
1
vote
0
answers
31
views
What are all linear extensions of the product order of $\{1, \dots, M\} \times \{1, \dots, N\}$?
Note: I have read somewhere that finding all linear extensions of a partial order is in general a #P-complete problem (which apparently means difficult, and thus no closed form expression), but just ...
3
votes
2
answers
227
views
Examples of Analysis of Branch and Bound Method
I am solving a graph problem, which can be formulated as an integer programme. Based on computer experiments, it seems that the branch and bound method works well. I would like to analyse the running ...
- 31
0
votes
0
answers
863
views
How to draw flowchart for if condition within nested loops?
Please find my program logic as below :
Please find my flowchart for the above program logic as below:
My superior asked me correct the flowchart. But I couldn't identify my mistakes.
Please guide ...
- 111
2
votes
0
answers
175
views
How to prune branches in a branch-and-bound solution for Flow Shop Scheduling?
I am implementing a Branch-and-Bound algorithm to find the optimal solution for the Flowshop Scheduling Problem, but I am stuck on the optimization phase, here is a rundown of the problem and what I ...
- 121
1
vote
1
answer
73
views
A problem to maximize the number of edges in a cycle while minimizing the total weight
I encountered the problem below and the only solution I came up with is branch and bound like that is used in TSP and I don’t think the bound I used is good enough. Are there any better idea on this?
...
- 185
0
votes
0
answers
67
views
Branch and bound Dual Gap
Let's suppose we want to solve the knapsack problem using the Branch and Bound algorithm.
I know that the algorithm ends when the optimality gap is = 0. However i have not understood how the dual ...
- 133
1
vote
1
answer
140
views
Shift Organization algorithms (Constraint Programming + Marriage problem)
I want to assign people to cover shifts considering a set of constraints and preferences. Here's the problem definition:
Daily shifts must be covered by workers, who are divided in three groups:
...
- 121
1
vote
0
answers
96
views
A question on analysis of the time complexity of a recursive branching algorithm
I'm reading papers on algorithms of maximum independent problem and the basic recursive branching rules is as follows:
Let $G(V,E)$ be an $n$-node undirected, simple graph without loops, and $\...
- 642
2
votes
1
answer
85
views
Branch & Bound: Avoiding equivalent solutions
There is a certain family of typical branch & bound problems in which we have to put $n$ objects into $m$ indistinguishable bags.
Usually solutions are represented by $n$-size vectors in which $V[...
1
vote
0
answers
29
views
Exploiting solution property in MIP
I am having to solve integer programming problem that has the following property:
For feasible solution $x$ maps to a large set $S(x)$ or other admissible solutions and I can find the best solution ...
- 51
1
vote
1
answer
69
views
Solving Unary Constraint Satisfaction Problem other than branch and bound
I am solving a problem of planning a meal, where I need to fulfill requests such as "create a two-dish meal that MUST have at most 2g of fat, the first dish MUST have 400kcal and SHOULD have at least ...
- 113
7
votes
1
answer
236
views
Branch and bound for minimum linear arrangement
I am trying to solve this branch and bound problem but I could not come up with any approximate cost function which is better than the cost.
Let's say $G$ is a graph of $n$ nodes $\{1, 2, 3, \ldots , ...
0
votes
1
answer
4k
views
Is there Any difference between dynamic programming vs branch-bound vs delayed column generation
I was reading about cutting stock problem
https://en.wikipedia.org/wiki/Cutting_stock_problem , this is best solved using dynamic programming but wiki page mentions 2 other techniques names Branch-...
- 101
3
votes
1
answer
55
views
Branch and Bound - Transform a into b
I'm trying to design an algorithm which will accept two natural numbers: a and b.
Its purpose is to get b from a by making the following operations: *3 and /2.
For example, if a = 10 and b = 7, then:
...
- 131
1
vote
0
answers
498
views
Solving a Knapsack problem with a special structure
I have a set of $N$ items to fill a knapsack with maximum capacity
$W$ and the maximum number of items that the knapsack can carry is $N_{m}$ items. The problem can be formulated as following:
max $\...
- 41
3
votes
0
answers
100
views
Branch and Bound running time and golden ratio
This is a follow up question to When does Branch and Bound exactly stop giving solutions for the bin packing problem
After testing many instances I found out that when r = V / Vtotal <= ϕ (Golden ...
- 41
1
vote
0
answers
447
views
When does Branch and Bound exactly stop giving solutions for the bin packing problem
I wrote a branch and bound algorithm for the bin packing problem and now I would like to know when exactly it stops giving solutions in a polynomial time.
I have N items (each item i has a volume Vi)...
- 41
1
vote
1
answer
106
views
Matching a set of paths to an incrementally generated graph
I am working on an approximate matching problem, where I have a set of paths in an unknown graph (A) and a partial graph (B), where B is generated incrementally during the matching process (and can be ...
- 111
4
votes
1
answer
829
views
Making a branch-and-bound algorithm more efficient for a large input
I am trying to implement the branch and bound algorithm to solve the knapsack problem (in the Coursera discrete optimisation course).
I tried implementing dynamic programming first, and that worked ...
- 657
2
votes
2
answers
14k
views
How to find the Branch factor of 8 Puzzle
I would like to know how to find the average branching factor for 8 puzzle.While referring Artificial Intelligence by George F Luger it says that:
Suppose,for example we wish to establish the ...
- 339
2
votes
1
answer
908
views
Can the effective branching factor be negative?
I've implemented A* algorithm in Python, after that I calculated the effective branching factor $ B^* $
$$ T+1=1+B^*+(B^*)^2+\dots +(B^*)^L$$
where $T$ is the number of expanded nodes.
My question ...
- 121
1
vote
1
answer
126
views
How does the Vertex Cover algorithm by Chen et al find its tuples?
I'm still fighting with the aforementioned paper "Improved upper bounds for vertex cover" by Chen, Kanj, Xia (PDF kindly provided by Yuval Filmus).
My current problem is that it's specified that the ...
- 75
2
votes
1
answer
1k
views
Traveling Salesman: how to use a lower bound?
Let me preface this question by giving some helpful background material.
I'm trying to solve the traveling salesman problem using branch and bound. Concretely, for a partial solution, I'm using the ...
- 161
3
votes
0
answers
430
views
Trying to understand the Gilmore-Lawler lower bound
For a class project we're developing a software that solves a common optimisation problem. After some research we've found out that our problem is called QAP (Quadratic Asssignment Problem) and the ...
- 327
11
votes
3
answers
8k
views
What is the difference between bounding and pruning in branch-and-bound algorithms?
Could anybody please explain what the difference between "bounding" and "pruning" in branch and bound algorithms is?
I'd also appreciate references (preferably books), where this distinction is made ...
- 2,350
10
votes
2
answers
13k
views
Branch and Bound explanation
I have a test about the branch and bound algorithm. I understand theoretically how this algorithm works but I couldn't find examples that illustrates how this algorithm can be implemented practically. ...
- 321