# Tag Info

### Dual bounds of integer programming problems

The notions of dual bound and primal bound originate a bit more generally, I think. We typically call an (iterative optimization) algorithm primal when it maintains a feasible solution in every ...
• 5,809
Accepted

### Branch and Bound Implementation

Read the ph.d. thesis of Tobias Achterberg where he describes the solver Scip. Have fun.
• 2,536
Accepted

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

Great question. You might be interested in this paper here: Learning MILP Resolution Outcomes Before Reaching Time-Limit by Martina Fischetti, Andrea Lodi, and Giulia Zarpellon. They don't exactly ...
• 5,809
Accepted

### Branch and Price algorithm is exact?

To answer your question, it is good to have in mind the following concepts: Dantzig-Wolfe decomposition : in essence, this is a change of variables. The initial variables are expressed as a convex ...
• 10.4k
Accepted

### CPLEX gives different solutions of MILP every run

There are a number of decisions CPLEX makes that can be affected by "randomness". In some cases, CPLEX is actually using a random number generator to make decisions (such as breaking ties). ...
• 31.1k
Accepted

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

If your outcome is confirmed by 10 runs with different random seeds (or 10 permutations of the input) on different instances of your problem, then you are facing a (rare) case where the default cuts ...
• 1,616

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

You could try changing the parameter mipfocus to 2 or 3 (https://www.gurobi.com/documentation/9.0/refman/mipfocus.html) in order to let Gurobi focus more on improving the bound or proving optimality. ...
• 3,487

### Branch and Bound Implementation

What makes any branch-and-bound implementation tick is the heuristics that accompany the algorithm, not branch-and-bound itself. I start by explaining branch-and-bound to frame why we need the ...
• 11.2k

### Branch and Bound Implementation

Check COIN-OR ALPS code (in C++) and Yan Xu's dissertation for explanation. He explains a scalable parallel branch and bound algorithm and presents experiments solving Knapsack instances with up to ...
• 101
Accepted

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

In Cplex, try the following: run it once with a node or time limit, then change the search strategy, remove the node/time limit and rerun the solver. This should work also in command mode. The ...
• 1,616

### Is "Branch and Bound" better than Evolutionary Algorithms?

First of all, evolutionary algorithms do not solve optimisation problems. They provide feasible solutions (if you are lucky) often with no measure of the quality of the solution returned - hence they ...
• 5,445

### Do solvers use GUB/SOS1 branching?

If you accept non-commercial solvers too, then SCIP seems to have it. From the link: constraints/sos1/branchingrule to decide whether to use neighborhood, ...
• 5,756

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

If you have a recent enough version of Gurobi, there is a tuning tool that tries to find better parameter sets than the default settings. For best results, run it for a while (at least overnight) and ...
Accepted

### Diving heuristics in branch and bound

Diving heuristics are primarily used to find feasible points, and are more common in problems with integer variables. Diving heuristics go down some branch of the tree until they (i) hit ...
• 11.2k

### What expresses the efficiency of an algorithm when solving MILPs

I agree with Erwin's comment about heuristics and strong branching. When comparing algorithms or models, I would lean toward compute time, with a few caveats: they would have to be tested on the same ...
• 31.1k
Accepted

### How do Quadratic Programming solvers handle variables without bounds?

Unless we can derive bounds during presolving, the standard way is to set a default variable range instead (e.g. $\pm1.e16$) so that we can generate the McCormick constraints. There are numerical &...
• 11.2k

### B&B hot and warm starting

In general, the definition of what is a warm start or hot start (or "jump start") depends on the actual solver. Different solvers allow different kind of hot/warm starts and may call things ...
Accepted

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

It is not possible, and the reason is that for them to give you the dual, they also need to give you the binding cutting planes at each node. Much of Gurobi's (and CPLEX's as well) magic relies on ...
• 1,519
Accepted

MINTO has not been updated in many years. It was innovative in its day, but most of its ideas like fractional cuts and presolve were incorporated years ago into commercial MILP solvers like CPLEX and ...

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

There can be many reasons why a branch-cut-and-price algorithm fails to solve an instance to optimality in a reasonable time. A large primal-dual gap because a heuristic solution is absent or of a ...
• 1,244

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

In addition to the above answers: It depends on what you want from the MIP-run. If you want to your run to find feasible solutions quickly, then keep ...

### What expresses the efficiency of an algorithm when solving MILPs

Obviously, the only universally valid (but little useful) answer is: it depends. One reason is that, as mentioned in other answers, implementation has a huge impact on practical performance. That ...
• 3,333
Accepted

### Do solvers use GUB/SOS1 branching?

I found in the IBM website that: CPLEX automatically converts SOS1 constraints on binary variables into a regular set packing constraint(source). On page 80 of this presentation by Jeff Linderoth, it ...
• 8,340

### How do Quadratic Programming solvers handle variables without bounds?

Besides simply adding a large bound (which can cause numerical issues and lead to poor branching) or presolve from constraints involving the unbounded variable, the solver might be able to derive ...
• 1,672
Accepted

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

Years ago I wrote an application that could visualize branch and bound trees. The tree was depicted on a scrollable canvas. You could zoom in and out and move similar to navigating Google maps. No ...
• 3,066
Accepted

• 2,050

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

If all of the unknown variables are required to be integers, then the problem is called an integer programming (IP) problem, if only some of the unknown variables are required to be integers, then the ...
• 2,052