Click here to Skip to main content
12,352,294 members (61,657 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as


44 bookmarked

C# Bin Packing - Cutting Stock Solver

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


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.


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

For simplicity, I write directly here the question:



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 andFileStream  which make simple storing in one file many collections of objects.   


[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.


  • 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


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


About the Author

Alberto Montibelli
Italy 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...

Comments and Discussions

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 Webform application? Pin
Member 1012380320-Oct-15 10:38
memberMember 1012380320-Oct-15 10:38 
AnswerRe: Use with a 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 
QuestionNumber of stocks and Items Pin
Member 1129772121-Jan-15 4:29
memberMember 1129772121-Jan-15 4:29 
AnswerRe: Number of stocks and Items Pin
Alberto Montibelli22-Jan-15 9:42
memberAlberto Montibelli22-Jan-15 9:42 
Questionbpc files Pin
Member 1129772119-Jan-15 5:13
memberMember 1129772119-Jan-15 5:13 
AnswerRe: bpc files Pin
Alberto Montibelli20-Jan-15 9:29
memberAlberto Montibelli20-Jan-15 9:29 
QuestionPseudoCode Pin
Member 112977219-Dec-14 22:48
memberMember 112977219-Dec-14 22:48 
AnswerRe: PseudoCode Pin
Alberto Montibelli20-Dec-14 3:31
memberAlberto Montibelli20-Dec-14 3:31 
Questionawesome work Pin
wiky.when12-Nov-14 22:03
memberwiky.when12-Nov-14 22:03 
AnswerRe: awesome work Pin
Alberto Montibelli16-Nov-14 9:14
memberAlberto Montibelli16-Nov-14 9:14 
QuestionAwesome Article....! Pin
Member 1107788712-Sep-14 2:26
memberMember 1107788712-Sep-14 2:26 
Questioncutting stock Pin
eduinge25-May-14 11:43
membereduinge25-May-14 11:43 
AnswerRe: cutting stock Pin
Alberto Montibelli26-May-14 10:36
memberAlberto Montibelli26-May-14 10:36 
GeneralRe: cutting stock Pin
eduinge9-Jul-14 13:52
membereduinge9-Jul-14 13:52 
GeneralRe: cutting stock Pin
Alberto Montibelli10-Jul-14 9:41
memberAlberto Montibelli10-Jul-14 9:41 
GeneralRe: cutting stock Pin
eduinge16-Jul-14 7:23
membereduinge16-Jul-14 7:23 

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.

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