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's gravatar image

accept rate: 0%

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's gravatar image

accept rate: 20%

edited 21 Nov '14, 03:57

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
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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



Asked: 20 Nov '14, 18:26

Seen: 1,689 times

Last updated: 21 Nov '14, 12:14

OR-Exchange! Your site for questions, answers, and announcements about operations research.