Algorithm to maximise raw material 1

[TimPen]

I have a piece of string which I need to cut into lengths.
I need to determine the the number of cuts per lenght to minimise waste

Say the length of the string is 100mm

Example 1
I need lengths of 40mm, 20mm
I would cut 2 of 40mm & 1 of 20mm

Example 2
I need lengths of 30mm
I would cut 3 of 30mm and have 10mm waste

I never know how many lenght variables there may be

How can I do this in a module?

Thanks in advance

 

[TimPen]

Many thanks

My sincere apologies!
I got the column headings "Boards Required" & "Strips Required" mixed up

Attached is the corrected file

 

[MajP]

So now it makes sense and confirms that Excel can solve this using the solver. The question is now how much do you want to automate it? You could write the vba in either Access or Excel to set up the model or you can do it manually in Excel. Neither would be overly complicated, but automating it in Excel would be simpler than automating from Access and calling Excel. How good is your VBA?

Manually, once you build a model the next time would take only a few minutes to set up a different one. I will run each of these and send you the spread sheet so you can see how to do it. The only somewhat tricky part is determining the feasible patterns. This could be automated, but can be done quickly manually. To do it manually (Example one)

1) take the stock and divide it by the small side. Figure out the max possible cuts and your answer is 17
2) Make a column (A) with values from 0 to 17 (representing the possible amount of small boards in a pattern. Round down to integer
3) Make a column B equal to A * lengths of small board. That will show how much of the pattern is used up by small boards
4) Make a column C which divides the (stock minus B) by the long board (representing how many more large boards you can get out of the pattern) round down
5) Make a column D which multiplies C * the long board dimension which represents the total amount of the pattern used up be the long boards
6) Make a column E which takes the stock length and subtracts B and D (Stock - amount of pattern consumed by small boards - amount of pattern consumed by long boards). This gives you the waste
7) Only keep those patterns where the waste is smaller than the short board dimension. These are the feasible patterns.

So the only thing that is really needed is a final matrix of fesible patterns representing the number of each board in a pattern

ex (I do not have the real numbers here but the matrix would look like)

142 442

17 1
10 3
4 4

That is the only difference in any of the models.

 

[TimPen]

Many thanks

So now it makes sense and confirms that Excel can solve this using the solver. The question is now how much do you want to automate it? You could write the vba in either Access or Excel to set up the model or you can do it manually in Excel. Neither would be overly complicated, but automating it in Excel would be simpler than automating from Access and calling Excel. How good is your VBA?

My VBA is pretty good (well I think so!) I would like to automate it from Access

Manually, once you build a model the next time would take only a few minutes to set up a different one. I will run each of these and send you the spread sheet so you can see how to do it. That would be great, thanks. The only somewhat tricky part is determining the feasible patterns. This could be automated, but can be done quickly manually. To do it manually (Example one)

1) take the stock and divide it by the small side. Figure out the max possible cuts and your answer is 17
2) Make a column (A) with values from 0 to 17 (representing the possible amount of small boards in a pattern. Round down to integer
3) Make a column B equal to A * lengths of small board. That will show how much of the pattern is used up by small boards
4) Make a column C which divides the (stock minus B) by the long board (representing how many more large boards you can get out of the pattern) round down
5) Make a column D which multiplies C * the long board dimension which represents the total amount of the pattern used up be the long boards
6) Make a column E which takes the stock length and subtracts B and D (Stock - amount of pattern consumed by small boards - amount of pattern consumed by long boards). This gives you the waste
7) Only keep those patterns where the waste is smaller than the short board dimension. These are the feasible patterns.

I understand your logic. Before I comment further i woulf like to see what Excel provides!

 

[MajP]

Here is the second example modeled in Excel.
Long side 622, short side 232.

http://www.4shared.com/file/6b25RHnq/232_622_Cutting_Stock.html

Using your solution of not mixing cuts it required 347 strips (267 strips @ 622, and 80 @ 232)

Using the solver I require only 291 strips with the following mix
pattern A: (2 @ 232, 3 @ 622) x 218
pattern B: (5 @ 232, 2 @ 622) X 73

1) Look at the link I previously provided on how to do the model in Excel.
2) Make sure to load the solver add-in
3) I have three tabs. The first is the default information, the second is how to find feasible patterns, the final is the solver model.

I am not sure if you can automate the solver (not sure if any objects are exposed). However, you can fully automate building the model, just will take some time.

 

[TimPen]

I can only say two things:
1. Brilliant
2. Thank you so much

I really appreciate your assistance
Bravo

Now to figure out how to automate solver!

 

[MajP]

I plan to keep working this. I will see if I can build a front end to the Excel model so that it automates constructing the model given the Stock Length, Short Side, Long Side, and # boxes.

