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 language | English |
|---|---|
| Title of host publication | Theory of Computing 2008 - Proceedings of the Fourteenth Computing |
| Subtitle of host publication | The Australasian Theory Symposium, CATS 2008 |
| Publication status | Published - 1 Dec 2008 |
| Externally published | Yes |
| Event | Theory of Computing 2008 - 14th Computing: The Australasian Theory Symposium, CATS 2008 - Wollongong, Australia Duration: 22 Jan 2008 → 25 Jan 2008 |
Publication series
| Name | Conferences in Research and Practice in Information Technology Series |
|---|---|
| Volume | 77 |
| ISSN (Print) | 1445-1336 |
Conference
| Conference | Theory of Computing 2008 - 14th Computing: The Australasian Theory Symposium, CATS 2008 |
|---|---|
| Country | Australia |
| City | Wollongong |
| Period | 22/01/08 → 25/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).