Which registers sum to a given number

[fdiaz1]

I have a potential project that I am not sure a PLC can handle. I would like to know if anyone can:
1. give me their opinion whether the Do-More can tackle my project need.
2. give me a nudge on how to even begin to do it.

I have 21 memory registers containing various numbers (0, 2.25, 0.75, 3, 1.97, etc...) I then need to find out which of those registers can sum a given number (18.125).
For Example:
V0 through V20 contain the sample numbers
V100 = the needed number
V101 = Optional Tolerance +/-
V200 = Result

Result = V3+V5+V6+V11+V14+V19= V100 +/- V101
What I need is the list of V locations that sum up to the "Needed Number" (V100)

The Tolerance(V101)will increase the chances of getting my needed sum. So if the needed value is 20 and there is a tolerance of +.5 then the sum can equal anything from 20 to 20.5

If there isn't a posible result then either a bit can be set or V200 = 0

I would like to be able to use the Do-more for this, but not sure how to go about it. 
Any help is appreciated.
 

[b_carlton]

Are you looking for best match (longer execution time) or just the first group which is within the tolerence (generally shorter execution time if an acceptable group exists)? How often does the list change? Is this like a multiple load cell weigher? Is it possible that a single number in the list be above the target (with tolerencce)?

[fdiaz1]

Are you looking for best match (longer execution time) or just the first group which is within the tolerence (generally shorter execution time if an acceptable group exists)?

Ideally the best match but I can settle for first group within tolerance.

How often does the list change?

A tolerable time would be about every 45 seconds to 1 minute, but it would be dependent on the result time. after result is given it would then read the next batch.

Is it possible that a single number in the list be above the target (with tolerencce)?

Not possible.

Is this like a multiple load cell weigher?

No, it is to width measure multiple strips to then put together and create a solid panel.

Thanks for the reply

[franji1]

There are 2 ** 20 possible combinations, which is over 1,000,000.  Although you only need the one "close enough", it may have to go through all 1,000,000 calculations (for the case when none of them give you an answer within tolerance).  Using integer math (I would do all integer arithmetic in "hundredths of an inch", or whatever units you are using), you could get that done within a few seconds, probably much less time if you have a tolerance.  If that is acceptable, then it would be relatively easy to do in a task code-block with a time slice of 1000 uSec using a brute force mechanism.

How fast do you need the answer, that is, from the point at which you have your 20 values, when do you need to know which combination of the 20 you need?

[fdiaz1]

How fast do you need the answer, that is, from the point at which you have your 20 values, when do you need to know which combination of the 20 you need?

The easy answer is ASAP... but I can tolerate up to 1 minute to solve, which I think is plenty.  what I dont know is how to execute something like this. what type of instructions could I use?

[Controls Guy]

Easiest answer,  don't brute force it.   Rank the pieces longest to shortest.   Start with the longest part.  Check if there is one other piece that brings the total within tolerance.   If so, done.   If not,  add the longest part that doesn't exceed the max tolerance, and repeat.   (Check again for a piece that brings you within tolerance, and so on).  When you get to a step where all the remaining pieces overshoot max, back up one step and delete the last piece added, replacing it with the next shortest piece, then resume the process.  Down from millions of ops to probably a few hundred.

[franji1]

Being a math dude, I wrote the solution.  I tested it on the simulator and the project is attached as a .ZIP file with the .DMD project and workspace files.  It appears to work.

The key algorithm is in task code-block Optimize.  It goes through ALL 1,048,575 combinations of 20 lengths (data-block Lengths0..19), finding the right combination that gets you within the Tolerance (D98) of the Target (D100).  Once it hits a combination that is within tolerance, it stops.  However, I kept the Tolerance 0 just to see how good the algorithm was, and it's pretty fast at finding the BEST answer.

Basically, when X0 goes from OFF to ON, it does the following:
1. Generate 20 random lengths in Lengths0..Lengths19 with values between 5 and 2005.
2. Generate a random Target between 5000 and 15000.
3. Find the optimal combination of the 20 lengths that fall within tolerance.  This is done by code-block Optimize.  I would definitely test it ON ACTUAL PLC HARDWARE with a large length that would require going through ALL the combinations with a tolerance of 0 (e.g. a Target of 100,000) just to see how "bad" it can be.
4. I put in metrics in $Main to calculate how long it takes.  R0 is how long in SECONDS the Optimize calculation took.

The specific lengths end up being in the bit block Selection0..19.  So if bit Selection17 is ON, then Length17 was part of the "optimal" solution.  If bit Selection0 is OFF, then Length0 was NOT part of the "optimal" solution.  So, some combination of bits Selection0..Selection19 tells you which of the Lengths0..Lengths19 should be "used".

I have also put the Optimized logic below to help the discussion.  The full project is in the attached .ZIP file.

Code: [Select]

