V Boyer
email: vboyer@laas.fr

D El Baz
email: elbaz@laas.fr

M Elkihel
email: elkihel@laas.fr

A dynamic programming method with lists for the knapsack sharing problem

Keywords: knapsack sharing problem, combinatorial optimization, Max-min programming, dynamic programming

In this paper, we propose a method to solve exactly the knapsack sharing problem (KSP) by using dynamic programming. The original problem (KSP ) is decomposed into a set of knapsack problems. Our method is tested on correlated and uncorrelated instances from the literature. Computational results show that our method is able to find an optimal solution of large instances within reasonable computing time and low memory occupancy.

Introduction

The knapsack sharing problem (KSP) is a max-min mathematical programming problem with a knapsack constraint (see [START_REF] Brown | Bounded knapsack sharing[END_REF] to [START_REF] Brown | The knapsack sharing problem[END_REF]). The KSP is NP-complete. The KSP occurs when ressources have to be shared or distributed fairly to several entities, e.g. distribution of scarce resources like ammunition or gazoline among different military units (see [START_REF] Brown | The knapsack sharing problem[END_REF]) or budget shared between districts of a city (see [START_REF] Yamada | Some exact algorithms for the knapsack sharing problem[END_REF]). The KSP is composed of n items divided into m different classes. Each class N i has a cardinality n i with i∈M n i = n and M = {1, 2, ..., m}. Each item j ∈ N i is associated with:

• a profit p ij ,
• a weight w ij ,

• a decision variable x ij ∈ {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:

(KSP )

               max min i∈M    j∈Ni p ij .x ij    = z(KSP ), subject to i∈M j∈Ni w ij .x ij ≤ C, x ij ∈ {0, 1} f or i ∈ M and j ∈ N i , (1.1)
where z(KSP ) denotes the optimal value of the problem (KSP ) and for i ∈ M and j ∈ N i , w ij , p ij and C are positive integers. Furthermore, we assume that i∈M j∈Ni w ij > C and max i∈M,j∈Ni

{w ij } ≤ C.
A common way to solve the KSP consists of its decomposition into knapsack problems (see for examples [START_REF] Hifi | The Knapsack Sharing Problem: An Exact Algorithm[END_REF] and [START_REF] Yamada | Some exact algorithms for the knapsack sharing problem[END_REF]). Indeed, for a class i ∈ M, we define the following problem:

(KP i (C i ))            max j∈Ni p ij .x ij = z(KP i (C i )), s.t. j∈Ni w ij .x ij ≤ C i , x ij ∈ {0, 1} j ∈ N i . (1.2) The objective is then to find (C * 1 , C * 2 , ..., C * m ) such that i∈M C * i ≤ C,
and min

i∈M {z(KP i (C * i ))} = z(KSP ),
where, for a problem P, z(P) represents its optimal value. An upper bound and a lower bound of z(P) will be denoted, respectively, by z(P) and z(P), respectively.

Hifi et al. have proposed to solve the knapsack problems (KP i (C i )) i∈M via a dense dynamic programming algorithm in [START_REF] Hifi | The Knapsack Sharing Problem: An Exact Algorithm[END_REF] and [START_REF] Hifi | An exact algorithm for the knapsack sharing problem[END_REF]. Their method starts with C i = 0, i ∈ M, and increases regulary the capacities until

i∈M C i > 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 (KP i (C i )) i∈M .

Our algorithm starts by solving the problems

(KP i (C i )) i∈M with C i ≥ C * i , i ∈ M and i∈M C i ≥ C.
At each step, we try to decrease the values of (C i ) i∈M , towards (C * i ) 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 ∈ M are sorted according to decreasing ratios pij wij , j ∈ N i . In the second section, we present the dynamic programming algorithm used to solve the problems (KP i ) i∈M . Section 3 deals with the algoritm we propose for the KSP. Computational results are displayed and analyzed in section 4. Some conclusions and perspectives are presented in section 5.

Basic dynamic programming procedure

In order to solve the problems (KP i (C i )) i∈M , we use a dynamic programming algorithm with dominance (see [START_REF] Bellman | Dynamic Programming[END_REF] - [START_REF] Boyer | Solution of multidimensional knapsack problems via cooperation of dynamic programming and branch and bound[END_REF] and [START_REF] Baz | Load balancing methods and parallel dynamic programming algorithm using dominance technique applied to the 0-1 knapsack problem[END_REF]).

Lists construction

We recall that i ∈ M denotes the index of the i th class of (KSP ). A list L ik is associated with each step k ∈ N i :

L ik =    (w, p) | w = k j=1 w ij .x ij ≤ C i and p = k j=1 p ij .x ij , x ij ∈ {0, 1}, j ∈ {1, 2, ..., k}    . (2.1)
The algorithm begins with the lists L i0 = {(0, 0)}. At each step k ∈ N i , the new list L ik is obtained as follows:

L ik = L i(k-1) ∪ (w + w ik , p + p ik ) | (w, p) ∈ L i(k-1) , w + w ik ≤ C i } .

