Proc LP Scheduling Problem

[deleted_user]

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

[deleted_user]

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

[deleted_user]

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)

[Matthew_Galati]

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}

[deleted_user]

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

[Matthew_Galati]

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

[deleted_user]

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

[deleted_user]

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

[Matthew_Galati]

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

[deleted_user]

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

Thanks

[deleted_user]

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

[Matthew_Galati]

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

[Matthew_Galati]

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.

[deleted_user]

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

[deleted_user]

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