a queueing model

[torestin]

Hi there,

i am trying to create a queuing model say something is going to be sold to the first person through the door so long as they satisfy certain income criteria.  So it would go something like this a-> person a; b-> person d; e->person b. For each product in list a, it go to the front of the remaining queue and pick the eligible purchaser. My code is pasted below.

The issue though is that it seems to move on from ineligible purchasers rather than keeping them in a queue. As you can see below, the 5th customer has too much income for the 5th product, but should have stayed in the queue and takes up the 6th offering. instead, it just skips ahead to the 6th customer.

Does anyone know what went wrong and how I can fix it?

thanks

JC

Data market;
input UB LB;
datalines;
137454.23 99272.50
127407.23 92016.34
134738.07 97310.83
118503.53 85585.88
117691.52 84999.43
126468.91 91338.66
138833.30 100268.50
;;;;
run;

data customers;
input pay;
datalines;
117605
120194
114285
92316
125917
106480
94244
127482
94744
106371
122085
100327
107315
115530
116100
100279
94117
111069
98615
115879
124773
118694
111970
118629
129623
121400
100992
129743
93083
90643
;;;;
run;

Data matching;
set market;
do i = 1 to 7
set customers;

if LB<pay<UB And control= . then do;
control=1;
output;
leave;
end;

end;
run;

Results:

137454.2	99272.5	1	117605	1
127407.2	92016.34	1	120194	1
134738.1	97310.83	1	114285	1
118503.5	85585.88	1	92316	1
117691.5	84999.43	2	106480	1
126468.9	91338.66	1	94244	1
138833.3	100268.5	1	127482	1

[ChrisNZ]

1. Why  7  in this line of code?

do i = 1 to 7

2. The problem you ignore, if I understand correctly, is that you need to remove customers as they are used.

If true, a hash table would serve you better than reading a static customer table.

[torestin]

hey thanks for that.

1) actually i am a bit lost about why I put the loop there in the first place now! but it's probably there to enable the leave statement...

2) what I was trying to do was actually to remove both the qualifying range and the customer from the respective sets. So it reads product 1 from the market set, picks out customer 1 from the customer set removes it, then move on to product 2, picks out customer 3, product 3/customer 2, etc. which iterates down the existing queue. I thought the hash table would only give me the match, or non-match - eg if customer 8 cannot find any matching product - but won't do the double elimination?

[ChrisNZ]

If you go through the products sequentially (SET statement) you don't need to remove them. just remove the customers from the hash table as you find a match when you iterate the hash table,

[torestin]

right...so this is how i thought hash would work: I need to insert a key/item into both set so they have something to match, and then I see if the condition is satisfied.

However, it now says pay is uninitiated so doesn't seem to have read the pay values into the hash table. Where did I go wrong?

Data market;
input control UB LB;
datalines;
1 137454.23 99272.50
1 127407.23 92016.34
1 134738.07 97310.83
1 118503.53 85585.88
1 117691.52 84999.43
1 126468.91 91338.66
1 138833.30 100268.50
;;;;
run;

data customers;
input control pay;
datalines;
1 117605
1 120194
1 114285
1 92316
1 125917
1 106480
1 94244
1 127482
1 94744
1 106371
1 122085
1 100327
1 107315
1 115530
1 116100
1 100279
1 94117
1 111069
1 98615
1 115879
1 124773
1 118694
1 111970
1 118629
1 129623
1 121400
1 100992
1 129743
1 93083
1 90643
;;;;
run;

Data M;

If _n_=1 then do;

Declare Hash m(dataset:"customers");

m.definekey('control');

m.definedata('pay');

m.definedone();
end;

Set market;
if m.find()=0 then do;

If LB<pay<UB then do;

Output;

m.remove();

end;
End;

Run;

[PeterClemmensen]

@torestin what does your desired result from this data look like? 

[torestin]

The desired result would look like this:

product                                           Customer pay            matching result

UB                      LB

137454.2             99272.5               117605                           137454.2             99272.5               117605

