How does a solver generally know whether a solution is optimal?

Question

I was wondering how does the solver for a MILP determine whether a solution is optimal. I am having a hard time to believe that the solver actually tries all solutions, since in some cases I have over 100 variables and a significant amount of constraints and the solver can solve it in matter of minutes.

So suppose, the search space using a "dumb" brute force method is $2^{100}$, does branch and bound together with the cutting plane method really decrease the space needed to search to such a small amount that it can conclude within minutes whether the solution is optimal?

If not, (which I think is the case), how do solvers generally determine whether a solution is optimal?

Answer 1

I am having a hard time to believe that the solver actually tries all solutions

Indeed, they typically do not explore the whole search space (though it's possible to build problematic instances where they would).

MILP solvers will use a combination of tools to do so, under the umbrella of the branch-and-cut paradigm (B&C is basically branch-and-bound with cutting planes). In the rest of my answer I assume basic familiarity with branch-and-bound schemes.

First, presolve will typically reduce the size of the problem, by eliminating variables, fixing some, aggregating some constraints, finding symmetries, etc. For instance, if your problem has a constraint of the form $$ x + 3y \leq 2 $$ for $x, y$ binary, then you can already set $y$ to zero (otherwise the constraint is automatically violated). Doing this kind of reductions can significantly reduce the search space.

The rest of the proof lies in the branch-and-bound tree. Imagine a problem with $100$ binary variables, which would give an exploration tree of $2^{100}$ leaves. A branch=and-bound algorithm will cut portions of that tree using various rules, thereby avoiding the need to explore it all.

There are mainly 2 ways of doing so:

• showing that a node in the tree (and thus all of its children) does not contain any feasible integer solution
• showing that a node in the tree (and thus all of its children) does not contain any optimal integer solution

Cutting planes

Cutting planes naturally restrict the search space. Assume that, at the current node, a binary variable $x$ takes value $0.5$, and that you find a valid cut $x \leq 0.6$.

Then, you know that the branching decision $x =1$ will result in an infeasible problem: you can prune the corresponding node, and all of its children. The earlier you can do so, the bigger the savings. This is why most of the cuts are typically generated at the root node of the tree.

Pruning by bound

Assume you have a feasible solution to your problem, and its objective value is $100$. Now, assume that, at the current node, the linear relaxation has an objective value of $110$.

Then, any integer point (if any) that would be obtained from any of the current's node children, would have an objective value of at least $110$: none of them can be optimal, and you can discard the node. Again, the earlier you can do that, the better.

Note that better linear relaxation provide better bounds, and there allow to discard nodes earlier, which speeds up performance. Cutting planes also improve the linear relaxation, thereby providing tighter bounds, which also helps to prune nodes faster.

Other tricks

The two techniques outlines above are, as far as I know, the most generic & common ones to prove optimality in an MILP; though not the only ones.

Other techniques include:

• reduced-cost fixing, which allows one to prove that a variable $x$ must take a certain value in any integer-optimal solution
• symmetry detection, which allow to discard portions of the search tree by showing only a small part needs to be explored for correctness
• integrality of the objective: if all variables are integer, and all objective coefficients are integer, then the optimal value must be integer. So, if you have a solution with objective value $10$, and a lower bound of $9.5$, you know you have the optimal. Obviously this does not hold for the mixed-integer case.

Answer 2

Optimality implies that a proof was constructed that proves there does not exist a better solution than the best feasible solution found. A brute force search does indeed give you a (rather long) proof. However, in many settings you can find shorter proofs than enumerating all possible cases. For example, when finding a shortest-path in a fully connected graph, we have better approaches than to enumerate all $2^{|V|}$ simple paths.

Typically, proving optimality can be done as follows: when you have a proof for a lower bound on the solution value and a proof for an upper bound on the solution value with equal bounds, you know the optimal solution value. If you have found an actual solution that has this solution value, you have an optimal solution.

If we assume a minimization problem such as the MILP, the upper bound typically corresponds to finding actual solutions: any feasible solution is by itself a proof of an upper-bound on the solution value (it is typically easy to verify the feasibility and objective value of a given solution). Often, the hard part is actually finding a concise proof for the lower-bound. The P vs NP problem actually is closely related to when we can and can not prove efficiently both a lower and upper-bound. For a minimization problem in P ^[1], we know that there always exists a proof of the optimal lower-bound which has a polynomial length in the description of the problem. For NP-hard problems, we generally have no idea how to construct polynomial sized proofs in general for this optimal lower-bound, although for specific problem instances we may end up being lucky that we can find a short proof.

So ultimately the whole thing boils down to how smart you are in finding short and concise proofs in an automated way. For MILP, the LP-relaxation will give you a proof of a lower-bound in polynomial time. If you somehow are able to find a solution/upper-bound with the same solution value, you are happy that your instance admits a short proof - you do not need full enumeration to build a proof, but can use the much shorter LP-relaxation. If there is a gap between your solution/upper-bound and the lower-bound given by the LP-relaxation, you can use case analysis (a common proving technique in mathematics) by partitioning the problem into sub-problems, hoping that these sub-problems can provide you with better gaps. This is ultimately what branch-and-bound does when you interpret it's workings as a proving-technique. In that context, the techniques mentioned by mtanneau's answer are basically smarter ways to perform (or even avoid) this case-analysis.

Often, a MILP solver just spends a lot of time trying to bring the proof for the lower-bound and the upper-bound close enough together to argue that the solution that was found is optimal. It can perfectly happen that the solver finds the optimal solution in a second, but needs hours to prove that it is actually optimal since the gap is not closed.

---

^[1] I might be a bit sloppy here since the P vs NP theory is mostly concered with decision problems rather than optimization problems, but for problems in P it should not really matter which type of problem you have.

Answer 3

This depends on your definition of "optimal". Generally speaking, a solution is optimal iff it satisfies the KKT conditions for optimality. In that sense, finding a KKT point is relatively simple, and proving that a given point satisfies (or not) KKT is as trivial as evaluating a system of equations.

If the problem is mixed-integer, the concept of optimality vanishes because, in the general case, integer feasible points will not necessarily satisfy KKT. In that case, we refer to a solution as optimal simply if it's integer feasible, even though the proper term is "feasible".

Going by the body of your question, I suspect you refer to "globally optimal" solutions, as in proving that an optimal/feasible (for MI) point is the best. This is the domain of deterministic global optimisation solvers and the main algorithm is branch-and-bound, although different algorithms exist for special cases (e.g., QP Diving for convex MINLP).

In order for a deterministic global optimisation solver to work well we need to implement literally thousands of algorithms, including:

• Primal heuristics to find locally optimal points
• Domain reduction techniques
• Problem reduction techniques
• Branching heuristics
• Techniques to generate multiple types of convex relaxations
• Continuous and integer cuts
• Symbolic reformulation techniques, usually to symbolically transform the problem to an easier problem class
• Techniques to eliminate singularities from the problem

The reason we can prove that a solution is globally optimal, even for non-convex problems, is that the techniques we use to generate the convex relaxations provide theoretical guarantees that the lower bounds (if we are minimising) we obtain will improve if the domain is reduced, which is why we use branch and bound. After creating enough nodes, we are left with a lowest lower bound (across the entire branch and bound tree) that is within an arbitrarily small tolerance of the best local solution/feasible point we have found so far. This means that this is literally the best possible value that can be achieved, ergo it is globally optimal.

For MILPs it's a very similar concept, MILP solvers relax integrality and solve that as their relaxation. When the worst value of the relaxed problem is within a tolerance of the best integer solution found so far, global optimality is proven.