9
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ 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 $\endgroup$
    – fontanf
    Jul 19, 2022 at 10:12

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Jul 18, 2022 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.