Hi, I'm developing a Constraint Programming (CP) model for a simple scheduling problem.

I decided to develop my model in IBM Ilog CPLEX Optimization Studio. I defined my both interval and sequence variables as follows:

dvar interval INTERVALS[i in machines][j in jobs] size PROCESS[i][j];

dvar sequence MACHINES[i in machines] in all(j in jobs) INTERVALS[i][j];

Here is my question: Can I access the position of interval variables (INTERVALS) in the sequence variable (MACHINES) during the optimization process?

asked 19 Feb '16, 01:41

monash's gravatar image

monash
372411
accept rate: 0%

edited 19 Feb '16, 01:42


Hello, There is no "direct" way to get this expression in CP Optimizer. One of the reasons why this expression is not provided is that, often (but not always) there are other more efficient ways to model the problem without them. So my first question is, why do you need this positional variable for ? This being said, there are several ways to get these variables in an indirect way. For instance, you could duplicate the sequence and the interval variables on the sequence so as to have a sequence variable with only unit length intervals. If you use "sameSequence" constraint between the two sequences, the position is given by the start value of the intervals on the "position" sequence. It is probably more clear with a pseudocode:

dvar interval INTERVALS[j in jobs] size ...;
dvar interval UNITDURATION[j in jobs] in 0..n size 1;
dvar int POSITION[j in jobs] in -1..n; // POSITION=-1 for absent intervals

dvar interval MACHINE in (j in jobs) INTERVALS[j];        // Real sequence
dvar interval MACHINE_POS in (j in jobs) UNITDURATION[j]; // Positional sequence

// Constraints:

noOverlap(MACHINE);
noOverlap(MACHINE_POS);
sameSequence(MACHINE,MACHINE_POS);
forall(j in jobs) {
  POSITION[j] == startOf(UNITDURATION[j],-1);
}

You may want to avoid the interval variables UNITDURATION to mess up with the search (they are not real decision variables) so you can either use search phases (fix INTERVALS first) or translate the intervals UNITDURATION[j] to the left with a big H value:

dvar interval UNITDURATION[j in jobs] in H..H+n size 1;
...
forall(j in jobs) {
  POSITION[j] == H - startOf(UNITDURATION[j],-1);
}

You can also consider using the "isomorphism" constraint (see delivered example sched_learningeffect).

But it would be good to know what you need these positional variables for because there may be more direct models.

Philippe

link

answered 19 Feb '16, 07:55

Philippe%20Laborie's gravatar image

Philippe Lab...
623
accept rate: 9%

Many thanks @philippe-laborie. Actually, my initial purpose was to sort an array of interval variables based on their "end" property. Have you any solution for this?

(19 Feb '16, 12:08) monash

@philippe-laborie: I tested your solution but it seems it doesn't work!

(24 Feb '16, 00:59) monash
Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

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

Tags:

×191
×37
×29
×2
×2

Asked: 19 Feb '16, 01:41

Seen: 1,149 times

Last updated: 24 Feb '16, 00:59

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