A multiplier adjustment approach for the set partitioning problem

A multiplier adjustment approach for the set partitioning problem

0.00 Avg rating0 Votes
Article ID: iaor19921905
Country: United States
Volume: 40
Start Page Number: 389
End Page Number: 397
Publication Date: Jan 1992
Journal: Operations Research
Authors: ,
Keywords: heuristics
Abstract:

The authors 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 the present 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. The authors 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.

Reviews

Required fields are marked *. Your email address will not be published.