A Novel Local Search Algorithm for Knapsack Problem

被引：0
|
作者：
Memariani, Mostafa [1 ]
Ghandeshtani, Kambiz Shojaee [2 ]
Madadi, Ahmad [3 ]
Neshati, Mohammad Mohsen [1 ]
机构：
[1] Ferdowsi Univ Mashhad, Dept Elect Engn, Mashhad, Iran
[2] Univ Tehran, Dept Elect Engn, Tehran, Iran
[3] Univ Amir Kabir, Dept Comp Engn, Tehran, Iran
来源：
PROCEEDINGS OF THE FOURTH INTERNATIONAL CONFERENCE ON ADVANCED ENGINEERING COMPUTING AND APPLICATIONS IN SCIENCES (ADVCOMP 2010) | 2010年
关键词：
Artificial intelligence; NP-hard; Knapsack problem; Combinational optimization;
D O I：
暂无
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
Knapsack problem is an integer programming that is generally called "Multidimentional Knapsack". Knapsack problem is known as a NP-hard problem. This paper is an introduction to a new idea for solving one-dimentional knapsack that with defining the "Weight Value Index", "Sorting" and "Smart local search" forms a new algorithm. This algorithm is mathematically formulated and has run on 5 sample problems of one-dimentional knapsack, that in most of them the result is close to the optimum. The results show that this method by comparison with the others recently published in this field, despite of its simplicity, has enough required functionality in order to get the result on the tested items.
引用
收藏
页码：77 / 80
页数：4
相关论文
共 50 条
  • [31] Local Branching-Based Algorithm for the Disjunctively Constrained Knapsack Problem
    Hifi, Mhand
    Negre, Stephane
    Mounir, Mohamed Ould Ahmed
    CIE: 2009 INTERNATIONAL CONFERENCE ON COMPUTERS AND INDUSTRIAL ENGINEERING, VOLS 1-3, 2009, : 279 - 284
  • [32] Solving Multiobjective Knapsack Problem Using Scalarizing Function Based Local Search
    Ben Mansour, Imen
    Alaya, Ines
    Tagina, Moncef
    SOFTWARE TECHNOLOGIES ( ICSOFT 2017), 2018, 868 : 210 - 228
  • [33] A Stochastic Local Search Heuristic for the Multidimensional Multiple-choice Knapsack Problem
    Xia, Youxin
    Gao, Chao
    Li, JinLong
    BIO-INSPIRED COMPUTING - THEORIES AND APPLICATIONS, BIC-TA 2015, 2015, 562 : 513 - 522
  • [34] AN ALGORITHM FOR THE KNAPSACK-PROBLEM
    AKINC, U
    IIE TRANSACTIONS, 1983, 15 (01) : 31 - 36
  • [35] A Hybrid Lagrangian Search Ant Colony Optimization algorithm for the Multidimensional Knapsack Problem
    Nakbi, Wafa
    Alaya, Ines
    Zouari, Wiem
    KNOWLEDGE-BASED AND INTELLIGENT INFORMATION & ENGINEERING SYSTEMS 19TH ANNUAL CONFERENCE, KES-2015, 2015, 60 : 1109 - 1119
  • [36] An iterative rounding search-based algorithm for the disjunctively constrained knapsack problem
    Hifi, Mhand
    ENGINEERING OPTIMIZATION, 2014, 46 (08) : 1109 - 1122
  • [37] Enhancing Reptile Search Algorithm Performance for the Knapsack Problem with Integration of Chaotic Map
    Barrera-Garcia, Jose
    Cisternas-Caneo, Felipe
    Crawford, Broderick
    Soto, Ricardo
    Becerra-Rozas, Marcelo
    Giachetti, Giovanni
    Monfroy, Eric
    ADVANCES IN SOFT COMPUTING, PT II, MICAI 2024, 2025, 15247 : 70 - 81
  • [38] A parallel Tabu Search algorithm for the 0-1 Multidimensional Knapsack Problem
    Niar, S
    Freville, A
    11TH INTERNATIONAL PARALLEL PROCESSING SYMPOSIUM, PROCEEDINGS, 1997, : 512 - 516
  • [39] A POLYNOMIAL LINEAR SEARCH ALGORITHM FOR THE N-DIMENSIONAL KNAPSACK-PROBLEM
    HEIDE, FMAD
    JOURNAL OF THE ACM, 1984, 31 (03) : 668 - 676
  • [40] Binary Moth Search Algorithm for Discounted {0-1} Knapsack Problem
    Feng, Yan-Hong
    Wang, Gai-Ge
    IEEE ACCESS, 2018, 6 : 10708 - 10719
12345