Notation:

For simplicty of presentation the above equation will also be written as follows in the sequel.

L ik = L i(k-1) ⊕ {(w ik , p ik )}.
The states (w, p) in a list are sorted according to the decreasing value of p. From the dynamic programming principle, dominated states, i.e. states (w, p) such that there exists a state (w , p ) with w ≤ w and p ≥ p, are removed from the list.

State elimination via upper bounds

In order to shrink lists L ik , k ∈ N i , an upper bound z(w, p), associated with state (w, p) ∈ L ik , is computed. For this purpose, we solve exactly the following linear continuous knapsack problem via the Martello & Toth's algorithm (see [START_REF] Martello | An upper bound for the zero-one knapsack problem and a branch and bound algorithm[END_REF]):

(LP (w,p) i (C i ))                max p + ni j=k+1 p ij .x ij , s.t. ni j=k+1 w ij .x ij ≤ C i -w, x ij ∈ [0, 1], j ∈ {k + 1, ..., n i }. (2.2) Let z(w, p) = z(LP (w,p) i (C i )) .
If z(w, p) ≤ z(KSP ), then the states (w, p) can be discarded.

We shall have:

L ik := L i(k-1) ⊕ {(w ik , p ik )} -D ik -B ik ,
where:

• D ik represents the list of dominated states in L i(k-1) ⊕ {(w ik , p ik )},
• B ik represents the list of states in L i(k-1) ⊕ {(w ik , p ik )} to be eliminated via upper bounds.

In the sequel, this phase is the so-called NextList phase.

Fixing variables

The following two methods are used to fix variables of the problem (KP i ).

Variable reduction technique 1

Let i ∈ M, k ∈ N i and (w, p) ∈ L ik . If p > z(KSP )
, where z(KSP ) is an upper bound of (KSP ) obtained by the solution of the linear continuous relaxation of (KSP ), then all free variables x ij , j ∈ {k + 1, ..., n i }, can be fixed at 0 for the state (w, p).

Indeed, as z(KSP ) ≤ z(KSP ), when p > z(KSP ) we can stop the exploration of this state because it will not give a better optimal value for (KSP ).

The second method to fix variables uses information provided by the solution of (LP

(w,p) i (C i )) associated to a state (w, p) ∈ L ik , k ∈ N i .
We use the following rule to fix the free variables of a state (w, p).

Variable reduction technique 2 (see [START_REF] Nemhauser | Integer and Combinatorial Optimization[END_REF])

Let i ∈ M, k ∈ N i and (w, p) ∈ L ik .
Let d be the index of the critical variable of (LP

(w,p) i (C i )), i.e.: d-1 j=k+1 w ij ≤ C i -w and d j=k+1 w ij > C i -w. If for j ∈ {k + 1, ...d -1, d + 1, ..., n i }, we have z(LP (w,p) i (C i )) -p ij -w ij . p id w id ≤ z(KSP ),
where z(KSP ) is a lower bound of (KSP ), then x ij can be fixed to 1 if j < d and to 0 otherwise. The computation of z(KSP ) is detailed in the next Section.

