# Tag Info

19

Read the ph.d. thesis of Tobias Achterberg where he describes the solver Scip. Have fun.

17

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 iteration. The Ford-Fulkerson algorithm for solving maximum flow is an example where we have a feasible flow in every iteration, or the simplex method, where we have ...

13

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 answer your question but you may see why the question is hard to answer and what partial progress can be made. A priori estimating the tree size is estimating ...

12

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 combination of the extreme points of the polygon defined by the constraints of the problem. Column generation : once this change of variables has been done, you ...

11

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 and heuristics are not needed and actually slow-down the solver (of course this can happen, as the default setting is not perfect in all cases).

10

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 important thing is that you do not change the Mip model between the first and second run (otherwise Cplex will start a new run from the root node). Using similar ...

10

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 2048 cores. You can ignore the parallelization related parts in code and the text if not interested.

9

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 heuristics, but if you are interested in implementation, you can skip to the end. Why branch-and-bound works For simplicity I will assume bisection branch and bound ...

9

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 run it with a few different instances of your problem. Here is some example code you can use to run it. def tune(model, time_limit=-1, trials_per_setting=3): ...

9

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. You can also try to set Cuts (https://www.gurobi.com/documentation/9.0/refman/cuts.html) to 2 in order to let Gurobi be more aggressive with the Cuts. But ...

9

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, bipartite, or SOS1 branching... AIMMS also seems to have a mention of SOS1 branching according to page 9 of this manual.

9

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 hardware, using the same number of cores/threads; they would have to be tested on multiple problem instances; they would have to use the same solver (if ...

9

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 & convergence issues to consider depending on the number that is chosen, so setting smaller bounds might be preferable if we are certain that it's safe from a ...

8

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 their proprietary cutting-planes, many of them unknown to us. So you're right, it is possible, but you will never have them give us that info.

7

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 model.params.MIPFocus=1; if you are not facing difficulty in finding feasible solutions but want to focus on proving the optimality of these solutions, then keep model.params.MIPFocus=2; or if you want your ...

7

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 infeasibility, (ii) hit a pre-specified tree depth, or (iii) find a feasible point. In cases (i) and (ii) the algorithm will backtrack and repeat the diving process down a ...

7

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 being said: No matter which metric you choose, I would look at each approach's scalability w.r.t problem size. There exist various statistical tests & ...

6

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 is mentioned that some noncommercial solvers like CBC and Ip_solve SOS(2) branching while CBC and MINTO equipped with GUB branching.

6

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 bounds by bound-propagation once a feasible solution is available. As an example (assuming you have some bound, otherwise an indefinite problem will be unbounded), ...

5

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 make a perfect prediction which branch to explore first, and produce perfect bounds that allow you to prune away every node in the tree except the ones that lead ...

5

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 problem is called a mixed integer programming (MIP) problem. A cutting-plane method is an optimization that iteratively refines a feasible set and is commonly ...

5

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 with a free academic license.)

5

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)

5

There are several open-source software packages that use branch-and-bound to solve integer programming, for example: GLPK: https://www.gnu.org/software/glpk CBC: https://github.com/coin-or/Cbc

5

For algorithms, hands down number of nodes, assuming you are not solving numerous (MI)LPs/node (e.g. you are not doing strong branching). This is how we evaluate potential when we prototype new algorithms at Octeract. The reason is that the steps performed per node can be optimised in many ways, while the number of nodes we need to explore is purely a result ...

4

Accepted answer from the cross-post: Stop Branch-and-Price tree and return gap You can easily compute this yourself: SCIPgetDualbound will return you the best (global) dual bound, and SCPgetPrimalbound will give you the best primal bound. -Leon Will delete this CW if Leon posts answer here.

4

Knitro offers two variations of branch-and-bound for mixed-integer nonlinear programs. The first (and default method) is a standard branch-and-bound method that solves a continuous nonlinear optimization problem at each node by relaxing the integer variables. The second (the Quesada-Grossmann approach) solves linear programming subproblems at most nodes and ...

4

In open source codes you usually have more flexibility to change the parameter directly compared to commercial solvers. Take SCIP for example where you can program your own node selector rules. You also have tons of parameters to adjust the node selection. CBC offers similar features.

4

I refer you to this question in which I mentioned some of the related papers investigated the performance of the Branch-and-Bound method by estimating the size of the BB tree. The old paper1 by Lai et al. investigated the performance of the parallel BB in which several nodes with least lower bounds are expanded simultaneously. In addition Lobjois et al. in ...

3

Glover and Sörensen (2015) Metaheuristics have been demonstrated by the scientific community to be a viable, and often superior, alternative to more traditional (exact) methods of mixed-integer optimization such as branch and bound and dynamic programming. Especially for complicated problems or large problem instances, metaheuristics are often able to offer ...

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