HARD PROBLEM GENERATION FOR MKP

Resumen

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.

Key words: Multidimensional Knapsack Problem, Hard Problems Generation, Integer Programming

RESUMEN
Desarrollamos generadores que producen alternativas que constituyen un reto para el MKP. Nuestro enfoque utiliza independientemente distribuciones exponenciales sobre una gama amplia para generar
los coeficientes de las restricciones, y el promedio correspondiente para cada variable se usa para calcular directamente los coeficientes correlacionados en la función objetivo. Los valores de RHS sonun porcentaje de la suma de coeficientes de las restricciones. Presentamos una tabla comparativa de la media del desempeño de los generadores más importantes reportados en la literatura y nuestros generadores sobre una gama amplia de parámetros y alternativas en la Biblioteca de IO.