A probabilistic analysis of the multiknapsack value function (Q909581)

The multiknapsack problem is discussed. The problem is to minimize \(\sum^{n}_{j=1}c_ jx_ j\) under the conditions \(\sum^{n}_{j=1}a_{ij}x_ j\leq b_ i\) \((i=1,2,...,m)\), \(x_ j\in \{0,1\}\) \((j=1,...,n)\); where the coefficients \(a_{ij}\), \(b_ i\), \(c_ j\) are real nonnegative numbers. The problem is known to be strong NP-hard. The behavior of the solution value of the multiknapsack problem with respect to changing coefficients \(b_ i\) is investigated. The coefficients \(c_ 1,c_ 2,..\). and the vectors \(a_ j=(a_{1j},a_{2j},...,a_{mj})\), \(j=1,2,..\). are assumed to be nonnegative independent identically distributed random variables and vectors, correspondingly. It is assumed also that the coefficients \(b_ i\) grow proportionality with the number n: \(b_ i=n\beta_ i\), \(i=1,2,...,m\), for \(\beta\in \{\beta |\) \(0<\beta <Ea_ 1\}\), where the random vector \(Ea_ 1\) is the finite expectation of vector \(a_ 1\). Under these assumptions it is shown that the sequence of optimal solution values (properly normalized) converges with probability 1 to some function of the coefficients \(b_ i\), \(i=1,2,...,m\), as n goes to infinity and m remains fixed. This function is computed in closed form for special cases of the problem when \(m=1\) and \(m=2\).