RRP: Reduced Raster Points Calculation

[JamesBremner]

The akgorithm RRP is used to reduce the number of discretization points calculated by DDP.

I cannot find psuedo code for this.

The paper describes the RRP as:

L is the total length.
P is the discretization points
P with hat is the raster points

s ?????

I cannot see how to implement this. It looks like it simply converts the P points to the same number of points with values of how much smaller they originals are then the total length. There must be more to it than that.

And what is s?

[Cashewfly]

I have only some additional data to add that might spur some thinking. In table 2 of the 3d paper, there is this entry:

gcut1_3dr is defined in the file gcut1.txt which can be gotten from the zip file referenced at http://www.loco.ic.unicamp.br/files/instances/3duk_knapsack.zip. gcut1.txt contains.

10
250 250 250
167 184 143
114 118 69
167 152 143
83 140 167
70 86 114
143 166 83
120 160 69
66 148 83
87 141 114
69 165 114
gcut1_3dr

The point of all this is that for the above data set, the number of discretization points is 92 and the number of raster points is 15.

I was puzzled by the use of 's' as well. It seems to be used without definition in several of the algorithms. I had hoped that it had some special meaning in academic pseudo-code that would be apparent to someone who was more familiar with reading academic papers.

I'm heading into a meeting...

[Cashewfly]

I just remembered I have something else to offer:

There is a function called constructRasterPoints(...) here:

https://github.com/rafaeelaudibert/RecursivePartitioningAlgorithm.dart/blob/1168ab628fd522da2f7ac49eb9aaebfc0e494464/cpp/sets.cpp

That I'd started looking at and never really gotten any further than that.

[JamesBremner]

I think the s must have been copied from the Scheithauer paper, which I have just uploaded to the doc folder

[JamesBremner]

from the Scheithauer paper

[JamesBremner]

Eq 1 looks like the conic combination == discretization points

https://en.wikipedia.org/wiki/Conical_combination

L is the size of the bin dimension ( width, depth or height )
l is the set of item dimensions
r is a point value
a is the set of positive integers
mhat is the number of different item types

[JamesBremner]

Eq 2

s in angle brackets is the largest conic combination point that is smaller than s

[JamesBremner]

Got it I think. In Eq 3 we are expected to substitute for angle bracket L-r angle bracket Eq 2 with L-r substitued for s.

[JamesBremner]

I will implement that and see what it looks like

[JamesBremner]

Implementation:

knapsack/src/RRP.cpp

Lines 1 to 44 in 31b78b1

	#include <vector>
	#include <algorithm>
	#include "knapsack.h"
	int LargestInVSmallerThanX(
	std::vector<int> V,
	int X
	)
	{
	int R = -1; // assume all +ve
	for( int t : V )
	{
	if( t <= X ) // smaller or equal
	if( t > R ) // largest
	R = t;
	}
	return R;
	}
	/** Calulate set of reduced raster points
	@param[in] D the bin size in one dimension
	@param[in[ d the item ypes sizes in same dimension
	This implements https://github.com/JamesBremner/knapsack/issues/1#issuecomment-648373643
	*/
	std::vector<int> RRP(
	int D,
	const std::vector<int>& d )
	{
	std::vector<int> reduced_raster_points;
	auto S = DDP( D, d ); // set of conic combinations
	for( auto p : S ) // loop over discretization points
	{
	int r = LargestInVSmallerThanX( S, D - p );
	if( r >= 0 )
	reduced_raster_points.push_back( r );
	}
	// arrange in ascending size
	std::reverse(reduced_raster_points.begin(),reduced_raster_points.end());
	return reduced_raster_points;
	}

For bin dimension 10 and item dimensions 5, 7 this gives

DDP
5 7 10
RRP
5

which looks very promising

[JamesBremner]

It seems that this is too aggresive.

With bin 13 x 13 x 13 and item type 4 x 4 x4 we should be able to cut out 27 items, with cuts a 4, 8 and 12 in each dimension.

However:

DP3UK
DDP
4 8 12
RRP
4 8
length raster points 4 8
width raster points 4 8
height raster points 4 8
Most valuable item in ( 4 4 4 ) has value 5
Most valuable item in ( 4 4 8 ) has value 5
Most valuable item in ( 4 8 4 ) has value 5
Most valuable item in ( 4 8 8 ) has value 5
Most valuable item in ( 8 4 4 ) has value 5
Most valuable item in ( 8 4 8 ) has value 5
Most valuable item in ( 8 8 4 ) has value 5
Most valuable item in ( 8 8 8 ) has value 5
horizontal cut 0 0 1 5 0 0 5<5+5
depth cut 0 1 0 5 0 0 5<5+5
vertical cut 1 0 0 5 0 0 5<5+5
vertical cut 1 1 1 5 0 0 5<5+5
item type 0 value 5 at 4 4 4
item type 0 value 5 at 4 4 8
item type 0 value 5 at 4 8 4
item type 0 value 5 at 4 8 8
item type 0 value 5 at 8 4 4
item type 0 value 5 at 8 4 8
item type 0 value 5 at 8 8 4
item type 0 value 5 at 8 8 8
8 items, total value 40

Vertical cuts at 4
Depth cuts at 4
Horizontal cuts at 4

[Cashewfly]

I've spent 15 minutes looking through the code and I'm not seeing any obvious bugs, and I agree with your reasoning that there should be 27 items. Despite that, I'm very impressed with today's progress!

[JamesBremner]

Thanks. Good to have a second pair of eyes on the code.

[JamesBremner]

The RRP code is apparently insufficiently aggressive.

From paper:

but RRP gives

DP3UK
read problem gcut1_3d
length raster points ( total 26 ) 66 66 70 70 70 83 83 87 87 87 87 87 87 87 87 87 114 114 114 120 136 157 167 180 180 184 
width raster points ( total 7 ) 86 86 86 86 86 118 160 
height raster points ( total 8 ) 83 83 83 83 83 114 167 167 

It is a pity that the paper does not provide the 15 raster points they use.

[JamesBremner]

Apparently the problem is in DPP ( rather than RPP )

DP3UK
read problem gcut1_3d
<=DPP total points 67
<=DPP total points 18
<=DPP total points 19
length raster points ( total 26 ) 66 66 70 70 70 83 83 87 87 87 87 87 87 87 87 87 114 114 114 120 136 157 167 180 180 184
width raster points ( total 7 ) 86 86 86 86 86 118 160
height raster points ( total 8 ) 83 83 83 83 83 114 167 167

[Cashewfly]

I agree about the papers lack of working data-sets. Did you have a chance to look at the conic combination and raster point code in

https://github.com/rafaeelaudibert/RecursivePartitioningAlgorithm.dart/blob/1168ab628fd522da2f7ac49eb9aaebfc0e494464/cpp/sets.cpp

[JamesBremner]

So, I am looking at the DDP algorithm

As far as I can see, my code has faithfully implemented it

knapsack/src/DDP.cpp

Lines 23 to 41 in 9d30fb3

	std::vector<int> P; // calculated discretization points
	std::vector<int> c( D+1 );
	for( int i = 0; i < (int)d.size(); i++ )
	{
	for( int j = d[i]; j <= D; j++ )
	{
	if( c[ j ] < c[ j - d[i] ] + d[ i ] )
	c[ j ] = c[ j - d[i] ] + d[ i ];
	}
	}
	for( int j = 1; j <= D; j++ )
	{
	if( c[ j ] == j )
	P.push_back( j );
	}
	return P;

Yet this code produces just 67, 18, 19 points, while the paper says it should produce 92, 92, 92.

[Cashewfly]

Did you notice the clause at the top of the table that states 'considering rotations'?

[JamesBremner]

Allowing rotation would add a lot of points!

[Cashewfly]

I think many of the points would be duplicates. I think rotation is the only thing that could explain the fact that all three orientations have 92 points.

[JamesBremner]

Here is a manual check on the RRP algorithm implementation

First, lets make the description in Scheithauer paper more understanable by ordinary human beings

Let S be the discretization points
Let L be the bin dimension

Using the function
< S, s > = max( max in S which is less than s )

Reduced raster points are
RRP(S) = all < S, L-r > where r in S

For problem of 4 unit cube items in 13 unit cube bin

S = { 4 8 12 }
L = 13

<S,4> = 8 ( 13 – 4 = 9 )
<S,8> = 4 ( 13 – 8 = 5 )
<S,12> = n/a ( 13 – 12 = 1 )

which is what the code I implemented produces.

So the bug ( which cause only 8 items to be cut from the bin ) must be in DP3UK itself

[JamesBremner]

I think many of the points would be duplicates.

Indeed!

So, let's skip all this mucking around with reduced raster points and simply remove duplicates from the discretization points!

The results for item4cube_bin13cube are perfect

