Re^12: Tricky chemicals optimization problem

I can answer these two questions tonight, the others will have to wait until Friday.

Which array is this in the code you provided?

If you look at the second block of output (100,000 nearest to your 85,000 machine limit) in Re^6: Tricky chemicals optimization problem, and I reformat the first line for machine E001 thus:

E001 => { 
    " total" => 99982.9104, 
    C015 => [24504.1632, 14837.91, 13323.6396, 12250.6656, 6234.5772, 
+5720.64, 5255.838, 4380.3252, 3468.138, 2386.0308, 1716.192, 1501.668
+, 1436.2488, 1430.16, 791.19, 703.4688],
    C064 => [42.0552] 
},
[download]

You can see that although the machine has 17 flows from the original dataset, they are made up of just two chemicals. So, by your latest description, that machine only requires two nozzles.

I hear what you are saying but I'm failing to see what the gap might be if we made minimizing the lines higher precedence... I.e., is the fact that your code is doing a good job of minimizing the nozzles a side effect of the operation , or are you purposefully designing it to do that -if so can you point out the line that provides that effect?

The fact that the loops of code attempt to fill each machine from flows of Cnnn first (largest first due to the sorting), and only switches to other chemicals when there are either no flows for this chemical left; or there are no flows of the current chemical that will fit in the remaining space, means that the very act of attempting to use the minimal number of machines will also ensure that each chemical is spread to as few machines as possible (within the limitations of the greedy algorithm).

