3 ms·

I love this kind of stuff but am always searching for a good engineering application of it, and I can't think of too much. Anyone have some ideas?

kwhitefoot 5y ago
It's not exactly the same but cutting shapes out of pieces of material in ways that waste as little as possible is surely related. The paper industry is very interested in a specialised subset of this kind of thing. So are factories that make transformer cores. The cores are made by stacking many (sometimes hundreds) of thin sheets of steel cut from rolls. Good quality core steel is expensive so it is important to waste as little as possible by making the cuts in the proper places.
- sidpatil 5y ago
  These are specifically known as cutting stock problems [1]. Example of a possible application: I used to work at a home improvement retailer, and one of my responsibilities was to cut plywood boards for customers, to the dimensions they specified. I'd often wonder if the cuts I was making were optimal. The constraints were that any cuts I made had to go all the way through the entire piece, and that the blade itself was 1/8" thick. [1] https://en.m.wikipedia.org/wiki/Cutting_stock_problem https://en.m.wikipedia.org/wiki/Cutting_stock_problem
  - madcaptenor 5y ago
    A similar problem shows up in quilting - fabric comes in rolls of about 44 inches wide (called "WOF" for "width of fabric" in some patterns). (Occasionally there are other pieces - for example you can buy "fat quarters" which are 18 by 22 inches, i. e. half a yard by half WOF.) You may need many small pieces, say rectangles or triangles a few inches on a side. And so it's natural to ask what the best way to cut them is - either with minimal waste, or with making the smallest number of cuts.
sidpatil 5y ago
Which field(s) of engineering did you have in mind? One obvious application would be to find the minimum dimensions for a box to contain a number of identically-shaped physical parts. This would be a three-dimensional packing problem. Another application could be to find out how to run the maximum number of VMs on a finite quantity of physical machines. This would be a multidimensional packing problem, possibly irregular since the VMs could have different memory, CPU, disk storage, etc. requirements.
cycomanic 5y ago
Actually coding theory and modulation formats in communications are essentially very closely related to packing theory (in particular sphere packing)
yumraj 5y ago
Amazon, or any other vendor for that matter, trying to figure out the smallest single box to ship all the items in your order using optimal packing material.
- PaulDavisThe1st 5y ago
  It's seem abundantly clear from real world experience that even if they have an algorithmic method to determine this, it's only 1 input into the process. Hello, amzn shipping box that is 8x larger than the single content package.
  - yumraj 5y ago
    > it's only 1 input into the process I'm sure you're right.. Other potential inputs are: - availability of boxes and the type of packing material near the packer - availability of space in the shipping container, so that it packs. This is again an application of the above concept. :) - the item being shipped, fragile vs not so fragile and so on - weight of the item, and how it fits in the container, similar to above and so on. Or, it is equally possible that currently there is no algorithm. the person packing just makes a judgement call :)

kwhitefoot 5y ago

It's not exactly the same but cutting shapes out of pieces of material in ways that waste as little as possible is surely related. The paper industry is very interested in a specialised subset of this kind of thing. So are factories that make transformer cores. The cores are made by stacking many (sometimes hundreds) of thin sheets of steel cut from rolls. Good quality core steel is expensive so it is important to waste as little as possible by making the cuts in the proper places.

sidpatil 5y ago
These are specifically known as cutting stock problems [1]. Example of a possible application: I used to work at a home improvement retailer, and one of my responsibilities was to cut plywood boards for customers, to the dimensions they specified. I'd often wonder if the cuts I was making were optimal. The constraints were that any cuts I made had to go all the way through the entire piece, and that the blade itself was 1/8" thick. [1] https://en.m.wikipedia.org/wiki/Cutting_stock_problem https://en.m.wikipedia.org/wiki/Cutting_stock_problem
- madcaptenor 5y ago
  A similar problem shows up in quilting - fabric comes in rolls of about 44 inches wide (called "WOF" for "width of fabric" in some patterns). (Occasionally there are other pieces - for example you can buy "fat quarters" which are 18 by 22 inches, i. e. half a yard by half WOF.) You may need many small pieces, say rectangles or triangles a few inches on a side. And so it's natural to ask what the best way to cut them is - either with minimal waste, or with making the smallest number of cuts.

sidpatil 5y ago

Which field(s) of engineering did you have in mind? One obvious application would be to find the minimum dimensions for a box to contain a number of identically-shaped physical parts. This would be a three-dimensional packing problem. Another application could be to find out how to run the maximum number of VMs on a finite quantity of physical machines. This would be a multidimensional packing problem, possibly irregular since the VMs could have different memory, CPU, disk storage, etc. requirements.

cycomanic 5y ago

Actually coding theory and modulation formats in communications are essentially very closely related to packing theory (in particular sphere packing)

yumraj 5y ago

Amazon, or any other vendor for that matter, trying to figure out the smallest single box to ship all the items in your order using optimal packing material.

PaulDavisThe1st 5y ago
It's seem abundantly clear from real world experience that even if they have an algorithmic method to determine this, it's only 1 input into the process. Hello, amzn shipping box that is 8x larger than the single content package.
- yumraj 5y ago
  > it's only 1 input into the process I'm sure you're right.. Other potential inputs are: - availability of boxes and the type of packing material near the packer - availability of space in the shipping container, so that it packs. This is again an application of the above concept. :) - the item being shipped, fragile vs not so fragile and so on - weight of the item, and how it fits in the container, similar to above and so on. Or, it is equally possible that currently there is no algorithm. the person packing just makes a judgement call :)