topic Re: Proc LP Scheduling Problem in Mathematical Optimization, Discrete-Event Simulation, and OR

Proc LP Scheduling Problem

deleted_user — Sun, 15 Jul 2007 02:05:38 GMT

Hello Sir,
I am currently trying to solve an optimization problem which is very similar to the LP Scheduling problem described in the SAS/OR document. Please refer the link below to see the problem.
http://www.caspur.it/risorse/softappl/doc/sas_docs/ormp/chap3/sect58.htm

I want to add another constraint which I have formulated and explained below, but I don't know how to code this in sparse data format.
For Ex: Let say the Maximum number of slots worked is 8 hours on Monday and minimum is 2 hours on Friday and I want to add a constraint such that the difference between minimum and maximum is 50% , so in this case the optimization will try to either increase slots on Friday or decrease it on Monday.

Here is the mathematical formulation of the above constraint:
Min (Σi Xk for all K) <= 0.5* Max (Σi Xk for all K)
where i denote person and K denote day

Any help is greatly appreicated.

Thanks
Ayush

Re: Proc LP Scheduling Problem

deleted_user — Sun, 15 Jul 2007 02:06:54 GMT

Oops I couldn't see the mathematical formulation, sending you the formulation again.
Here is the mathematical formulation of the above constraint:
Min (Σi Xk for all K) <= 0.5* Max (Σi Xk for all K)
where i denote person and K denote day

Re: Proc LP Scheduling Problem

deleted_user — Sun, 15 Jul 2007 02:14:40 GMT

Sorry , Again I was not able to view the mathematical equation so I am writing the formulation in plain english:
Minimum number of slots in 5 days should be less than 50% of maximum number of slots worked in 5 days

Min (Σi Xk for all K) LE 0.5* Max (Σi Xk for all K)

Re: Proc LP Scheduling Problem

Matthew_Galati — Sun, 15 Jul 2007 03:55:21 GMT

Do you want one of these constraints for each employee? Or, do you want the overall assignment across employees and slots?

Also, I assume you are trying to balance the workload across days? In the example you gave, the min=2, max=8. But the constraint you have below will be true for this case (2 >= 0.5 * 8 = 4). In addition, the case min=2, max=2 will be violated by this constraint. Do you mean GE, rather than LE?

min{ sum_{j} x[i,j,k], for all k} >= 0.5 max { sum_{j} x[i,j,k], for all k}, for all i
or
min{ sum_{i,j} x[i,j,k], for all k} >= 0.5 max { sum_{i,j} x[i,j,k], for all k}

Re: Proc LP Scheduling Problem

deleted_user — Sun, 15 Jul 2007 14:45:56 GMT

Hello Mathew,
I greatly appreciate your response. As said in my previous message that my problem is very similar to the scheduling problem but it differs in some respect. So in this case I am just looking at employee’s distribution across days and I would like to apply constraint for overall assignment of employee’s across days.
EX: Let say on Monday total number of hours worked by employees is 8 and on Friday it is 2. The constraint which I am trying to formulate should solve optimization problem by balancing the workload within some percentage (In my example I have assumed the variation to be 50%).
Here is my new constraint formulation:
I agree that my previous formulation should have GE or GT instead of LE or LT.

min{ sum_{i} x[i,k], for all k} GT 0.5 max { sum_{i} x[i,k], for all k}

The only difference between your formulation and mine is I am adjusting the workload for person and not taking into account the slots (j variable).

Once again I greatly appreciate your help and support.
Thanks

Re: Proc LP Scheduling Problem

Matthew_Galati — Sun, 15 Jul 2007 15:08:04 GMT

Ok, I can probably help.

Given I do not have your model, I will try to explain in the context of the original example. Therefore, your constraint would look like:
min{ sum_{i,j} x[i,j,k], for all k} >= 0.5 max { sum_{i,j} x[i,j,k], for all k}

What version of SAS/OR are you using? If you have version SAS 9.1.3, Release 3.1, then you might want to switch to using the new modeling language OPTMODEL. It is much better than the old style for manipulating model formulations. And, the new solvers have better performance than the older ones.

In fact, the scheduling example you mention has been converted to OPTMODEL here:
http://support.sas.com/onlinedoc/913/docMainpage.jsp
http://support.sas.com/onlinedoc/913/getDoc/en/ormpug.hlp/milpsolver_sect15.htm

Have a look. Let me know if you want help using the old style (PROC LP) or the new style (OPTMODEL).

Thanks,
Matt

Re: Proc LP Scheduling Problem

deleted_user — Sun, 15 Jul 2007 15:15:04 GMT

