There is definitely purchasable software which may expose dlls and some free software. Just Google “1D Cutting Stock Software.” If you can go this way, I would strongly recommend it. I will try to look at some of the free stuff and see if I can get something that Access can talk to. If what mcescher suggests works with Access that would be a good option. Adapting existing code into Access will not be trivial and writing something from scratch is not really doable in a cost effective way. Most of these programs solve this problem as a Linear Optimization Program (LP) using a technique called Delayed Column Generating which is solving two different but related LPs iteratively. There are also a lot of open source generic LP solvers, but even formulating the problem is somewhat difficult if you have not done this before.
I will try to explain in general how this is solved and what is involved in rolling your own solution.
The standard formulation for the cutting-stock problem starts with a list of “m” orders (where an order is a different cut size) each order requires q(j) pieces where j = 1 to m. In your example you have m = 11 orders with their corresponding quantities.
Piece
(m) Order Quantity (q)
1 18 5 q(1)
2 19 4
3 24 17
4 25 2
5 27 6
6 29 2
7 33 2
8 34 3
9 41 2
10 43 1
11 54 7 q(11)
In the first step in formalizing the problem you need to first identify all the feasible combinations of cuts (often called "patterns"). That usually requires some kind of spanning tree algorithm. For something small this may be doable, but the number of possible patterns grows exponentially as a function of m, the number of orders. ( As the number of orders increases, it may therefore become impractical to enumerate the possible cutting patterns which lead to another solution called the delayed column generating algorithm). A simple example would be
stock of 10 ft
Order Quantity
2 q(1) 20
3 q(2) 30
4 q(3) 40
This would lead to the feasible patterns of
X1 2 2 2 2 2
X2 2 2 2 3
X3 2 2 3 3
X4 2 2 2 4
X5 2 4 4
X6 3 3 4
X7 3 3 3
So there are “n” = 7 patterns, and in the LP we associate with each pattern a positive integer variable X(i), representing how many times pattern i is used, where i=1…n.
Now you need to know “A(i,j)” where A(i,j) is the number of cut size (orders) “j” in pattern “i”
From there you can build a linear integer program. This consists of an objective function (minimize or maximize) and a series of constraints. (This could be shown with summations, but too hard to type)
Objective: Minimize the number of cuts
Min X(1) + X(2) + X(3) + … + X(7) ( where X1 is the number of pattern 1, X2 number of pattern 2, etc)
Subject To
A(1,1)X1 + A(1,2)X2 + A(1,3)X3 … >= q(1)
….
A(3,1)X1 + A(3,2)X2 + A(3,3)X3 … >= q(3)
In other words the constraints say that the sum of the number of a given piece within each pattern is greater than or equal to the number of that piece required. So just writing the code to formulate the problem would not be that trivial. I would imagine you would have several hundred to thousands of feasible patterns for your example.
In general to solve an LP you convert those constraints and the objective function (plus some other columns) and put them into a matrix (called a tableau). The Simplex method uses interations of matrix pivots and then comparing that to the objective function to determine the next matrix pivot. So if your coding you need to code a lot of matrix math and matrix operations. Again not trivial.
Now in truth most Cutting Stock solvers do not do that. The reason as said, the number of feasible patterns may be too expensive to iterate. A solution known as a Delayed Column Generating algorithm is used. Instead of iterating all the patterns it starts with a few set of patterns. But after you do your iterations you solve another LP (it is called the dual and it is like a transpose of your original problem). This alternate problem is known as the knapsack problem, using dual variable information from your original linear program. That problem then gives the new pattern (column) to add to the original. Coding that would require formulating the second LP based on the original LP. And then you are not quite done, because this gives a non-integer solution requiring you to code a branch and bound algorithm as well.
Unlikely you could do this in excel because the number of variables (patterns) will likely exceed the built in solver capability. However, there is an open source called OpenSolver that can handle much bigger problems. I plan to take a look at that.
