Limbic~Region has asked for the
wisdom of the Perl Monks concerning the following question:
All,
If you are not familiar with the bin packing problem, it is the daunting (NP Hard) task of cramming a certain number of items into the fewest bins possible where each bin has a fixed capacity. A not too uncommon question here at the Monastery is how to minimize the number of CDs needed to burn all music files. I have been thinking about an interesting twist on the problem.
What if instead of trying to minimize the number of bins used you were trying to mazimize them. For instance, you wanted to make it look like you had purchased more gifts that you actually had. Presuming that every gift could fit into a single shipping box then you could send each gift in its own box. While this is obviously the maximum number of bins (provided you don't send any empty boxes) people are going to immediately see through your ruse.
Instead, you fill each box as close to capacity as possible but without doing it as efficiently as possible. Sound odd? I thought so too at first. It is easily reconciled when you consider that any attempt at solving the bin packing problem that is not the optimal solution is a series of bins as near capacity as possible without being as efficient as possible.
Imagine that a shipping box can only hold 10 units of weight and you have purchased 7 gifts with weights of 2, 2, 3, 4, 5, 6, and 7. You could get away with sending only 3 boxes by arranging them as:
1: 7, 3
2: 6, 4
3: 5, 2, 2
Instead, you send 4 and everyone is impressed with your generosity:
1: 7, 2
2: 5, 4
3: 6, 3
4: 2
My challenge then is to come up with an algorithm that provides the most inefficient solution to the bin packing problem while requiring that each bin be filled as near to capacity as possible. Update: This means you start filling the first bin until no more items will fit. Move on to second bin and repeat the process. The goal is to end up with as many bins as possible not the fewest.
Re: Challenge: Twist On Bin Packing
by moklevat (Priest) on Apr 07, 2006 at 14:02 UTC

Very interesting. In thinking about this it might be easier to find a solution if the problem is slightly refactored. Rather than discussing bins and gifts, I think that this problem lends itself better to considering volumes of liquid. We are not concerned with the way in which our bins are packed, rather we assume that whatever unit volume we place in each bin automatically fits in the best possible way (like liquid). Since we can consider this a problem of liquids, we may as well discuss beer. :)
I therefore propose the following modification of the problem as the The Pint Pouring Problem
At your local pub all beer is served in 1 pint glasses. Following a serious problem at the brewery today's shipment of beer was delivered in cans of various sizes, each less than a pint. The thrifty pub owner asks you to devise an algorithm for pouring as many pints as possible, but that also ensures that as many patrons as possible get a suitably full pint glass (say at least 90% full). Assume that cans cannot be split across pint glasses. Fewer pints poured means less revenue for the pub owner, but inadequately filled pints mean angry patrons and the potential for trouble.
Now to work on a solution...
Update:The combination of "as full as possible" and "as many bins as possible" in the original post create an inherent conflict (which, I suppose, is the point). Having said that, I have not been able to think of a case for which a variation on the "Best Fit Decreasing and First Fit Decreasing" strategy will fail. (that's not to say there isn't one, but I have to get *some* work done today). The algorithm:
0) Step zero is to set a threshold for adequately "full" that is less than 100%.
1) Sort all cans by size.
2) Begining with the largest can and moving smaller, pour as many cans in order that will fit in a single glass. If you come to a can that will overflow the glass go to the next step.
3) Beginning with the smallest cans and moving larger pour as many cans in order that will fit in the glass. If you come to a can that will overflow the glass go to Step 2 and begin filling the next glass.
Update:I have removed step zero. Limbic~Region didn't like it and it is unnecessary. It simply reparameterized the problem as if you had smaller glasses.
Final Update:The problem has been clarified somewhat and this solution does not fit, as L~R notes below.  [reply] 

