A generalized assignment problem with special ordered sets: A polyhedral approach

I. R. De Farias, E. L. Johnson, G. L. Nemhauser

Research output: Contribution to journalArticlepeer-review

32 Scopus citations

Abstract

We study a generalized assignment problem that arises in production scheduling in which special ordered sets of type II appear naturally in the formulation. We derive three families of facet-defining valid inequalities, and we show that they cut off all infeasible vertices of the LP relaxation. We also give the complete facetial description for a particular case. We then use the inequalities as cuts in a branch-and-cut scheme, and we report computational results that demonstrate the superiority of branch-and-cut over branch-and-bound on this class of problems.

Original languageEnglish
Pages (from-to)187-203
Number of pages17
JournalMathematical Programming, Series B
Volume89
Issue number1
DOIs
StatePublished - 2000

Fingerprint Dive into the research topics of 'A generalized assignment problem with special ordered sets: A polyhedral approach'. Together they form a unique fingerprint.

Cite this