# Verifying optimality of heuristic solutions

Suppose that we have an mixed-integer linear optimization problem and we obtain a solution using a heuristic. How can one check 1) whether this solution is optimal and 2) how difficult is it to do so?

My question is motivated by an instance of CVRP. I have seen many different metaheuristics that all converge to the same solution on this instance, so I'm wondering if we can verify whether the solution is optimal or not.

One naive way I can think of is to warm-start the MILP with the found solution, but I'm particularly interested in more advanced strategies.

• For the particular case of CVRP, the state-of-the-art exact solver is VRPSolver vrpsolver.math.u-bordeaux.fr you can try to provide it the best known solution and solve the instance with it Jul 19, 2022 at 10:12

Generally, the only way to prove that a given solution is optimal is to obtain a valid lower bound (assuming minimization) that matches the incumbent solution (with $$\epsilon$$ tolerance, to be specified by the user).