PROC OPTMILP help

[DarthPathos]

I'm not entirely sure how I get myself into these situations........

I'm not a mathematician or a trained stats person - I'm a database guy that's sort of "fallen into" analysis and stats.  Having said that, I'm learning a lot through using SAS and hope this is something someone can walk me through....

I decided I wanted to "play" around with building a schedule in SAS, using a "real life" example of trying to schedule a patient for multiple tests based on the times they're available, the times that the test is free, and maximising the efficiency (as many tests on as few days as possible).

I've read the 9.3 Documentation on the OPTMILP Procedure, and I understood that - everything made 100% sense as far as assigning the variables, setting the constraints, etc.  And that's as far as I got.

Here's a few lines of test data I'm playing with:

DATA RAW;

INPUT TESTNAME $ TESTCODE  $ DAY  $ START $ END  $ LOCATION $ WEIGHT;

DATALINES;

GFR GFRK MON 14:40 15:50 A1385 2

GFR GFRH MON 11:30 11:58 A1386 3

ECH ECHO TUE 12:45 13:15 H0302 1

ECH ECHO TUE 13:50 14:20 H0306 1;

So my constraints would be:

1) Only 1 test at a time;

2) Minimum 10 minutes between tests if they are in different rooms;

3) Tests with the same weights in the same room take precedence over tests with the same weights in different rooms.

Obviously my data above will not really generate anything because it's not "realistic" given my constraints, but I'm just working on an example here.

The example that is given in the documentation has multiple people, and the constraints are different (ie number of hours worked, number of time slots worked, either slot 4 or 5 has to be a lunch, etc.) so I'm having trouble translating my data and limitations to something workable. 

I've really tried to dig into the documentation, looking for other examples, SAS user group papers etc. and I cannot find *anything* - if you know of any good documentation about this, please send it my way!

Thanks Chris

[Philipp_SAS]

Hello Chris,

Unfortunately writing mathematical optimization models for real world problems is an art and a science at the same time. Some people make a living as Operations Research consultants doing just that (SAS also offers OR consulting services).

So if you want to learn writing mathematical models it's not a bad idea to start with the examples in the OPTMODEL doc but for solving real world problems you will have to get some background on mixed integer programming and modelling. A possible starting point is the book "Model building in mathematical programming" by Paul Williams, but there are tons of other books out there as well. Once you have a mathematical description OPTMODEL makes it fairly easy to code this model up in SAS.

Regarding you constraints, just a few ideas from the top of my head:

1) You probably need some binary variables for your tests and sets for rooms and times. Then you would have one constraint for each time that says that the sum of the variables has to be at most 1.

2) If your time set has 5 minute increaments then you basically say that the variables for different rooms following each time have to be 0, if that variable is 1.

3) I don't quite understand that constraint but something along 1) and 2) should allow you to model it

There are a few SAS Global Forum papers about OPTMODEL out there. But there is a lot more about mathematical programming and operations research in general on the web, you might want to search for that.

I hope this helps

Philipp

[DarthPathos]

Hey Philipp,

That's what I thought - I seem to bite off a little more than I can chew when it comes to these things :smileylaugh:

As I mentioned this is just for fun, so I'm going to be putting this on the back burner for now....

As far as Constraint 3 goes, what I wanted was if you had an Echo in room 123 weighted 2 and an XRay in room 712 weighted 2, both of which were available in the time slot immediately after a stress test in room 123, then SAS would pick the Echo as the next test; the goal being to minimize travel time for the patients.

Thanks for your time, and I will check out the papers and the book you recommended!

have a great day and don't work too hard

Chris

[Ed_Hughes_sas]

Chris,

Since this is a scheduling problem you might want to check out PROC CLP in SAS/OR which has special features for scheduling problems and also can specify an objective function.  It utilizes finite domain constraint programming.  If you're seeking a feasible schedule then PROC CPM in SAS/OR can also help.  It uses critical-path based methods and has a rich set of features for specifying priorities and other attributes among activities.
I agree with Philipp that your third constraint class needs a more rigorous specification.

Ed

[DarthPathos]

Hi Ed - Thanks for the reply - would you be able to connect with me through email?  I would like to discuss this a little more with you.  You can get my email from my profile.

Thanks so much

Chris