An algorithm for the KSP

In this section, we show how the dynamic programming method presented in the above Section can be used to find an optimal solution of (KSP ). For simplicity of notation, z(KSP ) is denoted by z in the sequel.

The main procedure DPKSP

The principle of our algorithm can be presented brievly as follows.

-A first lower bound of (KSP ), z, is computed with the greedy heuristic the so-called GreedyKSP (see Alg. 1).

-At each step k of the dynamic programming method:

• the lists (L ik ) i∈M, k≤ni are computed via the procedure NextList presented in the above Section,

• then, we try to reduce the free variables associated with each state in (L ik ) i∈M, k≤ni ,

• finally, the lower bound z and the capacities (C i ) i∈M , respectively, are updated via the procedures UpdateZ and UpdateC, respectively described below.

-The dynamic programming phase is stopped when all the lists (L ini ) i∈M have been computed. These lists are used by the procedure FindOptimalValue to find an optimal solution for the (KSP ).

Alg. 1 : GreedyKSP For i from 1 to m do p i := 0, w i := 0 and k i := 1 end do STOP:=0 while STOP=0 do

d := argmin{p 1 , p 2 , ..., p m } if k d ≤ n d then if w d + w dk d ≤ C, then x dk d is fixed to 1 p d := p d + p dk d w d := w d + w dk d end if k d := k d + 1 else STOP:=1 end if end while z = min{p 1 , p 2 , ..., p m }.
The main procedure, DPKSP, to solve the KSP is given in Alg. 2. The procedures UpdateZ, UpdateC and FindOptimalValue are detailed in the next subsections.

Alg. 2 : DPKSP

Initialisation: z := z(KSP ) := GreedyKSP z(KSP ) := z(CKSP ) For i from 1 to m do L i0 := {(0, 0)} end for k := 1 (C i ) i∈M := U pdateC(z, (L i0 ) i∈M ) Dynamic programming: STOP:=0 while STOP=0 do STOP:=1 For i from 1 to m do If(k ≤ n i ) STOP:=0; L ik := N extList(KP i , L i(k-1) )
For each state (w, p) ∈ L ik do Try to fix the free variables end for end if end for

z := U pdateZ (z, (C i ) i∈M , (L ik ) i∈M ) (C i ) i∈M := U pdateC(z, (L ik ) i∈M ) k := k + 1 end while Finding z * : z(KSP ) := F indOptimalV alue (z, (L ini ) i∈M )

The procedure UpdateC

In this subsection, we present how the values of (C i ) i∈M are updated. For this purpose, we compute the minimum values of the capacities (C i ) i∈M resulting from an improvement of the current lower bound z, of the KSP. For i ∈ M, and k ∈ N i ∪ {0}, the following linear problem is associated with a state (w, p) ∈ L ik :

(min W i ((w, p), z))

               min w + ni j=k+1 w ij .x ij , s.t. p + ni j=k+1 p ij .x ij ≥ z + 1, x ij ∈ [0, 1], j ∈ {k + 1, ..., n i }.
(3.1) Let us define:

min C i (L ik , z) = min (w,p)∈L ik {z(min W i ((w, p), z))} .
If we want to improve the best lower bound, z, then we must have, f or i ∈ M:

j∈Ni w ij .x ij ≤ C - i ∈M-{i} min C i (L i k , z), with x ij ∈ {0, 1}, f or j ∈ N i .
For i ∈ M, the initial value of C i is given by

C i = C - i ∈M-{i} min C i (L i 0 , z).
At each step k of DPKSP, we try to improve the value of C i with Alg. 3.

Alg. 3 : UpdateC

For i from 1 to m do

C i := C - i ∈M-{i} min C i (L i k , z)
end for

The procedure UpdateZ

