The group-theoretic approach in mixed integer programming

Jean Philippe P. Richard, Santanu S. Dey

Research output: Chapter in Book/Report/Conference proceedingChapter

17 Scopus citations

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 languageEnglish (US)
Title of host publication50 Years of Integer Programming 1958-2008
Subtitle of host publicationFrom the Early Years to the State-of-the-Art
PublisherSpringer Berlin Heidelberg
Pages727-801
Number of pages75
ISBN (Print)9783540682745
DOIs
StatePublished - Dec 1 2010
Externally publishedYes

Fingerprint Dive into the research topics of 'The group-theoretic approach in mixed integer programming'. Together they form a unique fingerprint.

Cite this