Questions tagged [branch-and-bound]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
2answers
162 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 ...
0
votes
0answers
47 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 ...
2
votes
0answers
55 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 ...
1
vote
1answer
52 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? ...
0
votes
0answers
40 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 ...
1
vote
1answer
87 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: ...
2
votes
0answers
75 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 $\...
2
votes
1answer
73 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
0answers
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 ...
1
vote
1answer
41 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 ...
7
votes
1answer
161 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
1answer
2k 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-...
3
votes
1answer
47 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: ...
1
vote
0answers
453 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 $\...
3
votes
0answers
82 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 ...
1
vote
0answers
391 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)...
1
vote
1answer
97 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 ...
4
votes
1answer
677 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 ...
2
votes
2answers
8k 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 ...
2
votes
1answer
574 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 ...
1
vote
1answer
102 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 ...
2
votes
1answer
952 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 ...
3
votes
0answers
380 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 ...
7
votes
3answers
5k 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 ...
9
votes
2answers
11k 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. ...