TY - JOUR
T1 - A generalized assignment problem with special ordered sets
T2 - A polyhedral approach
AU - De Farias, I. R.
AU - Johnson, E. L.
AU - Nemhauser, G. L.
PY - 2000
Y1 - 2000
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0000891832&partnerID=8YFLogxK
U2 - 10.1007/s101070000185
DO - 10.1007/s101070000185
M3 - Article
AN - SCOPUS:0000891832
SN - 0025-5610
VL - 89
SP - 187
EP - 203
JO - Mathematical Programming, Series B
JF - Mathematical Programming, Series B
IS - 1
ER -