3
$\begingroup$

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 existence. Thank you for the help.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

I found this one pretty good:

http://www.cs.princeton.edu/courses/archive/spr05/cos598B/liftproj.pdf

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .