H3CS Heuristics for the 3D Stock Cutting problem

[JamesBremner]

This divides the items into levels that are the same height and solves each level using a 2D algorithm

The challenge is the 2D algorithm.

In freelance chat I suggesting using DP3UK and confining everything to a single height. The advantage was we already have the code . However, it is a silly idea. DP3UK is unbounded, which means that it is free to duplicate some items and forget about others, which is not what we want here.

The paper references a lot of different possible 2D cutting algorithms, without going into detail for any. So, to keep things moving along I decided to implement an algorithm I am familiar with from my other work in this area. RK2FFG is rectangular knapsack 2D first fit greedy algorithm. https://github.com/JamesBremner/knapsack/blob/master/src/RK2FFG.cpp

I have committed an initial H3CS application using RK2FFG

This issue is intended to discuss how exactly to improve this going forward.

[JamesBremner]

The biggest limitation of RK2FFG is that it does not provide guillotine cuts - cuts that go from one edge of the bin all the way to the other. As I understand it, you are not cutting the timber, but stacking it. So perhaps guillotine cuts are just nice to have rather then necessary? Let me know.

[Cashewfly]

The timber application will require guillotine cuts exclusively.

I must have miscommunicated something earlier. The timber application will be cutting larger timbers into smaller timbers to fill custom timber orders.

[JamesBremner]

Well, I totally got the wrong end of the stick there. It makes a huge difference.

I have done several projects with cutting in 2D, but my 3D work so far has always been bin packing.

[JamesBremner]

Yes, I am planning on implementing a full timber allocation system. Incoming timbers can be up to 100000 integer units (100ft in 100ths of a ft) in length and 3000 integer units in height and depth. Stock will be several hundred timbers, and at any given time there will be several hundred items that will need to be optimally allocated.

"allocated" what doe the word mean to you?

I visualized tracks arriving with bundles of logs and you needing to work out where to place them in the timber yard. But you mean something like orders to be met by cutting large timbers into smaller ordered pieces. A single piece of timber 100 by 30 by 30 ft! Maybe 200 years ago Canada exported timbers like that, but not nowadays.

[Cashewfly]

3d guillotine cutting is why I'm so interested in this paper. As far as I can tell, it's the only place it's addressed.

[Cashewfly]

Oops, I mis-scaled. It would be a maximum of 100x3x3ft. More likely it would be 42x2x2ft.

Allocated means taking an inventory timber (which could be any size because 'waste' is returned to inventory) and cutting out pieces to fill custom orders. The pieces can also be any size. These will be typically be used in churches and residences and often upscale sporting goods stores.

A typical run would be 80 inventory items and 200 order items. Optimizing what is returned to inventory is also a huge factor. Wood is too expensive to let any of it go unused.

[JamesBremner]

Those sizes seem a lot more likely!

[JamesBremner]

Let's talk about guillotine cuts.

Here's a problem from a previous 2D client.

The client accepted this layout, becuase he could set his machine to do two horizontal guillotine cuts ( G-cuts ) and then vertical G-cuts on the smaller bits.

This one was rejected:

[Cashewfly]

I would also accept the first and reject the second.

[JamesBremner]

A typical run would be 80 inventory items and 200 order items.

How would you like to input this data? Do you have a sample dataset?

[JamesBremner]

Extending the idea of G-cuts to 3D: Do you accept the ideas of H3CS? Specifically, dividing up the items to be cut into levels of the same height. Thus the first G-cuts will be horizontal, splitting the levels apart.

If so, then I can use the ideas I developed for doing G-cuts in 2D.

[Cashewfly]

Yes, I think cutting in levels is worth pursuing. It seems likely that in most cases it will give good results.

I'll look into generating an input file of our current inventory and orders tomorrow morning.

Since you already have parsing code for the format from your Pack code I'll generate the data in that format, meaning

The bins should be passed in the following format:

"id:dim_unit:quantity:size1xsize2xsize3:weight"

The items passed like so:

"id:dim_unit:constraints:quantity:size1xsize2xsize3:weight"

[JamesBremner]

I can handle that input.

That format is from my old packing engine and it was inherited from a previous developer, so it is really old fashioned. These days I always have to write frontends for it.

Since we are starting fresh with a new cutting engine, I would prefer to use something more modern, if it is all the same to you Something like this can be simply generated using excel.

i 10000 300 300 5 stock1      // 5 inventory timbers 100ft by 3ft by 3ft  id is stock1  ( bins )

d 600 50 17  20 test        // demand to cut 20 timbers 6ft by 6in by 2in  id is test ( items )

[JamesBremner]

In general: space delimited text file with 6 columns, lines in any order

[Cashewfly]

I've uploaded timber-alloc-data.txt to the data folder

It contains 62 inventory items and 127 order items.

The only change from your suggested format is that the dimensions are scaled by 1000 rather than 100.

[JamesBremner]

I've uploaded timber-alloc-data.txt to the data folder

Not sure what you mean by this. I can see no commit from you.

In any case, please do not commit directly to the repository. Simply zip your file then drag and drop it into one of these comment boxes on the issue page.

I would welcome contributions from you to this repository. Let me know when you have a contribution, and I will take you through the procedure. ( essentially: fork repository, clone the fork, commit to fork, post a pull request. )

Another option is email. My address is on my profile https://github.com/JamesBremner

[Cashewfly]

I'll opt for the zip upload for now. My git / github skills are rusty.

timber-alloc-data.zip

[JamesBremner]

Looks good.

[JamesBremner]

I've uploaded timber-alloc-data.txt to the data folder

It contains 62 inventory items and 127 order items.

The order count is off.

>timberAllocation.exe ../data/timber-alloc-data.txt
TimberAllocation1
Inventory contains 62 timbers
Order demands 77 timbers

I'm fairly sure of my count because a small test gives

C:\Users\James\code\knapsack\bin>type ..\data\t1.txt
i 6000 1250 5500 3 4614
i 7000 1250 5500 4 4614
d 12000 1500 7500 5 299493
d 13000 1500 7500 6 299493
C:\Users\James\code\knapsack\bin>timberAllocation.exe ../data/t1.txt
TimberAllocation1
Inventory contains 7 timbers
Order demands 11 timbers

[Cashewfly]

You are right. I'm not sure where that 127 came from. Sorry!

[JamesBremner]

We seem to have reached agreement on the input file format for now. I have documented it at https://github.com/JamesBremner/knapsack/wiki/File-Formats

I have also proposed a similar output file format in that page. It is probably best to regard this as for debugging purposes at the moment. However, if you would like to discuss details of what you need in the output file(s), please open a new issue for that.

[JamesBremner]

Today I committed coded so that the timberAllocation application implements the H3CS algorithm.

Don't get excited!!!

This uses a extremely simplified 2D stock cutting algorithm as a placeholder so that I can shake the bugs out and have a stable platform to develop the various optimizing 2D algorithms that have been considered.

I have called the algorithm CS2LNW: Cutting stock 2 dimensional no width. The function declaration documentation describes the limitations and failures.

knapsack/src/TimberAllocation.h

Lines 179 to 200 in 9c10ed8

	/** Cutting stock 2 dimensional no width
	@param[out] I the instance
	@param[in level
	@param[in] h height in stock
	This is an extremely simple 2D cutting stock algorithm
	to be used as a placeholder in the H3CS algorithm.
	Currently it does not provide an interface allowing
	levels to be stacked, not for a level to be distributed
	over multiple stock timbers. I will be adding this.
	This makes no effort to stack in the width dimension.
	The effect is that this will fail if all the orders in
	a level cannot be cut in one line along the bottom of the
	allocated stock timber. Even if it does not fail, the wastage is
	likely to be enormous!
	*/
	void CS2LNW(
	cInstance& I,
	cLevel& level, int h );

[JamesBremner]

I have implemented level stacking ( cutting multiple levels from one stock timber )

[JamesBremner]

I have implemented allocating levels to multiple stock timbers as required.

Here is the output from running on timber-alloc-data.txt

a.zip

