24 votes

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 ...
user avatar
20 votes
Accepted

Branch and Bound Implementation

Read the ph.d. thesis of Tobias Achterberg where he describes the solver Scip. Have fun.
user avatar
  • 2,536
13 votes
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 ...
user avatar
13 votes
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 ...
user avatar
  • 10.4k
12 votes
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). ...
user avatar
  • 31.1k
11 votes
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 ...
user avatar
10 votes

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. ...
user avatar
  • 3,487
10 votes

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 ...
user avatar
10 votes

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 ...
user avatar
10 votes
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 ...
user avatar
10 votes

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 ...
user avatar
  • 5,445
9 votes

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, ...
user avatar
  • 5,756
9 votes

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 ...
user avatar
9 votes
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 ...
user avatar
9 votes

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 ...
user avatar
  • 31.1k
9 votes
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 &...
user avatar
9 votes

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 ...
user avatar
8 votes
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 ...
user avatar
8 votes
Accepted

Suggestions how to get access to MINTO MILP solver?

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 ...
user avatar
8 votes

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 ...
user avatar
7 votes

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 ...
user avatar
7 votes

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 ...
user avatar
  • 3,333
6 votes
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 ...
user avatar
  • 8,340
6 votes

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 ...
user avatar
6 votes
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 ...
user avatar
6 votes
Accepted

Reduce optimality gap and get a solution faster

If my understanding of the problem is correct, the following formulation should be tighter. I am assuming the types of possible bags are predefined. Let $x_i$ be the number of bags of type $i\in \{1,.....
user avatar
  • 10.4k
5 votes

Theoretical results on performance of branch-and-bound

If the problem you are solving is in $P$, I guess you can construct a branch-and-bound algorithm that only produces a polynomial number of nodes, since you can use your polynomial time algorithm to ...
user avatar
  • 2,050
5 votes

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 ...
user avatar
  • 2,052
5 votes

Branch and bound algorithm programming code

If you want to work inside Excel (or LibreOffice), you might look at OpenSolver. Google's OR-Tools includes the CBC solver and the option to use GLPK, SCIP or Gurobi. (Gurobi is commercial software ...
user avatar
  • 31.1k
5 votes

Branch and bound algorithm programming code

Depending on the type of your MIP, there are numerous open-source options: MILP: CBC Convex MINLP: Bonmin Non-convex MINLP: Couenne All of the above: SCIP (free for academics)
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible