# Questions tagged [branch-and-bound]

The tag has no usage guidance.

25 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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? ...
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 ...
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: ...
75 views

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 ...
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 ...
161 views

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 ...
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)...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...