127407.2             92016.34             120194                           127407.2             92016.34             120194

134738.1             97310.83             114285                           134738.1             97310.83             114285

118503.5             85585.88             92316                             118503.5             85585.88             92316

117691.5             84999.43             125917                           117691.5             84999.43             106480

126468.9             91338.66             106480                          126468.9             91338.66             125917

138833.3             100268.5             94244                            138833.3             100268.5             94244

so that the fifth product is matched with the 6th customer, but the 5th customer (pay) 125917 remains in queue and picks up the 6th product, instead of being skipped altogether

[PeterClemmensen · Accepted solution]

@torestin I like the idea of using a hash object to implement this. You can do something like this

data want;
    format UB LB pay;
    keep   UB LB pay;
    if _N_=1 then do;
        declare hash h(ordered:'Y');
        h.definekey('k');
        h.definedata('k', 'pay');
        h.definedone();
        declare hiter hi('h');
    end;

    do k=1 by 1 until (lr1);
        set customers end=lr1;
        h.add();
    end;

    do until (lr2);
        set market end=lr2;

        do until (LB <= pay <= UB);
            rc=hi.next();
        end;

        output;

        _k=k;
        rc=hi.last();
        rc=hi.next();
        rc=h.remove(key: _k);
    end;
run;

Result:

UB        LB       pay
137454.23 99272.5  117605
127407.23 92016.34 120194
134738.07 97310.83 114285
118503.53 85585.88 92316
117691.52 84999.43 106480
126468.91 91338.66 125917
138833.3  100268.5 127482  

[PeterClemmensen]

@torestin did this work for you?

[torestin]

Hey thanks for that. Yup it works...the only snag is that it seems to get stuck with larger dataset, I was going to do some investigation before coming back. 

[PeterClemmensen]

When you say 'get stuck' what do you mean?

[torestin]

it took overnight to do a match (400 in products; 2000 pop) and never actually finished it and i had to stop it. Log showed it read both and then nothing. So I am not sure if it actually started execute the hash table. (I am also using the university edition so maybe some restrictions on that?)

[PeterClemmensen]

Investigating my code a bit deeper, I think a problem may arise if no customer satisfies the range being considered. This would send the code into an infinite loop. Consider the situation and the code below

Data market;
input UB LB;
datalines;
137454.23 99272.50
127407.23 92016.34
134738.07 97310.83
118503.53 85585.88
117691.52 84999.43
126468.91 91338.66
138833.30 100268.50
;;;;
run;

data customers;
input pay;
datalines;
117605
120194
114285
1
1
1
1
1
1
1
1
1
1
1
;;;;
run;

data want;
    format UB LB pay;
    keep   UB LB pay;
    if _N_=1 then do;
        declare hash h(ordered:'Y');
        h.definekey('k');
        h.definedata('k', 'pay');
        h.definedone();
        declare hiter hi('h');
    end;

    do k=1 by 1 until (lr1);
        set customers end=lr1;
        h.add();
    end;

    do until (lr2);
        set market end=lr2;

        do until (LB <= pay <= UB | rc ne 0);
            rc=hi.next();
        end;
        if rc=0 then do;
           output;
           _k=k;
           rc=hi.last();
           rc=hi.next();
           rc=h.remove(key: _k);
        end;
        else do;
           pay=.;
           output;
           rc=hi.last();
           rc=hi.next();       
        end;

    end;
run;

[ChrisNZ]

@PeterClemmensen

Can't test now, so maybe a silly question.

Why not

        if rc then pay=.;
        else h.remove();
        output;
        rc=hi.first();
  

[PeterClemmensen]

@ChrisNZ as I understand it, I can't use the Remove() Method, when the object is locked by an iterator?

Feel free to test my code and find a better way. There is definitely a better way. I'm learning about stacks and queues in SAS myself, so any thoughts are greatly appreciated. I mainly used @hashmans book on the topic. 

Btw, now that I tagged him, he will probably come around and write a better solution in 3 lines 😉  At least, I'll learn something...