Author |
Topic: Plastic Rods For Molecular Models (Read 1043 times) |
|
MathsForFun
Full Member
Posts: 153
|
 |
Plastic Rods For Molecular Models
« on: Aug 7th, 2010, 12:38am » |
 Quote  Modify
|
At a chemistry laboratory the following lengths of plastic rods are needed for making molecular models:
Length Qty
2.86 29
3.15 34
3.50 50
3.58 13
4.38 50
5.29 50
5.75 25
5.94 38
6.47 45
6.92 50
The supplier provides rods of length 18.44, and these are then cut to the required length. How many rods of length 18.44 should be ordered, and how should they be cut to meet the modelling requirements?
|
|
 IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Plastic Rods For Molecular Models
« Reply #1 on: Aug 7th, 2010, 2:28pm » |
Quote Modify
|
By trial and error (and mostly by hand if that isn't already implied)):
[0,0,0,0,1,0,0,0,0,2] x 16
[0,1,1,0,0,1,0,0,1,0] x 34
[0,0,0,0,0,0,0,2,1,0] x 12
[4,0,2,0,0,0,0,0,0,0] x 8
[0,0,0,0,0,2,0,0,0,1] x 6
[0,0,0,0,3,1,0,0,0,0] x 4
[0,0,0,0,0,0,2,0,0,1] x 12
[0,0,0,1,2,0,0,1,0,0] x 11
[1,0,0,1,0,0,0,2,0,0] x 1
[0,1,0,1,0,0,1,1,0,0] x 1
Each list gives a partition for one rod, a number a[i] means you have a[i] pieces of the ith element in [2.86, 3.15, 3.50, 3.58, 4.38, 5.29, 5.75, 5.94, 6.47, 6.92]
This gives a total of 105 rods, which is one more than the theoretical minimum (the total length fo all pieces together is 1901.70, which is slightly over 103 times 18.44.
I did make an error in the process (see if you can spot it), and while that doesn't affect the validity of the solution (unless I made more mistakes), it's well possible this isn't optimal. (Which is moreso true because this was just a trial and error optimization and not an exhaustive search)
|
| « Last Edit: Aug 7th, 2010, 2:33pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Plastic Rods For Molecular Models
« Reply #2 on: Aug 7th, 2010, 2:43pm » |
Quote Modify
|
Come to think of it, I was being shortsighted.
Just replace one [0,1,1,0,0,1,0,0,1,0] by [0,0,3,0,0,1,0,0,0,0] and you can drop one [4,0,2,0,0,0,0,0,0,0] entirely. Bringing the total to 104.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Plastic Rods For Molecular Models
« Reply #3 on: Aug 7th, 2010, 3:03pm » |
Quote Modify
|
on Aug 7th, 2010, 2:28pm, towr wrote:By trial and error (and mostly by hand if that isn't already implied)):
[0,0,0,0,1,0,0,0,0,2] x 16
[0,1,1,0,0,1,0,0,1,0] x 34
[0,0,0,0,0,0,0,2,1,0] x 12
[4,0,2,0,0,0,0,0,0,0] x 8
[0,0,0,0,0,2,0,0,0,1] x 6
[0,0,0,0,3,1,0,0,0,0] x 4
[0,0,0,0,0,0,2,0,0,1] x 12
[0,0,0,1,2,0,0,1,0,0] x 11
[1,0,0,1,0,0,0,2,0,0] x 1
[0,1,0,1,0,0,1,1,0,0] x 1
Each list gives a partition for one rod, a number a[i] means you have a[i] pieces of the ith element in [2.86, 3.15, 3.50, 3.58, 4.38, 5.29, 5.75, 5.94, 6.47, 6.92]
This gives a total of 105 rods, which is one more than the theoretical minimum (the total length fo all pieces together is 1901.70, which is slightly over 103 times 18.44.
I did make an error in the process (see if you can spot it), and while that doesn't affect the validity of the solution (unless I made more mistakes), it's well possible this isn't optimal. (Which is moreso true because this was just a trial and error optimization and not an exhaustive search) |
|
I started analysing this solution before you posted again, so let me give my analysis of this one first:
* it meets the requirement, and I agree that it totals 105 supplier rods
* it leaves the laboratory with the following spare rods: 4x2.86, 1x3.15, 1x6.47, 16x0.22, 34*0.03, 12*0.09, 6*0.94, 4*0.01, 13*0.02, 11*0.16, 1*0.12
* this is the CS forum - you're supposed to do some programming!  Admittedly the result presentation looks like program output.
|
| « Last Edit: Aug 7th, 2010, 3:27pm by MathsForFun » |
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Plastic Rods For Molecular Models
« Reply #4 on: Aug 7th, 2010, 3:22pm » |
Quote Modify
|
on Aug 7th, 2010, 2:43pm, towr wrote:Come to think of it, I was being shortsighted.
Just replace one [0,1,1,0,0,1,0,0,1,0] by [0,0,3,0,0,1,0,0,0,0] and you can drop one [4,0,2,0,0,0,0,0,0,0] entirely. Bringing the total to 104. |
|
Yes - this solution is optimal (there are other optimal solutions as well). To get to this by trial and error is quite exceptional - must be many, many hours of practice at similar activity. When I attempted this puzzle by hand, I didn't get anywhere near the optimum. Very well done! 
Rather than discuss how this puzzle can be programmed right now, I think I'll leave it open to see whether anyone will solve it by programming.
Anyway to analyse your new solution, it now leaves the following spare rods: no spare rods greater or equal to the smallest rod needed, and the following small spare rods: 16*0.22, 33*0.03, 12*0.09, 6*0.94, 4*0.01, 13*0.02, 11*0.16, 1*0.12, 1*2.65
|
| « Last Edit: Aug 7th, 2010, 3:29pm by MathsForFun » |
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Plastic Rods For Molecular Models
« Reply #5 on: Aug 7th, 2010, 3:27pm » |
Quote Modify
|
I did a little bit of programming, to find partitions*. But not for how to combine them.
I couldn't really think of a good way to approach the problem, so as one might do, I tried it by hand first. And if that gives a solution rather than clues of how to approach the problem, I'm not one to complain.
I'm not sure how well my approach would work in general, but it might work as a heuristic if I could formalize it a bit.
*to elaborate a bit on this point: First I tried to find all partitions that left less than 0.15 of the rod as waste (that's the total unavoidable waste divided by the lower limit of rods). This didn't work well, because there were too few partitions with 6.92 in it. So I searched a bit further and added ones for 6.92 that had 0.22 as waste.
After that it didn't take too long to find a solution, though I might have gotten lucky.
Funnily enough, for a while I was sending reassembled rods back to the factory before I realized that wasn't allowed (i.e. I was subtracting partitions I hadn't added in the hopes of getting a better total).
|
| « Last Edit: Aug 7th, 2010, 3:38pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Plastic Rods For Molecular Models
« Reply #6 on: Aug 7th, 2010, 3:40pm » |
Quote Modify
|
on Aug 7th, 2010, 3:27pm, towr wrote:| I did a little bit of programming, to find partitions*. |
|
There are actually 396 different ways to cut a supplier rod when duplicates are removed (according to my program). To be brutally frank, getting an optimal solution without considering all of them was lucky (but still brilliant!).
|
| « Last Edit: Aug 7th, 2010, 3:55pm by MathsForFun » |
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Plastic Rods For Molecular Models
« Reply #7 on: Aug 8th, 2010, 12:15am » |
Quote Modify
|
Is anyone either trying to find an alternative solution (they do exist) or to solve this puzzle by programming?
If nobody tells me that that they are still working on this puzzle by 21:00 UK time (= 20:00 GMT/UST), I will start the discussion on resolution by programming. If anyone is working on it, then I will happily postpone that.
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Plastic Rods For Molecular Models
« Reply #8 on: Aug 8th, 2010, 8:51am » |
Quote Modify
|
on Aug 7th, 2010, 3:40pm, MathsForFun wrote:
There are actually 396 different ways to cut a supplier rod when duplicates are removed (according to my program). To be brutally frank, getting an optimal solution without considering all of them was lucky (but still brilliant!). |
|
Most of them would waste too much material (you can only waste 0.15 on average, after all); it only makes sense to use as many as possible of the ones that waste little. Unless a problem of this kind were stacked against it, it is probably a good heuristic in general.
And of course, you could start by using a small subset, and then increase it if it doesn't work out. (As indeed I did)
I'll give some more thought to solve a problem like this by programming. (But don't postpone a discussion for my sake, should I not post anything before tonight.)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Plastic Rods For Molecular Models
« Reply #10 on: Aug 8th, 2010, 2:14pm » |
Quote Modify
|
Seems like I should start looking into integer linear programming if I want to solve MathFF's puzzles 
on Aug 7th, 2010, 3:40pm, MathsForFun wrote:
There are actually 396 different ways to cut a supplier rod |
|
I'm not sure if it's useful, but you can reduce this to just 41 by transforming the problem. You can always cut a longer piece into a smaller one, so two long ones are as good as a long and small one.
So using the representation I had before, you can transform it to a running sum from the end (so e.g. [0,0,0,0,1,0,0,0,0,2] becomes [3,3,3,3,3,2,2,2,2,2]). And do the same for the target. Then if you can combine the transformed 'partitions' in such a way that the value at each index is greater or equal to that in the transformed target, you can distill a solution from it. It might be faster since you only have 41 patterns to consider, but it might be slower because the values in the target are larger. I haven't enough experience with integer linear programming to say.
|
| « Last Edit: Aug 8th, 2010, 3:04pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Plastic Rods For Molecular Models
« Reply #11 on: Aug 9th, 2010, 12:44am » |
Quote Modify
|
on Aug 8th, 2010, 1:49pm, Grimbal wrote:
That's right - the one-dimensional cutting stock problem to be precise. I did a search of several forums at this website, but was unable to find any previous mention of it.
Once you know what the problem is called, the quickest way to get an answer is to search the internet for a solver! 
I solved it by generating all cut patterns that leave less than the size of the smallest piece, and then writing them out in the form of an integer programming model. This guarantees to find an optimal solution, but if the required pieces are small relative to the supplied pieces, this method will produce an excessively large number of cut patterns, and would not be usable.
The linear programming community (if I may presume to speak on their behalf!) recommend using the delayed column generation method - but, in theory, this could produce an answer that is not 100% optimal.
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Plastic Rods For Molecular Models
« Reply #12 on: Aug 9th, 2010, 2:57am » |
Quote Modify
|
Wow, I just tried lpsolve on this problem, and it doesn't even take a second.
14 x [0 0 0 0 1 0 0 0 0 2]
5 x [0 0 0 0 0 1 0 1 0 1]
13 x [0 0 0 0 0 0 2 0 0 1]
4 x [0 0 1 1 1 0 0 0 0 1]
2 x [0 0 0 0 0 1 0 0 2 0]
16 x [0 0 0 0 0 0 0 2 1 0]
25 x [0 1 1 0 0 1 0 0 1 0]
2 x [0 0 0 2 0 1 0 1 0 0]
11 x [0 0 0 0 3 1 0 0 0 0]
2 x [1 1 1 1 0 1 0 0 0 0]
2 x [0 3 0 1 0 1 0 0 0 0]
1 x [0 0 4 0 1 0 0 0 0 0]
7 x [4 0 2 0 0 0 0 0 0 0]
This gives you
[30, 33, 49, 12, 52, 49, 26, 39, 45, 50]
"But wait", you'll say, "that gives you an extra 286, 2 x 438, 575, 594 and you still need a 315, 350, 358, 529". But you can cut those extra pieces to size. 594 -> 529, 575 -> 358, 438 -> 350, 438 -> 315.
Timing lpsolve for the original and transformed problem, computing both 1000 time, the original takes 42.97 seconds, and the transformed problem 3.59s. So that's an order of magnitude improvement over the straightforward approach.
|
| « Last Edit: Aug 9th, 2010, 2:59am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Plastic Rods For Molecular Models
« Reply #13 on: Aug 9th, 2010, 3:19am » |
Quote Modify
|
on Aug 9th, 2010, 2:57am, towr wrote:| Wow, I just tried lpsolve on this problem, and it doesn't even take a second. Timing lpsolve for the original and transformed problem, computing both 1000 time, the original takes 42.97 seconds, and the transformed problem 3.59s. So that's an order of magnitude improvement over the straightforward approach. |
|
I just tried it with all 396 different cut patterns, and it took just 0.047 seconds. I am not sure how you are modelling it, but here's my model:
min: e1 +e2 +e3 ... +e394 +e395 +e396 ;
+e186 +e185 +e184 ... +e2 +e2 +e2 +e2 +e2 +e1 +e1 +e1 +e1 +e1 +e1 >= 29;
+e282 +e281 +e280 ... +e5 +e5 +e2 >= 34;
+e333 +e332 +e331 ... +e8 +e6 +e3 >= 50;
+e359 +e358 +e357 ... +e22 +e7 +e4 >= 13;
+e375 +e374 +e373 ... +e23 +e17 +e9 >= 50;
+e388 +e387 +e386 ... +e24 +e18 +e10 >= 50;
+e394 +e393 +e392 ... +e25 +e19 +e11 >= 25;
+e396 +e396 +e395 ... +e26 +e20 +e12 >= 38;
+e396 +e394 +e391 ... +e61 +e21 +e13 >= 45;
+e392 +e387 +e384 ... +e62 +e52 +e14 >= 50;
int e1 e2 e3 ... e394 e395 e396;
Code:edit: ... +e2 +e2 +e2 +e2 +e2 +e1 +e1 +e1 +e1 +e1 +e1 >= 29;
would read better as...
... 5 e2 + 6 e1 >= 29;
but:
1. 5 e2 could be interpreted as 500
2. summing the number of each cut pattern for each rod length would have taken some work - and given the choice between me doing work and the computer doing it, the computer lost! |
|
|
| « Last Edit: Aug 9th, 2010, 3:31am by MathsForFun » |
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Plastic Rods For Molecular Models  rods.zip
« Reply #14 on: Aug 9th, 2010, 3:48am » |
Quote Modify
|
on Aug 9th, 2010, 3:19am, MathsForFun wrote:
I just tried it with all 396 different cut patterns, and it took just 0.047 seconds. I am not sure how you are modeling it, but here's my model: |
|
I modeled it basically the same way, but my computer is slow, and I did it via python. (So a lot of time may get lost just in the conversion of variables preparing it fro access to the library function.)
Try the transformed model, and see how fast that is on your computer.
Oh, and just to check, is that 0.047s for a thousand times?
[edit]Using the lpsolve IDE solver, using attached models,
original:
Time to load data was 0.016 seconds, presolve used 0.000 seconds,
... 0.109 seconds in simplex solver, in total 0.125 seconds.
transformed:
Time to load data was 0.000 seconds, presolve used 0.000 seconds,
... 0.016 seconds in simplex solver, in total 0.016 seconds.
Quote:| 2. summing the number of each cut pattern for each rod length would have taken some work - and given the choice between me doing work and the computer doing it, the computer lost! |
|
See, I just made the computer do that as well. And in any case, it's an improvement that a solver could do by itself if it knew the problem was of this kind.
[/edit]
|
| « Last Edit: Aug 9th, 2010, 4:17am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Plastic Rods For Molecular Models
« Reply #15 on: Aug 9th, 2010, 4:17am » |
Quote Modify
|
on Aug 9th, 2010, 3:48am, towr wrote:| ...just to check, is that 0.047s for a thousand times? |
|
For me, LP_Solve used 334 iterations, so maybe I am using a better set of solver options than you are.
For reference, the following super-simple model:
min: x + y;
3 x + 2 y >= 50;
7 x - 5 y <= 70;
int x, y;
Takes 7 iterations and 0.007 seconds to solve (approx 7x faster than the 0.047 seconds that it took to solve my model for this thread's puzzle).
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Plastic Rods For Molecular Models
« Reply #16 on: Aug 9th, 2010, 4:19am » |
Quote Modify
|
on Aug 9th, 2010, 4:17am, MathsForFun wrote:
For me, LP_Solve used 334 iterations, so maybe I am using a better set of solver options than you are. |
|
I think you don't understand what I'm saying at all. To get a better estimate of how long the solver took, I let it solve the problem 1000 times. I don't know how many iterations it took within one of those thousand times to solve the problem.
[edit]MEMO: lp_solve version 5.5.0.15 for 32 bit OS, with 64 bit REAL variables.
In the total iteration count 343, 2 (0.6%) were bound flips.
There were 27 refactorizations, 0 triggered by time and 8 by density.
... on average 12.6 major pivots per refactorization.
The largest [LUSOL v2.2.1.0] fact(B) had 45 NZ entries, 1.2x largest basis.
The maximum B&B level was 25, 0.0x MIP order, 21 at the optimal solution.
The constraint matrix inf-norm is 6, with a dynamic range of 6.
Time to load data was 0.016 seconds, presolve used 0.000 seconds,
... 0.109 seconds in simplex solver, in total 0.125 seconds.
MEMO: lp_solve version 5.5.0.15 for 32 bit OS, with 64 bit REAL variables.
In the total iteration count 43, 0 (0.0%) were bound flips.
There were 1 refactorizations, 0 triggered by time and 1 by density.
... on average 43.0 major pivots per refactorization.
The largest [LUSOL v2.2.1.0] fact(B) had 53 NZ entries, 1.0x largest basis.
The maximum B&B level was 18, 0.2x MIP order, 18 at the optimal solution.
The constraint matrix inf-norm is 6, with a dynamic range of 6.
Time to load data was 0.000 seconds, presolve used 0.000 seconds,
... 0.016 seconds in simplex solver, in total 0.016 seconds.
So my way takes 43 iterations instead of 343.
[/edit]
|
| « Last Edit: Aug 9th, 2010, 4:21am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Plastic Rods For Molecular Models
« Reply #17 on: Aug 9th, 2010, 4:26am » |
Quote Modify
|
on Aug 9th, 2010, 3:48am, towr wrote:Using the lpsolve IDE solver, using attached models,
original:
Time to load data was 0.016 seconds, presolve used 0.000 seconds,
... 0.109 seconds in simplex solver, in total 0.125 seconds.
transformed:
Time to load data was 0.000 seconds, presolve used 0.000 seconds,
... 0.016 seconds in simplex solver, in total 0.016 seconds. |
|
Using your models:
Simple: 343 iterations
time (total): 0.028 seconds
Transformed: 43 iterations
time (total): 0.009 seconds
So a significant speed up!
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
MathsForFun
Full Member
Posts: 153
|
|
Re: Plastic Rods For Molecular Models
« Reply #18 on: Aug 9th, 2010, 4:32am » |
Quote Modify
|
on Aug 9th, 2010, 4:19am, towr wrote:| I think you don't understand what I'm saying at all. To get a better estimate of how long the solver took, I let it solve the problem 1000 times. |
|
Sorry - I missed that.
|
|
IP Logged |
Everything is interesting if you look at it closely enough
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Plastic Rods For Molecular Models
« Reply #19 on: Aug 9th, 2010, 4:35am » |
Quote Modify
|
on Aug 9th, 2010, 12:44am, MathsForFun wrote:| I solved it by generating all cut patterns that leave less than the size of the smallest piece, and then writing them out in the form of an integer programming model. This guarantees to find an optimal solution, but if the required pieces are small relative to the supplied pieces, this method will produce an excessively large number of cut patterns, and would not be usable. |
|
The worst case is when all target rods have different sizes.
In a typical industrial applications you would produce a large number of items of a few different sizes. In that case the method would still work well, I guess.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print