9

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.

Leon Lan
  • 185
  • 1
  • 8
  • 2
    For the particular case of CVRP, the state-of-the-art exact solver is VRPSolver https://vrpsolver.math.u-bordeaux.fr/ you can try to provide it the best known solution and solve the instance with it – fontanf Jul 19 '22 at 10:12

1 Answers1

10

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

To my knowledge, the only way to achieve such a lower bound is by using a branch-and-bound based solver (Gurobi, CPLEX, SCIP, Xpress, MOSEK etc.). Since you already have a (very) good solution, I would increase the intensity of the cutting plane generation (in Gurobi, this is controlled by the Cuts parameter) in order to focus more on the generation of hopefully effective cuts. In Gurobi, you can also set the MIPFocus parameter to 2, which tells Gurobi to focus on the lower bound.

I think the other solvers have similar parameters, but I am not familiar with them as I work for Gurobi.

Richard
  • 3,459
  • 7
  • 19
  • 3
    In addition to this, I would be tempted to switch the solver to depth-first search, since we are tentatively assuming that the starting solution is optimal and thus the primal bound is unlikely to improve. – prubin Jul 18 '22 at 15:22