The Group-Theoretic Approach in Mixed Integer Programming

Jean-Philippe P. Richard () and Santanu S. Dey ()
Additional contact information
Jean-Philippe P. Richard: University of Florida, Department of Industrial and Systems Engineering
Santanu S. Dey: Université Catholique de Louvain, Center for Operations Research and Econometrics

Chapter Chapter 19 in 50 Years of Integer Programming 1958-2008, 2010, pp 727-801 from Springer

Abstract: 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.

Keywords: Mixed Integer; Valid Inequality; Group Problem; Group Relaxation; Nonbasic Variable (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-68279-0_19

Ordering information: This item can be ordered from
http://www.springer.com/9783540682790

DOI: 10.1007/978-3-540-68279-0_19

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().