A dual heuristic for mixed integer programming

作者：Li Yaxian^*; Ergun Ozlem; Nemhauser George L

来源：Operations Research Letters, 2015, 43(4): 411-417.

DOI：10.1016/j.orl.2015.05.007

• Dual heuristic
• Branch-and-bound
• Knapsack
• Relaxations

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.

• 出版日期2015-7
• 单位东北大学