Interactive Knapsacks: Theory and Applications

Abstract

Reppuongelmassa on kyse tavaroiden pakkaamisesta annettuun tilaan mahdollisimman tehokkaasti. Interaktiivisessa reppuongelmassa tutkitaan, kuinka yhden tilan täyttäminen vaikuttaa viereisiin tiloihin.

Interaktiivinen reppuongelma on reppuongelman yleistys ja moniulotteisen reppuongelman sukulaisongelma. Näitä yhteyksiä käyttäen voidaan interaktiivisen reppuongelman ratkaisumenetelmiä hyödyntää moniulotteisen reppuongelman ratkaisemisessa.

Interaktiivisen reppuongelman ratkaisualgoritmien avulla voidaan esimerkiksi optimoida sähkönjakelua sähkölaitoksen kannalta tai laskea, kuinka tielinjaa vedettäessä ja maastoa tasoitettaessa joudutaan siirtämään vähin mahdollinen määrä maa-ainesta.

Ahon tutkimuksessa tutustutaan myös interaktiivisen reppuongelman laskennalliseen monimutkaisuuteen ja muodostetaan sähkönjakelusovellukselle erilaisia ratkaisumenetelmiä. Lisäksi ratkaisumenetelmiä arvioidaan kokeellisesti.

The interactive knapsack problems are generalizations of the classical knapsack problem. Three different new NP-complete decision problems, interactive knapsack heuristic decision (IKHD), interactive knapsack desicion (IKD), and multi-dimensional interactive knapsack (MDIK), are presented for the interactive knapsack model. The interactions occur between knapsacks when an item is put into a knapsack. We identify several natural interaction types. Interactive knapsacks with one item are closely related to the 0--1 multi-dimensional knapsack problem.

By using interactive knapsacks we model various planning and scheduling problems in an innovative way. We show interactive knapsacks to have several applications, for example, in electricity management, single and multiprocessor scheduling, and packing of two, three and $n$-dimensional items to different knapsacks. Many natural problems related to interactive knapsacks are NP-complete. IKD and MDIK are shown to be strongly NP-complete.

IKHO and IKO are introduced as optimization versions of IKHD and IKD, respectively. IKHO and IKO are shown to be APX-hard. Further, we describe special cases of IKHO and IKO solvable in polynomial time; given an instance parameterized by $k$, the solution can be found in polynomial time, where the polynomial has degree $k$. A similar construction solves a special case of the 0--1 multi-dimensional knapsack and the 0--1 linear integer programming problems in polynomial time. We extend the 0--1 multi-dimensional knapsack solution to 0--$n$ multi-dimensional knapsack problems and to 0--$n$ integer programming problems. Our algorithms are based on the resource bounded shortest path search: we represent restrictions efficiently in a form of a graph such that each feasible solution has a path between given source and target vertices.

We apply interactive knapsacks to load clipping used in electricity management. Specifically, we implement several heuristic methods, dynamic programming, enumerative, and genetic algorithms for solving direct load control problem. The enumerative method and dynamic programming are slow while the heuristics and genetic algorithms are faster. The dynamic programming gives best results in reasonable time. Heuristics, however, are several times faster than the other methods.