Industrial division problem
We are talking about a metalwork factory. There is a machine that cuts long iron plates into smaller pieces, which are later used to create various products.
For example, I have a requirement to produce strings of the following length and quantity: 2 pieces of 248 mm, 5 of 1150 mm, 6 of 2843 mm, 3 of 3621 mm.
This is the partitioning exit.
On the input side I have (again, for example) 3 bars of 2500 mm, 2 bars of 5000 mm, 6 bars of 8000 mm and 3 bars of 10000 mm.
I have to find a way to optimally cut the input strips - the rest (the rest of the parts that are too small to use) after cutting should be as minimal as possible.
I created an algorithm that simply creates all possible combinations and then picks the best one. The code works, but once the input and output is a little more, the calculation can take a very long time, so I have to find a new approach to the problem.
Do you have any hints?
source to share
Your problem is a fairly common problem in Operations Research. look at the problem of cutting material . This problem is inherently NP-hard, as you can imagine. It doesn't scale well.
How to solve it? After you can define the model, it might be better to name some mixed software solver. I previously used LPSolve 5.5
There might be simpler algorithms you could code specifically with this problem. The problem with these algorithms usually arises when you need to add some lateral constraints that the authors didn't think of. MIP Solver is a more general tool.
source to share
Linear programming is your friend. See http://en.wikipedia.org/wiki/Linear_programming in general and in particular http://en.wikipedia.org/wiki/Linear_programming#Uses , http://en.wikipedia.org/wiki/ Linear_programming # Algorithms .
source to share
Looks like a backpack problem (know it's really nasty) I found this on NIST DADS (handy link), more accessible than ACM for non- Bin Packing members
source to share