optimizing waste when sawing wood (math?)

Hello to you all,

This is not a Windev problem but a mathematical one (I think)
I have wood with a length of 6 meters.
I have to saw it into pieces with a different length. I now all the pieces and the length of them.
The problem is that I want to use as little wood (pieces of 6 meters) as possible. So I have to optimize the cutting.

Has anybody an idea how to do that? Has anybody a procedure or an algorithem?

Thanks in advance.

Regards Frans

Hello Frans

I found this site that may help
[quotationsystem.com]

It has a flow chart that explains the process
[quotationsystem.com]

Regards
Al

What kind of pieces ?
rectangular, round, elliptic ...
Sorry Frans, there is no general purpose algo. for that task.

The algorithm(s) you are looking for are difficult, up to nearly impossible, to implement in WD.
For rectangular Cutting Optimisation :
[www.tmachines.com]
(An ActiveX Control).

In case that your Google Fu is not good enough Cutting Optimisation is what you need
Bjoern
Erm : Otherwise see my message :
[forum.mysnip.de]

Hello to you all,

Thanks al for your flowchart. Thats what I came up to but I needed a general algorith.
Bjoern, thank you too. Cuting optomisation was the word and I found [www.optimalprograms.com]
I think they have good programs. But integrating them would cost many many hours.

What i need know is a simple multiple loop (or recursif programming) which gives the following results:

When I give a 3 the result is:
1
1,2
1,2,3

1,3

2
2,3

3

When I give a 4 the result is:
1
1,2
1,2,3
1,2,3,4

1,3
1,3,4
1,4

2
2,3
2,3,4
2,4

3
3,4

4

I can't get it working. Who can help me? The lines don't have to be in that order. It has to reproduce all lines. Thats it but I don't see the light. Who can give the code for N-lines?

Thanks in advance.

Regards Frans






Edited 2 time(s). Last edit at 09/23/2008 12:32AM by Frans.

Hi Frans,

I realized that binary counting gives all possible combinations:
3 digits:

001 = --1
010 = -2- 
011 = -21
100 = 3--
101 = 3-1
110 = 32- 
111 = 321

Just have to figure out a way to substitute the bits for numbers.:rolleyes:

Regards,
Piet

Be careful the flow chart (woodcutflowchart) does not produce an optimized result! The algorithm that is presented in this flow chart is well known. It is used to minimise the total cost of 'links' in a network. For instance if you want to minimize the cost of a road network linking together several cities. You rank all the possible links starting with the less expensive. Then you add the links one by one to the map starting with the less expensive. If there is no loop you leave the link, if there a loop (i.e. the link is redundant) you remove it. In the end you get the 'cheapest' network.

But in this case it does not work.

Let's imagine we have 6 pieces of wood to cut of the follownig lengths:
4 m
2.2 m
2.1 m
1.3 m
1 m
0.8 m

If you follow the chart you start cutting 4m then 1.3 m in a long piece of 6 meters. Then you hace to cut 2.2m, 2.1m and 1 m in a second 6 meter piece. You are left with the 0.8 meter piece to cut in a third 6m piece. What a waste!

The optimized solution in this case is the following:
Cut 4m + 1m + 0.8m in one 6 m piece
Cut 2.2m + 2.1m + 1.3m in a second piece

You lose only the minimum (0.2 + 0.4)

The problem must be considered as a 'classic' decision tree. The software must compare all the possible combinations and select the one producing the smallest quantity of waste. That is easy to do with windev (you can write efficient recursive procedures with windev). Everything depends on the volume of data to process. If you have many combinations to compare the program will be very slow. In this case it is customary to add an 'heuristic function' to limit the number of combinations to calculate.

I hope my message is clear.

Good luck.

M.

Hi, there are various mathematical methods for optimization.
[en.wikipedia.org])

Mathematics / Operations Research started out with <b>Linear Programming</b>.

Most common LP-solution (optimization / minimization) for small numbers (< 100) of constraints is the SIMPLEX algorithm.
[en.wikipedia.org]
[de.wikipedia.org]

This first generation of optimization programs heavily relied on Matrices (well-supported in WinDev). One should understand what optimization algorithms do (and can do) before writing your own or employing a third party DLL / ActiveX. Recommended: Read on the web or buy a good book and read it from start to end.

An old but still good source for buying such 'parts' is Palisade [www.palisade.com] with their Evolver Developer Kit [www.palisade.com] There are free libraries available too: [ool.sourceforge.net] Palisade offers consulting services too. It may be faster to go for professional (= mathematicians) support than to do the full research on your own.