Rather than updating the lower bound z, with the GreedyKSP heuristic, which is time consuming, we make use of all the lists (L ik ) i∈M at step k in order to try to improve more efficiently this bound. Indeed, for each state in the list, a local greedy heuristic can be used in order to select a particular state. The selected state of each list is then combined with other states so as to try to improve z. The details of the heuristic are given in procedure UpdateZ (see Alg. 4).

Alg. 4 : UpdateZ

For i ∈ M do L ik = ∅ Greedy like step: For i from 1 to m do For (w, p) ∈ L ik do W := w and P := p For j from k + 1 to n i do If P ≥ z(KSP ) + 1 then exit the loop for

end if If W + w ij ≤ C i then W := W +
W i ≤ C then z(KSP ) := min i∈M {P i } end if

The procedure FindOptimalValue

In the end of the dynamic programming phase, all the lists (L ini ) i∈M , are available. In this section, we show how these lists are combined in O i∈M C i in order to find the optimal value of (KSP ). The states (w, p) in a list are sorted according to the decreasing value of p. Due to the dominance principle, they are also sorted according to the decreasing value of w. Thus, if we want to check if a given bound z ≥ z is feasible, then we have to take in each list L ini ,i ∈ M, the state (w i , p i ) which satisfies:

w i = min {w | p ≥ z, (w, p) ∈ L ini } . (3.2)
If i∈M w i ≤ C, then we have found a better feasible bound for (KSP ), i.e. z = min

i∈M {p i } ≥ z ≥ z.
Furthermore, all the states (w, p) ∈ L ini such that p < p i can be discarded. Otherwise, all the states (w, p) ∈ L ini such that p > p i (and w > w i ) can be removed as they will not provide a better solution. Indeed, in this case, we have the following inequalities:

z(KSP ) < z ≤ p i , i ∈ M.
Therefore, we have to decrease the value of the bound z and check if this new bound is feasible. Alg. 5 presents the procedure FindOptimalValue.

Alg. 5 : FindOptimalValue Initialization:

For i from 1 to m do Let (w i , p i ) be the first states in L ini end do We note that all the lists are considered only once in this procedure.

Computational experiments

The procedure DPKSP has been written in C and computational experiments have been carried out on an Intel Core 2 Duo T7500 (2.2 GHz). We have used the set of problems of Hifi (see [START_REF] Hifi | Library of instances[END_REF], see also [START_REF] Baz | Library of instances for knapsack sharing problems[END_REF]) with 168 uncorrelated instances and 72 strongly correlated instances; each group of problems contains four instances. The problems are detailed in Tables 1 and2. All the optimal values are known for these instances. The average processing time for the four instances of each group of problems is given in Tables 3 and4. The tables show that DPKSP is able to solve large instances (up to 20000 variables and 50 classes) within reasonable computing time. In the correlated case, an optimal solution is obtained in less than 13 minutes. The processing time is less than 1.5 minutes in the uncorrelated case. We note that our method is efficient when the number m of classes is relatively small (between 2 and 5 classes). This result can be explained by the fact that in this case we have to fill a limited number of knapsacks. The comparison with the results provided by Hifi et al. in [START_REF] Hifi | The Knapsack Sharing Problem: An Exact Algorithm[END_REF] and [START_REF] Hifi | An exact algorithm for the knapsack sharing problem[END_REF] shows the interest of our approach particulary in this context for both correlated and uncorrelated problems; indeed, the processing times of Hifi's algorithm tends to be important for these instances. The memory occupancy is presented in Tables 5 and6. Note that the vector x associated to each state is encoded as a bit string of 32 bits. These tables compare DPKSP with the algorithm of Hifi whose space complexity is O(n.C). We see that the approach of Hifi needs for some instances a large amount of memory (up to 638.42Mo) contrarily to our method (< 7Mo). Indeed, the space complexity of the dynamic programming algorithm with lists for a knasack problem of n variables with the capacity C is O(min{2 n+1 , nC}) (see [START_REF] Martello | Knapsack Problems: Algorithms and Computer Implementation[END_REF]). The space complexity of DPKSP is O m i=1 min{2 ni+1 , n i .C i } . Thus it is bounded by O(n.C). DPKSP is able to solve large problems with limited memory occupancy.

