topic Re: IML to replace greedy algorithm for inventory optimization in SAS/IML Software and Matrix Computations

IML to replace greedy algorithm for inventory optimization

AramF — Mon, 09 Dec 2024 10:32:20 GMT

Greetings. I currently run an optimization routine for 6000 SKUs using a greedy algorithm to search through different stocking levels to achieve a certain customer satisfaction KPI. My outcome is strongly influenced by my choice of starting stocking levels for each SKU. I would like to harness the power of IML to find the most optimal stocking solution, but unfortunately, my programming skills are better suited to entertain seasoned programmers than to provide material for serious critique. I hope I can learn from your help and further edit the code on my own to try different optimization parameters. While there are plenty of examples on the web with IML Knapsak solutions, my particular case is complicated by diminishing contribution for higher stocking levels for each SKU as well as selecting 1 stocking level out of multiple options for each SKU. I run SAS 9.4. In the example below I want to optimize 3 SKUs with different possible stocking levels. My goal is to identify plans for each of my SKUs, minimize total expenditure, and achieve a desired customer satisfaction contribution between 11-14 units. Thank you.

SKU	Stock	Cost	Contribution
A	1	10	1
A	2	20	1.9
A	3	30	2.8
A	4	40	3.75
A	5	50	4.7
B	1	20	1.7
B	2	40	2.6
B	3	60	3.4
B	4	80	4.0
B	5	100	5.1
C	6	210	3.0
C	7	245	4.2
C	8	280	4.8
C	9	315	6.3
C	10	350	6.7

Re: IML to replace greedy algorithm for inventory optimization

Rick_SAS — Mon, 09 Dec 2024 11:01:09 GMT

I assume from your comments that your programming skills are less than ideal? You might ask one of your team members to assist you.

If you haven't already done so, you can start by reading about how to optimize problems like this by using either genetic algorithms of mixed-integer programming in IML:

Calling @Ksharp

Re: IML to replace greedy algorithm for inventory optimization

Ksharp — Tue, 10 Dec 2024 02:43:42 GMT

I don't understand your question. Can you clarify it more ?
What is your object function ? and how many stock levels you want to pick up from each SKU at least ?

And for the optimization problem , the best choice is SAS/OR ,(although SAS/IML have some routine/function like NLP* and Genetic Algorithm for optimial question).
Therefore better post is at OR forum:
https://communities.sas.com/t5/Mathematical-Optimization/bd-p/operations_research

can calling @RobPratt

"my particular case is complicated by diminishing contribution for higher stocking levels for each SKU as well as selecting 1 stocking level out of multiple options for each SKU. "

What do you mean by that ?

Re: IML to replace greedy algorithm for inventory optimization

AramF — Tue, 10 Dec 2024 18:15:58 GMT

Hi Kshap,

The objective function is to minimize the cost of inventory.

The constraints are:

Achieve a set level of contribution

Include every SKU in your analysis.

In the classic Knapsack problem every fruit has a weight and a caloric value. Similarly in my problem, SKU has a cost and a value contribution to service level. The tricky difference is that the value of contribution is not scalar. It's based on Poisson distribution. So 1 unit could contribute 30% probability of service level, while 2 units together would have combined contribution 45%, or more accurately not 60%. (I translate probability into contribution value) Therefore as the procedure goes through different scenarios of potential solutions, N_unit contribution and 1unit contribution cannot occur for the same SKU in the same scenario.

My problem is actually very similar to https://communities.sas.com/t5/SAS-IML-Software-and-Matrix/Variation-of-Knapsack-Problem/td-p/569457. In that example there are 3 arrays (he calls them lists). To do the same thing I would need at least 6000 arrays for each SKU. I hope that clarifies it better. @Ksharp

@Rick_SAS Rick, I am afraid I am the last of the Mohicans here, the younger generation shy away from SAS in favor of Python and R. Yesterday I asked around for advice in other groups, but those users are just running old scripts that were not developed by them.

Re: IML to replace greedy algorithm for inventory optimization

AramF — Tue, 10 Dec 2024 18:39:16 GMT

Rick,

In the above referenced thread from 2019 you proposed this code.

proc iml;
L1 = {0 26 44};
L2 = {0 52 65 78};
L3 = {0  4 12 20 27 46};
target = 116;
G = ExpandGrid(L1, L2, L3);
idx = loc( G[,+]=target );
if ncol(idx)>0 then 
   soln = G[idx,];
else soln=.;  /* no soln */
print soln;

