Hybrid heuristic algorithm for the multidimensional knapsack problem

In this work, a new hybrid heuristic algorithm for the 0/1 multidimensional knapsack problem is proposed. In the algorithm, Lagrange multipliers for every constraint are determined to reduce the problem to single dimension and some initial solutions are obtained with greedy algorithms. Then, these s...

Full description

Saved in:
Bibliographic Details
Main Authors: Atilgan, C., Nuriyev, U.
Format: Conference Proceeding
Language:English
Subjects:
Boolean variables
core approach
greedy algorithm
hybrid heuristic
Knapsack problem
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this work, a new hybrid heuristic algorithm for the 0/1 multidimensional knapsack problem is proposed. In the algorithm, Lagrange multipliers for every constraint are determined to reduce the problem to single dimension and some initial solutions are obtained with greedy algorithms. Then, these solutions are improved with iterative procedures. In order to test efficiency of the algorithm, computational experiments were done on some library problems in literature. It was observed that the algorithm has high efficiency in terms of solutions and time.
DOI:10.1109/ICPCI.2012.6486459