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 language | English |
---|---|
Pages (from-to) | 187-203 |
Number of pages | 17 |
Journal | Mathematical Programming, Series B |
Volume | 89 |
Issue number | 1 |
DOIs | |
State | Published - 2000 |