Re: multi-dimensional knapsack problem (MKP) instance generation

I am interested in developing heuristic algorithms (e.g., GA) for
solving large-scale MKPs, but found little public problem instances of
large size for benchmark purpose. Those included in ORLIB are usually
small. Anyone knows where to find such info.?


Another question is how to generate large-sized problem instances with
known optimal value. Maybe I did not do enough literature review, but
does there exist a mechanism to construct such a problem instance,
instead of generating it randomly and getting bounds by using linear
programming software which is not feasible for large size problems.

For knapsack problems, instances of interest are generally classified
as
strongly correlated, weakly correlated and uncorrelated. I believe
that
J.E. Beasley's paper includes the mechanism used for generation of
the
ORLIB instances, and most of the ORLIB instances have not been
solved to provably optimum values. (The paper also includes the LP
bound
and the Genetic Algorithm solution)

It might be better to classify your instances based on correlation
between
profit and constraint values, and not just generate the instances
randomly.

As far as I know, you need to use the LP bound to evaluate your
algorithm as
its very difficult to find a provably optimal solution for large
instances of the
multidimensional knapsack problem.
.