Conclusions and perspectives

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 independant and could be done in parallel.

z

  := min i∈M {p i } z(KSP ) := z(KSP ) Checking feasibility: While z > z(KSP ) do For i from 1 to m do Find (w i , p i ) ∈ L ini such that w i := min {w | p ≥ z, (w, p) ∈ L ini } end for If i∈M w i ≤ C then z(KSP ) := z Exit the procedure Else For i from 1 to m do L ini := L ini -{(w, p) ∈ L ini | p > p i } end for z := min i∈M max (w,p)∈Lin i {p | p < z} end if end while

  w ij and P := P + p ij

	Choose (W i , P i ) ∈ L ik such that
	(W,P )∈L ik W i := min	{W }
	end for
	Updating z(KSP ):
	If
	i∈M
	end if
	end for
	If P ≥ z(KSP ) + 1 then
	L ik := L ik ∪ {(W, P )}
	end if
	end for
	end for
	Selected states:
	For i from 1 to m do

Table 6 :

 6 Correlated instances: memory occupancy (Mo)

	Instance	DPKSP	ALGO (Hifi)
	AmC.x	0.10	1.60
	BmC.x	0.30	9.97
	CmC.x	0.68	39.76
	DmC.x	1.26	89.60
	EmC.x	1.96	159.23
	FmC.x	6.21	638.42

Aknowledgement

The authors would like to thank the reviewers for their helpful comments contributing to improve the presentation of the paper.


easurement of photoplethysmographic (PPG) signal is widely used to assess metabolic conditions of monitored tissues. Probes were designed to acquire physiological changes through the spine induced by external stimulation. In vivo results demonstrate that such probes can be deployed to monitor and analyze autonomic functions of the spinal cord.

M

The Spinal Cord (SC) is the input of sensory information and output of the motor commands of the limbs and the trunk. Its damage can have major consequences. In addition to Magnetic Resonance Imaging [START_REF] Cohen-Adad | Investigations on spinal cord fMRI of cats under ketamine[END_REF], monitoring of haemodynamic constants in the SC is a promising technique of the neuronal activity measurement. One way to acquire a PPG signal uses a light source and a photodetector placed on opposite sides of the tissues to collect the amount of transmitted light. Depending on the organ to be monitored, signal acquisition can be impaired by tissue light attenuation leading to a small Signal-to-Noise Ratio [START_REF] Webster | Design of Pulse Oximeters[END_REF][START_REF] Bingger | In vivo monitoring of blood oxygenation using an implantable MEMS-based sensor[END_REF]. Measurements of functional activity in the SC of small animals by Near InfraRed Spectroscopy have been performed by [START_REF] Goguin | A low-cost implantable near-infrared imaging system of spinal cord activity in the cat[END_REF]. To study the potential transfer to humans of this imaging technique, custom probes must be designed to lead experiments on bigger animals. Due to its anatomic proximity with humans, pigs have been chosen for in vivo experiments. As show in Fig. 1, emitter and receptor are placed on either side of the T14 vertebra. On its optical path, light is altered passing by various materials (bone, dura mater, etc.), including the SC.

The PPG acquisition system is composed of a photodetector and two LEDs (624nm and 880nm). Analog signal preconditioning is achieved before digital conversion and signal processing. The overall system functions on battery to reduce parasitic signals and a LabVIEW interface is used to record real-time data.

Fig. 1 .

 1 Fig. 1. a) Scheme of principle of the system; b) 3D imagery of vertebrae during experiments. Fig. 2. PPG of the SC with IR LED.

Preliminary results on Fig.2show the effectiveness of this non-invasive technique into delivering haemodynamic induced changes. High quality data acquired assess the performances of such a complementary monitoring tool for the SC. Moreover, vital signs, including blood pressure, respiratory rate and oxygen saturation can be extracted.