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 
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 ubb_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 ubb_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 ubb_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 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
