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
1 vote
1 answer
52 views

Connections between Bounds in MIPs

we are currently learning about MIP/MILP minimization at university and have become familiar with the branch-and-bound algorithm. Unfortunately, the relationship between upper bound, lower bound and ...
Vv J's user avatar
  • 19
0 votes
0 answers
43 views

Local Branching in Branch-And-Price

Is it somehow possible to apply local branching in branch-and-price? In branch-and-bound it is easy to add a constraint that allows at most k decision variables to change compared to a given solution. ...
GeoRie's user avatar
  • 1
2 votes
1 answer
147 views

Why would a solver stay on node 0 and still improve the gap?

I understand how exploring the Branch-and-cut tree would help improve the best bound known and the incumbent of a MILP, however, on some instances that I deal with, my solver (Gurobi) seems to keep ...
JKHA's user avatar
  • 679
1 vote
1 answer
83 views

How to Set Up an Optimization Problem Like the 0/1 Knapsack

I'd like some help in understanding and setting up (what may be) an optimization problem that has some similarities to the 0/1 knapsack problem. In this problem the items are a given number of words (...
davypough's user avatar
  • 113
2 votes
0 answers
81 views

Branching the product of binary and continuous variable in Gurobi

I have a binary variable (X) multiplying a continuous variable (Y). I know I can linearize by adding an auxiliary variable (I have that model working), but I now want to do my own branching in the ...
orpanter's user avatar
  • 517
3 votes
1 answer
192 views

Reoptimization with GLPK in Julia/JuMP

I've been looking everywhere, and I can't seem to find any information on whether GLPK can do successive optimizations on the same model, on which we add a constraint at each iteration. More ...
Breizhen's user avatar
4 votes
1 answer
370 views

How do we branch a Cutting Stock problem using Branch and Price?

I'm sure this is a straightforward question, but since I started learning integer programming recently this isn't clear to me. Consider solving a 1 dimensional cutting stock problem using delayed ...
133crem's user avatar
  • 41
7 votes
1 answer
169 views

Name of graph algorithm arising while using the Ryan Foster Branching

I'm using the Ryan-Foster branching in my Branch and Price algorithm for a pickup and delivery problem, but I'm having trouble keeping track of all the pairs as I go down the search tree. Let's say ...
Victor Hugo's user avatar
4 votes
1 answer
187 views

Bounding function for branch-and-bound in game tree search

The scenario is a game where each round you can buy or sell farms that make a set profit each round. I thought about applying branch-and-bound to a game tree, where each node represents the game state ...
qwr's user avatar
  • 141
4 votes
1 answer
244 views

Reduce optimality gap and get a solution faster

I have a maximization problem that I know that the maximum value of the objective function should be 6000. When solving the problem using Xpress, I end up on something like the following: ...
christouandr7's user avatar
2 votes
1 answer
47 views

Objective value estimate for branches I create in Cplex

I' implementing custom branching heuristics for Cplex in python. I have a way to choose a (binary) variable to branch on, so use the following code to create two branches from BranchCallback (...
Elena's user avatar
  • 251
2 votes
2 answers
200 views

A branch-and-bound algorithm for number partitioning

I am working on a branch-and-bound algorithm for number partitioning, similar to Complete greedy algorithm. The input is a list of positive integers and an integer $k$; the output is a partitioning of ...
Erel Segal-Halevi's user avatar
5 votes
1 answer
128 views

Changing a parameter while branching in SCIP

I use pyscipopt. I know how to add constraints while branching using handlers (kind of), but now I want also to change some parameters. I imagine is similar, but couldnā€™t found an example. What I want ...
orpanter's user avatar
  • 517
3 votes
1 answer
812 views

Solving a MIP by Relaxation

I have tried to understand the method of relaxing an integer program. I am in the process of implementing and solving a MIP for the FJSSP. For this I use the python-MIP package to solve it. From my ...
user18609205's user avatar
4 votes
0 answers
352 views

CPLEX Python: Current subproblem model in branch and bound

I have an MILP problem and use CPLEX (Python interface). I am working on user heuristics for branching in the branch-and-bound procedure. With HSCallback I managed to get the information about the ...
Elena's user avatar
  • 251
7 votes
1 answer
190 views

What insights/info can be gathered from visualizing the Branch & Bound tree

What insights/info can be gathered from visualizing the Branch & Bound tree. Some commercial solvers (FICO Xpress) don't seem to provide any API to readily visualize the tree. It has to be ...
user3711946's user avatar
6 votes
1 answer
145 views

