Hey there,

I'm writing on a CP-model for a timetabling-problem. I have to schedule events for classes in a given time-interval. Each event needs resources like a chemie-lab or driving range. It is possible to 'overbook' a resource. For example: in a time-slot 3 events need resource A, but only 2 are available. The objective-function is to minimize the overbooking.

Now I've got:

    forall(s in timeslots){
    forall(r in resources){
         sum(e in events: r in requirement[e]) 
         ((s.start>=startOf(itvs[e]) && s.end<=endOf(itvs[e]) && resourceassignment[e][r] == 1)? requirementNb[e] : 0 )
         resourcesNb[r] + conflict[s,r];

This produces way too much constraints. Since itvs[e] and resourceassignment[e][r] are decision variables, I can't use them in a if-clause. In the worst-case I get card(timeslots) x card(resources) x card(events) x 4 constraints. The consequence is, that an instance with 200 events can't be handled by OPL and I get a 'not enough memory'-error.

Do you have any ideas how I could fix this?

Many thanks, André

asked 06 Apr '13, 07:47

andrep's gravatar image

accept rate: 0%

edited 26 Jul '13, 12:20

fbahr's gravatar image

fbahr ♦

You should use cumulative functions in OPL. Set one such cumulative function per resource. This cumulative function will perform the role of the sum over events and requirements in your code snippet, albeit much more efficiently.


answered 06 Apr '13, 08:28

jfpuget's gravatar image

accept rate: 8%

I tried cumulative functions, but I've got two problems.

  1. I've a set of resources for the events, so I would need a request like
 resourceUsage[r in resources] = sum(e in events: r in requirement[e] && resourceassignment[e][r] == 1) pulse(interval[e], requirementNb[e]);

but that's not working, 'cause resourceassignment is a decision variable. Any suggestions?

(09 Apr '13, 07:59) andrep

You should have a look at the scheduling models provided with OPL. Your events should be represented by interval variables on which you apply cumulative functions.

(10 Apr '13, 06:49) jfpuget

I've done that and my events are interval variables. But you're right. With the cumulative functions it is possible to reduce the used memory, but I have to change my objective function.

(10 Apr '13, 11:57) andrep
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 06 Apr '13, 07:47

Seen: 1,928 times

Last updated: 26 Jul '13, 12:20

OR-Exchange! Your site for questions, answers, and announcements about operations research.