I naturally would not come up with this solution due to my inexperience, so I thought maybe there are eloquent ways of dealing with the multitude of SKUs and different stocking levels within each SKU that someone has already developed. My way of thinking is actually more along the lines of Ksharp's idea of making each SKU a stand alone table and then performing a cartesian product on all of them. It is wonderfully clear solutions, yet intuitively I feel I might get some results in the next century if I go that route given my SKU population. So hoping to address that issue in ways that I normally would not.

Re: IML to replace greedy algorithm for inventory optimization

Rick_SAS — Tue, 10 Dec 2024 20:05:01 GMT

Your problem sounds large and complex. Unfortunately, I have several work-related projects that require my attention. I cannot think about your problem right now, but hopefully someone else can offer you advice.

Regarding my post from 2019, that method is a brute-force method that examines all combinations. It will not work for large problems.

Re: IML to replace greedy algorithm for inventory optimization

ChanceTGardener — Tue, 10 Dec 2024 23:16:15 GMT

In your toy input data, should the stock for C be 1-5 as well, similar to A and B?

Assuming yes, and if I'm following along correctly, the solution to your toy example should be:

A = 5

B = 3

C = 1

Total Cost = 320

Total Contribution = 11.1

Is this correct? If not, please explain why not.

Re: IML to replace greedy algorithm for inventory optimization

AramF — Tue, 10 Dec 2024 23:42:15 GMT

Hi Chance,

SKU C can start from 1 and go to 10. In this case starting from 5 was intentional because there are SKUs that have minimum stocking qty> 1 for business reasons. Other wise yes, your solution was correct because it was above 11 units and had the lowest cost.

POSSIBLE SOLUTIONS
A	B	C	Contribution	Cost
1	5	9	12.4	425
1	5	10	12.8	460
2	3	9	11.6	395
5	3	5	11.1	320	winner

Re: IML to replace greedy algorithm for inventory optimization

ChanceTGardener — Wed, 11 Dec 2024 01:27:12 GMT

Thanks, I understand better now. Do you license SAS/OR?

If so, happy to provide some code to get you started that formulates and solves this as a mixed-integer linear programming problem.

Re: IML to replace greedy algorithm for inventory optimization

Ksharp — Wed, 11 Dec 2024 06:32:09 GMT

It looks like you just need a simple mixed integer linear programming (MILP) problems.

Since you have so many variables and so many constraint conditions, the only choice is using SAS/OR, if you do not have its license ,you could try free OR by SAS OnDemand for Academic :

SAS OnDemand for Academics

Anyway, here is an example:


proc optmodel;
set idx={1..15};
num cost{idx}=[10 20 30 40 50    20 40 60 80 100    210 245 280 315 350];
num contribution{idx}=[1 1.9 2.8 3.75 4.7   1.7 2.6 3.4 4.0 5.1  3.0 4.2 4.8 6.3 6.7];

var v{idx} binary;

min obj=sum{i in idx} cost[i]*v[i];

con con :11<=(sum{a in 1..15} contribution[a]*v[a])<=14  ;
con con1:sum{a1 in 1..5}   v[a1]=1;
con con2:sum{a2 in 6..10}  v[a2]=1;
con con3:sum{a3 in 11..15} v[a3]=1;

solve with clp / findallsolns;

print obj  Cost	Contribution v;
quit;

Re: IML to replace greedy algorithm for inventory optimization

Ksharp — Wed, 11 Dec 2024 07:26:01 GMT

If you want input thing is a dataset/table , not want type it by hand, try the following code:

NOTE: I changed the index of stock(from 1 to 5) in SKU=C to make the code easy to read, you can easily change the index by a data step.

data have;
infile cards expandtabs truncover;
input sku $ stock	Cost	Contribution;
cards;
A	1	10	1
A	2	20	1.9
A	3	30	2.8
A	4	40	3.75
A	5	50	4.7
B	1	20	1.7
B	2	40	2.6
B	3	60	3.4
B	4	80	4.0
B	5	100	5.1
C	1	210	3.0
C	2	245	4.2
C	3	280	4.8
C	4	315	6.3
C	5	350	6.7
;



proc sort data=have out=sku nodupkey;by sku;run;
proc sort data=have out=stock nodupkey;by stock;run;
proc optmodel;
set<str> sku;
set stock;
num cost{sku, stock};
num contribution{sku, stock};

read data sku into sku=[sku];
read data stock into stock=[stock];
read data have into [sku stock] cost contribution;

var v{sku, stock} binary;

min obj=sum{i in sku,j in stock} cost[i,j]*v[i,j];
con con1 :11<=(sum{i in sku,j in stock} contribution[i,j]*v[i,j])<=14  ;
con con2{m in sku}:sum{n in stock} v[m,n]=1;
solve with clp / findallsolns;
create data want from [solution sku2 stock2]={s in 1.._NSOL_,i in sku,j in stock} 
                      cost2=cost[i,j] contribution2=contribution[i,j] flag=v[i,j].sol[s];
