12,352,294 members (61,657 online)
alternative version

42.9K views
44 bookmarked
Posted

# C# Bin Packing - Cutting Stock Solver

, 9 Aug 2014 CPOL
 Rate this:
Application for solving Bin Packing and Cutting Stock problem

#### Introduction

This article with the related C# solution and executable application is a proposal for the solution of two well known classes of Operational Research problems: the Bin Packing and the Cutting Stock with many sizes of Bin/Stock. This work also include some useful features, such as the possibility of introducing cost and quantities constraints in searching solutions. Finally, remaining in the very spirit of CodeProject, a non design time feature has been added - see the History section below and the related Comments and Discussion section.

## Background

In the Bin Packing Problem a set of items must be grouped into bins of a certain size (capacity of the bin): the aim is to minimize the total number of bins.

In the Cutting Stock Problem a set of items must be cutted from Stocks of a certain size (length of the stock): the aim is to minimize the total number of stocks.

In the past several different methods were developed by researcher in order to solve this couple of very interesting and practical problems, including linear programming, heuristics, and evolutionary algorithms such as genetic algorithms and ant colony optimization systems [1, 2, 3, 4, 5]. Being known that in Operational Research only small size problems can be exhaustively investigated in order to find the "Absolute optimum" solution, it's obvious that any solver attempt aims to find a more general "Optimum solution" which only sometimes can be also an "Absolute optimum".

To complicate things it should be noticed that in practice it's fairly common to tackle problems with bins of multiple sizes, or stocks of multiple length. This leads to an exponential growth of the problem size.
It should be clear by definitions given that the Bin Packing Problem and the Cutting Stock Problem share a common nature. The algorithm proposed in this work is able to handle both of them.

## Using the application

To understand how this application works we follow an example that I took from

http://www.codeproject.com/Questions/553711/optimizedpluscuttingplussolutionplus-knapsack-2fbi

For simplicity, I write directly here the question:

Quote:

Hi,

I need the following solution and have been battling to get it right. I have also searched high and low but could not find anything that I could use. Perhaps I am not understanding my own problem well enough.

I need to be able to programmatically find the best way to cut lengths of Rope/Pipe.

Here is the scenario:

I have the following lenthgs in stock: 3 X 4.7m 5 X 7.4m 3 X 11.2m 4 X 9.8m (these are lengths of rope that I currently have in stock).

I need to cut the following lengths for an order: 2 X 3m 4 X 1.2m 1 X 6m 2 X 5.4m

The application exploits a Windows Form which is suitable for a comfortable data input

The Form exposes two `DataGridView` with their respective `BindingNavigators` and some `Buttons`

• SEARCH, which starts the solving process for the current problem
• RESET, which clears both the DataGridView for the set up of a new problem
• OPEN, which load a file saved problem
• SAVE, which save the current input data into a file

There is also a `CheckBox `with a red text that will appear at some point of the researching process, and in the lowest part of the Form there is a `ToolStrip` which brings a `ProgressBar` and a `Label` that give information about what is happening.

In the top-right part of the Form a message in the downright spirit of CodeProject can be red.

The user should insert the size and the number of pieces in the `DataGridViewItems`.

By default, if there isn’t explicit input by the user, the program will automatically consider a minimum of 1 piece for the just inserted item. A `TextBox` embedded in the `BindingNavigatorItems` will show the real-time total sum of the items.

The `DataGridViewStocks` should be filled with the size, the cost and the maximum number of available pieces for each stock (if it’s limited). To effectively consider this upper limit in the calculation a confirm by `CheckBox` is required. This is why it’s possible to simulate different scenarios simply checking or unchecking checkboxes.

Be aware that only the stock size is always taken into consideration during the algorithm, as will be clear after seen the flow chart.

One more thing is about the cost. Obviously this is the cost of the stocks, but for further analysis this value could include other parameters, such as cost for shipment and so on. In this way, a same size of stocks can be evaluated with two different costs and maximum number of pieces.

In the driver example written above, and downloadable at the top of the article, there isn’t information regarding the costs, so I fixed them in order to show how many result can be found.

However when the input is accomplished the “SEARCH” button must be pressed, and the program runs according to this flow chart

The First step is to build a quick solution, regardless the cost or the limited number of available pieces.
This solution has name “Bound Solution” and will be an upper bound for any further attempt of improvement.
The second step consists in a deeper look for a better solution, and it’s now that come into play the ‘optional parameters’ cost and max number of pieces.

As one can see running the application with the given input data, at this point our driver example finds two solution: one is a “Best Cost Solution”, while the other is a “Best Size Solution”.

Now if the problem is enough small and if the “Absolute Best Size Solution” (mathematically speaking regarding the total size of the solutions found) hasn’t been met, a further search is performed. The aim of this final step is to fit one of the many bin/stock combinations which have minimum sum. There is no guarantee that such a solution exists, and this process can be time consuming. At this point appears the above mentioned `CheckBox` with red text “End Search”, as the picture below shows. When checked, the search algorithm stops and results are immediately shown.