Matt,
Thanks again for your response. I am currently using SAS V8 and I will greatly appreciate if you can help me in explaining the steps used in Proc LP.

Once again thank you very much for your time and support.

Ayush

Re: Proc LP Scheduling Problem

deleted_user — Sun, 15 Jul 2007 16:38:23 GMT

Matt,
I am asking your help to build LP problem since I have spent a lot of time in developing and coding other constraints of my model and also I don't have Version 9.1.3 with me.

But one thing I would like to mention about LP problem is, albeit the LP formulation is hard to code but it give a very good understanding of the problem and since Optmodel is higher version of LP model, it won't be hard for me to implement the same problem using Optmodel procedure.

Also a quick question, when you mentioned in your earlier email that Optmodel has a good solver than LP procedure, do you mean that it is better in terms of accuracy,processing time etc ? Can you please mention pros and cons of using Optmodel vs. LP procedure?

Thanks

Re: Proc LP Scheduling Problem

Matthew_Galati — Sun, 15 Jul 2007 17:14:23 GMT

Ok - I will work on both the PROC OPTMODEL and PROC LP versions when I have some free time tomorrow. Then you can see how each works.

The new OPT* procedures in 9.1.3 have significant enhancements to the underlying algorithms. OPTMODEL has access to each of these solvers through the modeling language. So, if you run OPTMODEL, you are using the new solvers. In particular, PROC LP is being phased out by OPTLP (for linear programming) and OPTMILP (for linear integer programming). You should see a significant improvement in processing time for most LPs and MILPs. Also, we now provide a conversion program to go from the old PROC LP format directly to OPTLP and OPTMILP. This will ease the transition to the new solvers.
http://support.sas.com/samples_app/01/sample01730_1_lp2mpsd.sas.txt

And here is a little more info about OPTMODEL:
http://support.sas.com/rnd/app/or/mp/MPToolsN.html#OPTMODEL

Re: Proc LP Scheduling Problem

deleted_user — Sun, 15 Jul 2007 18:45:38 GMT

Matt,
I greatly appreciate for your time and support and I look forward to hear from you soon.

Thanks

Re: Proc LP Scheduling Problem

deleted_user — Tue, 17 Jul 2007 23:24:56 GMT

Hello Matt,
I was wondering if you had a time to look at the problem mentioned in my earlier email.

I greatly appreciate for all the help and support you have been providing me and look forward to hear from you soon.

Thanks

Re: Proc LP Scheduling Problem

Matthew_Galati — Wed, 18 Jul 2007 00:33:11 GMT

Sorry - I've been very busy. I will post something tomorrow.

Re: Proc LP Scheduling Problem

Matthew_Galati — Wed, 18 Jul 2007 16:36:32 GMT

I've attached the adjusted documentation example code.

Since I am unable to post formatted SAS code to this message box, please refer to the attachment.

To enforce a constraint like this, min{ sum_{i,j} x[i,j,k], for all k} >= 0.5 max { sum_{i,j} x[i,j,k], for all k}, using a linear programming formulation, you will need to add 2 new variables to the problem which will define the min (MinSlots) and max (MaxSlots) number of slots assigned.

Then, you will need constraints to enforce this relationship. For the min, just make sure the sum across assignments is always greater than MinSlots (con MinSlotDef). For the max, the sum should always be less than MaxSlots (con MaxSlotDef).

After this, enforcing your new constraint is easy. Just make MinSlots >= 0.5 * MaxSlots (con MinMaxDiffLimit).

So, for doing this in PROC LP, you need to simply introduce 2 new variables and 3 new constraints using the sparse data format. This can be done in the normal manner.

Re: Proc LP Scheduling Problem

deleted_user — Wed, 18 Jul 2007 23:35:59 GMT

Matt,
I greatly appreciate for your help and interest. Since the code is written for Optmodel procedure so it will take me a while to implement it in Proc LP.

I will keep you posted about how it works in LP proc.

Once again thank you so much for your help and support.

Thanks

Re: Proc LP Scheduling Problem

deleted_user — Thu, 19 Jul 2007 02:11:40 GMT

Matt,
Just one more question:
Following is my presentation of data after applying my constraint (not the constraint which you have suggested, as I am still unsuccessful in applying that one).

My Constraint: Person can only work in one of the five weekdays ( for ex :X denotes the assignment from LP problem )
Name Mon Tue Wed Thu Fri
N1 X
N2 x
N3 X
N4 X
N5 X
N6 X
N7 X
N8 X

and so on.. I would like to balance the allocation between days (Min and Max) to be within some percentage.