Strong branching scores when objective function is constant

I have a MILP feasibility problem, so the objective function is constant (0). I have read that strong branching scores measure changes in the objective value. So my question is, what would be the ...
Elena's user avatar
  • 251
2 votes
3 answers
175 views

Warm starting ideas for iteratively solving a model with a few additional constraints

I'm trying to solve a MILP model iteratively, and at each iteration a few constraints are added to the problem that cut off the previous optimal solution. I'm trying to figure out ways to implement a ...
jackson's user avatar
  • 29
2 votes
1 answer
328 views

Strong branching

Within B&B when it comes to select variables to branch on, I can use the concept of "strong branching". The optimizer, in my case CPLEX, then performs branching on variables it selects. ...
Clement's user avatar
  • 2,224
9 votes
1 answer
289 views

Odd behavior in the branch bound and price algorithm with column generation

I have two questions on branch-bound-and-price. Why does it sometimes fail? For instance, the paper by Dabia et al shows results where the proposed algorithm fails for some cases. The paper does not ...
Dr. Soomin Woo PhD's user avatar
7 votes
1 answer
428 views

Data structures for branch and bound: Efficiently finding the branch node vs. efficiently fathoming

I am implementing a branch and bound algorithm for the knapsack program that is essentially identical to the one described here. I am trying to decide on the optimal data structure to store the set of ...
Max's user avatar
  • 544
1 vote
1 answer
98 views

Can branch and bound be defined as a method to search a non-convex solution space which uses linear programming models to guide the search?

Can branch and bound be defined as a method to search a non-convex solution space which uses linear programming models(and solving them) to guide the search?
gmn's user avatar
  • 632
7 votes
1 answer
984 views

Is "Branch and Bound" better than Evolutionary Algorithms?

I have been trying to find examples of major research studies examining the properties and performance of the "Branch and Bound" Algorithm compared to "Evolutionary Algorithms". ...
stats_noob's user avatar
  • 1,831
5 votes
1 answer
842 views

CPLEX gives different solutions of MILP every run

I am solving a mixed-integer (binary) linear problem using CPLEX as a solver (branch-and-bound method). But I encountered the following issue. Each run I get a different solution at a different node ...
errenmike1806's user avatar
3 votes
1 answer
738 views

B&B hot and warm starting

In a branch and bound algorithm, what is the difference between hot and warm starting and what kind of information does each of them require to store in memory? Otherwise, for the hot starting, what ...
O. Sd's user avatar
  • 65
1 vote
2 answers
279 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 ...
vp_050's user avatar
  • 169
2 votes
1 answer
132 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 ...
worldsmithhelper's user avatar
2 votes
0 answers
81 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. ...
worldsmithhelper's user avatar
9 votes
2 answers
207 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 ...
Vicent's user avatar
  • 191
4 votes
2 answers
314 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 ...
worldsmithhelper's user avatar
5 votes
1 answer
189 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?
mcek's user avatar
  • 45
2 votes
0 answers
109 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 ...
SHUVABRATA CHAKRABORTY's user avatar
7 votes
3 answers
1k 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 ...
user3680510's user avatar
  • 3,655
4 votes
4 answers
478 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 ...
Clement's user avatar
  • 2,224
13 votes
1 answer
972 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 ...
A.A's user avatar
  • 233
2 votes
2 answers
854 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 ...
SHUVABRATA CHAKRABORTY's user avatar
4 votes
3 answers
2k 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 ...
newbie's user avatar
  • 81
12 votes
3 answers
3k 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 (...
Makis Karasavvidis's user avatar
1 vote
1 answer
316 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 ...
User123456789's user avatar
7 votes
1 answer
236 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 ...
David M.'s user avatar
  • 2,077
8 votes
1 answer
730 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 ...
VincFort's user avatar
  • 183
5 votes
2 answers
166 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 ...
Math is fun's user avatar
16 votes
4 answers
5k 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 ...
rasul's user avatar
  • 2,140
17 votes
2 answers
3k 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 ...
Djames's user avatar
  • 1,143
10 votes
3 answers
987 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 ...
Austin Buchanan's user avatar
11 votes
4 answers
409 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 ...
ydubey7's user avatar
  • 579
9 votes
1 answer
319 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, ...
Skander H.'s user avatar
  • 2,139
12 votes
3 answers
5k 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 ...
A.Omidi's user avatar
  • 8,812
14 votes
1 answer
752 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 ...
Oguz Toragay's user avatar
  • 8,642
8 votes
2 answers
144 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?
Majid's user avatar
  • 366