Unless you change how you are doing things your problem is very defined and simplified from other models (Your only doing two types of cuts: short and long and you need the same amount of short and long sides). With that said, I plan to look at coding a module for this specific problem.

I think I can code a brute force that will run relatively quickly. I also plan to look at seeing if I can code a branch and bound solution.
In the short time you should be able to build spread sheets for each of your models.

 

[MajP]

Download this program.

http://delphiforfun.org/programs/Cutting Stock.htm

pretty cool, but the answers were off by 1 sheet from my Excel solutions. But it gives a real fast answer.

 

[TimPen]

found this:

http://www.dailydoseofexcel.com/archives/2005/09/12/cutting-stock-lengths/

 

[MajP]

You do not want that. It may give a slightly better version of your original method, or the same answer. Definitely will not optimize it.

All that is going to do is start filling boards with long cuts. If there is room for a small cut it will include it, if not goes to the next board and fills with long cuts until all long cuts are used. Then it would fill the boards with short cuts. In the case where there is not enough scrap to get a short cut on the long cut boards it gives you your original answer.

Assume there are 10 feasible patterns. Your original solution only considered two: All long, All short. This only considers 3
All Long
All long and (1) short (assuming longs are never twice as big)
All short.

 

[TimPen]

OK
Thanks

I will wait for you!

 

[MajP]

If you have not found it yet

http://peltiertech.com/Excel/SolverVBA.html

Tells you how to automate solver. So the only thing you have to figure out is defining the feasible patterns.
I would not wait for me, but go ahead with automating building the model and running solver.

Are you able to manually build a model, based on the example?

 

[TimPen]

I will look at this.
I am away for the next three days, so my response will be delayed - but I will respond!

 

[MajP]

http://www.4shared.com/file/-5rtUt9W/1D_Cutting_Stock_Template.html

Ok I did it. It is pretty cool if I say so myself.
User provides stock length, short side length, long side length, number of short side required, number of long side required.
Model builds a worksheet
Creates all feasible patterns
runs solver
Returns the integer optimal solution that minimizes the total patterns (strips) used.

Automating this from access would be simple. I use a user form to input the values and pass to a routine. but you can simply call from Access. You will then need to return the pattern count in the solution set. Should be able to keep this all hidden from the Access user. Should be relatively easy.

I have researched this and think rolling your own solution is doable, but very complicated. Since the number of patterns will be small in your case, you could by-pass having to do a column generating algorithm. However, I still think you would have to code the simplex method solution to get the non-integer solution. Then you have to do a branch and bound to find the integer solution. This requires a lot of array coding and matrix operations. There is lots of code for doing this, but I have not seen a vb solution.

They want to charge $1200! This is what they quoted me, and it is simply too expensive. I don't mind contributing, but this is too expensive

Just send me half what they are asking and we will call it even. Just kidding, it was an interesting problem.

 

[MajP]

http://www.4shared.com/file/jdN8eGx2/All_Examples.html

I used the model to run all examples. Take a look at the possible savings. The red is your original solution.

After doing that I plan to change it to just add a new sheet for each model instead of deleting the sheet. That way you could run all of the required patterns and have a worksheet for each, like I did.

 

[MajP]

Tim,
Are you still monitoring this thread? I have developed a solution for this problem that I believe is at most 1 strip more than the optimum. It works without any LP solver and all code can be in Access.

 

[TimPen]

Hi MajP

My sincere apologies!
As mentioned in a previous thread, I have been away. I returned this morning, but yes I am still monitoring this thread and would love to see your solution

 

[MajP]

I do not know if you watch any reality TV but there are a ton of shows now where someone finds something in a barn, storage bin, attic, etc. and take it into a pawn shop, appraiser, gun range, thrift store, etc., and no matter how obscure the owner knows exactly what it is and spits off a diatribe of random facts. Or they call in an expert friend who knows exactly what it is and spouts off a diatribe of random facts. This makes interesting and entertaining TV, but it is a little hard to believe any pawn shop owner really knows the names of all astronauts on Appollo 7. Most of the time the people just want to get through the random facts and know how much cash their crap is worth. So this will be kind of like this where I will give you a bunch of random background information before showing you the money. However, unlike the guys doing the appraisal I had to do a lot of research, and realized I pretty much forgot everything I have ever learned. Albert Einstein said "Education is what remains after one has forgotten everything one learned in school." So at least I proved I am "educated."
So as you know your problem is known as a 1 Dimensional Stock Cutting Problem. This is a classic problem in the field of Linear Optimazation. You can google this and see many papers and video lectures on this specific problem.
Linear optimization problems are problems of the form
Maximize/minimize some objective function
Subject to the following contraint functions
ex.
Maximize Z = 5 X1 + 3 X2

Subject to:
2 X1 + X2 >= 40
X1 + 2 X2 >= 50
X1 >= 0
x2 >= 0