moklevat,
No, you can't pick an aribtrary limit less than 100% that you have to meet. As you can see from my example, one of the shipping boxes (in your case pint mugs) is only 2. Sure the bar owner may choose just to accept this as a loss and drink it himself but that doesn't change the nature of the problem.
Starting with the first mug, fill it as close to the top as you can without over filling or without leaving any beer in the can. Move on to the second mug and repeat the process. The goal being to choose the grouping of cans such that you end up with the most number of mugs and not the least.
I am not sure if your algorithm works but given its simplicity I hope so. I will set something up to bruteforce this weekend and compare the results to your approach.
Update: As you can see, this approach fails with a bin size of 10 and an input list of 1,1,1,2,2,3,4,6,7,7
 [reply] 

Fair enough, step zero is not necessary for the algorithm to work, it just provides an additional parameter to adjust pint/bin size. Without step zero the algorithm still produces 4 pints/bins, and the last person gets 3 units rather than 2 units.
1: 7, 2
2: 6, 2
3: 5, 4
4: 3
 [reply] [d/l] 

Hmm. I would have taken a different tactic...
Assume that you have an infinite number of standard containers with a given length/width/height. You also have a finite number of items to go in the containers, each item having its own l/w/h (which can be different for each item).
The trick then would be to pack items in containers such that each container can hold no more items... but optimizing for empty space.
Order of packing then becomes the issue.
Actual code is left as an exersise for the reader. :)

WARNING: You are logged into reality as root.
 [reply] 
Re: Challenge: Twist On Bin Packing
by eric256 (Parson) on Apr 07, 2006 at 15:43 UTC

So you are looking for a solution of bins where all bins are full (i.e. no available items will fit) and then the solution with the most bins.
BTW There are many solutions to even just your example:
6, 2
7, 3
5, 2
4
7, 2
6, 2
4, 5
3
7, 2
6, 2
4, 3
5
etc....
I think that is where some of the confusion is, we are used to shuffling the items to make them fit best, but in this case we don't want a best fit we want most bins. Do you have a meteric in mind for which of the solutions I just provided is best?
 [reply] [d/l] 

eric256,
BTW There are many solutions to even just your example:
I know but I think I have represented an optimal solution (3 bins) and a solution that would fit the criteria for the puzzle (4 bins).
Do you have a meteric in mind for which of the solutions I just provided is best?
If any solution exists that exceeds 4 bins that would be the answer but if there are ties any will do.
 [reply] 
Re: Challenge: Twist On Bin Packing
by japhy (Canon) on Apr 07, 2006 at 16:16 UTC

Is it the goal to have as many bins as possible while having as many of THOSE as close to capacity? My algorithm ends up reporting (7,3), (4,2,2), (6), (5). I'm not sure I'm solving the right problem.
 [reply] 

japhy,
This solution is valid AFAICT since it produces 4 bins and if you were filling them left to right none of the remaining items could fit in the current bin. In the event of ties (different arrangements producing the same number of bins) either solution is acceptable.
 [reply] 
Re: Challenge: Twist On Bin Packing
by japhy (Canon) on Apr 07, 2006 at 16:30 UTC

I think you can always get a mostbins solution by putting as many of the smallest elements in one bin, and then moving on to the next, recursively. (2,2,3), (4,5), (6), (7) is the result for the set you've given.
 [reply] 

japhy,
I am working on a brute force implementation so that people can test their theories. It isn't as easy as I thought it might have been.
Update: As pointed out by Anonymous Monk later in this thread with a bin size of 10 and an input list of 1,1,1,2,2,3,4,6,7,7  this method fails
 [reply] 

sub bin {
my ($size, @set) = @_;
my $best = [];
my @bins;
_bin($size, \@set, \@bins, 0, $best);
print "BEST: <@{[ map qq{[@$_]}, @$best ]}>\n";
}
sub _bin {
my ($size, $set, $bins, $i, $best) = @_;
if (@$set == 0) {
@$best = map [@$_], @$bins if @$bins > @$best;
return;
}
my $rem = $size  sum($bins>[$i]);
for (sort { $set>[$b] <=> $set>[$a] } grep { $set>[$_] <= $rem }
+0 .. $#$set) {
my $n = splice @$set, $_, 1;
push @{ $bins>[$i] }, $n;
_bin($size, $set, $bins, (sum($bins>[$i]) == $size) ? $i+1 : $i,
+$best);
_bin($size, $set, $bins, $i+1, $best) if 0 == grep { $set>[$_] <=
+ ($rem$n) } 0 .. $#$set;
pop @{ $bins>[$i] };
pop @$bins if @{ $bins>[$i] } == 0;
splice @$set, $_, 0, $n;
}
}
sub sum {
my $s = 0;
$s += $_ for @{ $_[0] };
$s;
}
 [reply] [d/l] 