There were always some special optimization methods for specific problems. e.g. the Travelling Salesman problem or the Newspaper Sales problem. Sometimes, you can find that your problem is better (and faster) solved by such a specialized algorithm.

The new generation of optimization methods tends to use <b>Genetic Algorithms</b> [en.wikipedia.org] where the near-to-optimal solution evolves by 'breeding' of generations of good solutions. GA has the advantage of being faster than matrix-based algorithms for problems with huge amounts of constraints.

Kind regards,
Guenter




Edited 1 time(s). Last edit at 09/23/2008 07:20AM by Jimbo.

Hello to you all,

I was gladly surprised by the fact that so many programmers did take the time for thinking about this problem. Thank you very much for the fast and excellent help.

Reading the reply's and looking at the solutions I think that for me the solution from Piet is the best (read fastest).
I have to optimize 100 to 200 cuttings. So looking for the first best cutting (with the lest waiste) and deleting the pieces I have already cut. Then reapeat the proces again works fine and fast enough for me.

So I looked in Windev for a binary datatype and couldn't find it.
I need functions like NumToBinary and BinaryToString. Or an alternatif. And then I have the program in no time working.
I think that there was something about it in the old forum. Is there a new page so that I can search in it?

Regards and thanks in advance.

Frans

Hi Frans,

Just to continue the idea of Guenter, a MiniMax algorythm with alpha beta pruning could lead to very good results in your case. The decision tree, if coded rigth for your needs, will always output the best solution. But it will require you time to understand the logic, then implement the alpha-pruning for optimization (that will be crucial in your case). (And it is more simple to implement than Genetic algorithm.)

I made a tictactoe game with that algo (to practice and understand it's working) and I can't beat the computer. It simply always win or get a nul match. Since that day I do not play my tictactoe game .

So the same logic will certainly give you good results if well implemented. You will always have a "win" since, like a chess game, the computer will evaluate the "best" solution. It takes time, but if the output makes you save a lot of money (by reducing waste), then it's worth the efforts.

There are excellent ressources on the web. Some will be more helpful that others. Here are couple links, but some could make you understand better than others. (I unfortunately "lost" an excellent link that made me understand it all... sorry.)

[en.wikipedia.org]
[www.cs.mcgill.ca]


Binary
There are no direct way (that I konw of) in WinDev, but you have the BinaryAND & al. functions. You can also use Val() with the hexadecial capability to build numbers. (i.e. you know the binary value.) 1 is 0001, 2 is 0010, 3 is 0011, 4 0100... so you "know" what you are doing. So BinaryAND(12,4) will give 2 (i.e. 1100 && 0010 = 0100 indeed) and BinaryAND(12,1) will give 0.

Then you can build a NumberToBinary easily by simply raising 2 to the exponent-1 of the desired bit (the fourth bit "1000" is Power(2,4-1)=8="1000". Then simply add:
Myinteger = Power(2,4-1)+Power(2,2-1)+Power(2,1-1)=11="1011"...

Same principle if you want to manage a string...
s is string = RepeatString("0",8)
s[[4]]="1" // the 4 can be obtained with BinaryAND, or other calculations, etc.
s = "00001000"

Hope this helps.

Hi Frans,

I just thought it was a nice puzzle. I came up with this:

sCombi is string
i,j,nbPieces,nCount is int

nbPieces=5  //Make this a funcion parameter

FOR i=1 _TO_ Power(2,nbPieces)
	nCount++	
	sCombi=RepeatString(" ",nbPieces)
	FOR j=1 _TO_ nbPieces
		IF BinaryAND(i,Power(2,j-1)) THEN
			sCombi[[j]]=NumToString(j)
		END
	END
	Trace(sCombi)
END

HTH, regards,
Piet

Hello to you all,

I have got it working.
I used the routine from Piet.
I use a maximun length and a minimum (600 cm max and 595 cm min)
With the binary numbers I search for length>min and length<max
When I found one I immediatly search for another combination. That way I don't have to search for all the 2 power number possibilities.
This goes very quick. Then I have some pieces left that could not fit in the 595..600 range.

Then I use the routine from Piet again and calculate all the possible values. I take the one nearest to 600 out.
Then I repeat this until all the pices are used.
Works fine and fast enough.

Thanks to you all for your help.

Regards, Frans