#!/usr/local/bin/perl -w

sub init {
    $N = 35;
    for $i (1..$N){
	for $j (0..(5+int(rand(21)))){
	    if (rand()>=.5) { $x[$i][$j]=1 }else{ $x[$i][$j]=0; }
	}
	$w[$i] = 20 + int (rand(231));
    }
    $weight=0;
    $count =0;
}

$min=0;
for (;;){
INI:    init();
    for $i (1..$N){
	if ($x[$i][0]==1){
	    $weight+=$w[$i];
	    goto INI if ($weight>1700);
	    for $j (1..$#{$x[$i]}){
		if ($x[$i][$j]==1){
		    $count++;
		    goto INI if ($count>200);
		}
	    }
	}
    }
    if ($weight>=$min){
	print "$0 $weight\t$count subobjects\n";
	$min = $weight;
    }
}

__END__
From pongo_sk@hotmail.com Mon Oct  4 11:36:56 2004
Date: Mon, 4 Oct 2004 18:36:56 +0900
From: John <pongo_sk@hotmail.com>
Newsgroups: sci.op-research
Subject: help: performance of a greedy heuristic

Hi, there.

I have a dimensional knapsack problem:
    - each object has a profit value
    - each object consists of multiple sub-objects
    - each sub-object has a weight
    - the whole sub-objects of an object is put in the knapsack as a unit
    - two constraints on
        - maximum number of sub-objects to be put in the knapsack
        - maximum weight to be put in the knapsack

I tried a simple greedy to find sub-optimal solutions by considering objects
in the decreasing order of profit/number_of_sub-objects.

When compared with optimal solutions using exhaustive searching,
the heuristic solutions were almost always above 95% of optimal solutions.

Does this make sense?

I don't think the heuristic is excellent but there must be something with
data characteristics.
One of the experimented problem instances, for example, is
    - the number of 0-1 variables (objects): 35
    - the number of sub-objects for each object: 5 ~ 25 (random)
    - the limit of number of sub-objects for the knapsack: 200
    - the total weight of each object: 20 ~ 250 (random)
    - the limit of total weight for the knapsack: 1700

I expected wide variations in the heuristic solutions w.r.t. the optimal
solutions,
but the heuristic solutions were "QUITE CLOSE" to the optimal ones in most
cases.

Could anybody give comments on this results and on the relationship between
data characteristics and the simple greedy heuristic, if possible?

Many thanks in advance,
--
John,
pongo_sk@hotmail.com