16

Tobias Achterberg's thesis includes a review of MIP solver technology from around 2009, including branching decisions and node selection.


13

It is a cutting plane, but it is implied by $x_2+x_4\le 1$ and $x_3\le 1$ so not very useful.


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).


11

Since branching rules are crucial for the performance of solvers they are also a very well guarded secret. I can say from experience that some form of reliability branching is sufficient to get a reasonable solver performance (not top of the class though). The devil is in the detail then because there are a ton of different ways of updating the pseudo-costs ...


10

Assuming you are using more than a single thread, then Gurobi performs all work you code in the callbacks with a single thread. All remaining threads process the branch and bound nodes (without doing the callbacks). When your user cuts are added is then determined by some black box magic of Gurobi. To be specific, suppose we have 4 threads. Then, 3 of the ...


8

While lazy constraints must be added each time a node is expanded at a branch-and-bound tree, a solver is not obligated to add user cuts at any point in time; it chooses when to add user cuts. If you want Gurobi to add them immediately, you are better off adding lazy constraints. See here: https://orinanobworld.blogspot.com/2012/08/user-cuts-versus-lazy-...


6

Graph cuts were mainly used in computer vision, where since 2011 deep neural networks have taken over the field. The decline from 2015 on is attributable to a time delay in picking up neural networks. Specifically, graph cuts were used for inferring maximum probable states in Markov Random Fields (MRF), with input costs coming from hand-tuned features. ...


5

This question was also asked and answered on a CPLEX forum and on my blog. Update: The gist of the answer is that when you add a cut in a callback, CPLEX updates the node solution to reflect that cut and then invokes the callback again (still at the same node) to see if you have more cuts to add. To let CPLEX move on to another node, your callback needs to ...


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

Is there a variant of integer programs for which Gomory's cutting plane algorithm demonstrably takes a superpolynomial number of iterations? Yes Definitions: "Superpolynomial time An algorithm is said to take superpolynomial time if $T(n)$ is not bounded above by any polynomial. Using little omega notation, it is $\omega (n^c)$ time for all constants ...


4

You need to use a callback, and CPLEX introduced a new callback system ("generic callbacks") in version 12.8 (I think) while maintaining support, at least for now, for the original callback system ("legacy callbacks"). The details of doing the branching depend in part on which system you use. With legacy callbacks, you create a class that ...


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 ...


3

Note that a different solver might yield a different result. The quality differences between solver, especially between open-source and commercial solvers, are huge. That said, there are problems where cuts, pre-solving, primal heuristics and other features don't help all that much. In some rare cases, as pointed out by Matteo Fischetti, they even hurt ...


2

To add to the linked answers: if the upper bound is obtained by taking a convex relaxation (e.g. a semidefinite relaxation), you could strengthen the formulation by running a cutting-plane method to solve the continuous relaxation and applying the cuts generated from the relaxation before branching. If you do this your initial upper bound should match the ...


2

In addition to the issues it creates (covered by the link @RobPratt provided), it's worth nothing that the upper bound probably contributes nothing to the solver's performance. It will possibly give you a more realistic gap measure (if the solver uses it), but I don't see it guiding the solver's behavior in a useful way. If you want to test this, introduce ...


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