# Knapsack Inequalities Accelerated Benders Decomposition

 1 1 All, Recently I implemented Benders decomposition to one of my MIP problems. And used some acceleration techniques to speed up convergence. I used Knapsack Inequalities as shown by the authors in link text on page 103. They mention that this inequality along with CPLEX help convergence. I am not sure how it works. It would nice if anybody can help me understand this inequality or else provide me with a paper that explains the theory behind knapsack inequalities. Any help is greatly appreciated. asked 20 Nov '14, 18:26 satvad 25●7 accept rate: 0%

 1 If you take the optimality cut and the valid upper bound inequality and rearrange terms such that on the left hand side you have $$y$$ times something, and on the right hand side you have the constants. Then sum the two inequalities and obtain the (valid) inequality $(c+a_i)^Ty\leq ub-b_i$ Then notice if you round down all the coefficients on the left hand side, the entire left hand side becomes smaller (as $$y\geq 0$$). Therefore the inequality $\lfloor (c+a_i)^T\rfloor\leq ub-b_i$ is valid. Now, all coefficients on the left hand side has become integer, and since $$y$$ is also integer we know that the left hand side is integer for all values of $$y$$. Therefore, we can also round down the right hand side, by which we get $\lfloor(c+a_i)^T\rfloor\leq \lfloor ub-b_i\rfloor$. This is called a Chvatál cut (look it up, here the weigths of the two inequalities are equal to 1). answered 21 Nov '14, 03:56 Sune 958●4●14 accept rate: 20% Thank you Sune. So, if I am solving a Max problem and not a Min as shown in the above paper by using the same logic replacing ub with lb and reversing the sign to a greater than holds true? (21 Nov '14, 08:05) satvad Yes. The inequalities would then just be of "greater than" type instead of "less than". And you would round up instead of rounding down. (21 Nov '14, 12:13) Sune
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×190
×71
×35
×13