Originally posted by: qtbgo

Hi, in the following constraints of my model, when I  increase the size of set P, it takes 30 minutes to extract the model. Is there any way to reduce this time?

Originally posted by: ChrisBr

Hello,

Could you provide us more information please?
When you write
   when I  increase the size of set P
What is the size of P in this case? What is this size when the extract time is OK?

Which OPL's version are you using?
Did you try to unset the presolve option?

Regards,

Chris.
 

Originally posted by: qtbgo

Hi, Chris, I use 12.6. Please see the attached model. If you set n to 100, it's OK.  But if you set n to, for example, 1500, then it cannot extract the model in 10 minutes.

I tried disable presolve, but no effect.

Originally posted by: qtbgo

It seems that the time is spent on loading the big set P.

So, I guess it will be better to code <i,j,v,w> into a single number, and uncode it when needed.

In my model, i ,j in 1..5000, v,w in 1..99. My coding solution is 

i*10^8 +j*10^4+v*10^2+w

But it seems too big a number and may exceed the maxint in OPL. Could anyone suggest a better coding solution?

Originally posted by: ChrisBr

Hello,

I don't think that the set's construction is guilty.
But you are trying to set a big number of constraints! Which is costly in time and memory.
You wrote
   "In my model, i ,j in 1..5000, v,w in 1..99"
and following your set's definition
    P = {<v,w,i,j> | v, w in 1..nQC, i, j in 1..n : v < w && i > j};
This gives a cardinality > 6e10 which is ... a lot!
Do you really want to set such a big number of constraints? Or is it possible that the set is more sparse?

By the way, it seems that setting precedence-constraints using such a way for a large number of interval-vars might not to be very effective.

Would you like to expose your problem? We could think to another way to write your model.

Regards,

Chris.
 

Originally posted by: qtbgo

Chris, I have simplified the problem.

In fact, this is a scheduling problem in container terminal. n is the number of containers,  it may reach 3000. nQC is the number of quay cranes, it may reach 20.

 This constraint is used for that the quay cranes should  not cross over each other.

 P = {<v,w,i,j> | v, w in 1..nQC, i, j in 1..n : v < w && l[i] > l[j] - 2 * (w-v)};

where l[i], l[j] is the bay of container i on the ship.

Is there a more efficient way to model this?

Originally posted by: PhilippeLaborie

Hello,
You could think of a model with state functions.

For each quay crane v in 1..nQC, you define a state function position[v] that models the position of the crane over time. In OPL:

stateFunction position[v in 1..nQC];

Then for an interval variable requiring a crane v to work at a bay location l[i] for a job i, you can post:
- a constraint alwaysEqual(position[v], opt[i][v], l[i]) stating that crane v is at position l[i]
- a set of constraint for the cranes w that are at the left hand side of crane v (w<v) stating that these cranes w cannot be at a position greater than l[i] (this can be adjusted with v-w to account for the necessary cranes in between w and v, and symmetrically
- a set of constraint for the cranes w that are at the right hand side of crane v (w>v) stating that these cranes w cannot be at a position lower than l[i] (this can be adjusted with w-v to account for the necessary cranes in between v and w

Here is a small example for illustration. I added a cumul function mainly to visualize the global use of quay cranes, but this constraint can also be useful for the search as a redundant constraint.

using CP;

int n     = 100;
int nQC   = 7;
int nBays = 50;

int p[i in 1..n] = 1+rand(100);
int l[i in 1..n] = 1+rand(nBays);

int horizon = n*100;

dvar interval task[i in 1..n] in 0..horizon size p[i];
dvar interval opt [i in 1..n][v in 1..nQC] optional;

stateFunction position[v in 1..nQC];
cumulFunction cumulQC = sum(i in 1..n) pulse(task[i],1);

minimize  max(i in 1..n) endOf(task[i]);

subject to {
  forall (i in 1..n) {
    alternative(task[i], all(v in 1..nQC) opt[i][v]);
  }
  forall(v in 1..nQC) {
    noOverlap(all(i in 1..n) opt[i][v]);  
  }
  cumulQC <= nQC; // Redundant
  forall(i in 1..n, v in 1..nQC) {
    alwaysEqual(position[v], opt[i][v], l[i]);
    if ((l[i]<v) || (nBays-l[i]<nQC-v)) {
      // Unreachable position for crane v        
      !presenceOf(opt[i][v]); 
    } else {
        forall(w in 1..nQC : w<v) { 
              // Quay cranes at rank w on the left of v cannot be working at a bay > l[i]-v+w
              alwaysIn(position[w], opt[i][v], 1, l[i]-v+w);        
            }
            forall(w in 1..nQC : w>v) { 
              // Quay cranes at rank w on the right of v cannot be working at a bay < l[i]-v+w
              alwaysIn(position[w], opt[i][v], l[i]-v+w, nBays);    
            }
     }
  }
}

Two additional remarks:

1- State functions also support transition times so that can be useful if you want to model a transition time for the crane to move from one bay to another.

2- The above model implicitly assumes that while the quay cranes are not working, they can be moved to let some other cranes access other bays. If this is not allowed, you should think of adding additional interval variables that really represent the intervals of time a given crane occupies a given bay location. Working interval variables will be included inside these bay occupation intervals.

 Philippe

Originally posted by: qtbgo

Dear Philippe, Your solution is very interesting. My initial test show that the performance has been improved greatly.

Thank you.