your X1,X2, ... are called your decision variables. These usually represent tangible things like number of patterns, hours worked, resources, dollars. So they are never negative, and thus the bottom two constraints. With only two variables you can solve this graphically by drawing all contraints and the area bounded by all constraints is the feasible region. The solution has to lie in the feasible region. It can further be proven that the solution will always lie on the boundary of the feasible region where two or more constraints come together. That is called an extreme point. Three variables could be drawn on a computer and instead of lines intersecting you would have a region bound by planes. More than 3 variables you have to have faith.
If you look at this picture you see all four constraints plotted and the feasible region. The feasible region is the area with vertices a,b,c,d (the extreme points). The solution has to be at a, b,c,or d.

Now plot the objective function 5X1 + 3X2. This is shown by the red line. Keep moving it to the right until, you can go no further without and still touch the feasible region. The point it touches is the extreme point C. The value of X1 and X2 at C therefore optimizes the objective.

You can figure out the extreme points by solving any combination of those two inequalites. And since you are solving a point on a line you can replace the inequality with equal signs. This tells you where these two lines come together and we know that is at point C.
2 X1 + X2 = 40
X1 + 2 X2 = 50

This can be done easily by solving for X1 in one equation and subbing it into the othe equation
X1 = 50-2X2
sub into 1
2(50 - 2X2) + X2 = 40
100 - 4X2 + X2 = 40
60 = 3X2
X2 = 20
sub back into X1 = 50-2X2
X1 = 50-2*20
X1 = 10
extreme point C = (10,20)

(So your are asking, "Is there a point here?" Your problem can be boiled down to a series of 2 variable problems that looks almost exactly like the above.)

This works fine for 2 variables and a handful of constraints, but most real problems are 10s, 100s, 0r 1000s of variables and 10s, 100s, 0r 1000s of constraints. So although the Russians discovered linear optimization around the turn of the century, it was not until a great American Mathematician, George Dantzig came up with an algorithm, was there any practical use. His algorithm is called the simplex method. Basically it sets this problem in a matrix and uses a system of matrix operations to come up with the solution. Dantzig is really interesting and worth a read. However, even then it was not until computers were available that the real value was realized. One story of him is legendary.

An event in Dantzig's life became the origin of a famous story in 1939 while he was a graduate student at UC Berkeley. Near the beginning of a class for which Dantzig was late, professor Jerzy Neyman wrote two examples of famously unsolved statistics problems on the blackboard. When Dantzig arrived, he assumed that the two problems were a homework assignment and wrote them down. According to Dantzig, the problems "seemed to be a little harder than usual", but a few days later he handed in completed solutions for the two problems, still believing that they were an assignment that was overdue.[5]
Six weeks later, Dantzig received a visit from an excited professor Neyman, eager to tell him that the homework problems he had solved were two of the most famous unsolved problems in statistics.[2] He had prepared one of Dantzig's solutions for publication in a mathematical journal. Years later another researcher, Abraham Wald, was preparing to publish a paper which arrived at a conclusion for the second problem, and included Dantzig as its co-author when he learned of the earlier solution.
This story began to spread, and was used as a motivational lesson demonstrating the power of positive thinking. Over time Dantzig's name was removed and facts were altered, but the basic story persisted in the form of an urban legend, and as an introductory scene in the movie Good Will Hunting.

So the 1D Cut Stock cutting problem can be solved as a Linear Program using the simplex method... sort of.
minimize the sum of the patterns
subject to number of patterns * the number of specific cuts of a certain length in a pattern = the total number of required cuts of a certain length

If you can figure out all the feasible patterns this can be modeled and solved with the simplex method. Unfortunately most real world problems are not like yours. There may be many different stock lengths, many different lengths of required cuts, and different amount of cuts required. The number of feasible patterns can soon go into the thousands or more, making the problem cumputationally difficult even with advance computers. In the 1960s Gilmore and Gomory in a series of papers came up with a method that did not require enumerating all patterns. Like you, they started with just the patterns that contained one type of cut. They set it up using the simplex and did the first set of matrix manipulation. From there they solved a parrallel problem called the dual based off the constraints. This was in the form of another classic problem called the "knap-sack" problem. The answer from the knap sack told them which pattern to add to their matrix as a column. Each new column improves the optimization. Therefore this method is known as the "delayed column-generating" algorithm. Every iteration adds a new column. Basically you only add patterns that are possibly in the solution set. This could reduce a problem that had millions of iterations into tens or hundreds.

Now there is unfortunately one more step. The solution to these algorithms is continous. In other words X1,X2,.. XN can be a non integer solution. Integer solutions to optimization problems are normally solved by first finding the continous solution and then using that as a starting point to find the integer solution. A popular algorithm is known as Branch and Bound.
So most of the software packages doing Cutting Stock problems apply these methods. That means to make a general solution if you can not find the code
Simply formulate the problem
code the simplex
Code the column generating
code the knap sack
code a branch and bound or similar integer algorithm
Yeah... I do not think so. However you can find this code out there and with enough time build this. I have seen some code an it is actually pretty concise.

