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.

Answer 1

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;
        }
    }
}

Answer 2

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.

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.

Answer 4

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.