Notice that there are no W cuts, because the simple-minded 2D packing algorithm used ignores the width dimension. So the result is horribly inefficient! It does demonstrate that the H3CS is basically running on a real world problem instance.

Next: replace the 2D algorithm with a full-featured 2D optimizing algorithm. My intention is to try https://github.com/JamesBremner/pack2 Unless you have some other idea?

[Cashewfly]

I think trying the pack2 algorithm is a good way to proceed.

I've been looking through the a.a output file and believe I understand the format. The first thing that catches my eye is the allocation

a.a

a 3751 821644:10
a 3751 821644:11
a 3751 821644:12
a 3751 821644:13
a 3751 821644:14
a 3751 821644
a 3751 821644:9
a 3751 821644:8
a 3751 821644:7
a 3751 821644:6
a 3751 821644:4
a 3751 821644:3
a 3751 821644:2
a 3751 814843
a 3751 821644:5

timber-alloc-data.txt

i 10000 5750 5750 1 3751
d 10000 5500 7500 14 821644

---

This allocation doesn't work because the demand dimension 7500 is greater than the inventory dimension 5750. Is this what you mean when you say the algorithm is ignoring the width dimension?

I presume it is. Mostly I'm asking to see if I'm truly understanding the output format.

[JamesBremner]

Is this what you mean when you say the algorithm is ignoring the width dimension?

Yes.

I have understated the problems with CS2LNW. It is not just inefficient, it may produce unfeasible solutions. This could be fixed relatively simply, but I think it better to move onto to trying 'real' 2D packing algorithms.

to see if I'm truly understanding the output format.

Check out the file format documentation at https://github.com/JamesBremner/knapsack/wiki/File-Formats Let me know if you want a different file format.

[Cashewfly]

I can visualize the current format, so let's go with that.

[JamesBremner]

I have integrated pack2 with TimberAllocation. Here is the result when pack2 is used to pack the levels.

a (2).zip

[JamesBremner]

Looking at the result in detail: the level with the most orders is 3500

level 3500 ( 505837:5 505837:3 505837:2 505837:4 505837:14 505837:6 505837:7 505837:8 505837:9 505837:10 505837:11 505837:12 505837:13 627349 627349 627349 627349 516465 516465 516465 627349 627349 627349 627349 627349 627349 627349 627349 505837 )

Most of these do not get cut. I believe this is because there is insufficient inventory. If I multiply inventory id 7376

16000 4250 10000 1 7376

to 20

i 16000 4250 10000 20 7376

then the level is packed OK.

This encourages me that the application is doing sensible things.

[Cashewfly]

I agree with you that it is working in a reasonable manner. That's pretty impressive. I've been looking through the code and find it readable and understandable though I'm sure there are fine points in there I'm only going to understand with more detailed examination. Things are looking good!

[JamesBremner]

Thanks!

I'm happy to add code documentation at any points where you suggest that it is required.

[Cashewfly]

I've been trying to build and work through the project with the build file timberAllocation.cbp and it's failing with

/home/kent/swc/jamesb/knapsack-master/src/taCutter.cpp: In function ‘bool ta::CS2Pack2(ta::cInstance&, ta::cLevel&, int)’:
/home/kent/swc/jamesb/knapsack-master/src/taCutter.cpp:313:20: error: ‘RawCutList’ was not declared in this scope
auto binList = RawCutList( E )[0];
^~~~~~~~~~
/home/kent/swc/jamesb/knapsack-master/src/taCutter.cpp:314:20: error: unable to deduce ‘auto&&’ from ‘binList’
for( auto& c : binList )
^~~~~~~
I'm guessing this is a problem with me being unfamiliar with codeblocks. Do you have any suggestions that might help me get this to build and run?

[JamesBremner]

This is because I have not committed the changes to pack2 required by TimberAllocation.

Please hold while I do so.

[JamesBremner]

Committed.

You will need to update your code for BOTH pack2 and knapsack

[JamesBremner]

To prevent build problems, check out https://github.com/JamesBremner/knapsack/wiki/TimberAllocation-build