Introduction
The original idea behind this article is a proposal for the solution of two well known classes of Operation Research problems: the Bin Packing and the Cutting Stock with many sizes of Bin/Stock. Altough this work meets the traditional one dimension problem, the exposed approach could be employed to solve the two and three dimensions problem. This work also include some useful features, such as the possibility of considering cost and quantities constraints in searching solutions. Finally, remaining in the very spirit of CodeProject, two more non- design time features has been added: constraints on minimum reject, and a method for improving solutions by making "local moves" - 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 Operation 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. In this example, at the original problem has been added dummies constraints on minimum rejects:
<img height="304px" src="706136/BPCSproblem.png" width="640px" />
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 the following flow chart:
<img src="706136/FlowChart.png" />
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.
<img height="304px" src="706136/SearchingSolution.png" width="640px" />
This snapshot gives an idea of the result:
<img height="542" src="706136/Result.png" width="634" />:
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:
- 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.
- 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.
- 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 Operation 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 of 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.
Is it a good idea to ask for a minimum rejects?
As I said in the introduction, the main purpose of this article is to find a good, and possibly quick, solution at the traditional Bin Packing/Cutting Stock Problem, whose solving time may be unacceptable even for small set of bin/stocks and small number of items. This concept implies the objective function is the minimization of the row materials employed. Thus we can consider as good choices all that ideas which doesn't increase the row material consumption - regardless to what could happen in the next job, or in the next of the next... Inspired to this principle is the "local move" that I called "QualifySolution". The constraint of "Minimum Reject" could lead to a not worst solution. In this case it would be another good "local moves" for our job. On the other hand, more often the result could be worst. In this case, I suggestat least to compare this results with those obtained excluding the minimum rejects. Here is a point where readers and users can make their experiences, possibly giving reasonable feedback at the CodeProject community through the Comments and Discussion section.
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 andFileStream
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
- 2014-01-06
- Modified download section
- 2014-08-02
- Modified both the article and the code due to the post dated 25-May-2014:
- Added QualifySolution method
- Updated article
