How to find optimum combination for Cutting Stock Problem using Knapsack

Question

EDIT (31-12-2019) - https://jonathan.overholt.org/projects/cutlist

Above is the link of the free project which is what exactly I am looking for. I am just looking for proper guidance so that I can make it work.

I am working on minimizing the wastage of aluminium extrusion cutting for Aluminium Sliding Window Fabricators and I am not able to figure out which Algorithm/Data Structure I should go with for the problem.

I have done basic research and found that the problem falls in Cutting Stock Problem (Also called One dimensional cutting problem), Linear Programming Problem, Greedy Algorithm. BUT I am unable to decide which one I should go with and also how to start with.

Brief about the problem :

Basically the window fabricators have 3 sizes of material options to purchase.

12 | 15 | 16 (IN FT)

Now the input would be the size of Window.

WIDTH x HEIGHT (IN FT)

1) 6 x 8 - 10 Windows

2) 9 x 3 - 20 Windows

The calculation is (2 x Width) + (2 x Height). So from the above sizes of window, they need extrusion as follow.

1) 6' (FT) Size Pieces -> 2 x 10 = 20

2) 8' (FT) Size Pieces -> 2 x 10 = 20

3) 9' (FT) Size Pieces -> 2 x 20 = 40

4) 3' (FT) Size Pieces -> 2 x 20 = 40

Using knapsack, we can find out the combination but it has restriction of having size to 1 only whereas here in my case I have 3 different sizes available out of which I would like to generate the best optimum combination for the cutting stock problem.

I would need help in how should I proceed for the above problem with respect to data structure and algorithm in Java or any other language. My knowledge in Maths is not up to the mark and that's why I am facing issue in implementing the logic in my project and like to get some help from the community.

Enravish

Could you explain how these numbers relate? I don't see any connection between any of these numbers. – Oneway

@NicoSchertler I have edited the question based on my further research and I got that I have to generate the combinations/patterns using knapsack or other method & once I have the combinations I can find out "number of extrusions" to order so that wastage of cutting is minimum. – Enravish

It looks like a 2 dimensional cutting stock problem. In 1d cutting stock problems, you have a width W of master material with length of standard size. Then, you are required to build out of these, b_i units each of smaller item with width a_i and length of standard size. Obviously, b_i <= W for the problem to be feasible. But in your case, you have another dimension in each requirement. That is still doable as the 2d cutting stock problem, but the question is missing one dimension of the master material. Also, problem becomes more difficult in 2d because you can flip width and length. – Coldhearted

en.wikipedia.org/wiki/Cutting_stock_problem – Coldhearted

Yes, I read that Wikipedia page but as I mentioned I am not good at math & data structure implementation so not able to figure out how should i start with. – Enravish

In agreement with @NicoSchertler - as it stands, I do not understand how these numbers relate. Can you clarify, perhaps by adding the missing dimensions, and a clearer description of the problem? Feel free to use the terminology for the cutting-stock problem, and perhaps some images! – Sadiesadira

@Scorpion, 2 questions: Do you intend to use a solver with MIP capabilities or hand-jam something (much harder.) Second, is it truly the case that your desired cuts are frequently easily divisible into the stock length (like 6 foot cuts into a 12 foot piece) which would give rise to some easy pre-work on the optimization or are the cuts really like 6' 3"? – Quod

Answer 1

I'll echo the sentiment of the other answers: while there might be a "most correct" solution to this problem, what you're really looking for is a "correct enough" solution.

That said, I wrote up this little appendix to help make sense of the code in the project you referenced: cutlist generator design notes

Paraphrased:

Each iteration starts by creating a new instance of the longest stock and placing as many pieces into it as will fit. The stock is then reduced to the smallest stock that all of the selected pieces still fit into. This is all repeated until no pieces remain.

Another word of advice: make sure to clearly identify all of the assumptions you're building into the algorithm. Mine assumes that longer stock is cheaper per unit and that it's always preferred, but I've been asked for variations to optimize for the least number of cuts (bundle cutting) or to keep track of and prefer to use offcuts from previous runs first.

As always: Understand your customer's process very clearly before setting the assumptions.

