Improving problem reduction for 0-1 Multidimensional Knapsack Problems with valid inequalities

Gu, H

Improving problem reduction for 0-1 Multidimensional Knapsack Problems with valid inequalities

Gu, H

Permalink

Publication Type:: Journal Article
Citation:: Computers and Operations Research, 2016, 71 pp. 82 - 89
Issue Date:: 2016-07-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted ManuscriptAdobe PDF (399.31 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Gu, H https://orcid.org/0000-0003-2035-2583	en_US
dc.date.available	2020-05-25T19:08:52Z
dc.date.issued	2016-07-01	en_US
dc.identifier.citation	Computers and Operations Research, 2016, 71 pp. 82 - 89	en_US
dc.identifier.issn	0305-0548	en_US
dc.identifier.uri	http://hdl.handle.net/10453/41562
dc.description.abstract	© 2016 Elsevier Ltd. All rights reserved. This paper investigates the problem reduction heuristic for the Multidimensional Knapsack Problem (MKP). The MKP formulation is first strengthened by the Global Lifted Cover Inequalities (GLCI) using the cutting plane approach. The dynamic core problem heuristic is then applied to find good solutions. The GLCI is described in the general lifting framework and several variants are introduced. A Two-level Core problem Heuristic is also proposed to tackle large instances. Computational experiments were carried out on classic benchmark problems to demonstrate the effectiveness of this new method.	en_US
dc.relation.ispartof	Computers and Operations Research	en_US
dc.relation.isbasedon	10.1016/j.cor.2016.01.013	en_US
dc.subject.classification	Operations Research	en_US
dc.title	Improving problem reduction for 0-1 Multidimensional Knapsack Problems with valid inequalities	en_US
dc.type	Journal Article
utslib.citation.volume	71	en_US
utslib.for	0103 Numerical and Computational Mathematics	en_US
utslib.for	0102 Applied Mathematics	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	open_access
pubs.publication-status	Published	en_US
pubs.volume	71	en_US

Abstract:

© 2016 Elsevier Ltd. All rights reserved. This paper investigates the problem reduction heuristic for the Multidimensional Knapsack Problem (MKP). The MKP formulation is first strengthened by the Global Lifted Cover Inequalities (GLCI) using the cutting plane approach. The dynamic core problem heuristic is then applied to find good solutions. The GLCI is described in the general lifting framework and several variants are introduced. A Two-level Core problem Heuristic is also proposed to tackle large instances. Computational experiments were carried out on classic benchmark problems to demonstrate the effectiveness of this new method.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/41562