27
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 ...
- 5,909
20
votes
Accepted
Branch and Bound Implementation
Read the ph.d. thesis of Tobias Achterberg where he describes the solver Scip.
Have fun.
- 3,046
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 ...
- 5,909
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 ...
- 12.9k
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). ...
- 37.9k
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 ...
- 1,656
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.
...
- 3,635
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 ...
- 11.9k
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 ...
- 101
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 ...
- 1,656
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 ...
- 6,352
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, ...
- 5,864
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 ...
- 91
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 ...
- 11.9k
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 ...
- 37.9k
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 &...
- 11.9k
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 ...
- 448
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 ...
- 1,549
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 ...
- 196
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 ...
- 1,394
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 ...
- 668
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 ...
- 4,068
7
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 ...
- 3,396
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 ...
- 8,622
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 ...
- 1,702
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,.....
- 12.9k
6
votes
Bounding function for branch-and-bound in game tree search
A classical branch-and-bound is an algorithm used to prove optimality. In the end, all nodes have been explored. The bound is exact and is a critical component of the algorithm.
What you are looking ...
- 2,495
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 ...
- 2,080
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 ...
- 2,098
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 ...
- 37.9k
Only top scored, non community-wiki answers of a minimum length are eligible