首页    期刊浏览 2024年07月06日 星期六
登录注册

文章基本信息

  • 标题:A hybrid guided neighborhood search for the disjunctively constrained knapsack problem
  • 本地全文:下载
  • 作者:Mhand Hifi ; Sagvan Saleh ; Lei Wu
  • 期刊名称:Cogent Engineering
  • 电子版ISSN:2331-1916
  • 出版年度:2015
  • 卷号:2
  • 期号:1
  • DOI:10.1080/23311916.2015.1068969
  • 出版社:Taylor and Francis Ltd
  • 摘要:

    In this paper, we investigate the use of a hybrid guided neighborhood search for solving the disjunctively constrained knapsack problem. The studied problem may be viewed as a combination of two NP-hard combinatorial optimization problems: the weighted-independent set and the classical binary knapsack. The proposed algorithm is a hybrid approach that combines both deterministic and random local searches. The deterministic local search is based on a descent method, where both building and exploring procedures are alternatively used for improving the solution at hand. In order to escape from a local optima, a random local search strategy is introduced which is based on a modified ant colony optimization system. During the search process, the ant colony optimization system tries to diversify and to enhance the solutions using some informations collected from the previous iterations. Finally, the proposed algorithm is computationally analyzed on a set of benchmark instances available in the literature. The provided results are compared to those realized by both the Cplex solver and a recent algorithm of the literature. The computational part shows that the obtained results improve most existing solution values.

  • 关键词:combinatorial optimization ; hybridation ; integer programming ; knapsack ; neighborhood
国家哲学社会科学文献中心版权所有