Re: Challenge: Twist On Bin Packing
by kvale (Monsignor) on Apr 07, 2006 at 16:49 UTC

First, lets order the bins 1 through N. I'll call a packing 1stable if no
set of single elements can be moved from later bins B to earlier bins A to
reduce the muber of bins used. In this sense the OP solution is is 1stable:
the 2 cannot be moved to an earleir bin.
If there is no ordering requirement, the OP soultion is not stable: I can move
the 5 and the 2 to the fourth bin, the 3 to the first bin and the 4 to the
third bin to eliminate a bin. So, the OP must be thinking about the ordered
case.
Simialrly, suppose 2stable allows both sinlge moves and transpositions. Then
the 2 and 3 of the first and third bins can be excahnged and then 2 in the
fourth bin can be moved into the third bin, reducing the number of bins. So
the OP must be only thinking about single moves.
To solve the ordered 1stable problem, I suggest, sorting the gifts from
smallest to largest and then fill up bins using sequential elements from the
sorted list. For the OP example, (2, 2, 3, 4, 5, 6, 7) this would give
1: 2,2,3
2: 4,5
3: 6
4: 7
which gives the same maximum number of bins, but spreads the gifts about more
evenly. Intuitively, by using up all the smallest elements that could be used
to fill up the interstices first, the remaining bins will be taken up by
larger elements with lots of empty space.
 [reply] [d/l] 

I agree; the leasttogreatest gives the highest magnitude (number of bins).
 [reply] 

Smallest to largest won't always give the maximum number of bins. Take 1,1,1,2,2,3,4,6,7,7 for example.
Filling them smalles to largest you get 4 bins:
1,1,1,2,2,3
4,6
7
7
But you can get 5 bins by filling it:
6,1,1,1
2,2,3
7
7
4
 [reply] 




It seems that L~R has some work cut out to compare the LeasttoGreatest method with any other contenders, on a large enough set of random samples, and tell us if there are any interesting anomalies. [Well, it is his problem, and I have to get some work done before hometime ;]
QM

Quantum Mechanics: The dreams stuff is made of
 [reply] [d/l] 

This is cool. The leasttogreatest approach will indeed give a larger number of bins than the approach I posted above under some circumstances, so this may be the winner. However, it will also lead to larger variability in the contents of the bins and could lead to more bins being, for example, 51% full. Ultimately the relative importance of "filling the bins as close to capacity as possible" and "maximizing the number of bins" remains somewhat unclear.
 [reply] 
Re: Challenge: Twist On Bin Packing
by eric256 (Parson) on Apr 07, 2006 at 16:37 UTC

I'm not sure it is 100% always going to work, but it seems to ;)
use strict;
use warnings;
use Data::Dumper;
my @packages = sort { $b <=> $a } (2,2,3,4,5,6,7);
print Dumper(@packages);
my @bins;
while (@packages) {
my @temp = shift @packages;
while (@packages) {
last if sum(@temp) + $packages[1] > 10;
my $next = pop @packages;
push @temp, $next;
}
push @bins, [@temp];
}
print Dumper(\@bins);
sub sum {
my $s = 0;
$s += $_ for @_;
return $s;
}
 [reply] [d/l] 

eric256,
No such luck. As Anonymous Monk points out elsewhere in this thread, the test case to meet is a bin size of 10 and an input list of 1,1,1,2,2,3,4,6,7,7 for which your solution fails.
 [reply] 
Re: Challenge: Twist On Bin Packing
by Limbic~Region (Chancellor) on Apr 08, 2006 at 01:05 UTC

