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