Best combinations of different medication bottles

[Ivy]

Dear All,

May you help ?  How I should programm the folliowing ?

There are 4 different medication bottle size as below. I want to find the best bottle combination with less medication waste, then less bottles used to apply patients' target medication needs. The max bottle can be used is 6.

For example:

1. targetmedication 150,  the best bottle combination is :  3*50 = 150 , 3 bottles of size 50, there is no medication waste. 

2. Targetmedication  175,  the best bottle combination is :  3 bottle of size 50 and 1 bottle of size 30. There is only 5 mg medication waste.

%let vial1 = 90 ;
%let vial2 = 80 ;
%let vial3 = 50 ;
%let vial4 = 30 ;

data test;
do i = 10 to 290 by 5;
Targetmedication = i ;
output;
end;
;
run;

[ballardw]

Do you have access to Proc Optmodel?

[Shmuel]

I have done it with sas bsae.

my results are different, in some cases, than expectations

the program contains next steps:

1) calculate all combinations of 4 kinds of bottles with use of upto 6 bottels.

    note: volumes of bottles and limit of six bottles is hard coded in the program.

2) selecting the combination with minimum number of bottles per volume. (total 50 combinations from 30 to 540 by 10).

3) creating a format of volume range with its combination of bottels.

4) testing as requested.

/* all combinations of 4 kinds of bottles up to 6 bottles */

data bottles_comb /*stack=20*/;
     array bot {4} b30 b50 b80 b90;
     array vol {4} (30 50 80 90);     
     link initiate;
     
     do i=1 to 6;  /* number of bottles */
        link initiate;
        select (i);
          when (1) link one;
          when (2) link two;
          when (3) link three;
          when (4) link four;
          when (5) link five;
          when (6) link six;
        end; 
     end;
return;
*--------------*;
initiate:
   do t=1 to 4; bot(t)=0; end;  /* initiate number of bottels */
return;
*--------------*;
one:
  do i1=1 to 4; 
     bot(i1)=1; 
     link combine;
     bot(i1)=0;
  end;
return;
*--------------*;
two:  
  do i1=1 to 4;
    bot(i1) = 1;
    do i2=i1 to 4;
       bot(i2)+1;
       link combine;
       bot(i2) = bot(i2)-1;  
    end;
    bot(i1)=bot(i1)-1; 
  end;
return;
*--------------*;
three:
  do i1=1 to 4;
    bot(i1) = 1;
    do i2=i1 to 4;
       bot(i2)+1;
       link combine_3;
       bot(i2) = bot(i2)-1;  
    end;
    bot(i1)=bot(i1)-1; 
  end;
return;
combine_3:
  do i3 = i2 to 4;
     bot(i3)+1;
     link combine;
     bot(i3) = bot(i3)-1;
  end;
return;
*--------------*;
four:
  do i1=1 to 4;
    bot(i1) = 1;
    do i2=i1 to 4;
       bot(i2)+1;
       link combine_43;
       bot(i2) = bot(i2)-1;  
    end;
    bot(i1)=bot(i1)-1; 
  end;
return;
combine_43:
  do i3 = i2 to 4;
     bot(i3)+1;
     link combine_4;
     bot(i3) = bot(i3)-1;
  end;
return;
combine_4:
  do i4 = i3 to 4;
     bot(i4)+1;
     link combine;
     bot(i4) = bot(i4)-1;
  end;
return;
*--------------*;
five:
  do i1=1 to 4;
    bot(i1) = 1;
    do i2=i1 to 4;
       bot(i2)+1;
       link combine_53;
       bot(i2) = bot(i2)-1;  
    end;
    bot(i1)=bot(i1)-1; 
  end;
return;
combine_53:
  do i3 = i2 to 4;
     bot(i3)+1;
     link combine_54;
     bot(i3) = bot(i3)-1;
  end;
return;
combine_54:
  do i4 = i3 to 4;
     bot(i4)+1;
     link combine_5;
     bot(i4) = bot(i4)-1;
  end;
return;
combine_5:
  do i5 = i4 to 4;
     bot(i5)+1;
     link combine;
     bot(i5) = bot(i5)-1;
  end;
return;
*--------------*;
six:
  do i1=1 to 4;
    bot(i1) = 1;
    do i2=i1 to 4;
       bot(i2)+1;
       link combine_63;
       bot(i2) = bot(i2)-1;  
    end;
    bot(i1)=bot(i1)-1; 
  end;
