The temporal knapsack problem and its solution

Bartlett M., Frisch A. M., Hamadi Y., Miguel I., TARIM Ş. A., Unsworth C.

Second International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2005, Prague, Czech Republic, 31 May - 01 June 2005, vol.3524, pp.34-48, (Full Text) identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 3524
  • Doi Number: 10.1007/11493853_5
  • City: Prague
  • Country: Czech Republic
  • Page Numbers: pp.34-48
  • Hacettepe University Affiliated: Yes

Abstract

This paper introduces a problem called the temporal knapsack problem, presents several algorithms for solving it, and compares their performance. The temporal knapsack problem is a generalisation of the knapsack problem and specialisation of the multidimensional (or multiconstraint) knapsack problem. It arises naturally in applications such as allocating communication bandwidth or CPUs in a multiprocessor to bids for the resources. The algorithms considered use and combine techniques from constraint programming, artificial intelligence and operations research. © Springer-Verlag Berlin Heidelberg 2005.