# Branch and bound Dual Gap

Let's suppose we want to solve the knapsack problem using the Branch and Bound algorithm. I know that the algorithm ends when the optimality gap is = 0. However i have not understood how the dual bound is improved at every step. Can you explain me ? Thanks

• Can you add an easily-accessible reference to the "the knapsack problem using the Branch and Bound algorithm" that explains "gap" and "dual gap"? – Apass.Jack Jan 2 at 20:14
• dual gap is = (upper bound - lower bound) – Jhdoe Jan 3 at 7:47