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

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.

• The question is not clear to me Jan 6, 2022 at 15:58
• 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
– 2022
Jan 6, 2022 at 16:11
• 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 Jan 6, 2022 at 16:20