0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.