The upshot of that is that is all the flows of particular chemical on any given machine can be combined into one nozzle; and thus minimizing the number of machines also tends to minimize the number of nozzles. (Again, within the limitations of the greedy algorithm.

Those greedy algorithm limitations mean that it may be possible to reduce the nozzle count a little by juggling the smaller components around; but it will only be a very small percentage.

If that was actually necessary; then you move into the realms of either:

Genetic programming:
Try swapping a few things around in a few random combinations and then discard the some of the least good ones. Rinse and repeat until either no further improvement has been seen for some number of iterations; or until some time limit is reached.
A full brute force, exhaustive search.
This method is guaranteed to find the absolute optimum solution. Eventually! But even for the relatively small number of thing you are dealing with, it is apt to take many days or even weeks to run.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.

In the absence of evidence, opinion is indistinguishable from prejudice.

div

Comment on Re^12: Tricky chemicals optimization problem Download Code

Replies are listed 'Best First'.
Re^13: Tricky chemicals optimization problem by Anonymous Monk on Jan 16, 2017 at 01:55 UTC
Hey UK, Is there any chance you can suggest which parts of the code I need to focus on to accomplish the change to minimizing nozzles before minimizing number of machines? Even if it's simpler to minimize nozzles and not worry about machines I can probably take it further from that point - I'm a bit stuck at the moment thanks again for the help /thoughts	[reply]
Re^14: Tricky chemicals optimization problem by BrowserUk (Patriarch) on Jan 16, 2017 at 03:13 UTC
which parts of the code I need to focus on to accomplish the change to minimizing nozzles before minimizing number of machines? Well, the minimum number of nozzles is simply the number of chemicals; plus that number required to ensure that no single nozzle is delivering more than your machine limit. This code, simply reads your sample data, discards any 'zero flows' and accumulates all flows for each chemical. <Reveal this spoiler or all spoilers in this node or all in this thread> The provisional result is that there are 406 non-zero flows for 61 chemicals. But, some of those chemicals have combined flows that are greater than the 85,000 seconds/machine you've stipulated. Those need to be split across 2 or more machines. Doing so results in a requirement for 71 machines to dispense the 61 chemicals: C:\test>1179307-3 chems: 61 flows:406 C001 : total: 28973 requires: 1 machines C002 : total: 90027 requires: 2 machines C003 : total: 41827 requires: 1 machines C004 : total: 4534 requires: 1 machines C005 : total: 10415 requires: 1 machines C008 : total: 14094 requires: 1 machines C009 : total: 53928 requires: 1 machines C010 : total: 14980 requires: 1 machines C011 : total: 174279 requires: 3 machines C012 : total: 142552 requires: 2 machines C013 : total: 61747 requires: 1 machines C014 : total: 64160 requires: 1 machines C015 : total: 99940 requires: 2 machines C016 : total: 154115 requires: 2 machines C017 : total: 26431 requires: 1 machines C018 : total: 27339 requires: 1 machines C019 : total: 31297 requires: 1 machines C020 : total: 47061 requires: 1 machines C021 : total: 15559 requires: 1 machines C022 : total: 28242 requires: 1 machines C023 : total: 89116 requires: 2 machines C024 : total: 5849 requires: 1 machines C025 : total: 114277 requires: 2 machines C026 : total: 64940 requires: 1 machines C027 : total: 224536 requires: 3 machines C028 : total: 50540 requires: 1 machines C029 : total: 6377 requires: 1 machines C030 : total: 18461 requires: 1 machines C032 : total: 7803 requires: 1 machines C033 : total: 20790 requires: 1 machines C036 : total: 26358 requires: 1 machines C037 : total: 9812 requires: 1 machines C038 : total: 10748 requires: 1 machines C039 : total: 1143 requires: 1 machines C041 : total: 10822 requires: 1 machines C042 : total: 19757 requires: 1 machines C043 : total: 52357 requires: 1 machines C044 : total: 6781 requires: 1 machines C045 : total: 30224 requires: 1 machines C046 : total: 32096 requires: 1 machines C047 : total: 48541 requires: 1 machines C048 : total: 27570 requires: 1 machines C050 : total: 29900 requires: 1 machines C054 : total: 8274 requires: 1 machines C055 : total: 31052 requires: 1 machines C056 : total: 22770 requires: 1 machines C057 : total: 923 requires: 1 machines C058 : total: 18493 requires: 1 machines C059 : total: 62858 requires: 1 machines C060 : total: 16173 requires: 1 machines C061 : total: 19757 requires: 1 machines C062 : total: 24930 requires: 1 machines C063 : total: 13365 requires: 1 machines C064 : total: 20018 requires: 1 machines C065 : total: 40595 requires: 1 machines C066 : total: 12721 requires: 1 machines C067 : total: 2336 requires: 1 machines C068 : total: 25561 requires: 1 machines C069 : total: 2802 requires: 1 machines C070 : total: 33950 requires: 1 machines C071 : total: 59932 requires: 1 machines Total: 71 machines. Capacity: 6035000 (2456835.3312) [download] But now, some of the machines (eg.those running C057 & C039) are grossly under-utilised and those chemicals need to be combined into fewer machines. The simplest approach to that is a variation of the greedy knapsack algorithm which I will call (because I haven't seen it described anywhere) and the max-min algorithm. Basically you order the nozzles largest to smallest. You look at the largest and then track backward from the smallest until you find the largest (single chemical) nozzle that can be combined with that largest nozzle without breaking the machine limit. Combine them into a single machine and remove the small one from them from consideration. Rinse and repeat. When the smallest left is too big to be combined, remove the current largest from consideration also. Rinse and repeat until no nozzles are left. This isn't guaranteed to produce the absolute optimal solution in terms of minimizing the number of machines, but it will always produce the minimum number of nozzles and very close to the minimal number of machines. I don't have code for this approach this evening, but I'll try to post some tomorrow. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity. In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l] [select]
Re^15: Tricky chemicals optimization problem by Anonymous Monk on Jan 16, 2017 at 05:26 UTC
Ok I think I am following..... - I will also try to code it and see how far I can get. Just to make it easier problem don't even worry about minimizing number of machines at all. I can go back and tinker later. And thanks again.... I realize how much time you're already given to this post, and it's very appreciated.	[reply]
Re^16: Tricky chemicals optimization problem by BrowserUk (Patriarch) on Jan 16, 2017 at 21:56 UTC