HARD PROBLEM GENERATION FOR MKP

Abstract

We developed generators that produce challenging MKP instances. Our approaches uses independently exponential distributions over a wide range to generate the constraint coefficients, and the corresponding average for each variable is used to calculate directly correlated coefficients in the objective function. RHS values are a percentage of the sum of constraint coefficients. We present a comparative table with the average performance of the most important generators reported in the literature and our generators over a wide range of parameters and instances in the OR Library