MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to find a book or a paper, which explains, how and why the Sherali-Adams relaxation method works. The original paper (1990) is difficult for me to understand. I need a more basic introduction, of which I suspect the existance. Thank you for the help.

share|cite|improve this question
up vote 2 down vote accepted

It isn't clear from your posting whether you're trying to understand:

Why the inequalities generated by the Sherali-Adams procedure are valid?


Why the procedure is complete in the sense that after enough iterations you arrive at the convex hull of the integer solutions of the original integer linear programming problem?

I suppose that you might also be interested in the question of how this can be used in practice.

You should be aware that Sherali-Adams is just one of several "lift and project" schemes based on LP or SDP relaxations that provide a ladder of relaxations of an integer programming problem from the simple LP relaxation up to a relaxation that has only integer solutions as its extreme points.

You might find the following paper by Monique Laurent to be useful in understanding this stuff:

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.