DP3UK
read problem item4cube_bin13cube
<=DPP total points 3
<=DPP total points 3
<=DPP total points 3
length raster points ( total 3 ) 4 8 12 
width raster points ( total 3 ) 4 8 12 
height raster points ( total 3 ) 4 8 12 
Most valuable item in ( 4 4 4 ) has value 64
Most valuable item in ( 4 4 8 ) has value 64
Most valuable item in ( 4 4 12 ) has value 64
Most valuable item in ( 4 8 4 ) has value 64
Most valuable item in ( 4 8 8 ) has value 64
Most valuable item in ( 4 8 12 ) has value 64
Most valuable item in ( 4 12 4 ) has value 64
Most valuable item in ( 4 12 8 ) has value 64
Most valuable item in ( 4 12 12 ) has value 64
Most valuable item in ( 8 4 4 ) has value 64
Most valuable item in ( 8 4 8 ) has value 64
Most valuable item in ( 8 4 12 ) has value 64
Most valuable item in ( 8 8 4 ) has value 64
Most valuable item in ( 8 8 8 ) has value 64
Most valuable item in ( 8 8 12 ) has value 64
Most valuable item in ( 8 12 4 ) has value 64
Most valuable item in ( 8 12 8 ) has value 64
Most valuable item in ( 8 12 12 ) has value 64
Most valuable item in ( 12 4 4 ) has value 64
Most valuable item in ( 12 4 8 ) has value 64
Most valuable item in ( 12 4 12 ) has value 64
Most valuable item in ( 12 8 4 ) has value 64
Most valuable item in ( 12 8 8 ) has value 64
Most valuable item in ( 12 8 12 ) has value 64
Most valuable item in ( 12 12 4 ) has value 64
Most valuable item in ( 12 12 8 ) has value 64
Most valuable item in ( 12 12 12 ) has value 64
horizontal cut 0 0 1 64 0 0 64<64+64
depth cut 0 1 0 64 0 0 64<64+64
depth cut 0 1 2 64 0 0 64<64+64
horizontal cut 0 1 2 128 0 1 128<128+64
depth cut 0 2 1 64 0 1 64<64+64
vertical cut 1 0 0 64 0 0 64<64+64
vertical cut 1 0 2 64 0 0 64<64+64
horizontal cut 1 0 2 128 0 1 128<64+128
vertical cut 1 1 1 64 0 0 64<64+64
vertical cut 1 2 0 64 0 0 64<64+64
depth cut 1 2 0 128 0 1 128<64+128
vertical cut 1 2 2 64 0 0 64<64+64
depth cut 1 2 2 128 0 1 128<64+128
vertical cut 2 0 0 64 0 1 64<64+128
vertical cut 2 0 2 64 0 1 64<64+192
vertical cut 2 1 1 64 0 1 64<64+128
vertical cut 2 2 0 64 0 1 64<64+256
vertical cut 2 2 2 64 0 1 64<64+384
item type 0 value 64 at 4 4 4
item type 0 value 64 at 4 4 8
item type 0 value 64 at 4 4 12
item type 0 value 64 at 4 8 4
item type 0 value 64 at 4 8 8
item type 0 value 64 at 4 8 12
item type 0 value 64 at 4 12 4
item type 0 value 64 at 4 12 8
item type 0 value 64 at 4 12 12
item type 0 value 64 at 8 4 4
item type 0 value 64 at 8 4 8
item type 0 value 64 at 8 4 12
item type 0 value 64 at 8 8 4
item type 0 value 64 at 8 8 8
item type 0 value 64 at 8 8 12
item type 0 value 64 at 8 12 4
item type 0 value 64 at 8 12 8
item type 0 value 64 at 8 12 12
item type 0 value 64 at 12 4 4
item type 0 value 64 at 12 4 8
item type 0 value 64 at 12 4 12
item type 0 value 64 at 12 8 4
item type 0 value 64 at 12 8 8
item type 0 value 64 at 12 8 12
item type 0 value 64 at 12 12 4
item type 0 value 64 at 12 12 8
item type 0 value 64 at 12 12 12
27 items, total value 1728

Vertical cuts at 4 
Depth cuts at 4 
Horizontal cuts at 4 

[Cashewfly]

LOL! I was just writing that. It looks like there is some slight problem with RRP, but since RRP is just an optimization I think we can safely bypass it in the interests of moving on with the other algorithms.

[JamesBremner]

OK