A Multiplier Adjustment Approach for the Set Partitioning Problem
Thomas Justin Chan and
Candace Arai Yano
Additional contact information
Thomas Justin Chan: Solution Technologies Consulting Ltd., Vancouver, B.C., Canada
Candace Arai Yano: The University of Michigan, Ann Arbor, Michigan
Operations Research, 1992, vol. 40, issue 1-supplement-1, S40-S47
Abstract:
We introduce an effective branch-and-bound algorithm for solving the set partitioning problem. The new algorithm employs a new multiplier-adjustment-based bounding procedure, and a complementary branching strategy which results in relatively small search trees. Computational results based on 20 moderately sized crew scheduling problems indicate that our new algorithm is on average 16.6 times faster than the popular code, SETPAR. The improvements are mainly due to the bounding procedure, which is fast, easy to use, and provides tight lower bounds. On average, the bounds are 97.6% of the optimal objective value of the linear programming relaxation after only five iterations, and 98.5% after ten iterations. Moreover, the lower bounds are observed to be monotonically nondecreasing. We also apply the technique of variable elimination, which is very effective in reducing the size of the problems. On average, 89% of the variables are eliminated from the problem at the root node.
Keywords: programming; algorithms; heuristic: multiplier adjustment method with variable elimination; programming; integer: branch-and-bound algorithm for the set partitioning problem (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (2)
Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.1.S40 (application/pdf)
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:inm:oropre:v:40:y:1992:i:1-supplement-1:p:s40-s47
Access Statistics for this article
More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().