We have a manual process where if a 250mg dose of Drug A is required, we give 120mg + 75mg + 55mg as 3 separate doses, or (2 x 75mg) + 100mg, or (2 x 80mg) + 90mg
What I'm after is the best way to calculate if the available dose is divisible by any combination of 120mg, 100mg, 90mg, 80mg, 75mg, 55mg (will vary depending on Drug choice)
My current approach would be to Loop through the available doses till it equals the required dose starting with:
1 of smallest size then loop through 1 of remaining sizes
1 of second smallest size then loop through 1 of remaining sizes
etc...
Then 2 of smallest size & loop through 1 of remaining sizes
and so on.. till we get to max of 3 separate doses of any combination.
I can put some rules in if only 1 in stock of that size then no need to run for 2.
My worry is although a quick calculation for a human to work out the loops are going to make this a very slow bit of code that I really need to be a quick check if stock available.
Many thanks in advance for any insight into the best approach to this issue.
Concerned about the logic: I would think the process would be
Target = Dosage total, Pack = null, Diff = Target
For the selected Drug, while DIFF <> 0,
Select Drug AvailableDose = or < Diff
Pack = Drug AvailableDose + Pack
Diff = Target - AvailableDose
If Diff < 0 then AvailableDose = stepdown to next smallest
Next (Drug Dose)
Pack = string listing tablets to make target
Of course this does not consider stock levels, max 3 combos, and other constraints (?).
Advantage: Minimises the number of tablets. If you always start from the smallest, then you will inevitably be discarding valid combos where combos exceed 3 before arriving at the target.
Re speed - you will need to ensure an appropriate index exists on your table involving the Drug and the AvailableDose. Presume the table of drug and tablet exists (not a column for each available dose).
I like to solve such tasks by query. After all, you ask your question in a database forum.
Create a table with a column dose and write your values in it.
A CROSS JOIN is created in a query and all conceivable variants of combinations are determined, which are then restricted to a meaningful overview by conditions.
SQL:
SELECT
T1.dose AS D1,
T2.dose AS D2,
T3.dose AS D3,
T1.dose + T2.dose + T3.dose AS [Sum]
FROM
tblDoses AS T1,
tblDoses AS T2,
tblDoses AS T3
WHERE
T1.dose + T2.dose + T3.dose <= 250
AND
T1.dose <= T2.dose
AND
T2.dose <= T3.dose
ORDER BY
4 DESC,
1,
2,
3
Wouldn't you also consider the fact that a 500mg pill could be cut in half (if it's a solid cuttable pill)? So checking for the largest dosage available and seeing if the target equals half should be in there.
We have a manual process where if a 250mg dose of Drug A is required, we give 120mg + 75mg + 55mg as 3 separate doses, or (2 x 75mg) + 100mg, or (2 x 80mg) + 90mg
What I'm after is the best way to calculate if the available dose is divisible by any combination of 120mg, 100mg, 90mg, 80mg, 75mg, 55mg (will vary depending on Drug choice)
My current approach would be to Loop through the available doses till it equals the required dose starting with:
1 of smallest size then loop through 1 of remaining sizes
1 of second smallest size then loop through 1 of remaining sizes
etc...
Then 2 of smallest size & loop through 1 of remaining sizes
and so on.. till we get to max of 3 separate doses of any combination.
I can put some rules in if only 1 in stock of that size then no need to run for 2.
My worry is although a quick calculation for a human to work out the loops are going to make this a very slow bit of code that I really need to be a quick check if stock available.
Many thanks in advance for any insight into the best approach to this issue.
Believe or not, this is similar to problems in queueing theory and also to problems in load optimization for shipping.
FIRST, you have to decide not only the primary goal (total dose) but the secondary goal (which can differ wildly). For secondary goals: Do you want to do the dosage with the fewest separate dose sizes, or the smallest separate dose sizes, ... and you have a list of available sizes, so you need to stay within fixed dose sizes. Other questions you need to ask include: What do you do when you cannot reach the target using three of the largest doses? What will you do when no combination of the available doses can reach the target exactly?
It might be possible to compute this using recursion - by trying to pick the LARGEST dose that is smaller than the target first, and then subtracting that dose size from the target and treating it as a new problem for a smaller target. (That "treat the remainder as a new problem with a smaller target" is the recursion step.) Along the steps of the selection, you accumulate the doses selected by previous iterations. This would give you the selected dose in larger units, but you would have to also take into account the quantity on hand for each selected dose to see if the allocation could even be made.
Because you have multiple ways to select combinations, you will find that this automated method would tend to not give you some dose combinations that you would have preferred that it choose. The trick there is to somehow quantify WHY you would or would not have made the choice. Because you have so many options, all I can do is offer the insight. This would be a very complex problem and anything I try to code for you would make a lot of assumptions that wouldn't fit into your situation.
Mike, the sky is the limit with possibilities, your imagination is the limit with implementation. I only know of two basic approaches for this class of problem - smallest first or largest first. "Random" first is in that part of queueing theory that I never got to. But the restrictions on "max 3 doses" and "availability of doses" will make this a tricky combination. I will say this: Biggest Doses First would tend to minimize the count of doses and be the best way to assure that you are within the 3 dose limit. Smallest Doses First would likely tend to trigger recomputes because it would tend to use too many smaller doses and hit that 3 dose limit.
And to other members, several of you offered a similar approach that would essentially be the same as recursion. I may just be the only one who used that word.
Thank you all, got a lot to think through. At this point it's a quick check to see if it would be possible. Later on there's code to consider all the variables, expiry time, stock levels, min number of doses, average usage of size, but that runs at a part when the hourglass can kick in and the user can wait. But don't want to go down this route if the end result is going to be no available stock combination.
I have used Target dose - Largest size = Remainder then try to assign to the remainder which works well where there's only 4 size options but became difficult to follow for more sizes with the additional rules I'd use to minimise the calculation burden.
As we're only trying to answer is it possible in any combination it's hard to know if you'll get to the True answer by starting with the smaller variable or the larger variable but I take your point Doc Larger first is probably better.
The code is a loop so it doesn't matter how many sizes there are. For example, 250, 125, 50, 25. If you want a dose of 275, you end up with 250 + 25. It doesn't matter that 2(125), and 1(25) also satisfy or if 11(25) works. Starting from the large size, you always get the most efficient breakdown. The middle sizes are tried and discarded. The complications arise if you want to limit the number of pills and the available sizes can't satisfy the requirement. Or, you don't have inventory in the sizes that will work. The looping also is very complicated if the sizes are not multiples. For example if 37.5 and 25 were the only options a final solution could not be found without backing out and trying again which gets really complicated.
You can get to "True" from either direction assuming the available sizes provide a solution, but do you want to dispense 11 pills or 2 is the question.
AFAIK all the proposed solutions are pretty infeasible if the max amount of pills was unconstrained. You have varying amount of doses and a varying amount of mixes. 1 pill solution, 2 pill solution, 3 pill solution, .... N pill solution. You cannot "loop" all solutions because you do not know how many potential loops. However, since you specify that a maximum 3 pill mix is only allowed this solution can be easily done as EBS17 proposes.
The unconstrained solution is much harder to do, but the algorithms to do this are very well known. Normally this is done normally with a spanning tree. This is often the first step in doing other optimization problems such as a Cutting Stock problem. You have to define all the feasible patterns. This attachedf PDF article does a good job of defining the spanning tree to get feasible patterns. I use a version of this algorithm. If you start adding values to the preferred choices this problem becomes a Knapsack problem.
I have database that will spit out frame sizes for cutting. We then manually enter this information into another software tool that will optimize the cut order to minimize the number of 14 foot boards used. It would be beneficial to do the optimizing in the database and eliminate the extra...
www.access-programmers.co.uk
KnapSack and Bin Packing Discussion and algorithms
I am after some code/advice for Access. I have a list of Order Numbers(Unique) and what cubic metres that each are, I also have a cost benefit per Order. I would like to run some code to be able to find every combination of Orders but within a given constraint of Cubic size (65Cube) to find...
www.access-programmers.co.uk
In my solution I have a table of drugs and related pill doses. You can add as many drugs as you want and there potential pill sizes.
tblDrugs tblDrugs
drugID
drugName
1
Drug A
2
Drug B
tblDrugDoses tblDrugDoses
drugDoseID
Dose
Units
drugID_FK
1
55
mg
1
2
75
mg
1
3
80
mg
1
4
90
mg
1
5
100
mg
1
6
120
mg
1
7
50
mg
2
8
40
mg
2
9
30
mg
2
10
20
mg
2
Drug A is your example, Drug B is the example in the PDF.
Using Drug B and 130 mg total dose. You have pill sizes of 50, 40, 30, 20 You create a spanning tree as follows to get all feasible solutions.
Basically you work from left of the tree to right. Algorithm is explained in detail.
The table might make it easier to explain
Create far left branch 1
1. Order pill sizes from large to small
2. Start with 130 and figure out how many of level 1 (50 mg) can divide into it. That is 2. You have a remainder of 30.
3. Next go to level 2 (40 mg) and see how many of 40 can go into the remainder. That is zero.
4.Next go to level 3 (30) mg and see how many can go into the remainder (30) and that is 1.
5. Next go to level 4 (20) and see how many can go into the remainder (0) and that is 0.
Now you work from the bottom up to create the next branch (Column 2).
1. move up the first branch above the last level until you find a level with a quantity of more than 0.
2. There is a 1 in level 3 (30)
3. Decrement that by 1 and recalculate the residual.
4. Work back down.
5. See how many level 4 (20) can go into the remainder (30). And that is 1.
Keep doing this until there is no quantiies above the last level.
Here is the class module to do it.
Code:
Option Compare Database
Option Explicit
'To match example make the rows and columns 1 based
Private m_DrugID As Long
Private m_Column_J As Long
Private m_Level_I As Long
Private m_Doses() As Long
Private m_TotalDosage As Long
Private m_MaxLevel As Integer
Private m_LastQuantities() As Long
Private m_IncludeUnfilled As Boolean
Private m_IncludeZeroQuantity As Boolean
Private M_RS As DAO.Recordset
Public Sub Initialize(drugID As Long, totalDosage As Long, Optional IncludeZeroQuantity As Boolean = False, Optional IncludeUnfilled As Boolean)
Dim strSql As String
Dim rs As DAO.Recordset
Dim I As Long
Dim startTime As Long
startTime = Timer
'IncludeUnfilled used to log patterns where there is still leftover/residual
'In this problem you would not include these, but in general pattern building you would
'IncludeZeroQuantity used if you want to show pill sizes that are not used
m_DrugID = drugID
m_TotalDosage = totalDosage
m_IncludeUnfilled = IncludeUnfilled
m_IncludeZeroQuantity = IncludeZeroQuantity
m_Level_I = 1
strSql = "Select Dose from tblDrugDoses where DrugID_FK = " & drugID & " ORDER BY Dose desc"
Set rs = CurrentDb.OpenRecordset(strSql)
rs.MoveLast
rs.MoveFirst
ReDim m_Doses(1 To rs.RecordCount)
ReDim m_LastQuantities(1 To rs.RecordCount)
I = 1
Do While Not rs.EOF
m_Doses(I) = rs!Dose
rs.MoveNext
I = I + 1
Loop
m_MaxLevel = I - 1
UpdateNewColumn 0
InitializeRecordset
FillTable
Debug.Print "Time to complete: " & Timer - startTime '78 sec at 1500 drug a
End Sub
Private Sub InitializeRecordset()
Set M_RS = CurrentDb.OpenRecordset("Select * from tblFeasibleDoses where true = false", dbOpenDynaset)
End Sub
Public Sub UpdateNewColumn(currentRow As Integer)
Dim TheDose As Long
Dim TheDoseQuantity As Long
Dim TheResidual As Long
Dim strSql As String
Dim I As Integer
'Update the new column of the array of quantities, but only log when residual is 0
TheResidual = m_TotalDosage
For I = 1 To UBound(m_Doses)
TheDose = m_Doses(I)
If I <= currentRow Then
TheDoseQuantity = m_LastQuantities(I)
Else
TheDoseQuantity = SmallestInt(TheResidual, TheDose)
m_LastQuantities(I) = TheDoseQuantity
End If
TheResidual = TheResidual - TheDose * TheDoseQuantity
Next I
'Debug.Print TheResidual
If m_IncludeUnfilled = True Or TheResidual = 0 Then LogFeasible
End Sub
Public Sub LogFeasible()
Dim strSql As String
Dim I As Long
Dim TheDose As Long
Dim TheDoseQuantity As Long
Dim TheResidual As Long
'for simplicity add the new records, but the insert and update could be all done at once
m_Column_J = m_Column_J + 1
TheResidual = m_TotalDosage
For I = 1 To UBound(m_Doses)
TheDose = m_Doses(I)
TheDoseQuantity = m_LastQuantities(I)
m_LastQuantities(I) = TheDoseQuantity
TheResidual = TheResidual - TheDose * TheDoseQuantity
If M_RS Is Nothing Then InitializeRecordset
If TheDoseQuantity <> 0 Or m_IncludeZeroQuantity Then
M_RS.AddNew
M_RS!totalDosage = m_TotalDosage
M_RS!DrugID_FK = m_DrugID
M_RS!DoseValue = m_Doses(I)
M_RS!DoseQuantity = TheDoseQuantity
M_RS!solutioncolumn = m_Column_J
M_RS!Solutionrow = I
M_RS!Residual = TheResidual
M_RS.Update
End If
Next I
End Sub
Public Sub FillTable()
Dim I As Integer
Dim SomethingFound As Boolean
Do
' Debug.Print LastQuantitiesToString
For I = UBound(m_LastQuantities) - 1 To 1 Step -1
' Debug.Print m_LastQuantities(I)
SomethingFound = False
If m_LastQuantities(I) > 0 Then
m_LastQuantities(I) = m_LastQuantities(I) - 1
m_LastQuantities(UBound(m_LastQuantities)) = 0
UpdateNewColumn I
SomethingFound = True
Exit For
End If
Next I
Loop Until SomethingFound = False
End Sub
Private Function SmallestInt(Residual As Long, TheDose As Long)
SmallestInt = Residual \ TheDose
End Function
'--------------------------------------------------- To String-----------------------------------------------------------
Public Function DosesToString() As String
Dim strout As String
Dim I As Long
For I = 1 To UBound(m_Doses)
If strout = "" Then
strout = m_Doses(I)
Else
strout = strout & ", " & m_Doses(I)
End If
Next I
DosesToString = strout
End Function
Public Function LastQuantitiesToString() As String
Dim strout As String
Dim I As Long
For I = 1 To UBound(m_LastQuantities)
If strout = "" Then
strout = m_LastQuantities(I)
Else
strout = strout & ", " & m_LastQuantities(I)
End If
Next I
LastQuantitiesToString = strout
End Function
Public Function ToString() As String
ToString = "Required Dosage: " & m_TotalDosage
ToString = "Levels: " & m_MaxLevel
ToString = ToString & vbCrLf & "Doses: " & DosesToString
End Function
Here is the algorithm. Still very efficient. Will give you all feasible solutions for any pill combination and Total dosage in fraction of seconds.
Part 2
So using your data for Drug A and 250. All possible patterns are saved to the table.
This is the 1st two solution for the 29 potential patterns. (Cannot post all here do to size)
DrugID_FK
TotalDosage
SolutionColumn
SolutionRow
DoseValue
DoseQuantity
Residual
1
250
1
1
120
2
10
1
250
1
2
100
0
10
1
250
1
3
90
0
10
1
250
1
4
80
0
10
1
250
1
5
75
0
10
1
250
1
6
55
0
10
1
250
2
1
120
1
130
1
250
2
2
100
1
30
1
250
2
3
90
0
30
1
250
2
4
80
0
30
1
250
2
5
75
0
30
1
250
2
6
55
0
30
Solution 1 is
2 x 120 with a waste of 10
Solution 2 is
1 x 120
1 x 100
with a waste of 30.
Not very easy to read, but you could format into a report.
Pattern 1 is 2 x 120 with a waste of 10
Pattern 2 is 1 x 100, 1 x 120 with a waste of 30
etc
In my solution I did all feasible patterns, but your problem just needs to return those patterns with 0 waste.
The way this should work is you need to enter your drugs and the possible pill sizes.
In the main form select your drug, it then displays the possible pill sizes. Type in the dosage. Then hit the button to create a solution.
The subform shows all possible solutions.
MajP that's a stunning solution, runs supper fast and I can build the start point on stock sizes available so Wow.
The fact that the solution gives a Dosage Pattern a few rules can select the best pattern for our purpose to use later on in the code. This option will speed up the later processes.
Going to take some time to work in but Absolutly Amazing Thank you.
Impressive analysis MajP. The OP said a max of 3 combinations. Which should trim the tree. Also, the OP would need to confirm, that not all drugs are available/produced in all dosages?
I have a degree that included a lot of optimization and mathematical modeling. I may not know how to do it anymore but do know where to go look. This one is actually relatively simple to code. But these types of problems can get surprisingly out of control fast. Trying to loop through all the possibilities may not even be possible. Something more complicated is a Dijkstra or Floyd Warshal, but I have demoed a few optimization models using Access. Normally these are heuristics because coding a guaranteed solution tends to get real difficult.
I'm trying to get my head around using the following data to create the shortest route between 2 places in a map using VBA in either excel or access. ID Name Connection 1 Connection 2 1 Location1 2 2 Location2 3 4 3 Location3 2 4 Location4 2 5 5 Location5 3 5 So...
www.access-programmers.co.uk
This spanning tree problem is not really an optimization, but it is commonly used in setting up other problems.
Also, the OP would need to confirm, that not all drugs are available/produced in all dosages?
Since the OP stated a Max of 3 the solution can be done as EBS17 points out. I could have modified the code to let the user define the max pill size. The algorithm would be the same, but it would only log these solutions and kick out of the algorithm early.
Got to say it is an impressive solution, @MajP - my little exposure to queueing theory was enough to get me out of trouble more often than in trouble, but I could never avoid trouble completely since I'm originally a chemist, not a mathematician. My entrance to computer work was a back-door sort of thing necessitated by family circumstances. Despite needing some advanced math for my doctorate, it wasn't that particular branch of math. I've sort of picked up some of the practical tricks over a few years, but it helps if you actually studied the subject in depth.
FYI, I did not originally see that you were limiting to three pills. If that is the case doing what @ebs17 suggests is probably the easy way to go. I incorporated a version here. The query solution is simple and fast and does not require code. It gets more tricky if you remove the three pill constraint. However if some dosages have different max amount of individual dosages you could make a 3,4,5...N individual queries.
The query is slightly modified to
Code:
SELECT A.dose AS Dose1,
B.dose AS Dose2,
C.dose AS Dose3,
[a].[dose] + [b].[dose] + [c].[dose] AS TotalDose,
C.drugid_fk
FROM (qrydrugdoseswith0 AS A
INNER JOIN qrydrugdoseswith0 AS B
ON A.drugid_fk = B.drugid_fk)
INNER JOIN qrydrugdoseswith0 AS C
ON B.drugid_fk = C.drugid_fk
WHERE
( ( ( B.dose ) <= [a].[dose] )
AND ( ( C.dose ) <= [b].[dose] )
AND ( ( [a].[dose] + [b].[dose] + [c].[dose] ) =
[forms] ! [frmmakepatternsquery] ! [txtrequired] )
AND ( ( C.drugid_fk ) = [forms] ! [frmmakepatternsquery] ! [cmbodrug] ) )
ORDER BY A.dose,
B.dose,
C.dose;
If this was a more generic problem with an unknown amount of partitions (assume something beside pill dosage like cutting a roll of steel) then that would be limiting. Assume it was something up to 10 partitions and 5 choices. Writing the query would be a pain, and this could blow up quickly because that cartesian returns 9 million records before getting filtered.
A few comments on this:
- Before execution, SQL statements are just some text. Text can be generated and composed using VBA. My longest SQL statement composed by VBA was about 1200 characters.
- Large amounts of data due to the duplication of variants are of course a problem. This will push your limits, also in terms of performance. But large amounts of data are also a challenge for a developer - anyone without great skills can move 537 records back and forth.
The most time consuming will be the execution of the CROSS JOIN itself. The result could be written to a temporary table and the fields indexed there in order to be able to filter better.
- The overall calculation for a specific case would be carried out once (not live every time from the beginning) and the combinations found would be fixed in a table in order to look up there in the practical work in a significantly smaller amount.
