Abstract
In this chapter, we provide an overview of the mathematical foundations and recent theoretical and computational advances in the study of the grouptheoretic approach in mixed integer programming. We motivate the definition of group relaxation geometrically and present methods to optimize linear functions over this set. We then discuss fundamental results about the structure of group relaxations. We describe a variety of recent methods to derive valid inequalities for master group relaxations and review general proof techniques to show that candidate inequalities are strong (extreme) for these sets. We conclude by discussing the insights gained from computational studies aimed at gauging the strength of grouptheoretic relaxations and cutting planes for mixed integer programs.
| Original language | English (US) |
|---|---|
| Title of host publication | 50 Years of Integer Programming 1958-2008 |
| Subtitle of host publication | From the Early Years to the State-of-the-Art |
| Publisher | Springer Berlin Heidelberg |
| Pages | 727-801 |
| Number of pages | 75 |
| ISBN (Print) | 9783540682745 |
| DOIs | |
| State | Published - 2010 |
| Externally published | Yes |