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, Çek Cumhuriyeti, 31 Mayıs - 01 Haziran 2005, cilt.3524, ss.34-48 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 3524
  • Doi Numarası: 10.1007/11493853_5
  • Basıldığı Şehir: Prague
  • Basıldığı Ülke: Çek Cumhuriyeti
  • Sayfa Sayıları: ss.34-48
  • Hacettepe Üniversitesi Adresli: Evet

Özet

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.