// Options: Export code block Optimize from address 0 to 223;
// Code Block delimiter instructions; Unformatted Rung Comments;
// Element Documentation Database; Memory Configuration/Devices with User Add-Ons only;
// prefer NickNames over Element names; rung/address annotations;
// <SPACE> parameter delimiter;
// Write/overwrite file C:\Do-more\Designer1_2\Projects\Optimize.txt

PLC DM-SIM

#BEGIN MEM_CONFIG
 Lengths SDWORD decimal 100
 Selection BIT decimal 128
 GenData TASK  0 -1
 Optimize TASK  0 -1
#END

// Beginning of Code Block Optimize
$TSK Optimize

// Rung Optimize#1
// Offset 0
#BEGIN COMMENT
"Initialize current optimal selection to nothing (no lengths are part of the optimized solution),"
"Initialize the optimal error to the largest signed integer (2 billion) (ANYTHING will be better than THAT error)"
"Set my .TimeSlice to 1ms (1000 microseconds, this let me get some work done every ladder scan)"
#END

MOVE 0 CurrOptSelection
MOVE 0x7FFFFFFF OptimalError
MOVE 1000 Optimize.TimeSlice

// Rung Optimize#2
// Offset 7
#BEGIN COMMENT
"This loop goes through EVERY POSSIBLE COMBINATION of lengths as 2 ** 20 bit patterns, from 0x0001 thru 0xFFFFF."
#END

FOR Selection0:SD 0x1 0xFFFFF 1

// Rung Optimize#3
// Offset 14
#BEGIN COMMENT
"Calculate the sum of the current ""selected bits"" in Selection0..Selection19."
"First, initialize the current sum to 0."
#END

MOVE 0 CurrLengthSum

// Rung Optimize#4
// Offset 16
#BEGIN COMMENT
"For 20 rungs, if that Selection bit is set, add the corresponding Lengths value to CurrLengthSum."
"So the first time through, only the first rung that addes Lengths0 will be utilized, and for the last time thorugh (0xFFFFFF), ALL 20 bits will be set, so all 20 rungs will add their lengths."
""
"**** Do NOT use a FOR/NEXT loop of 0..19 with array indexing, because array indexing is SLOW.  THIS ALGORITHM NEEDS TO BE FAST!  So, it's okay to burn 20 rungs. ***"
#END

STR Selection0
MATH CurrLengthSum "CurrLengthSum + Lengths0"

// Rung Optimize#5
// Offset 25
STR Selection1
MATH CurrLengthSum "CurrLengthSum + Lengths1"

// Rung Optimize#6
// Offset 34
STR Selection2
MATH CurrLengthSum "CurrLengthSum + Lengths2"

// Rung Optimize#7
// Offset 43
STR Selection3
MATH CurrLengthSum "CurrLengthSum + Lengths3"

// Rung Optimize#8
// Offset 52
STR Selection4
MATH CurrLengthSum "CurrLengthSum + Lengths4"

// Rung Optimize#9
// Offset 61
STR Selection5
MATH CurrLengthSum "CurrLengthSum + Lengths5"

// Rung Optimize#10
// Offset 70
STR Selection6
MATH CurrLengthSum "CurrLengthSum + Lengths6"

// Rung Optimize#11
// Offset 79
STR Selection7
MATH CurrLengthSum "CurrLengthSum + Lengths7"

// Rung Optimize#12
// Offset 88
STR Selection8
MATH CurrLengthSum "CurrLengthSum + Lengths8"

// Rung Optimize#13
// Offset 97
STR Selection9
MATH CurrLengthSum "CurrLengthSum + Lengths9"

// Rung Optimize#14
// Offset 106
STR Selection10
MATH CurrLengthSum "CurrLengthSum + Lengths10"

// Rung Optimize#15
// Offset 115
STR Selection11
MATH CurrLengthSum "CurrLengthSum + Lengths11"

// Rung Optimize#16
// Offset 124
STR Selection12
MATH CurrLengthSum "CurrLengthSum + Lengths12"

// Rung Optimize#17
// Offset 133
STR Selection13
MATH CurrLengthSum "CurrLengthSum + Lengths13"

// Rung Optimize#18
// Offset 142
STR Selection14
MATH CurrLengthSum "CurrLengthSum + Lengths14"

// Rung Optimize#19
// Offset 151
STR Selection15
MATH CurrLengthSum "CurrLengthSum + Lengths15"

// Rung Optimize#20
// Offset 160
STR Selection16
MATH CurrLengthSum "CurrLengthSum + Lengths16"

// Rung Optimize#21
// Offset 169
STR Selection17
MATH CurrLengthSum "CurrLengthSum + Lengths17"

// Rung Optimize#22
// Offset 178
STR Selection18
MATH CurrLengthSum "CurrLengthSum + Lengths18"

// Rung Optimize#23
// Offset 187
STR Selection19
MATH CurrLengthSum "CurrLengthSum + Lengths19"