Now as per your suggestion , I have to create Maxslots and Minslots variable and use those variables into three constraints mentioned in your message.
I am stuck at this step as how to define my MAXSLOTS and MINSLOTS variable and how to code them in sparse data format.

/* max number of slots */
var MaxSlots >= 0 <= NSlots;
/* min number of slots */
var MinSlots >= 0 <= NSlots;

What would be NSLOTS in my problem above?

I will greatly appreciate if you can help me in explaining the LP sparse data format to my problem above.

Once again thank you very much for your time and interest.

Thanks

Re: Proc LP Scheduling Problem

deleted_user — Thu, 19 Jul 2007 02:13:44 GMT

Previous assignment was not aligned properly:

Name Mon Tue Wed Thu Fri
N1 ......X
N2 ..............X
N3 ......X
N4 .................................X
N5 ......X
N6 ......X
N7 ..................................X
N8 ......X

Re: Proc LP Scheduling Problem

deleted_user — Thu, 19 Jul 2007 17:00:13 GMT

Matt,
for some reasons this forum doesn't allow me to type certain characters so I am sending you my question again.
How do I identify Nslots in my problem? for ex if there are N person and d days then whether Nslots will be N or a permutation and combination of N AN D?
2) Let say I assume Nslots to be a constant for all the weekdays, so how can I write the following equation in sparse format( I got an error while running LP proc)
Var MAXslots >=0 <= Nslots
Var MinSlots >= 0 <= Nslots
3) Also when writing the constraint , is Minslots same for all days or is it different for each day Ex:When you wrote condition Sum(Person Slot) for all weekdays >= Minslots, whether this condition should be for Minslots(D) (weekdays ) ? Can you also explain me how to implement this in sparse format?

Re: Proc LP Scheduling Problem

Cynthia_sas — Thu, 19 Jul 2007 22:03:36 GMT

if you want to type the less-than character, type &-lt-; -- that's ampersand-LT-semi-colon -- but type without the dashes:
[pre]
<
&-lt-; produced the above less than sign (without the dashes in the string)

>
&-gt-; produced the greater than sign (without the dashes in the string)
[/pre]

In order to have your program code line up correctly, type
[pre]
[-pre-] (no dashes in the string)
square bracket pre square bracket at the beginning of code and

square bracket /pre square bracket at the end of the code
[-/pre-] (no dashes in the string)

** Notice how this code is in a "preformatted" font;
proc whatever data=mydata;
run;

[/pre]
by square bracket, I mean the [ character at the beginning of pre and the ] as the square bracket after the pre.

cynthia

Re: Proc LP Scheduling Problem

deleted_user — Thu, 19 Jul 2007 23:45:20 GMT

Cynthia,
Thanks for your message !! It really helped me a lot ..

Is there any way to upload my data to this forum so that Matt and other people can easily understand my probem.

For All : I am really sorry for my previous messages which might have created confusion because of lot of typos in it.

Matt: Below is the code which I am writing in the data model step,please help me in resolving this problem in Lp procedure

[pre]

DATA Model;
set raw end=eof; /* My Raw data is slightly in different format */
length _row_ $ 20 _col_ $ 16 _type_ $ 8;
keep _type_ _col_ _row_ _coef_;
/*objective function and other constraints are not written here */

/* Below is the code which I am trying to incorporate in my model data */
if eof then do;
_row_='Maxslots';
_type_='ge';
_col_='_RHS_';
_coef_=0;
output;
_row_='Maxslots';
_type_='Le';
_col_='_RHS_';
_coef_=1965; /* Nslots = 1965 I have assumed this to be equal to number of person (N)*/
output;
_row_='MINslots';
_type_='ge';
_col_='_RHS_';
_coef_=0;
output;
_row_='MINslots';
_type_='Le';
_col_='_RHS_';
_coef_=1965; /*NSlots = 1965*/
output;
end;

run;

[/pre]

Re: Proc LP Scheduling Problem

deleted_user — Mon, 23 Jul 2007 01:28:08 GMT

Matt,
Finally, I was able to write code and run proc LP optimization problem. Thanks for all your help.

Even though the optimization ran smoothly I have encountered some of the issues while running it and I was not sure if those issues were caused due to LP proc or because of my constraints formulation , So I thought I will post my issues on this forum to get some feedback from all of the group.

1) One of my constraints checks condition where X GE O.5 Y and though the optimization problem gave me expected result but I think it took lot of iterations to converge. My hypothesis is that it might be caused because of numerical precision as 0.49999999999999999999999 and 0.5 are different when SAS is making arithmetic calculations. Do you think the same way?

2) I started with 1989 unique observations and end up with 1994 unique observations. Is this happening because of rounding error?
Please advice.