return;
combine_63:
  do i3 = i2 to 4;
     bot(i3)+1;
     link combine_64;
     bot(i3) = bot(i3)-1;
  end;
return;
combine_64:
  do i4 = i3 to 4;
     bot(i4)+1;
     link combine_65;
     bot(i4) = bot(i4)-1;
  end;
return;
combine_65:
  do i5 = i4 to 4;
     bot(i5)+1;
     link combine_6;
     bot(i5) = bot(i5)-1;
  end;
return;
combine_6:
  do i6 = i5 to 4;
     bot(i6)+1;
     link combine;
     bot(i6) = bot(i6)-1;
  end;
return;
*--------------*;
combine:
   volume = 0;
   if 0 lt sum(b30,b50,b80,b90) le 6 then do;
       do t = 1 to 4;
          volume = volume + bot(t)*vol(t);
       end;
       output;
   end;
   keep i b30 b50 b80 b90 volume; 
return;
run;

proc sort data=bottles_comb out = temp;
  by volume i;
run;

/* select the minimum number of bottels per volume */
data combinations;
 set temp;
  by volume;
     if first.volume;
run;  /* output contains 50 combinations */

data cntl;
 set combinations;
     start = lag(volume);
     if _N_=1 then start = 0;
     end=volume;
     fmtname = 'comb';
     label = 'b30='||left(b30)||' b50='||left(b50)||
            ' b80='||left(b80)||' b90='||left(b90);
     keep start end fmtname label;
run;     
   
proc format lib=work cntlin=cntl; run;

/*** testing as required by user ***/

data test;
   do vol=10 to 290 by 5;
      comb = put(vol,comb.);
      output;
   end;
run;

[art297]

Here is a method in which you create a master file and then access it using a macro that runs proc sql.

It doesn't account for unique combinations (e.g., if you needed 10 mg,, filling the 90 mg, pouring it into an 80 mg container, then using the remaining 10 mg). Not sure how many bottles you would count for that!

The code I used was stolen from one of @Reeza's posts:

libname mydata '/folders/myfolders';

data mydata.want (keep=b: k total);
  *can load temporary array from dataset if required;
  array x1[24] _temporary_ (30 30 30 30 30 30 50 50 50 50 50 50 80 80 80 80 80 80 90 90 90 90 90 90);
  array x2[24] $2 _temporary_ ('1' '2' '3' '4' '5' '6' '7' '8' '9' '10' '11' '12' '13' '14' '15' '16' '17' '18' '19' '20' '21' '22' '23' '24');
  *array for output;
  array y1(24) ;
  array y2(24);
  array b(6);
  n=dim(x1);
  *loop overall all possible output ranges;
  do k=1 to n;
    *Determine number of combinations required;
    ncomb=comb(n, k);
    *Create all combinations;
    do j=1 to ncomb;
      *create the combination;
      call lexcomb(j, k, of x1[*]);
      call lexcomb(j, k, of x2[*]); 
      *Set all values to missing;
      call missing(of y1(*));
      call missing(of y2(*)); 
      *Copy over the values to the array for output;
      do i=1 to k;
        y1(i)=x1(i);
        y2(i)=x2(i);
      end;
      if k lt 7 then do;
        do i=1 to 6;
          b(i)=y1(i);
        end;
        total=sum(of b(*));
        output;
      end;
    end;
  end;
run;

proc sort data=mydata.want nodupkey;
  by b1 b2 b3 b4 b5 b6 k total;
run;

%macro findit(criterion);
  proc sql;
    select *
      from (select * 
              from mydata.want
                where total ge &criterion.)
        having total eq min(total)
          order by k
    ;
  quit;
%mend findit;

%findit(150)

HTH,

Art, CEO, AnalystFinder.com

[Ivy]

Thank you very much for the avices, 

I found out a solution:

1.  Caculate the permutation of all these 4 sizes , there are 24 arrangement of these 4 sizes.

2.  Then calcualte the number of bottle used from the bottle 1 to bottle 2 

3. Choose the min of waste with min of number of bottles.

Ivy

[Shmuel]

Your case was a chalenge for me.

According to my code there are 50 differnet combinations of bottels with max use of 6 bottels.