// Rung Optimize#24
// Offset 196
#BEGIN COMMENT
"Calculate the absolute error based on the CurrLengthSum and the Target value"
#END

STR $On
MATH CurrAbsolutError "ABS(Target - CurrLengthSum)"

// Rung Optimize#25
// Offset 206
#BEGIN COMMENT
"Is this Selection combination better than the OptimalError so far?"
"If so, save this combination selection set and error value."
#END

STRLT CurrAbsolutError OptimalError
MOVE CurrAbsolutError OptimalError
MOVE Selection0:SD CurrOptSelection

// Rung Optimize#26
// Offset 214
#BEGIN COMMENT
"Is this optimal error within our Tolerance, if so, break out of the big/long FOR/NEXT loop, cuz we are DONE!"
#END

STRLE OptimalError Tolerance
BREAK

// Rung Optimize#27
// Offset 220
NEXT

// Rung Optimize#28
// Offset 222
#BEGIN COMMENT
"Move the current optimal selection into the ACTUAL Selection bit set using casts."
#END

MOVE CurrOptSelection Selection0:SD

// End of Code Block Optimize
$TSKEND Optimize

#BEGIN ELEMENT_DOC
"D0","StartTime","",""
"D98","Tolerance","",""
"D99","CurrOptSelection","",""
"D100","Target","",""
"D101","CurrLengthSum","",""
"D102","OptimalError","",""
"D103","CurrAbsolutError","",""
"R0","CalcTime","Seconds",""
#END



[franji1]

Well, I ran it on hardware with .TimeSlice set to 1000 (1.000ms), and set the Tolerance to -1 to force it to go through all 1M combinations and the timing was not good.  It took 51 seconds for it to iterate through all of them.

I tweaked the .TimeSlice to 10000 (10.000 ms), and that reduced the timing by almost half, down to 34 seconds.
I then tried .TimeSlice of 50000 (50.000 ms) and that cut it back by just 3 sec, down to 31 seconds.
I then tried .TimeSlice of 5000 (5.000 ms) and that bumped it up to 38 seconds.
.TimeSlice of 2000 (2.000 ms) and it was 44 seconds.
So it appears that somewhere between 2000 and 5000 is the sweet spot (2ms to 5ms).  The .TimeSlice will bump the overall PLC scan time (although only when that code-block is running).

Again, this is worst-case.  When I had tolerances of "10", it typically took less than a second to find something in-tolerance, but it is not guaranteed.  I saw one calc time be 19 seconds.  Tighter tolerances will cause the algorithm to run longer, wider tolerances will cause it to run shorter.

I've attached a histogram data set of a bunch of random samples with .TimeSlice of 2000 (2.000 ms) and Tolerance of 10.
The count in each N register is the number of runs that fell within the N-index "number of seconds", meaning N0 is count of runs that took 0-1 second, N1 is count of runs that took 1-2 seconds, N2 2-3 sec, ... N10 10-11 sec, ... N36 36-37 seconds.  Most of the runs took less than 1 second, and except for a handful, most were 6 seconds or less, but there are a few out-liers.

[BobO]

Do you think it could be optimized easier if the list was sorted first?

[franji1]

It would help a little, but it is still probabilistic.  If you look at the data, most took less than a second.  Worst case is still an issue, regardless - when no combination of the 20 boards are in-tolerance.  Could that be calculated faster?  Sure.  You also then must maintain the mapping of the original positions to the sorted positions (I'm assuming the actual original order matters, since you need to act on the original "length 17", not the 17th largest length).

Also, the complexity of any "optimization" is also a "hit", and it may be a wash, or even worse!  (think "intelligent" cache hit/miss algorithms).  Your "typical" case may double from 1 second to 2 seconds, so on 100 "batches", you lost 100 seconds, to save time on a "worst case" situation that occurs once every 100 batches, down from 30 seconds to 15 seconds.  So you lose 100 sec go gain 15 sec.

This sounds like a good Ph.D. thesis.

Until you actually implement these complex algorithms and model it, you never know how fast you can make it.  40 seconds is within his "worst case" tolerance, and most are 1 second or less.

[ATU]

What about presorting the pieces in groups within a specified range of lengths.  It should cut down on the number iterations, not having to scan the entire lot. Also consider a different approach where you presort the smallest pieces looking for combinations that fit together to make close to whole number lengths. This may sound strange, but I wrote a program for my website cart that packs items inside the volume of a box and at first it was unbelievably slow, but when I started to presort and combine items prior to the iteration technique, it really sped things up.

[franji1]

Bad news.  I just realized I was only using 20 lengths, not 21 lengths as OP stated.  Hence, worst case takes TWICE as long (because there are 2 ** 21 combinations).  So, now I am getting 96 seconds to run through every combination at 2ms .TimeSlice.