Lets then look at your problem which is far simpler than most real world problems. You have only two types of cuts, which leads to two constraints (plus all the non negativity constraints. You can not have negative amount of patterns). We know we can enumerate all feasible patterns, and we know that the continous solution occurs at an extreme point.
So unless I am wrong about this (because this is my premise that the whole thing is based on), your solution occurs at an extreme point of only 2 or less variables. Each pattern is represented by a variable so here is the approach.
1)Enumerate all feasible patterns. Easy since only 2 types of cuts.
2)Take every pattern by itself and solve for X. To determine best solution using a single pattern.
3)Next take every combination of 2 patterns and solve for this to get the best solution using two patterns.

This gives a continous solution. But if you round up from this, the worst it can be is one more sheet than the optimal solution. I am not going to code an integer solution at this time.

So here is an example.
Short side: 142
Long side: 442
Stock: 2440
Required short sides: 800
Required long sides: 800

Here are all the feasible patterns
FEASIBLE PATTERNS:
P1: 1x142, 5x442
P2: 4x142, 4x442
P3: 7x142, 3x442
P4: 10x142, 2x442
P5: 14x142, 1x442
P6: 17x142, 0x442

Figure out the best you can do with one pattern. (5 possible solutions since the lat pattern can not provide a solution since it has no long sides)
The answer is
200 strips of (4x142, 4x442)

Now solve every combination of the two patterns.
X1 is the number of pattern one
X2 is the number of pattern two
for example the first to problems would be this problem
mimimize X1 + X2
ST: 1 X1 + 4X2 >= 800 Required number of Short Sides
5 X1 + 4X2 >= 800 Required number of Long Sides
As shown above you can solve this problem by the substitution method.

Now I had the code that allows me to generate all the combinations of patterns. Because you have to solve
P1 and P2
P1 and P3
..
P1 and P6
P2 and P3
...
P2 and P6
..
P5 and P6

And that code is difficult by itself.

BEST TWO PATTERN SOLUTION
150.72 of 1x142, 5x442
46.38 of 14x142, 1x442
Total Patterns 197.1015

BEST TWO PATTERN INTEGER SOLUTION
151 of P1: 1x142, 5x442
47 of P2: 14x142, 1x442
Total Patterns 198

So in theory this sounded easier, but it really became a bear. Heck I probably could have coded the real method.

In certain cases there is not a 2 pattern solution or the one pattern solution is better.

Now I just round up the two pattern or one pattern continous solution to the integer solution. If you applied an integer algorithm more patterns could enter the solution, but I believe at best you can save one strip. So give it a try, and compare to the solver method to verify my logic is not wacked. I have it in excell and hope you can follow the code. Run the user form from the Macro and try some different problems. It uses a user form to pass the values and display the result, but you should be able to pass into to module values from an access form or table.

The mdl of concern is called mdlCSP and the method is runCSP. Everything is encapsulated in class modules, and you do not really have to understand what is in there. Just see how to instantiate a cuttingStockProblem object and use the methods/properties of that object.

Here is the code in Excel

http://www.4shared.com/file/Wryjiaa3/1D_Cutting_Stock_Template_No_S.html

 

[TimPen]

Hi MajP

Thank you very much.

I have one last question (I hope)

Your model allows a single stock length and two cut sizes. In real life I would have a single stock length with multiple cut sizes!

I had a scenario today where I had one stock length and four cut sizes. Can you model be adapted for this?

I really do appreciate your assistance

 

[MajP]

No my code was specifically designed to solve only the two size problem.

My original code using solver could be easily modified to provide a solution for a multi cut problem up to about 6 cut sizes. That is because it requires you to still enumerate the possible patterns. As stated, this blows up real quickly. Assume you have 6 cut sizes and you can get at the most 4, 6, 8, 10, 12, 14 pieces of a given cut out of a strip.
To enumerate the possible patterns you would have to cycle through 4*6*8*10*12*14 = 322560 iterations.

So more than six patterns really requires delayed column generating or another dynamic programming algorithm. Have you downloaded this program?

http://delphiforfun.org/programs/Cutting Stock.htm#Download

This thing works amazing, and it demonstrates the efficiency of the algorithm. Even shows you a picture of your cuts and can do cost. It is crazy fast. I ran a 12 cut problem and it still solved it instantaneously. It is really easy to use. It is written in delphi with the source code provided. If it was me I would just use this and put the answer into my database. Maybe you can use sendkeys and automate it.

If you had a whole lot of time then I would try to translate into vb. If I get motivated I might try it, but that will take a me whole lot of time.