Topic
  • 7 replies
  • Latest Post - ‏2014-04-15T13:12:00Z by qtbgo
qtbgo
qtbgo
116 Posts

Pinned topic how to reduce extract time?

‏2014-04-07T11:30:15Z |

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?

forall(<v, w, i, j> in P )  
    endBeforeStart(opt_z1[w][j], opt_z1[v][i],deltaTime[<v,w,i,j>]);  
  • ChrisBr
    ChrisBr
    41 Posts

    Re: how to reduce extract time?

    ‏2014-04-07T14:52:22Z  

    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.
     

  • qtbgo
    qtbgo
    116 Posts

    Re: how to reduce extract time?

    ‏2014-04-08T07:12:28Z  
    • ChrisBr
    • ‏2014-04-07T14:52:22Z

    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.
     

    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.

    Attachments

  • qtbgo
    qtbgo
    116 Posts

    Re: how to reduce extract time?

    ‏2014-04-09T11:37:59Z  
    • ChrisBr
    • ‏2014-04-07T14:52:22Z

    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.
     

    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?

     

  • ChrisBr
    ChrisBr
    41 Posts

    Re: how to reduce extract time?

    ‏2014-04-10T14:39:33Z  
    • qtbgo
    • ‏2014-04-09T11:37:59Z

    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?

     

    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.
     

  • qtbgo
    qtbgo
    116 Posts

    Re: how to reduce extract time?

    ‏2014-04-12T08:05:44Z  
    • ChrisBr
    • ‏2014-04-10T14:39:33Z

    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.
     

    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.

    forall(<v, w, i, j> in P )  
        endBeforeStart(opt_z1[w][j], opt_z1[v][i],deltaTime[<v,w,i,j>]);  

    Is there a more efficient way to model this?

     

     

    Updated on 2014-04-13T03:35:43Z at 2014-04-13T03:35:43Z by qtbgo
  • PhilippeLaborie
    PhilippeLaborie
    49 Posts

    Re: how to reduce extract time?

    ‏2014-04-14T11:59:36Z  
    • qtbgo
    • ‏2014-04-12T08:05:44Z

    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.

    forall(<v, w, i, j> in P )  
        endBeforeStart(opt_z1[w][j], opt_z1[v][i],deltaTime[<v,w,i,j>]);  

    Is there a more efficient way to model this?

     

     


    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

  • qtbgo
    qtbgo
    116 Posts

    Re: how to reduce extract time?

    ‏2014-04-15T13:12:00Z  


    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.

    <pre class="html dw" data-editor-lang="js" data-pbcklang="html" dir="ltr">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); } } } } </pre>


    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

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

    Thank you.