Cutting glass with knapsacks

Jump to Comments

Suppose you are a thief and you stealthily enter a house carrying only a backpack. The residents astonishingly only have five objects in the house (as shown below). How do you maximize your profits so that everything you take fits in your backpack? If you can answer this question, then you have solved the knapsack problem. Like many problems, the knapsack problem is easy enough to state but tough to solve. For sufficiently large scenarios, no optimum solution can be found.

I have written some code in MATLAB that can find optimal solutions for the rectangular knapsack problem where you have to maximise the area used when fitting smaller rectangles into the larger tile. For example, in the diagram below, how do you fit the 2×3 and 3×4 rectangles into the 5×5 tile such that you use the most area in the 5×5 tile? Rectangular knapsack needs to be solved very often in many industries including the glass cutting industry where you want to complete your orders but don’t want to waste glass (in other words, maximise area used).

I used straightforward dynamic programming in the solution which means that I try to find the optimal solutions of the subproblems and then, combine the subproblems to find the optimal solution of the main problem. So, using the set of given rectangles, I optimise area used in 1×1 tile and then using those results, I optimise a 1×2 tile and so on, until I find the optimal solution for the 5×5 tile. Using such a method, we can solve pretty large problem instances in a reasonable amount of time.

Based on a lot of research, there are many interesting ways in which we can make the code even faster. One of the optimizations that I am using is discretization points [1] which preserves the optimality of the solution. These points are the only points where you can cut the tile and so, obviously, you need to only consider these points. With respect to the earlier example, we actually don’t need to consider the 1×1 tile sub-problem because it is never possible to have any rectangles in such a small tile. So, using this optimisation, we only need to consider a tiles with dimensions like 2×3 or 2×4.

Besides the rectangular knapsack (found in rk.m), I also consider the same problem allowing for rotation and allowing for staged cutting. All the code can be found here and the instructions to use the functions can be found in readme.rtf.

[1] Based on ideas in Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation by G.F. Cintra, F.K. Miyazawa, Y. Wakabayashi, E.C. Xavier

---

Possibly related posts: (automatically generated)

• Who Am I?
• Math Club and other observations

7 Comments

Filed under Programming

Tags: computer science, knapsack, matlab, np-hard