Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms (Q1338142)

Characteristics influencing the efficiency of Lagrangean relaxation algorithms, such as the probability of the existence of \(\varepsilon\)- optimal and optimal \(\delta\)-feasible generalized saddle points of the Lagrange function, the magnitude of the duality gap, are investigated. The probabilistic analysis is conducted under the assumption that the coefficients of the multidimensional knapsack problem are independently distributed. In section 3 the author derives several general sufficient conditions of ``good'' asymptotic behaviour of the mentioned characteristics. In section 4 several specific classes of probabilistic models are introduced in detail. For each of these models explicit formulas for the optimal Lagrange multipliers are derived and sufficient conditions are expressed through the parameters of the model. In the last section a fast statistically efficient algorithm with linear running time for the approximate solution of the problem with random coefficients is presented. The paper is clearly and precisely written and can be highly recommended.