Paten

In your case your assumption was to have Logner stocker because its cheaper, in my case I need to have Least wastage/scrap so that they can overcome excessive wastage issue. As the material comes in KG and they have options to purchase from 12/15/16 Feet sizes. Can you suggest me how can I achieve the minimum wastage in this scenario? – Enravish

Answer 2

There is no algorithm that will guarantee you the optimal solution other than brute-force checking all possible combinations. That's obviously not a good algorithm, at least not if you have large data sets.

You should have a look at heuristic search algorithms like Simulated Annealing, MCTS or the like. It should be no problem finding existing implementations of heuristic search engines that allow you to provide them with

• an input set (random distribution of pieces on material),
• a transition function (move pieces between materials),
• and an evaluation function (the amount of waste)

and compute a near-optimal solution for you.

Farad

There is no algorithm that will guarantee you the optimal solution other than brute-force checking all possible combinations. This is false. There are algorithms that give proven optimal solutions for this problem without trying all possible combinations. A simple example: this problem can be stated as a mixed-integer programming problem or can be solved directly with a branch & bound algorithm. – Denominator

Answer 3

Have you considered the simplex algorithm? You have a minimization problem which can either be transformed into a maximization problem and then be solved by the algorithm or be solved by the dual simplex algorithm. You'll find implementations on Google.

Loganiaceous

Answer 4

below code will give you combinations or pattern sorted in waste (min=0). just give your allowed waste. So, it's muliple nested loop with deep according to your number cuts so if 50 cuts then you will have 50 nested loops, that is why I change it to recursive, idea from other thread. Still working on code to apply the algorithm.

using System;
using System.Collections.Generic;
using System.Linq;

namespace Bar_Cutting_Recursive
{
    public class BarCuts
    {
        public int[] Qty { get; set; }
        public double TotalLength { get; set; }
        public double Waste { get; set; }
       
        public String result()  // return output.
        {
            return $"{string.Join(", ", Qty)}, TL = {TotalLength}, Waste = {Waste:F2}";
        }
    }

    internal class Program
    {
        private static double[] BarCuts = {9,8,7,6};  // List of Bar Cuttings.
        private static int BarLength = 20;
        private static double WasteRqd = 4;
        private static List<BarCuts> CutCombs= new List<BarCuts>();
        static void Main(string[] args)
        {
            int[] limits = GetLimits(BarCuts);           
            AddToCollectionRecursive(limits);
            CutCombs.Sort(delegate(BarCuts w1, BarCuts w2) { return w1.Waste.CompareTo(w2.Waste); });

            foreach (var item in CutCombs)
                Console.WriteLine(item.result());
            Console.ReadLine();
        }

        static void AddToCollectionRecursive(params int[] limits)
        {
            AddTo(new List<int>(), limits, limits.Length - 1);
        }

        static void AddTo(IEnumerable<int> value, IEnumerable<int> counts, int left)
        {
            for (var i = 0; i < counts.First(); i++)    // should change the upper limit or some break in outermost level if total > 20.
            {
                var list = value.ToList();
                list.Add(i);
                if (left == 0)
                {
                    // nt added
                    double tl = Combination_Length(list);
                    if (tl > BarLength) { break; }

                    double waste = BarLength - tl;          // BarLength = avlb bar length.
                    if (waste <= WasteRqd)
                    {
                        CutCombs.Add(new BarCuts { Qty = list.ToArray(), TotalLength = tl, Waste = waste });
                    }

                }
                else
                {
                    AddTo(list, counts.Skip(1), left - 1);
                }
            }
        }

        static double Combination_Length(List<int> CutsQty)
        {
            double tl = 0;
            for (int j = 0; j < CutsQty.Count; j++)
                tl += CutsQty[j] * BarCuts[j];
            return tl;
        }

        static int[] GetLimits(double[] Cuts)
        {
            int[] L = new int[Cuts.Length];
            for (int i = 0;i < Cuts.Length;i++)
            {
                L[i] = Convert.ToInt32(BarLength / Cuts[i]) + 1;
            }
            return L;
        }
    }
}

Fluker