Comments (2)
  • Add a Comment
  • Edit
  • More Actions v
  • Quarantine this Entry

1 PaulRubin commented Permalink

Two thoughts:

1. "If the gap is larger than 0, the smaller the gap the better x is." That's true if you are comparing two feaible solutions with different gaps and the same lower bound. More generally, a smaller gap may indicate a better solution, a tighter lower bound, or both.
2. Customers interested in a "satisficing" solution provide their own stopping criterion ("good enough"), as do customers with a tight time limit ("I can't wait for a better solution"). Other customers, staring at a long search and not needing proven optimality, but also not having a hard time limit, may want some help deciding whether to let the solver keep running or to pull the plug and take the current incumbent solution. That's where a gap estimate becomes useful. This is a problem not only for CP but moreso for metaheuristics. CP will eventually terminate when the solution space is fully explored. Most metaheuristics will chug on forever, even if they're just spinning their wheels.

2 JeanFrancoisPuget commented Permalink

Paul, you are right, the gap can be made smaller by improving the lower bound, which doesn't improve the quality of the feasible solution. It improves the confidence in the value of the feasible solution though.

To your second point, indeed the gap can be used as a stopping criteria. You also point to something else. Constraint Programming (CP) is able to prove optimality when it has exhausted its branch and bound tree. But as far as I know no CP solver today report a gap although it could be done, for instance by reporting as lower bound the lowest bound on the objective across all open nodes. It remains to be seen if this would provide a useful gap compared to what MP provides. I would imagine that for some class of problems (eg job shop scheduling) it could provide strong lower bounds.