quit;

proc print data=want noobs;
run;

Re: IML to replace greedy algorithm for inventory optimization

AramF — Wed, 11 Dec 2024 08:23:01 GMT

Ksharp,

I ran the code exactly as you typed and it worked perfectly. BIG SUCCESS !!!!! Thank you so much.

I then tried to change two things:

1. I updated the SKU C to 6-10 instead of 1-5 and got "Semantic Error" in Solution Status.

2. I renumbered SKU C to 1-5 as you originally posted and removed the last 2 observations, so SKU C only had 1-3 observations. That caused Semantic Error too.

Is there a way to run <Optimodel> with dissimilar stock values for each SKU, because that is a very real situation that I face?

Re: IML to replace greedy algorithm for inventory optimization

AramF — Wed, 11 Dec 2024 08:43:19 GMT

When I say dissimilar stock, I mean A could have 2 stocks, B 4 stocks and C 5 stocks.

SKU	Stock	Cost	Contribution
A	1	10	1
A	2	20	1.9
B	1	20	1.7
B	2	40	2.6
B	3	60	3.4
B	4	80	4
C	6	210	3
C	7	245	4.2
C	8	280	4.8
C	9	315	6.3
C	10	350	6.7

Re: IML to replace greedy algorithm for inventory optimization

Ksharp — Wed, 11 Dec 2024 08:52:00 GMT

OK. Here is .

I make a new index of stock(1 2 3 4 ....) , you could merge old index of stock back by one more data step (as I showed).

data have;
infile cards expandtabs truncover;
input sku $ stock	Cost	Contribution;
cards;
A	1	10	1
A	2	20	1.9
A	3	30	2.8
A	4	40	3.75
A	5	50	4.7
B	1	20	1.7
B	2	40	2.6
B	3	60	3.4
B	4	80	4.0
B	5	100	5.1
C	6	210	3.0
C	7	245	4.2
C	8	280	4.8
C	9	315	6.3
C	10	350	6.7
;

data have2;
 set have(rename=(stock=old_stock));
 by sku;
 if first.sku then stock=0;
 stock+1;
run;
proc sql;
create table have3 as
select a.*,coalesce(b.Cost,0) as cost,coalesce(b.Contribution,0) as Contribution
 from (select * from (select distinct sku from have2),(select distinct stock from have2)) as a
 natural left join
 have2 as b ;
quit;

proc sort data=have3 out=sku nodupkey;by sku;run;
proc sort data=have3 out=stock nodupkey;by stock;run;
proc optmodel;
set<str> sku;
set stock;
num cost{sku, stock};
num contribution{sku, stock};

read data sku into sku=[sku];
read data stock into stock=[stock];
read data have3 into [sku stock] cost contribution;

var v{sku, stock} binary;

min obj=sum{i in sku,j in stock} cost[i,j]*v[i,j];
con con1 :11<=sum{i in sku,j in stock} contribution[i,j]*v[i,j]<=14  ;
con con2{m in sku}:sum{n in stock} v[m,n]=1;
solve with clp / findallsolns;
create data want from [solution sku2 stock2]={s in 1.._NSOL_,i in sku,j in stock} 
                      cost2=cost[i,j] contribution2=contribution[i,j] flag=v[i,j].sol[s];
quit;

data want2;
 length sku2 $ 100;
 merge want have2(keep=sku stock  old_stock rename=(sku=sku2 stock=stock2));
 by sku2 stock2;
run;
proc print data=want2 noobs;
run;

Re: IML to replace greedy algorithm for inventory optimization

Ksharp — Wed, 11 Dec 2024 09:03:55 GMT

@AramF wrote:

When I say dissimilar stock, I mean A could have 2 stocks, B 4 stocks and C 5 stocks.

SKU

Stock Cost Contribution

A 1 10 1

A 2 20 1.9

B 1 20 1.7

B 2 40 2.6

B 3 60 3.4

B 4 80 4

C 6 210 3

C 7 245 4.2

C 8 280 4.8

C 9 315 6.3

C 10 350 6.7

So the number of stock from each SKU is varying ?

Just change the constraint condition and could yield THREE solutions:

data have;
infile cards expandtabs truncover;
input sku $ stock	Cost	Contribution;
cards;
A	1	10	1
A	2	20	1.9
A	3	30	2.8
A	4	40	3.75
A	5	50	4.7
B	1	20	1.7
B	2	40	2.6
B	3	60	3.4
B	4	80	4.0
B	5	100	5.1
C	6	210	3.0
C	7	245	4.2
C	8	280	4.8
C	9	315	6.3
C	10	350	6.7
;

data have2;
 set have(rename=(stock=old_stock));
 by sku;
 if first.sku then stock=0;
 stock+1;
run;
proc sql;
create table have3 as
select a.*,coalesce(b.Cost,0) as cost,coalesce(b.Contribution,0) as Contribution
 from (select * from (select distinct sku from have2),(select distinct stock from have2)) as a
 natural left join
 have2 as b ;
quit;

proc sort data=have3 out=sku nodupkey;by sku;run;
proc sort data=have3 out=stock nodupkey;by stock;run;
proc optmodel;
set<str> sku;
set stock;
num cost{sku, stock};
num contribution{sku, stock};

read data sku into sku=[sku];
read data stock into stock=[stock];
read data have3 into [sku stock] cost contribution;

var v{sku, stock} binary;

min obj=sum{i in sku,j in stock} cost[i,j]*v[i,j];
con con1 :11<=sum{i in sku,j in stock} contribution[i,j]*v[i,j]<=14  ;
con con2{m in sku}:sum{n in stock} v[m,n]>=1;
solve with clp / findallsolns;
create data want from [solution sku2 stock2]={s in 1.._NSOL_,i in sku,j in stock} 
                      cost2=cost[i,j] contribution2=contribution[i,j] flag=v[i,j].sol[s];
quit;
proc sort data=want;by sku2 stock2;run;
data want2;
 length sku2 $ 100;
 merge want have2(keep=sku stock  old_stock rename=(sku=sku2 stock=stock2));
 by sku2 stock2;
run;
proc sort data=want2;by solution sku2 stock2;run;
proc print data=want2 noobs;
run;

Re: IML to replace greedy algorithm for inventory optimization

AramF — Wed, 11 Dec 2024 09:13:31 GMT

I don't think I made myself clear. Let me try to do a better job. BTW, that you so much for your generosity in working this.

In my work I could have for SKU A 100 different stocks (10 thru 110), For SKU B 15 different stocks (1 thrugh 15) and SKU C 10 different ones (32-42). The reason for it, is that I have Min stock and Max Stock values that are determined by business rules outside of optimization.

To use the code that you offered, would I need SKU A, B and C each have 100 different stocks instead of 100 for A, 14 for B and 10 for C?

Re: IML to replace greedy algorithm for inventory optimization

Ksharp — Wed, 11 Dec 2024 09:21:12 GMT

@AramF wrote:

I don't think I made myself clear. Let me try to do a better job. BTW, that you so much for your generosity in working this.

In my work I could have for SKU A 100 different stocks (10 thru 110), For SKU B 15 different stocks (1 thrugh 15) and SKU C 10 different ones (32-42). The reason for it, is that I have Min stock and Max Stock values that are determined by business rules outside of optimization.

To use the code that you offered, would I need SKU A, B and C each have 100 different stocks instead of 100 for A, 14 for B and 10 for C?

Sure. Of course you can. Just change the constraint condition in code:

data have;
infile cards expandtabs truncover;
input sku $ stock	Cost	Contribution;
cards;
A	1	10	1
A	2	20	1.9
A	3	30	2.8
A	4	40	3.75
A	5	50	4.7
B	1	20	1.7
B	2	40	2.6
B	3	60	3.4
B	4	80	4.0
B	5	100	5.1
C	6	210	3.0
C	7	245	4.2
C	8	280	4.8
C	9	315	6.3
C	10	350	6.7
;

data have2;
 set have(rename=(stock=old_stock));
 by sku;
 if first.sku then stock=0;
 stock+1;
run;
proc sql;
create table have3 as
select a.*,coalesce(b.Cost,0) as cost,coalesce(b.Contribution,0) as Contribution
 from (select * from (select distinct sku from have2),(select distinct stock from have2)) as a
 natural left join
 have2 as b ;
quit;

proc sort data=have3 out=sku nodupkey;by sku;run;
proc sort data=have3 out=stock nodupkey;by stock;run;
proc optmodel;
set<str> sku;
set stock;
num cost{sku, stock};
num contribution{sku, stock};

read data sku into sku=[sku];
read data stock into stock=[stock];
read data have3 into [sku stock] cost contribution;

var v{sku, stock} binary;

