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
