THE MULTIDIMENSIONAL 0-1 KNAPSACK PROBLEM - A New Heuristic Algorithm Combined with 0-1 Linear Programming

Anikó Csébfalvi, György Csébfalvi

2011

Abstract

In this paper, we present a new population-based heuristic for the multidimensional 0-1 knapsack problem (MKP) which is combined with 0-1 linear programming to improve the quality of the final heuristic solution. The MKP is one of the most well known NP-hard problems and has received wide attention from the operational research community during the last four decades. MKP arises in several practical problems such as the capital budgeting problem, cargo loading, cutting stock problem, and computing processors allocation in huge distributed systems. Several different techniques have been proposed to solve this problem. However, according to its NP-hard nature, exact methods are unable to find optimal solutions for larger problem instances. Heuristic methods have become the alternative, and the last generation of them, are being successfully applied to this problem. Hence, in practice, heuristic algorithms to generate near-optimal solutions for larger problem instances are of special interest. The presented hybrid heuristic approach exploits the fact, that using a state-of-the-art solver a small binary linear programming (BLP) problem can be solved within reasonable time. The computational experiments show that the presented combined approach produces highly competitive results in significantly shorter run-times than the previously described approaches.

Paper Citation

in Harvard Style

Csébfalvi A. and Csébfalvi G. (2011). THE MULTIDIMENSIONAL 0-1 KNAPSACK PROBLEM - A New Heuristic Algorithm Combined with 0-1 Linear Programming . In Proceedings of the International Conference on Evolutionary Computation Theory and Applications - Volume 1: ECTA, (IJCCI 2011) ISBN 978-989-8425-83-6, pages 203-207. DOI: 10.5220/0003671302030207

in Bibtex Style

@conference{ecta11,
author={Anikó Csébfalvi and György Csébfalvi},
title={THE MULTIDIMENSIONAL 0-1 KNAPSACK PROBLEM - A New Heuristic Algorithm Combined with 0-1 Linear Programming},
booktitle={Proceedings of the International Conference on Evolutionary Computation Theory and Applications - Volume 1: ECTA, (IJCCI 2011)},
year={2011},
pages={203-207},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003671302030207},
isbn={978-989-8425-83-6},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Evolutionary Computation Theory and Applications - Volume 1: ECTA, (IJCCI 2011)
TI - THE MULTIDIMENSIONAL 0-1 KNAPSACK PROBLEM - A New Heuristic Algorithm Combined with 0-1 Linear Programming
SN - 978-989-8425-83-6
AU - Csébfalvi A.
AU - Csébfalvi G.
PY - 2011
SP - 203
EP - 207
DO - 10.5220/0003671302030207