min obj=sum{i in sku,j in stock} cost[i,j]*v[i,j];
con con1 :11<=sum{i in sku,j in stock} contribution[i,j]*v[i,j]<=14  ;
con con2{m in sku}:sum{n in stock} v[m,n]=2;  /*each SKU have two stock*/  /*  >=1  means at least one stock from each SKU*/
solve with clp / findallsolns;
create data want from [solution sku2 stock2]={s in 1.._NSOL_,i in sku,j in stock} 
                      cost2=cost[i,j] contribution2=contribution[i,j] flag=v[i,j].sol[s];
quit;
proc sort data=want;by sku2 stock2;run;
data want2;
 length sku2 $ 100;
 merge want have2(keep=sku stock  old_stock rename=(sku=sku2 stock=stock2));
 by sku2 stock2;
run;
proc sort data=want2;by solution sku2 stock2;run;
proc print data=want2 noobs;
run;

Base on your orginal data, you can not set solution, you need to change this sample data .

I have to leave now!

Re: IML to replace greedy algorithm for inventory optimization

AramF — Wed, 11 Dec 2024 09:22:48 GMT

I just realized that my reply had wrong counts. Let me redo the numbers:

In my work I could have for SKU A 100 different stocks (10 thru 109), For SKU B 15 different stocks (1 thru 15) and SKU C 10 different ones (32-41). The reason for it, is that I have Min stock and Max Stock values that are determined by business rules outside of optimization.

To use the code that you offered, would I need SKU A, B and C each have 100 different stocks instead of 100 for A, 15 for B and 10 for C?

Re: IML to replace greedy algorithm for inventory optimization

AramF — Wed, 11 Dec 2024 09:38:00 GMT

con con2{m in sku}:sum{n in stock} v[m,n]=2;  /*each SKU have two stock*/  /*  >=1  means at least one stock from each SKU*/

I was afraid that this is what you understood. I did not mean that.

What I am asking is can my starting dataset be Table A instead of original Table B. In Table A there is an unequal number of stocking possibilities in each SKU. I still want only 1 outcome to be used in the solution per SKU, but for SKU A it is 1 out 2, for SKU B it is 1 out 4 and for SKU C it is 1 out 5? I will never want to get 2 stock possibilities out of a particular SKU.

Table A				Table B
SKU	Stock	Cost	Contribution	SKU	Stock	Cost	Contribution
A	1	10	1	A	1	10	1
A	2	20	1.9	A	2	20	1.9
B	1	20	1.7	A	3	30	2.8	removed
B	2	40	2.6	A	4	40	3.75	removed
B	3	60	3.4	A	5	50	4.7	removed
B	4	80	4	B	1	20	1.7
C	6	210	3	B	2	40	2.6
C	7	245	4.2	B	3	60	3.4
C	8	280	4.8	B	4	80	4
C	9	315	6.3	B	5	100	5.1	removed
C	10	350	6.7	C	6	210	3
				C	7	245	4.2
				C	8	280	4.8
				C	9	315	6.3
				C	10	350	6.7

Re: IML to replace greedy algorithm for inventory optimization

ChanceTGardener — Wed, 11 Dec 2024 11:17:11 GMT

This model will accommodate an unequal number of possibilities (stocks) per SKU. Additionally, the stocks can, but are not required to increment by 1. See SKU C as an example in the input data below.

The output data set shows the optimal number of each SKU to stock.

Feel free to change the input data to accommodate the different scenarios you may face to confirm it performs well across all of them.

data input_data;
 input sku $ stock cost contribution;
datalines;
A 1 10 1
A 2 20 1.9
A 3 30 2.8
A 4 40 3.75
A 5 50 4.7
B 1 20 1.7
B 2 40 2.6
B 3 60 3.4
B 4 80 4.0
B 5 100 5.1
C 1 210 3.0
C 17 245 4.2
C 18 280 4.8
C 30 315 6.3
C 100 350 6.7
;

proc optmodel;

set <str,num> ARCS;

set SKUS = setof{<i,j> in ARCS} i;
set STOCK = setof{<i,j> in ARCS} j;

num cost{ARCS};
num contribution{ARCS};

read data input_data into ARCS=[sku stock] cost contribution;

var Assign{ARCS} binary;

impvar TotalContribution = sum{<i,j> in ARCS} Assign[i,j] * contribution[i,j];

min TotalCost = sum{<i,j> in ARCS} Assign[i,j]*cost[i,j];

con contribuion_lb: 11 <= TotalContribution <= 14;

con sku_minimum{i in SKUS}: sum{j in STOCK: <i,j> in ARCS} Assign[i,j] = 1;

solve;

print TotalContribution;
print TotalCost.sol;

create data output_data from [sku stock] = {<i,j> in ARCS: Assign[i,j] > 0.5};

quit;