Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers

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?

or

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:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.2521

share|improve this answer
add comment

Your Answer

 
discard

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.