An Integer Programming-based Local Search for Large-Scale Multidimensional Knapsack Problems
Journal Title: International Journal on Computer Science and Engineering - Year 2011, Vol 3, Issue 6
Abstract
Integer programming-based local search (IPbLS) is a metaheuristic recently proposed for solving linear combinatorial optimization problems. IPbLS is basically the same as the first-choice hillclimbing except for using integer programming for neighbor generation. Meanwhile, the multidimensional knapsack problem (MKP) is one of the most well-known linear combinatorial optimization problems and has received wide attention. Integer programming (IP) is very effective for small-scale or mid-scale MKP but suffers from large memory requirement for large-scale MKP. In this paper, we present an IPbLS for solving large-scale MKP. First, an initial solution is generated by IP, and then neighbor solutions are repeatedly obtained by IP using problem reduction. We used the largest 30 problem instances available on the OR-Library as experimental data. The proposed method could find better solutions than the best-known solutions for 6 problem instances. Furthermore, we confirmed that our average result of the best solutions outperforms the result of the best-known method.
Authors and Affiliations
Junha Hwang , Sungjae Park , In Yeup Kong
Keywords
Related Articles
- EP ID EP139856
- DOI -
- Views 122
- Downloads 1
Role of ICT in Improving the Excellence of Education
Information and Communication Technology (ICT) is increasingly becoming indispensable part of the education system. ICT has changed the style of functioning of the educational system and its governance. This paper consid...
Simultaneous Pattern and Data Clustering Using Modified K-Means Algorithm
In data mining and knowledge discovery, for finding the ignificant correlation among events Pattern discovery (PD) is used. PD typically produces an overwhelming number of patterns. Since there are too many patterns, it...
WEB-BASED QUERY BUILDER
Database Management systems are widely used on industries to administer databases like MySQL. The most common way of managing these databases is via long commands or scripts that need to be entered on a console. In some...
Question Categorization Using SVM Based on Different Term Weighting Methods
This paper deals with the performance of Question Categorization based on four different term weighting methods. Term weighting methods such as tf*idf, qf*icf, iqf*qf*icf and vrf together with SVM classifier were used fo...
Person Identification Using Fingerprint by Hybridizing Core Point and Minutiae Features
Fingerprint recognition refers to the automated method of verifying a match between two human fingerprints. Fingerprints are one of many forms of biometrics used to identify an individual and verify their identity. The n...