The windows of my apartment are old and drafty, so I wanted to use one of those plastic window insulation kits to better insulate the windows. So I measured all four of the windows:

• 37” wide by 72.5” tall
• 25” wide by 72.5” tall
• 25” wide by 72.5” tall
• 43” wide by 72.5” tall

From past experience, I know it’s best to leave around 1.5” - 2” leeway on the edges to allow for imprecise alignment of the plastic to the window frame, so the actual areas we need look more like this:

• 40” x 76”
• 28” x 76”
• 28” x 76”
• 47” x 76”

Then I went to the hardware store. The kits don’t come in continuous rolls, they come in fixed sheets. Here were the options:

• 42” x 62”
• 62” x 84”
• 62” x 210”
• 84” x 110”
• 84” x 111.6”

How do we decide what sizes to get?

Well, clearly the 42” by 62” is out, because neither of its dimensions is larger than any of the windows. (It is possible to tape the pieces together, but it’s easy to end up with a bad seal or a pile of tangled plastic. I wouldn’t recommend it.)

So now our options are:

• 62” x 84”
• 62” x 210”
• 84” x 110”
• 84” x 111.6”

At this point, the decision is less clear. If we wanted to optimize for minimal waste of plastic, there are algorithms for calculating optimal arrangement, often used for plywood and sheet metal. I believe it’s the 2D version of the bin packing problem, which is a big topic in discrete mathematics.

In the bin packing problem, objects of different volumes must be packed into a finite number of bins or containers each of volume V in a way that minimizes the number of bins used.

https://en.wikipedia.org/wiki/Bin_packing_problem

If we optimize for price, I think this corresponds to the knapsack problem.

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

https://en.wikipedia.org/wiki/Knapsack_problem

I have raw metal sheets of various rectangular sizes (x1*y1, x2*y2, … xn*yn). I want to cut them to various different sizes (a1*b1, a2*b2, … ai*bi). In some cases a tolerence of t might be added to all four sides of each rectangle to be cut. I want an algorithm to generate a cutting plan that would MINIMIZE the number of raw sheets to be used and to minimize the scrap.

http://answers.google.com/answers/threadview/id/141254.html

I am working on a project where I produce an aluminium extrusion cutting list.

The aluminium extrusions come in lengths of 5m.

I have a list of smaller lengths that need to be cut from the 5m lengths of aluminium extrusions.

The smaller lengths need to be cut in the order that produces the least amount of off cut waste from the 5m lengths of aluminium extrusions.

https://stackoverflow.com/questions/22145/calculating-a-cutting-list-with-the-least-amount-of-off-cut-waste

I’m writing an application to use in the lumber yard. Given a number of board or beam lengths, the goal is to calculate the number of boards needed while minimizing waste.

https://stackoverflow.com/questions/10431969/algorithm-for-fitting-boards-to-available-lengths-minimizing-waste

However, there are other practical considerations, too. Cutting large plastic like this is challenging, because it’s hard to mark a straight line and keep consistent right angles. Since the 62” sheets are shorter than the window height, I figured I would have to make more cuts even if I could get a nice solution. Also, 210 inches is 17.5 feet, which is going to be hard to lay out on a living room floor. Based on these observations, (and the price of the kits, which unfortunately I forgot to record) I went with the 84” by 110”.

(Full optimization based on criteria of area and price is left as an exercise to the reader.)

But there is one simple optimization we can do: how can we squeeze the most windows out of a single 110” sheet? I think this is the 1D version of the cutting stock problem.

One way is the dimensionality of the cutting: the above example illustrates a one-dimensional (1D) problem; other industrial applications of 1D occur when cutting pipes, cables, and steel bars. Two-dimensional (2D) problems are encountered in furniture, clothing and glass production.

https://en.wikipedia.org/wiki/Cutting_stock_problem

Because there’s only four members of the set, this is well within reach of brute-force combinatorics. We can just calculate the powerset of the window lengths via Python’s itertools.chain.from_iterable() function, divide by the total sheet size to get a percentage, and then sort by the largest percentage. I used this StackOverflow question as the basis:

https://stackoverflow.com/questions/18035595/powersets-in-python-using-itertools

Here’s the results:

lengths: [40, 28, 47, 28]
maximum total length: 110
best: ((28, 47, 28), 0.9363636363636364)
93.6% (28, 47, 28)
87.3% (40, 28, 28)
79.1% (40, 47)
68.2% (47, 28)
61.8% (40, 28)
50.9% (28, 28)
42.7% (47,)
36.4% (40,)
25.5% (28,)
 0.0% ()

and here’s the code:

import itertools

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s)+1))

if __name__ == '__main__':
    lengths = [40, 28, 47, 28]
    print('lengths:', lengths)
    max_length = 110
    print('maximum total length:', max_length)
    percent_usage = {}
    best = (None, None)
    for candidate in powerset(lengths):
        total_length = sum(candidate)
        if total_length > max_length:
            # Too long
            continue
        p = total_length / max_length
        percent_usage[p] = candidate
        best_l, best_p = best
        if best_l is None or p > best_p:
            best = candidate, p
    print('best:',best)
    for p, s in sorted(percent_usage.items(), reverse=True):
        print("{:>5.1%} {}".format(p, s))