Integrality gaps for Sherali-Adams relaxations.
Moses CharikarKonstantin MakarychevYury MakarychevPublished in: STOC (2009)
Keyphrases
- lp relaxation
- mixed integer
- linear programming
- linear program
- message passing
- feasible solution
- linear programming relaxation
- knapsack problem
- optimal solution
- integer programming
- energy minimization
- integer program
- lower bound
- valid inequalities
- mixed integer programming
- np hard
- global constraints
- cutting plane
- convex hull
- belief propagation
- solution quality
- lot sizing
- semidefinite
- objective function
- column generation
- maximum a posteriori
- linear systems
- mathematical model
- sufficient conditions
- graph cuts
- graphical models
- probability distribution
- search algorithm
- real time
- extreme points