What do solvers like Gurobi and CPLEX do when they run into hard instances of MIP?

Question

MIP is NP-Hard, so it is possible that an instance is very difficult and has multiple local minima that the search can get stuck in.

With a Metaheuristic Algorithm, the stochastic and approximate nature of the algorithm means that that is a risk we were assuming from the get go. And we are willing to start over if the algorithm doesn't converge towards an acceptable solution.

But with classical solvers like Gurobi or CPLEX, which, if I understand correctly, are deterministic, what happens when they come across such an instance? Do they just stay stuck in the local minima for a really long time and take several days to complete their run? Do they error out after a certain number of trials?

Answer 1

The term "local optimum" is a little misleading here. Assuming your MIP is linear (or at least convex), every local minimum is also a global minimum, so there is no such thing as "getting stuck in a local minimum."

When we say that a (meta)heuristic gets "stuck in a local minimum," we are referring to a local minimum as defined by the search neighborhood. For example: If a "move" in the heuristic involves swapping two model elements (e.g., open one facility and close another), then a local minimum occurs when no move results in a better objective function. But this is not the same as saying that the solution to the MIP is a local minimum, because it's still possible that there are directions in the solution space that lead to improvement.

To put it another way, if you are at a non-optimal point in the solution space in a linear/convex MIP, there must exist a direction that improves the objective. However, this direction might not be a legal "move" for the heuristic, and in that case we say the heuristic is "stuck in a local minimum." In my opinion it's a slightly sloppy use of the terminology.

Now, to your original question, MIPs can still be hard even though the solver doesn't get "stuck in a local minimum." When that happens, CPLEX, Gurobi etc. will keep working at it until one of the termination criteria is met. Those criteria could be a sufficiently small gap between the upper and lower bounds, a sufficiently long CPU time, a sufficiently large number of iterations, etc.

Answer 2

As pointed out by others here, in principle a branch-and-cut based solver can't get stuck, it can just continue until in the worst case it enumerated all integer solutions. Of course that might take forever.

That said, sophisticated solvers have all kinds of tricks to avoid "getting stuck", meaning not having any progress for a long time. One such trick that not many people talk about is restarting the branching phase of the solver. Restarts are mentioned in Tobias Achterbergs thesis in section 10.9, but back then he came (in his context) to the conclusion that they don't work very well. Nevertheless, I know that at least one commercial solver (namely SAS) does use restarts successfully and there are hints in the logs that other solvers do as well.

Restarts are especially good if some variables have been fixed globally (or at least have tightened bounds globally), even if it is not possible to keep some of the search information from the previous attempt to solve the problem, this will lead to a different tree. There is a decent chance that on its second (or 3rd or 4th) attempt the solver will do better or even solve the problem to within the required gap. Note that this is not very elegant or anything but it seems to work in practice.

Answer 3

Gurobi and CPLEX use (very sophisticated) variants of the branch-and-bound algorithm.

In Mixed Integer Programs, there can be both continuous and integer variables. It turns out that the integer variables are the complicating factor: without integer variables, what remains is a Linear Program (LP). LPs are always convex, which implies that every local optimum is a global optimum. Hence, you can never get stuck in a local minimum when solving an LP.

As an example, assume that we have a single complicating integer variable $x$ that is allowed to take values between 1 and 3, that is $x\in \{1,2,3\}$. I will explain how branching can be used to deal with this integer variable (more on bounding later).

First, we ignore the integer requirement, and instead we use $1 \le x \le 3$. We call this the linear programming relaxation. And for good reason! There are no more integer variables, so we are left with an LP that is easy to solve. We solve the LP, and we find that $x = 2.5$ in the current solution.

However, we have not solved the original problem, as $x = 2.5$ is not integer. To continue, we branch. That is, we split the problem in two. Problem 1 requires that $x \in \{1,2\}$ while Problem 2 requires that $x = 3$. Obviously, one of the two contains the optimal solution to the MIP.

In Problem 1, we get the relaxation $1 \le x \le 2$. If we are lucky, solving the LP will give either $x=1$ or $x=2$. If this is not the case, we will branch again into $x=1$ or $x=2$, resulting in Problem 3 and Problem 4. If Problem 2 is feasible, we get a solution with $x=3$. If we have performed all the necessary splits, for all variables, we can compare all MIP solutions that we have obtained, and pick the best one.

Because of how we split the problem, a global optimum is guaranteed to be found. We cannot get stuck in a local optimum: if the integer variables do not yet have integer values, we branch, and if all integer variables have integer values, the remaining LP cannot get stuck.

Then for the bounding part of branch-and-bound. By calculating bounds on the objective value for each of the subproblems, we are often able to tell that a subproblem does not contain a global optimum. In that case, we do not have to branch further, and we can focus on the other subproblems. Bounding is extremely important in practice

Answer 4

All non-trivial MIPs are hard, intuitively because our optimality conditions become integrality conditions.

Finding an integer solution

A common way of doing this is to relax the integer variables to continuous and solve the relaxed problem. This solution will typically be optimal but not integral, in which case we solve a series of problems trying to find an integer solution in the neighborhood of the continuous one. One example of this would be a feasibility pump.

Finding the best integer solution

The most common way to do this is using branch-and-bound. MILP solvers make this look easy sometimes, but it's mostly by educated guessing that any large problem is solved quickly. In branch-and-bound there are 5 elements that vastly affect the convergence rate:

1. Selecting which node to branch on (heuristic)
2. Selecting which variable to branch on (heuristic)
3. Finding a feasible upper bound (heuristic)
4. Quality of lower bounds (deterministic)
5. Domain reduction using constraint propagation/OBBT (deterministic)

As we can see from the list above, three out of five components are heuristics. Therefore, regardless of the quality of a solver, certain problems will be extremely challenging because they don't fit its default heuristics very well. This is why changing the model a bit can help: minor changes can sometimes result in completely different branch-and-bound behaviour.

So what do solvers do if their heuristics don't work?

Usually they just get pwned. Because of the chaotic nature of branch-and-bound it's hard to tell when something isn't working. The algorithm might seem stuck for 2 hours and then it can suddenly converge. There is no way to know conclusively that what we are trying doesn't work, therefore we should try something else. As others have said, restarting is a viable option, but it's hard to pull off correctly for the reason I just mentioned.

Another thing some solvers do is to dynamically change some heuristics, but the pitfall here is that once we have created a bloated branch-and-bound tree using a bad heuristic, the problem is probably doomed anyway so we're better off restarting with a different configuration.

What if the problem is non-convex?

Then it's about 1,000,000 times harder to demonstrate the same level of consistency that MILP solvers do. On top of the above we also need libraries of reformulations (heuristic), combinations of different domain reduction methods (heuristic), specialised structures for representing the problem which change depending on the problem's size (heuristic), we need to chose which of our many heuristics to apply on what problem (metaheuristic), and so on.