The core concept for 0/1 integer programming

Sam Huston, Jakob Puchinger, Peter Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

Abstract

In this paper we examine an extension of the core concept for the 0/1 Multidimensional Knapsack Problem (MKP) towards general 0/1 Integer Programming (IP) by allowing negative profits, weights and capacities. The core concept provides opportunities for heuristically solving the MKP, achieving higher quality solutions and shorter runtimes than general IP methods. We provide the theoretical foundations of the extended core concept and further provide computational experiments showing that we can achieve similar computational behavior for extended MKP instances with negative weights, profits and capacities.

Original languageEnglish
Title of host publicationTheory of Computing 2008 - Proceedings of the Fourteenth Computing
Subtitle of host publicationThe Australasian Theory Symposium, CATS 2008
Publication statusPublished - 1 Dec 2008
Externally publishedYes
EventTheory of Computing 2008 - 14th Computing: The Australasian Theory Symposium, CATS 2008 - Wollongong, Australia
Duration: 22 Jan 200825 Jan 2008

Publication series

NameConferences in Research and Practice in Information Technology Series
Volume77
ISSN (Print)1445-1336

Conference

ConferenceTheory of Computing 2008 - 14th Computing: The Australasian Theory Symposium, CATS 2008
CountryAustralia
CityWollongong
Period22/01/0825/01/08

Cite this

Huston, S., Puchinger, J., & Stuckey, P. (2008). The core concept for 0/1 integer programming. In Theory of Computing 2008 - Proceedings of the Fourteenth Computing: The Australasian Theory Symposium, CATS 2008 (Conferences in Research and Practice in Information Technology Series; Vol. 77).