The knapsack sharing problem (KSP) is a max–min mathematical programming problem with a knapsack constraint (see Brown, 1979, Brown, 1991 and Brown, 1994). The KSP is NP-complete. The KSP occurs when resources have to be shared or distributed fairly to several entities, e.g. distribution of scarce resources like ammunition or gasoline among different military units (see Brown, 1979) or budget shared between districts of a city (see Yamada et al., 1997 and Yamada et al., 1998). The KSP is composed of n items divided into m different classes. Each class NiNi has a cardinality n i with ∑i∈Mni=n∑i∈Mni=n and M={1,2,…,m}M={1,2,…,m}. Each item j∈Nij∈Ni is associated with:
•
a profit pij,
•
a weight wij,
•
a decision variable xij ∈ {0, 1}.
We wish to determine a subset of items to be included in the knapsack of capacity C , so that the minimum profit associated with the different class is maximised. The KSP can be formulated as follows:
equation(1.1)
View the MathML source(KSP)maxmini∈M∑j∈Nipij·xij=z(KSP),s.t.∑i∈M∑j∈Niwij·xij⩽C,xij∈{0,1}fori∈Mandj∈Ni,
Turn MathJax on
where z (KSP ) denotes the optimal value of the problem (KSP ) and for i∈Mi∈M and j∈Ni,wij,pijj∈Ni,wij,pij and C are positive integers. Furthermore, we assume that ∑i∈M∑j∈Niwij>C∑i∈M∑j∈Niwij>C and maxi∈M,j∈Ni{wij}⩽Cmaxi∈M,j∈Ni{wij}⩽C.
A common way to solve the KSP consists of its decomposition into knapsack problems (see for examples Hifi and Sadfi, 2002 and Yamada et al., 1998). Indeed, for a class i∈Mi∈M, we define the following problem:
equation(1.2)
View the MathML source(KPi(Ci))max∑j∈Nipij·xij=z(KPi(Ci)),s.t.∑j∈Niwij·xij⩽Ci,xij∈{0,1}j∈Ni.
Turn MathJax on
The objective is then to find View the MathML source(C1∗,C2∗,…,Cm∗) such that
View the MathML source∑i∈MCi∗⩽C,
Turn MathJax on
and
View the MathML sourcemini∈M{zKPiCi∗}=z(KSP),
Turn MathJax on
where for a problem P,z(P)P,z(P) represents its optimal value. An upper bound and a lower bound of z(P)z(P) will be denoted, respectively, by View the MathML sourcez¯(P) and View the MathML sourcez̲(P), respectively.
Hifi et al. have proposed to solve the knapsack problems (KPi(Ci))i∈M(KPi(Ci))i∈M via a dense dynamic programming algorithm in Hifi and Sadfi, 2002 and Hifi et al., 2005. Their method starts with Ci=0,i∈MCi=0,i∈M, and increases regularly the capacities until ∑i∈MCi>C∑i∈MCi>C.
In this article, we propose an algorithm for solving the KSP. Our algorithm is based on a dynamic programming procedure with dominance technique to solve the knapsack problems (KPi(Ci))i∈M(KPi(Ci))i∈M. Our algorithm starts by solving the problems (KPi(Ci))i∈M(KPi(Ci))i∈M with View the MathML sourceCi⩾Ci∗,i∈M and ∑i∈MCi⩾C∑i∈MCi⩾C. At each step, we try to decrease the values of (Ci)i∈M(Ci)i∈M, towards View the MathML source(Ci∗)i∈M. The use of lists permits one to reduce the memory occupancy; the expected benefit being the solution of large instances.
Without loss of generality, we consider in the sequel that the items in a class i∈Mi∈M are sorted according to decreasing ratios View the MathML sourcepijwij,j∈Ni.
In Section 2, we present the dynamic programming algorithm used to solve the problems (KPi)i∈M(KPi)i∈M. Section 3 deals with the algorithm we propose for the KSP. Computational results are displayed and analyzed in Section 4. Some conclusions and perspectives are presented in Section 5.
In this paper, we have proposed a method to solve the KSP with a dynamic programming list algorithm.
The original problem (KSP) is decomposed into a set of knapsack problems. The initial value of the knapsack capacity is obtained via an overestimation. This value is updated and decreased throughout the solution process.
Computational results show that best results were obtained when the number of classes is relatively small. They show also that DPKSP is able to solve large instances within reasonable computing time and small memory occupancy. Moreover, our method use less memory than previous methods in the literature.
We think that very good results can be obtained with our method for instances with bigger capacities and a great number of classes (in the problems considered, capacities are generated so that they are equal to the half sum of all item weights, as a consequence, the bigger the weights, the bigger the capacity is).
In future work, it would also be interesting to consider a multi method that combines the advantages of our approach with the one of Hifi et al.
In order to decrease the processing time, parallel implementation of DPKSP could be considered. Indeed, the computations on knapsack sub-problems are independent and could be done in parallel.
