2
$\begingroup$

I'm struggling with this question for weeks:

What is the main difference between the role of computation lower bounds for exact methods, heuristics, and hybrid of exact and heuristics?

I try to answer that by saying:

Lower bound for exact methods is "an aid tool" to solve the problem but not an independent solution tool. While for heuristics methods, it is "a measuring tool" for the quality of the solution. Is that right?

What about the hybrid of exact and heuristics methods?

I need references to understand the difference.

Improve this question
$\endgroup$
3
  • $\begingroup$ The question is not clear to me $\endgroup$
    – fontanf
    Jan 6, 2022 at 15:58
  • $\begingroup$ I meant, please correct me if I am wrong, for exact method lower bounds and upper bounds used together to prove the optimal solution. Thus LB here is an aid tool to solve the problem. While for heuristic, we estimate the quality of its solution by | solution - lower bound|/ lower bound $\endgroup$
    – 2022
    Jan 6, 2022 at 16:11
  • $\begingroup$ I'm not sure. For example, in constraint programming, there are generally no bound until the end of the search, and just at the end, the algorithm deduces that the current best solution is optimal. On the contrary, in cutting planes, there are no feasible solution until the end of the search, and just at the end, the current infeasible solution that gave the bound becomes feasible and therefore optimal $\endgroup$
    – fontanf
    Jan 6, 2022 at 16:20

1 Answer 1

Reset to default
3
$\begingroup$

I would say that a "best bound" (lower bound if you are minimizing) has essentially the same role regardless of whether the method is exact or approximate: to give you an idea of how close to optimal your current solution is, and what your worst-case risk is if you settle for the current solution. One difference I can see is that it is fairly common to use the gap between the incumbent solution and best bound as a stopping criterion when using an exact solver, whereas I don't recall seeing that done when using a heuristic.

For branch-and-bound / branch-and-cut / branch-and-price type algorithms, the bounds on individual nodes obviously play a role in pruning those nodes and also in steering the algorithm (selecting the next node to explore).

Improve this answer
$\endgroup$

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.