recursive bin packing

Question

For the company I work for we spec lengths of tube of varying lengths.
For a given project let's say there is a list like this

100', 115', 105', 205', 195', 240', 240', 130', 180', 140', 225', 85'

Edit 4: Entries in the list can not go over 285', and are always rounded to the nearest 5'.

The goal is to figure out how to cut the different lengths of tube from as few rolls as possible to reduce waste. We use rolls of 1000', 500', and 300'. We also figure 15' of extra tube per grouping. So a 1000' roll only takes 985' from the 1960' total for the project, 485' of a 500' and 285 of 300. So this project would need 2 1000' rolls.

I already have logic for determining how many of each roll type will be needed.

I start the recursive function like so

public static bool RecursiveLoopGroup(Int32 remainingLength, List<System.Collections.DictionaryEntry> loops, int[] bundlesNeeded, ref List<System.Collections.Generic.Dictionary<String, Int32>> dt1000, ref List<System.Collections.Generic.Dictionary<String, Int32>> dt500, ref List<System.Collections.Generic.Dictionary<String, Int32>> dt300)
    {
        Debug.Print("\nStarting RecursiveLoopGroup Method");
        System.Collections.Generic.Dictionary<String, Int32> returnDict = new System.Collections.Generic.Dictionary<String, Int32>();
        List<System.Collections.DictionaryEntry> modifiedLoopList = new List<System.Collections.DictionaryEntry>(loops);
        List<System.Collections.DictionaryEntry> skipEntries = new List<System.Collections.DictionaryEntry>();
        System.Collections.DictionaryEntry lastEntry = new System.Collections.DictionaryEntry();

The returnDict is a dictionary of the loops that get grouped for return. So if

Group 1 : 100', 115', 105', 205', 195', 240'

Was found to be a good group, these would be returned in returnDict, with their keys being unique numbers specific to each length of tube. More on that later.

The modifiedLoopList is a copy of the loop List given. This is so as the function gets called recursively I can pass the reduced list to the new iteration.

skipEntries is to keep track if which loops have been tried to be grouped with the current working group, but were not effective. More on that later.

and lastEntry is to keep track of the last loop that was added to the current working group. It is used to remove the last loop from the group is a solution can't be found with the current configuration.

The algorithm is this

Determine which size group the current iteration is working on 1000', 500', or 300'
Look at each loop starting from the front of the list, if adding it to the group will not go over the limit of the group, add it.
Once you've formed a group, call the recursive function with the list of remaining loops, and repeat until each loop is in a group.

So far this looks like this

bool success = false;//exit condition for while loop
        while (!success)
        {
            //since you cant edit the loop list while iterating, must save loops added to loop group to be removed after
            List<System.Collections.DictionaryEntry> loopsToRemove = new List<System.Collections.DictionaryEntry>();

            //loop through each loop in the modfiedLoopList, which is the list of all the loops to use
            foreach (System.Collections.DictionaryEntry entry in modifiedLoopList)
            {
                //check if adding the loop will put the group over the limit or not
                if (groupTotal + (Int32)entry.Value <= groupLimit && skipEntries.Count > 0)
                {
                    bool entryIsInSkipList = false;//exit condition for the foreach loop
                    //check if the current entry is on the list of entries to skip
                    foreach (System.Collections.DictionaryEntry skip in skipEntries)
                    {
                        if (entry.Equals(skip))
                        {
                            entryIsInSkipList = true;
                            break;//breaks the foreach loop, since the entry was on the skip list
                        }

                    }
                    //if the entry was on the skip list, then move to the next entry
                    if (!entryIsInSkipList)
                    {
                        groupTotal += (Int32)entry.Value;
                        loopsToRemove.Add(entry);
                        totalRemaining -= (Int32)entry.Value;
                        returnDict.Add((String)entry.Key, (Int32)entry.Value);//the dictionary that will be returned by each iteration, which contains the loops as entries that get treated as a group
                    }
                }//end if adding entry will go over limit
                else if(groupTotal + (Int32)entry.Value <= groupLimit)//need this else incase there are no entries in the skip list yet
                {
                    groupTotal += (Int32)entry.Value;
                    loopsToRemove.Add(entry);
                    totalRemaining -= (Int32)entry.Value;
                    returnDict.Add((String)entry.Key, (Int32)entry.Value);
                }
            }//end foreach entry in loopList

            //remove used loops from list after iterating
            foreach (System.Collections.DictionaryEntry entry in loopsToRemove)
            {
                modifiedLoopList.Remove(entry);
            }

            //if the list count is not zero, there are still loops to place
            if (modifiedLoopList.Count != 0)
            {
                Debug.Print("\nThere are " + modifiedLoopList.Count.ToString() + "Loops left");
                Debug.Print("\nReturn Dict = " + returnDict.ToArray().ToString());

                #region reset number of needed bundles and exit
                //If each bundle is 0, then you're in the last group being formed.
                //if you're in the last group being formed and there are still some left
                //then the current grouping fails, so add the loop group this iteration is on and return up
                //to the iteration before
                if (bundlesNeeded[0] == 0 && bundlesNeeded[1] == 0 && bundlesNeeded[2] == 0)
                {
                    if (groupLimit == 1000)
                        bundlesNeeded[0]++;
                    else if (groupLimit == 500)
                        bundlesNeeded[1]++;
                    else if (groupLimit == 300)
                        bundlesNeeded[2]++;
                    return false;
                }
                #endregion number of needed bundles and exit

                bool needToUndoLast;

                if (groupTotal < (groupLimit - slackAmount)) needToUndoLast = false;
                else needToUndoLast = RecursiveLoopGroup(totalRemaining, modifiedLoopList, bundlesNeeded, ref dt1000, ref dt500, ref dt300); //if the iteration called by this fails, then something might be wrong with this groups configuration.

                //So remove the last entry, adding it to the skip list so the same grouping isn't tried again, and try another grouping
                //configuration with the next loop in the list
                if (!needToUndoLast)
                {
                    
                    //if the return dictionary is empty, then all the loops are on the skip list
                    //so a configuration could not be found SEE ELSE
                    if (returnDict.Count != 0)
                    {
                        System.Collections.Generic.KeyValuePair<String, Int32> lastDictEntry = returnDict.ElementAt(returnDict.Count - 1);
                        lastEntry = new System.Collections.DictionaryEntry((String)lastDictEntry.Key, (Int32)lastDictEntry.Value);
                        Debug.Print("\nNeed to undo last. Last Entry is" + lastEntry.Key.ToString() + "," + lastEntry.Value.ToString());
                        groupTotal -= (Int32)lastEntry.Value;
                        totalRemaining += (Int32)lastEntry.Value;
                        returnDict.Remove((String)lastEntry.Key);
                        skipEntries.Add(lastEntry);
                        //int returnIndex = loops.IndexOf(lastEntry);
                        modifiedLoopList.Add(lastEntry);

                        purgeSkipList(skipEntries);
                    }
                    else//so add back the needed loop length, and return to the iteration before so it can try a different configuration
                    {
                        if (groupLimit == 1000)
                            bundlesNeeded[0]++;
                        else if (groupLimit == 500)
                            bundlesNeeded[1]++;
                        else if (groupLimit == 300)
                            bundlesNeeded[2]++;
                        return false;
                    }


                }//end need to undo if
                else
                {
                    success = true;//if an undo isn't needed, then the iteration that was called succeeded, which means all groupings work
                }

            }//end if list has remaining loops
            else
            {
                success = true;//no remaining loops, all have been sorted properly
            }


        }//end while loop

the PurgeSkipList function is to keep the skip list in order based on the unique number for each loop, which increment more or less.

I think running through an example with the list from above will help. I'll use pictures to help. It's important to know we don't want to make perfect rolls of 1000', 500', and 300' but give 15' of slack on each. So the total taken from the remaining unassigned loops can be 985', 485', and 285'

So first we start with the unsorted list

The algorithm would start from the top and select all it can that will fit into a total of 985'

Then the function would be called recursively and the next group would start being created

At this point the last 85' loop can't be added as it would create create a 1000' group and we can only go to 985'. So this recursive call would return false, meaning it failed to completely sort all the loops.

This would then trigger the group above it to remove the last loop in the group, add it to a skip list so the same configuration is not tried again. Then go back through all the remaining loops again and find the next one to try and create a finished group. I'll now just show the step as it's just a cycle now

As you can see the last instance would work for both loops. The grouping works best when the loop being built is as close to 985' as possible. I've implemented a check right after checking if there are any more loops, to see if the loop being built is close enough, and if it's way off then the rest of the iterations would be a waste since it would all result in a fail. So I'm trying to stop unnecessary recursion when possible.

This method worked pretty quickly for this list, but when I move to a normally large group (34 distinct lengths for a total of about 100 pieces and almost 7000 feet), or our extreme edge case of almost 26000 feet, it never seems to find a solution.
So any help trying to optimize, I realize that is a big ask, but would help a lot, Thank you.

What is an algorithm with low resource use for larger data sets?

Edit 1: It was suggested to me that I post this here when I first posted on Stack Overflow.

Edit 2: This is the code for how I determine what the optimal number of rolls will be needed for the loop grouping

public static int[] findOptimalBundlesNeeded(Int32 totalLength)
    {
        int[] arrReturn = { 0, 0, 0 };//index 0 represents 1000's rolls, index 1 500's, and index 2 300's

        while (totalLength > 0)
        {
            if (totalLength > 1000)
            {
                arrReturn[0]++;
                totalLength -= 985;//for every 1000' roll, we are only taking 985 from the total tubing, 15 being left for safety
            }
            else if (totalLength > 500)
            {
                arrReturn[1]++;
                totalLength -= 485;
            }
            else if (totalLength > 300)
            {
                arrReturn[2]++;
                totalLength -= 285;
            }
            else
            {
                arrReturn[2]++;
                totalLength = 0;
            }


        }

The logic being that if I have a total length of tube that needs to be sorted, say 1960', I take 985' from the total and that will equal 1 1000' roll since we add 15 of slack to each roll. The same logic applies for 500' and 300'.

And if the math comes out where you get two of either 500' or 300', you round up because two 500' could be a 1000' and 2 300' could be a 500'.

Edit 3: And here is the purgeSkipList function that is used in the main recursive function.

 public static void purgeSkipList(List<System.Collections.DictionaryEntry> skipList)
    {
        System.Collections.DictionaryEntry last = skipList.ElementAt(skipList.Count-1);
        List<System.Collections.DictionaryEntry> tempRemoveList = new List<System.Collections.DictionaryEntry>();
        foreach (System.Collections.DictionaryEntry entry in skipList)
        {
            if (!last.Equals(entry))
            {
                if(Convert.ToDecimal((String)entry.Key) > Convert.ToDecimal((String)last.Key))
                {
                    tempRemoveList.Add(entry);
                }
            }
            
        }
        foreach (System.Collections.DictionaryEntry remove in tempRemoveList)
        {
            skipList.Remove(remove);
        }
    }

The logic here is that there are cases when trying different combinations of loops, that two loops can be added while trying to add up to the limit. So there would be a group of x number of loops, and these two loops are one of the iterations attempting to find a solution. Lets call the two loops y1 and y2.

If it turns out that the group x + y1 + y2 results in a failed configuration, we remove y2 and try x + y1 with all the other available loops in trying to find a working solution.

But if none of those groupings work, we now remove y1 so we are back to just the group x. But we might want to try y2 with another loop as a new pair say x + z1 + y2.

This logic makes it so loops that are further down the list can be tried again. This is tied to their unique identified.

Each loop corresponds to a manifold, and then is numbered 1 - 8. So a list would look like 1.1, 1.2, 1.3...

This numbering system can also be seen in the pictures from the original post.

Answer 1

I know I asked about the comments in a comment on the question, so I'll just point out that this type of commenting makes code so hard to read.

bool success = false;//exit condition for while loop
while (!success)

You don't need a comment for what success is used for, it's on the very next line. Same for comments like // end if .... If the code is hard enough to follow that these are helpful, you need to split the code into separate methods.

On to some code:

public static int[] findOptimalBundlesNeeded(Int32 totalLength)
{
    int[] arrReturn = { 0, 0, 0 };//index 0 represents 1000's rolls, index 1 500's, and index 2 300's

    while (totalLength > 0)
    {
        if (totalLength > 1000)
        {
            arrReturn[0]++;
            totalLength -= 985;//for every 1000' roll, we are only taking 985 from the total tubing, 15 being left for safety
        }
        else if (totalLength > 500)
        {
            arrReturn[1]++;
            totalLength -= 485;
        }
        else if (totalLength > 300)
        {
            arrReturn[2]++;
            totalLength -= 285;
        }
        else
        {
            arrReturn[2]++;
            totalLength = 0;
        }

    }
}

You don't need a while loop for this, you just need division. Something like this (my C# is rusty so it might not be 100% correct).

public static int[] FindOptimalBundlesNeeded(int totalLength)
{
    // I may have misunderstood what the padding is for. I assumed it meant each 1000 roll only has 985 useable.
    const int padding = 15;
    int remainder;
    int numberOf1000 = Math.DivRem(totalLength, 1000 - padding, out remainder);
    int numberOf500 = Math.DivRem(remainder, 500 - padding, out remainder);
    int numberOf300 = Math.Ceiling(remainder/(300.0 - padding));
    return new int[] { numberOf1000, numberOf500, numberOf300 };
}  

There's a serious problem with this though. Assume a cutting list of { 286, 286, 286, 286 } giving a total length of 1144. Your optimal solution gives 1x1000 roll and 1x300 roll. That's not valid, you can't cut 286 from a 300 roll. I don't know how this is used but it can easily suggest something that can't really be achieved. If this forms an important part of your algorithm, which I suspect it does, the whole thing is flawed. As soon as you have a cut over 285, you risk never finding a solution. Based on this, I won't look at the rest of the code.

Edit: And what about 8x250? Total length 2000 gives an 'optimal solution' of 2x1000 rolls and 1x300 roll. However, you can only cut 3x250 from 1000 (because of the 15 padding/buffer) so the optimal solution is not achievable (you can only cut 7 from 2x1000 and 1x300). Your optimal solution is basically trying to find a zero waste solution which is probably not possible.

You really want to add some usings, namespace qualifying everything makes the code unnecessarily verbose.

If you are happy with an approximate solution, you could sort the cutting list in descending size order and just do a first (or best) fit bin pack which may be good enough for your purposes.