TY - GEN
T1 - The core concept for 0/1 integer programming
AU - Huston, Sam
AU - Puchinger, Jakob
AU - Stuckey, Peter
PY - 2008/12/1
Y1 - 2008/12/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84863568666&partnerID=8YFLogxK
M3 - Conference Paper
AN - SCOPUS:84863568666
SN - 9781920682583
T3 - Conferences in Research and Practice in Information Technology Series
BT - Theory of Computing 2008 - Proceedings of the Fourteenth Computing
T2 - Theory of Computing 2008 - 14th Computing: The Australasian Theory Symposium, CATS 2008
Y2 - 22 January 2008 through 25 January 2008
ER -