期刊
ANNALS OF OPERATIONS RESEARCH
卷 183, 期 1, 页码 125-142出版社
SPRINGER
DOI: 10.1007/s10479-009-0546-z
关键词
Relaxation; Heuristic; Multidimensional knapsack problem
资金
- International Campus on Safety and Intermodality in Transportation the Nord-Pas-de-Calais Region
- European Community
- Regional Delegation for Research and Technology
- Ministry of Higher Education and Research
- National Center for Scientific Research
At the end of the seventies, Soyster et al. (Eur. J. Oper. Res. 2:195-201, 1978) proposed a convergent algorithm that solves a series of small sub-problems generated by exploiting information obtained through a series of linear programming relaxations. This process is suitable for the 0-1 mixed integer programming problems when the number of constraints is relatively smaller when compared to the number of variables. In this paper, we first revisit this algorithm, once again presenting it and some of its properties, including new proofs of finite convergence. This algorithm can, in practice, be used as a heuristic if the number of iterations is limited. We propose some improvements in which dominance properties are emphasized in order to reduce the number of sub problems to be solved optimally. We also add constraints to these sub-problems to speed up the process and integrate adaptive memory. Our results show the efficiency of the proposed improvements for the 0-1 multidimensional knapsack problem.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据