Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142249 | Operations Research Letters | 2015 | 7 Pages |
Abstract
In linear programming based branch-and-bound algorithms, many heuristics have been developed to improve primal solutions, but on the dual side we rely solely on cutting planes to improve dual bounds. We design a dual heuristic which incorporates relaxation algorithms within a branch-and-bound framework to improve dual bounds. We study the effect of solving various relaxations with dual heuristics by conducting a series of computational tests on the multi-dimensional knapsack problem.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Yaxian Li, Ozlem Ergun, George L. Nemhauser,