×

The group-theoretic approach in mixed integer programming. (English) Zbl 1187.90004

Jünger, Michael (ed.) et al., 50 years of integer programming 1958–2008. From the early years to the state-of-the-art. Papers based on the presentations at the special session at the 12th combinatorial optimization workshop AUSSOIS 2008, Aussois, France January 7–11, 2008. With DVD. Berlin: Springer (ISBN 978-3-540-68274-5/hbk; 978-3-540-68279-0/ebook). 727-801 (2010).
Summary: 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.
For the entire collection see [Zbl 1181.90003].

MSC:

90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C11 Mixed integer programming

Software:

FEASPUMP; MIPLIB
PDFBibTeX XMLCite
Full Text: DOI