Title

Coefficient Ratios In Simulated 0-1 Knapsack Problems

Keywords

0-1 Knapsack Problem; Coefficient ratios; Explicit correlation induction; Implicit correlation induction; Random variate generation

Abstract

In many computational studies with simulated 0-1 Knapsack Problem (KP01) instances, positive correlation is induced between the objective function and constraint coefficients. It is widely reported that the performance of enumerative procedures for KP01 degrades as the coefficient correlation is increased. We investigate the parameters of coefficient-ratio distributions under implicit and explicit correlation induction approaches for simulating KP01 instances. We show how the induced correlation level affects the expectation, variance, and coefficient of variation of the coefficient ratios. Finally, we discuss implications of our findings for previous and future computational experiments on simulated KP01 instances.

Publication Date

12-1-2006

Publication Title

WMSCI 2006 - The 10th World Multi-Conference on Systemics, Cybernetics and Informatics, Jointly with the 12th International Conference on Information Systems Analysis and Synthesis, ISAS 2006 - Proc.

Volume

6

Number of Pages

51-56

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

Socpus ID

79955917369 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/79955917369

This document is currently not available here.

Share

COinS