Click here to Skip to main content
12,952,277 members (66,231 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

58.9K views
5.6K downloads
54 bookmarked
Posted 5 Jan 2014

C# Bin Packing - Cutting Stock Solver

, 9 Aug 2016 CPOL
Rate this:
Please Sign up or sign in to vote.
Application for solving Bin Packing and Cutting Stock problem

 

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:

 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:

 

 

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 result:

 

:

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 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 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
    • 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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Alberto Montibelli
Engineer
Italy Italy
I am an 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 that in the early ‘80s I used so much in playing games and learning the bases of Basic. Then in my career I met other languages. 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...

Comments and Discussions

 
PraiseGood solver - source code availability Pin
richtersson4-Apr-17 10:23
memberrichtersson4-Apr-17 10:23 
QuestionMancano i sorgenti Pin
Z@clarco1-Mar-17 10:06
memberZ@clarco1-Mar-17 10:06 
GeneralSource Code Pin
Member 387249320-Feb-17 20:23
memberMember 387249320-Feb-17 20:23 
QuestionSource??? Pin
Todd Carnes25-Jan-17 11:29
memberTodd Carnes25-Jan-17 11:29 
QuestionSource Codes Pin
leighdar13-Jan-17 0:47
memberleighdar13-Jan-17 0:47 
QuestionSource Codes for Thesis Pin
Member 104760962-Jan-17 7:01
memberMember 104760962-Jan-17 7:01 
AnswerRe: Source Codes for Thesis Pin
gb198220014-Jan-17 15:08
membergb198220014-Jan-17 15:08 
AnswerRe: Source Codes for Thesis Pin
Member 129112265-Jan-17 18:18
memberMember 129112265-Jan-17 18:18 
QuestionInteresting but no source Pin
Ggalla1779210-Aug-16 17:34
memberGgalla1779210-Aug-16 17:34 
AnswerRe: Interesting but no source Pin
Alberto Montibelli12-Aug-16 2:29
memberAlberto Montibelli12-Aug-16 2:29 
GeneralRe: Interesting but no source Pin
Ggalla1779216-Aug-16 6:45
memberGgalla1779216-Aug-16 6:45 
QuestionPut criteria on acceptable reject Pin
Member 126290251-Aug-16 7:25
memberMember 126290251-Aug-16 7:25 
AnswerRe: Put criteria on acceptable reject Pin
Alberto Montibelli9-Aug-16 9:35
memberAlberto Montibelli9-Aug-16 9:35 
SuggestionRe: Put criteria on acceptable reject Pin
Member 126290259-Aug-16 11:27
memberMember 126290259-Aug-16 11:27 
QuestionBad solution and additional function with reject Pin
Member 119818833-Nov-15 22:14
memberMember 119818833-Nov-15 22:14 
AnswerRe: Bad solution and additional function with reject Pin
Alberto Montibelli4-Nov-15 9:55
memberAlberto Montibelli4-Nov-15 9:55 
GeneralRe: Bad solution and additional function with reject Pin
CarolineS4-Nov-15 19:24
memberCarolineS4-Nov-15 19:24 
QuestionUse with a C#.net Webform application? Pin
Member 1012380320-Oct-15 10:38
memberMember 1012380320-Oct-15 10:38 
AnswerRe: Use with a C#.net Webform application? Pin
Alberto Montibelli3-Nov-15 8:26
memberAlberto Montibelli3-Nov-15 8:26 
QuestionC# Bin Packing - Cutting Stock Solver Pin
Member 1191867626-Aug-15 15:48
memberMember 1191867626-Aug-15 15:48 
AnswerRe: C# Bin Packing - Cutting Stock Solver Pin
Alberto Montibelli29-Aug-15 3:26
memberAlberto Montibelli29-Aug-15 3:26 
QuestionUse stock only once? Pin
Member 1161491027-May-15 1:18
memberMember 1161491027-May-15 1:18 
AnswerRe: Use stock only once? Pin
Alberto Montibelli29-Aug-15 2:55
memberAlberto Montibelli29-Aug-15 2:55 
Questionreject is to low Pin
sho43-Mar-15 6:04
membersho43-Mar-15 6:04 
AnswerRe: reject is to low Pin
Alberto Montibelli6-Mar-15 21:54
memberAlberto Montibelli6-Mar-15 21:54 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170525.1 | Last Updated 9 Aug 2016
Article Copyright 2014 by Alberto Montibelli
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid