Hard problem generation for MKP

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 objectiv...

Full description

Saved in:
Bibliographic Details
Main Authors: Osorio, M.A., Cuaya, G.
Format: Conference Proceeding
Language:English
Subjects:
Approximation algorithms
Benchmark testing
Exponential distribution
Hard Problems Generation
Heuristic algorithms
Integer Programming
Libraries
Linear programming
Multdimensional Knapsack Problem
Multidimensional systems
Operations research
Resource management
Solids
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1550-4069
2332-5712
DOI:10.1109/ENC.2005.22