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
0
votes
2answers
38 views

Branch and bound method for solving non-convex integer non-linear multi-objective optimization problem?

Following are the characteristics of my problem: Objective function: two non-linear functions and one linear function Decision variable: two integer variables ($X_1$ and $X_2$) Constraint: three (two ...
2
votes
1answer
72 views

Suggestions how to get access to MINTO MILP solver?

I came across the MINTO MILP solver today. A solver i wasn't aware of or at least had not paid attention too. While development seem to have stopped two decades ago however i still wouldn't mind ...
2
votes
0answers
74 views

What if anything do linear relaxations of "nearby" MILP nodes tell us about other MILP nodes

Assume we are given MILP where $y \in (\mathbb{R}^+)^n$, $x_1, x_2 \in \{0, 1\}$ are the integer variables. It is obvious that this problem when solved via branch and bound has a 2 deep b&b-tree. ...
9
votes
2answers
175 views

MINLP involving integrals, sparse matrices and CDF of random variables. Best environment?

INTRODUCTION My research often involves solving MINLP problems with few constraints (usually two) and not many variables (say between one and three integer ones, and between one and five real-valued ...
4
votes
2answers
121 views

When solving many MILPs how to assign CPU cores to solver instances?

Let's say I have an 16 core machine and many roughly equally hard MILP problems and enough RAM. The latency of solving doesn't matter. With how many cores should I start solvers on to maximize ...
5
votes
1answer
91 views

Breadth First Search vs. Best First Search

What is the main difference between Breadth First Search and Best First Search? What is meant by saying Breadth First Search requires previous knowledge?
2
votes
0answers
65 views

How to implement CPLEX user cuts using CPXaddusercuts in C API?

I am trying to use CPXaddusercuts to add cutting planes, which have not been violated yet but are likely to be violated as we go down the branch & bound tree, to the list (pool) of constraints. As ...
7
votes
3answers
968 views

How do Quadratic Programming solvers handle variables without bounds?

Solvers for non-convex QPs generally do the McCormick relaxation of the term $xy=z$ and then do spatial branch and bound. This requires that $x$ and $y$ have given bounds, how do they handle the case ...
4
votes
4answers
442 views

What expresses the efficiency of an algorithm when solving MILPs

What is the appropriate measure to indicate the efficiency of an algorithm\model that solves a MILP through B&B? Is it the number of nodes examined to reach the optimum? the number of iterations ...
11
votes
1answer
213 views

Branch and Price algorithm is exact?

I know that the Column Generation algorithm delivers an exact solution when you are solving a linear programming optimization problem. I want to know that, does this column generation approach deliver ...
2
votes
2answers
192 views

How to use tight upper and lower bounds to get to the optimal value via branch and bound?

I have algorithms that get me a tight upper (UB) and lower (LB) bound to a maximization binary integer program (a routing problem). My formulation is non-compact and requires the addition of sub-tour ...
4
votes
3answers
1k views

Branch and bound algorithm programming code

I want to solve an integer programming problem using the branch and bound method, but I'm having trouble finding the programming code. From what I saw, almost all algorithms use it for traveling ...
10
votes
3answers
914 views

Settings for a faster solution of a MILP (GUROBI, python)

Using GUROBI with python. When solving a MILP, I notice that the incumbent is very early (25sec) at the optimal point but the best bound is so slow to fall (maximization problem) that it takes ages (...
1
vote
1answer
145 views

Branch-and-Price: return gap using SCIP

I implemented a branch-and-price tree in python. I would like to stop the process after 5 hours and return the gap in % between the best integer solution found so far and the optimal solution. How ...
7
votes
1answer
95 views

Gurobi: can you retrieve the dual solution from each node of the B&B tree using callbacks

When solving a MIP with Gurobi, one can use the cbGetNodeRel() function to extract the primal solution to the LP relaxation at each node in the branch and bound ...
7
votes
1answer
351 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
115 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 ...
16
votes
4answers
3k 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 ...
15
votes
2answers
896 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
836 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
152 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
178 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, ...
12
votes
3answers
2k 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
594 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
124 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?