This snapshot gives an idea of the simple result print out:

By the way, for the driver example doesn’t exist any “Absolute Best Size Solution”. Howewer, if you are curious to see this event happen, you can slightly modify the item of size 5,4: change its size into 5,8 and ask for only 1 piece of it, then press “SEARCH” and wait a few seconds.

## A look to the algorithms

When the “SEARCH” `Button` is pressed, a CuttingStock object is constructed and a solving process begins according to the previous flow chart .

The Bound Solution is obtained exploiting a “Greedy First Fit” algorithm. In simple word, this algorithm processes all the items and assigns them to the biggest bin/stock available. When the bin/stock can’t hold the item, it tries to assign this item at the first bin/stock that can hold it. If no bin/stock has enough space, than a new bin/stock is used. After the assignement procedure the algorithm look for an improvement following these ordered steps:

1. Trying to reduce the size of some bin/stock if it's employ is less or equal the size of another bin/stock available. This is performed calling the DownSize(List<Bin> mySolution) method.
2. Trying to qualify the solution: the QualifySolution(List<Bin> mySolution) method is called, and it explores the possibility to free some space in the bin/stock making a series of local moves. The following, short paragraph will give more details about this idea.
3. Trying again to DownSize the solution .

Once got a Bound Solution, the application build a set of potential improving solution exploiting the BranchAndBound class. This class is inspired to the Branch & Bound strategy, which is fairly common in Operational Research and gives back a `List` of potential better solutions which is both sorted on Cost and on Size and is passed to a “Greedy Best Fit” algorithm until new solutions will be found. This greedy algorithm works in a similar way to the “Greedy First Fit”, the main differences being that now it tries to fit the items with the set derived by the Branch & Bound and that when a bin/stock can’t hold the item, it tries to assign this item at the bin/stock which can hold it giving the lowest reject. Hower, if it runs succesfully, it is able to return a so called "Best Size Solution" and "Best Cost Solution", both of them being precessed by the already told QualifySolution(List<Bin> mySolution) method.

At this point a new search will be performed only to achieve the Absolute Best Size with a "Greedy Next Fit" algorithm applied to the branches of the Branch & Bound space with size equal to the  "Absolute optimum" value. This step will not be executed if "Best Size Solution" is also "Absolute Best", or if there are too much items to process (the design choice is 12). This greedy algorithm is the simplest and the quickest of all: the items are placed in a bin/stock until it’s enough empty, than a new bin/stock is added. However, to be sure every possible permutation of the items in ListOfItems must be tried to fit a given set of bins/stocks. This is the main reason for which I made the choice to introduce a constraint on the number of items to process. This seeming simple idea took several lines of code, and I leave the comments in it to better clarify the concept.

## What is a Qualified Solution?

According to the statements given in the Background section, the aim in the Bin Packing or Cutting Stock problem is to minimize the amount of row material - bins or stocks. Provided that we are able to get this purpose, we can consider a more advanced target: to get a solution which allow us a good reusability of its reject. Given a problem and its solutions, provided that they have the same total size of bins/stocks, we can consider as "more qualified" a solution which gives a reject still reusable in a next job process. At the opposite, we can consider as "less qualified" a solution whose reject is not reusable and so it's completely useless. Altough this aspect seems to be interesting, I haven’t found references to it in the work coming from the field of research. At the same way, I didn’t find any attention in optimizing according to the “Cost” or giving a limitation at the number of some stock - the two features I decided to set in the application at design time. To fit the need to get a "more qualified" solution the dedicated method QualifySolution(List<Bin> mySolution) has been added to the code. The basic plan behind this action in "qualifying" is to free space in the bins/stocks trying to move items from one bin/stock to another: this one is chosen with a "Best Fit" criteria, whilst the items to move are selected from the greatest to the lowest running back from the last bin/stock to the first bin/stock in the examined solution.

## Points of Interest

This is my first C# application, and I must say that although I’m not at all a software developer I met several interesting feature in C# and .NET framework which I hope could be useful for other beginners:

• The use of `DataGridView `control with in-memory data structure instead of a physical database;
• The implementation of several sorting method for the `List` collections;
• The useful `Linq` query and the method to put the query result in a separated collection;
• The powerful couple of classes `BinaryFormatter` and```FileStream  ```which make simple storing in one file many collections of objects.

## References

