Sixth Mexican International Conference on Computer Science (ENC'05)
Hard Problem Generation for MKP
Puebla, Mexico
September 26-September 30
ISBN: 0-7695-2454-0
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 for the most important generators reported in the literature and our generators, over a wide range of parameters and instances in the OR Library.
Index Terms:
Multdimensional Knapsack Problem, Hard Problems Generation, Integer Programming.
Citation:
Maria A. Osorio, Germn Cuaya, "Hard Problem Generation for MKP," enc, pp.290-297, Sixth Mexican International Conference on Computer Science (ENC'05), 2005