Questions tagged [branch-and-bound]

For questions related to the branch-and-bound method for integer programming problems, which recursively divides the solution space and identifies upper and lower bounds on the optimal objective function value.

Filter by
Sorted by
Tagged with
7
votes
1answer
84 views

Diving heuristics in branch and bound

I am reading about extensions on plain vanilla B&B and heuristics for smaller trees/better branching. I have come across diving heuristics, which on the SCIP site is defined as: A diving ...
5
votes
2answers
78 views

What is the technique of branch-and-bound used in Knitro to solve MINLP?

I am using Knitro to solve an MINLP using branch-and-bound and I want to know about the reference or technique they are adopting to code their algorithm. I know that there are many applications of ...
14
votes
3answers
940 views

Branch and Bound Implementation

Branch and Bound (B&B) is a general solution approach to solve combinatorial optimisation problems. I was wondering how B&B is implemented in practice. Although it may be relevant, but I am ...
12
votes
2answers
137 views

Dual bounds of integer programming problems

I often read in papers when branch-and-X algorithms are used to solve mixed integer programming problems, that the lower bound (in the minimization case) obtained from solving a linear programming ...
10
votes
3answers
707 views

Do solvers use GUB/SOS1 branching?

GUB/SOS1 branching is an old and well-known idea (see for example page 9 of Jeff Linderoth's notes). Is this implemented in commercial solvers these days? The Gurobi documentation mentions SOS1 ...
10
votes
3answers
131 views

Theoretical results on performance of branch-and-bound

Are there any theoretical results on the performance of branch-and-bound, even for a subset of instances of a particular discrete optimization problem? As an example, does there exist a result of ...
9
votes
1answer
120 views

Rules of thumb for using classic methods (e.g. branch and bound) vs. meta-heuristics (G.A, S.A, etc..) for non-convex problems?

Are there any rules of thumb for when to use classical methods like branch and bound, branch and cut, etc...for non-convex problems, vs using meta-heuristic methods like genetic algorithms, ...
11
votes
3answers
606 views

Performance of a branch and bound algorithm VS branch-cut-heuristics

I was trying to solve a moderate scheduling model using an open-source solver. I did two different ways. A) using pure branch and bound algorithm (disable all options). B) using the default setting ...
14
votes
1answer
476 views

Estimation of the size of Branch-and-Bound trees using ML

A short background: A paper [1] published in 2006 intends to show that the time needed to solve mixed-integer programming problems by branch and bound can be roughly predicted early in the solution ...
8
votes
2answers
115 views

How to change the search strategy in a B&B framework, i.e., start with depth first and then continue with best node?

Is there any implementation, code or software, which can switch between search strategies in a B&B framework?