What is your prefernce of using bottels for a given volume of medication ?

For 175 you preferred th ecombination of 2*50+30, which sums into 180.

The same 180 can be achieved by 6*30 or by 2*90.

Would you say that you preer use bottels of 50 then use minimum number of bottels ?

You said "there are 24 arrangement of these 4 sizes".

With 6 bottels you can supply maximum of 6*90 i.e. 540.

With 4 bottels the maximum is 4*90 i.e. 360 only. Is it enough ?

Relating to the code I posted, with some more work I can reorganize it and shorten it.

I suggest - run the code and look at file temp - you will find all the possible unique combinations.

Then decide - what are the rules to choose which combination is preffered for a given volume.

I chossed the minimum number of bottels. That can be changed, for examole:

- bottels size order of prefference

- having bottels price, the minimun expence

[DanielSantos]

Hi.

It looks like the subset sum variant of the knapsack problem, which is a combinatorial optimization problem.

https://en.wikipedia.org/wiki/Knapsack_problem

If you have a SAS/IML licensed on your site you'll have at your disposal procedures who can handle this, see the following example:

http://support.sas.com/documentation/cdl/en/imlug/66112/HTML/default/imlug_geneticalgs_sect013.htm

R will handle that also (with the appropriate package).

That said, it can be done programmatically, but it's not the best thing to do in SAS/Base

One approach (listed above) would be to generate all possible combinations under the target value and then pick the best.

If the variables of the problem can change, than it might be not very pratical to code like that.

So it can be done recursively at a performance cost, but then you only have to run it once and keep the solution for everytime you need.

Here's my solution, which will produce every possible combination thus giving you always the best match, which is = target or best with lesser bottles.

Calculations are done in macro language, which might be not easy to understand, but solving the problem is not an easy task 🙂

* recursively search best combination;
%macro recursive_subset_sum(VALUES,SUM,TARGET,SUBSET,INDEX,INDEXN,SIZE,_SUBSET);
%local VALUES SUM TARGET SUBSET INDEX INDEXN SIZE _SUM _VALUE _INDEX;
%let _SUM=%eval(&SUM+%scan(&VALUES,&INDEX));
%if &INDEX eq &INDEXN or
    %sysfunc(countw(%str(&SUBSET))) eq &SIZE or
    &SUM eq &TARGET or &_SUM gt &TARGET %then %do;
    %if &_SUM gt &TARGET and %scan(&&&_SUBSET,-1) lt &SUM %then 
        %let &_SUBSET=&SUBSET ∑
%end;
%else %do;
%let _INDEX=%eval(&INDEX+1);
%let _VALUE=%scan(&VALUES,&_INDEX);
%recursive_subset_sum(&VALUES,&SUM,&TARGET,&SUBSET,&_INDEX,&INDEXN,&SIZE,&_SUBSET)
%recursive_subset_sum(&VALUES,&_SUM,&TARGET,&SUBSET &INDEX,&_INDEX,&INDEXN,&SIZE,&_SUBSET)
%end;
%mend recursive_subset_sum;

* solve given problem;
%macro solve(VALUES,TARGET,SIZE);
%let VALUESN=%sysfunc(countw(%str(&VALUES)));
%let FIXVALUES=;
%do _I=1 %to &SIZE;
%let FIXVALUES=&FIXVALUES &VALUES;
%end; 
%let _SOLUTION=0;
%recursive_subset_sum(&FIXVALUES,0,&TARGET,,1,%eval(&VALUESN*&SIZE),&SIZE,_SOLUTION)
%let SOLUTION=;
%do _I=1 %to %sysfunc(countw(%str(&_SOLUTION)))-1;
%let SOLUTION=&SOLUTION %eval(%sysfunc(mod(%scan(&_SOLUTION,&_I)-1,&VALUESN))+1;
%end;
&SOLUTION
%mend solve;

%let TARGET=105;
%let VALUES=30 50 80 50 20 50;
%let SIZE=6;

%put Best Solution = %left%trim(%solve(&VALUES,&TARGET,&SIZE));

And to keep it in a dataset

data test;
length S $50;
do i = 10 to 290 by 5;
    S=resolve(cats('%solve(',"&VALUES,",i,",&SIZE)")); 
    put _all_; * show me;
    output;
end;
run;

Hope it helps.

Daniel Santos @ www.cgd.pt