[1] P.C. Gilmore, R.E. Gomory. A linear programming approach to the cutting stock problem. Operations Research, 9:848-859, 1961.
[2] Silvano Martello, Paolo Toth. Knapsack Problems, Algorithms and Computer Implementations. John Wiley and Sons Ltd., England, 1990.
[3] Emanuel Falkenauer, Alain Delchambre. A genetic algorithm for bin packing and line balancing. Proceedings of the IEEE 1992 International Conference on Robotics and Automation, Nice, France, May 1992.
[4] Emanuel Falkenauer. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2:5-30, 1996.
[5] Rhyd Lewis. A General-Purpose Hill-Climbing Method for Order Independent Minimum grouping Problems: A Case Study in Graph Colouring and Bin Packing. Computers and Operations Research, vol. 36(7), pp. 2295-2310.

## History

• 2014-01-04
• Original article
• 2014-01-06
• 2014-08-02
• Modified both the article and the code due to the post dated 25-May-2014:
• Updated article

## Share

 Engineer Italy
I am an Electrical Engineer experienced in designing instruments and controls for industrial polluted air and V.O.C treatment plants. Currently I work in designing radiant heating/cooling systems and related controls, solar systems and other solutions for buildings energy efficiency.

My first personal computer was a ZX Spectrum Sinclair (I still have it!) that in the early ‘80s I used so much in playing games and learning the bases of Basic. Then in my career I met PASCAL, VAL, AWL, VBA (for MS Office and CAD). Other than programming my hobbies are graphology, acoustic guitar, good books, my orchard, astronomy and play chess.

I live in the North West of Italy, very close to mountains and lakes and I like simple things. In summer you can find me somewhere walking on the mountains or going around with my sport bike. In winter you can probably meet me in my chessclub.
If you are planning to visit Italy I will be glad to show you some of this beautiful places and landscapes.

## You may also be interested in...

 First PrevNext
 Bad solution and additional function with reject Member 119818833-Nov-15 22:14 Member 11981883 3-Nov-15 22:14
 Re: Bad solution and additional function with reject Alberto Montibelli4-Nov-15 9:55 Alberto Montibelli 4-Nov-15 9:55
 Re: Bad solution and additional function with reject CarolineS4-Nov-15 19:24 CarolineS 4-Nov-15 19:24
 Use with a C#.net Webform application? Member 1012380320-Oct-15 10:38 Member 10123803 20-Oct-15 10:38
 Re: Use with a C#.net Webform application? Alberto Montibelli3-Nov-15 8:26 Alberto Montibelli 3-Nov-15 8:26
 C# Bin Packing - Cutting Stock Solver Member 1191867626-Aug-15 15:48 Member 11918676 26-Aug-15 15:48
 Re: C# Bin Packing - Cutting Stock Solver Alberto Montibelli29-Aug-15 3:26 Alberto Montibelli 29-Aug-15 3:26
 Use stock only once? Member 1161491027-May-15 1:18 Member 11614910 27-May-15 1:18
 Re: Use stock only once? Alberto Montibelli29-Aug-15 2:55 Alberto Montibelli 29-Aug-15 2:55
 reject is to low sho43-Mar-15 6:04 sho4 3-Mar-15 6:04
 Re: reject is to low Alberto Montibelli6-Mar-15 21:54 Alberto Montibelli 6-Mar-15 21:54
 Number of stocks and Items Member 1129772121-Jan-15 4:29 Member 11297721 21-Jan-15 4:29
 Re: Number of stocks and Items Alberto Montibelli22-Jan-15 9:42 Alberto Montibelli 22-Jan-15 9:42
 bpc files Member 1129772119-Jan-15 5:13 Member 11297721 19-Jan-15 5:13
 Re: bpc files Alberto Montibelli20-Jan-15 9:29 Alberto Montibelli 20-Jan-15 9:29
 PseudoCode Member 112977219-Dec-14 22:48 Member 11297721 9-Dec-14 22:48
 Re: PseudoCode Alberto Montibelli20-Dec-14 3:31 Alberto Montibelli 20-Dec-14 3:31
 awesome work wiky.when12-Nov-14 22:03 wiky.when 12-Nov-14 22:03
 Re: awesome work Alberto Montibelli16-Nov-14 9:14 Alberto Montibelli 16-Nov-14 9:14
 Awesome Article....! Member 1107788712-Sep-14 2:26 Member 11077887 12-Sep-14 2:26
 cutting stock eduinge25-May-14 11:43 eduinge 25-May-14 11:43
 Re: cutting stock Alberto Montibelli26-May-14 10:36 Alberto Montibelli 26-May-14 10:36
 Re: cutting stock eduinge9-Jul-14 13:52 eduinge 9-Jul-14 13:52
 Re: cutting stock Alberto Montibelli10-Jul-14 9:41 Alberto Montibelli 10-Jul-14 9:41
 Re: cutting stock eduinge16-Jul-14 7:23 eduinge 16-Jul-14 7:23
 Last Visit: 31-Dec-99 18:00     Last Update: 27-Jun-16 8:18 Refresh 12 Next »