All,
I have been unable to find anything other than a bruteforce method that always produces a correct answer. Feel free to use this to bench any new ideas against but all the existing ones in this thread are wrong. Please let me know if you discover a short cut.
When I first started learning perl, tye told me I had to stop thinking that less lines of code meant faster code. I think I learned this lesson well as the following brute force method is pretty fast but is definately not succinct. If you are interested in knowing how it works  let me know
The module:
 [reply] [d/l] [select] 
Re: Challenge: Twist On Bin Packing
by TedPride (Priest) on Apr 08, 2006 at 17:16 UTC

The object is to find the smallest combination of items that "fills" each bin, while still using as many of the smaller items as possible. So for 1 1 1 2 2 3 4 6 7 7...
1 1 1 2 4 (all 1's always go in first bin, and 2 4 adds up to 7 and uses a 2)
2 3 (adds up to 5 and uses 2 and 3)
6
7
7
I've tested with various sequences of numbers, and this method seems to always work. You still have to bruteforce a small number of combinations to find the smallest value, but the most you'll have to do for each bin is maybe a dozen.
EDIT: This assumes the bin size is small. Complexity increases relative to the number of combinations possible for the current bin, which can be fairly large if you have a large bin and a lot of small items. I'm still trying to figure out a way to increase efficiency for that. Anyhow:
use strict;
use warnings;
my ($binsize, %n, @n, $total, $smallest, $bin, @bin, @bins);
$binsize = 50;
push @_, ((int rand 10) + 1) for 1..1000;
my $c = 0;
my $time = time();
$n{$_}++, $total += $_ for @_;
while ($n{1} && $n{1} > $binsize) {
push @bins, [split //, '1'x$binsize];
$n{1} = $binsize;
$total = $binsize;
}
while ($total > $binsize) {
@n = (); push @n, [$_, $n{$_}] for sort {$a <=> $b} keys %n;
$smallest = $binsize + 1;
find(\@n, 0, 0, 0, '');
$n{$_}, $total = $_ for @bin = split / /, $bin;
push @bins, [@bin];
}
$bin = '';
$bin .= "$_ "x$n{$_} for sort {$a <=> $b} keys %n;
push @bins, [split / /, $bin];
for (@bins) {
print "@$_\n";
}
print "$c iterations in " . (time()  $time) . " seconds";
sub find {
$c++;
my ($n, $p, $stotal, $small, $set) = @_;
my ($num, $count) = $n[$p] ? @{$n[$p]} : 0;
if ($p > $#$n  $stotal + $num > $binsize) {
if ($smallest > $stotal && (!$small  $stotal + $small > $bin
+size)) {
$bin = $set;
$smallest = $stotal;
}
return;
}
my $remains = $binsize  $stotal;
my $max = $remains < $num * $count ? int($remains / $num) : $count
+;
for (reverse 0..$max) {
find($n, $p+1, $stotal+$num*$_, ($small  $_ == $max ? $small
+ : $num), $set."$num "x$_);
}
}
This required 1586177 function calls and 19 seconds for 1000 items between 1 and 10 and a bin size of 50. If you reduce the bin size to 10, then it only takes 15526 iterations and 5 seconds. I'm sure there's a way to significantly improve on this. For instance, if you have a bin size of 50, 20 2's, 10 3's, and a 5, then the minimum number of 2's you'll be using is all of them, since 40 + the largest number is smaller than 50. There's no need to go through the entire range of possibilities.  [reply] [d/l] 
Re: Challenge: Twist On Bin Packing
by aquarium (Curate) on Apr 07, 2006 at 13:45 UTC

 [reply] 

aquarium,
I did say exactly what "most inefficient" meant. It means you use the maximum number of bins while filling each one as near to capacity as possible. I think the example was pretty clear even if the wording wasn't.
 [reply] 

Perhaps a better definition would be "No remaining item can be added to any bin".
QM

Quantum Mechanics: The dreams stuff is made of
 [reply] 



