Topic
  • 10 replies
  • Latest Post - ‏2012-10-15T08:05:10Z by SystemAdmin
qtbgo
qtbgo
134 Posts

Pinned topic how to refomulate this meta-constraint to direct consraint?

‏2012-10-12T01:05:16Z |
Hi,I have the folloeing meta-constraint

forall(i,j in 1..n : i!=j) startOf(qtasks[j])>=endOf(qtasks[i]) => startOf(qtasks[j]) >= startOf(ytasks[i]) + 10;


In order to improve performance, I want to transform it to direct constraint using endBeforeStart,for example. I tried several times, but failed.

Could some tell me how to achieve it?

Thanks
Updated on 2012-10-15T08:05:10Z at 2012-10-15T08:05:10Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    623 Posts

    Re: how to refomulate this meta-constraint to direct consraint?

    ‏2012-10-12T07:12:46Z  
    Hello.

    Indeed, it is not possible to use constraint endBeforeStart in a metaconstraint.

    It seems to me that in some cases it could be modeled using noOverlap constraint with transition distance. It depends on what exactly do you want to achieve by this constraint. Could qtasks overlap? Is ytasks a typo? Could you describe a little bit more the scheduling problem?

    Best regards, Petr
  • qtbgo
    qtbgo
    134 Posts

    Re: how to refomulate this meta-constraint to direct consraint?

    ‏2012-10-12T08:51:50Z  
    Hello.

    Indeed, it is not possible to use constraint endBeforeStart in a metaconstraint.

    It seems to me that in some cases it could be modeled using noOverlap constraint with transition distance. It depends on what exactly do you want to achieve by this constraint. Could qtasks overlap? Is ytasks a typo? Could you describe a little bit more the scheduling problem?

    Best regards, Petr
    Thank you for your reponse. I am not good at English. But I'll try to make it clear.

    First, There is no typo. ytasks and qtasks are different. They are related by this constraint.

    They are all noOverlaped(I have implement this).

    There is only one quay crane to unload containers from ship to some trucks.
    qtasks is for the quay crane, ytasks for trucks. (Of course I also have
    
    ytruckTasks[i][j]
    
    )

    I have built a model, this constraint is from the model. and I want to change this constraint to direct constraint for better performance.

    hope you can understand me.
  • SystemAdmin
    SystemAdmin
    623 Posts

    Re: how to refomulate this meta-constraint to direct consraint?

    ‏2012-10-12T11:54:13Z  
    • qtbgo
    • ‏2012-10-12T08:51:50Z
    Thank you for your reponse. I am not good at English. But I'll try to make it clear.

    First, There is no typo. ytasks and qtasks are different. They are related by this constraint.

    They are all noOverlaped(I have implement this).

    There is only one quay crane to unload containers from ship to some trucks.
    qtasks is for the quay crane, ytasks for trucks. (Of course I also have <pre class="jive-pre"> ytruckTasks[i][j] </pre> )

    I have built a model, this constraint is from the model. and I want to change this constraint to direct constraint for better performance.

    hope you can understand me.
    In this case, I think that it could be modeled using startOfNext function.
    From what I understand, there is noOverlap on qtasks. In order to use startOfNext, there also have to be sequence variable qtasks:
    
    dvar sequence quayCrane in all (i in 1..n) qtasks[i]; ... subject to 
    { noOverlap(quayCrane); ... forall (i in 1..n) startOf(ytasks[i]) + 10 <= startOfNext(quayCrane, ytasks[i], 1000000); ...
    

    The expression startOfNext above returns start of the immediate successor on ytasks[i] on quayCrane. If ytasks[i] is the last task on quayCrane then the expression returns 1000000. You may need to adjust the value 1000000 to something what makes sense for your data. This model should improve the propagation especially if ytasks cause delays between qtasks.

    Let me know if I didn't understand your problem right.

    Best regards, Petr
  • SystemAdmin
    SystemAdmin
    623 Posts

    Re: how to refomulate this meta-constraint to direct consraint?

    ‏2012-10-12T12:08:18Z  
    In this case, I think that it could be modeled using startOfNext function.
    From what I understand, there is noOverlap on qtasks. In order to use startOfNext, there also have to be sequence variable qtasks:
    <pre class="jive-pre"> dvar sequence quayCrane in all (i in 1..n) qtasks[i]; ... subject to { noOverlap(quayCrane); ... forall (i in 1..n) startOf(ytasks[i]) + 10 <= startOfNext(quayCrane, ytasks[i], 1000000); ... </pre>
    The expression startOfNext above returns start of the immediate successor on ytasks[i] on quayCrane. If ytasks[i] is the last task on quayCrane then the expression returns 1000000. You may need to adjust the value 1000000 to something what makes sense for your data. This model should improve the propagation especially if ytasks cause delays between qtasks.

    Let me know if I didn't understand your problem right.

    Best regards, Petr
    I just noticed I made a mistake and exchanged ytasks for qtasks inside startOfNext. It should be:
    
    startOf(ytasks[i]) + 10 <= startOfNext(quayCrane, qtasks[i], 1000000);
    

    It also applies to the explanation:
    The expression startOfNext above returns start of the immediate successor of qtasks[i] on quayCrane. If qtasks[i] is the last task on quayCrane then the expression returns 1000000.

    I'm sorry about that.

    Petr
  • qtbgo
    qtbgo
    134 Posts

    Re: how to refomulate this meta-constraint to direct consraint?

    ‏2012-10-12T13:08:12Z  
    I just noticed I made a mistake and exchanged ytasks for qtasks inside startOfNext. It should be:
    <pre class="jive-pre"> startOf(ytasks[i]) + 10 <= startOfNext(quayCrane, qtasks[i], 1000000); </pre>
    It also applies to the explanation:
    The expression startOfNext above returns start of the immediate successor of qtasks[i] on quayCrane. If qtasks[i] is the last task on quayCrane then the expression returns 1000000.

    I'm sorry about that.

    Petr
    It's great. The performance have been improved greatly.
    Thank you, Petr.
  • qtbgo
    qtbgo
    134 Posts

    Re: how to refomulate this meta-constraint to direct consraint?

    ‏2012-10-12T23:00:42Z  
    I just noticed I made a mistake and exchanged ytasks for qtasks inside startOfNext. It should be:
    <pre class="jive-pre"> startOf(ytasks[i]) + 10 <= startOfNext(quayCrane, qtasks[i], 1000000); </pre>
    It also applies to the explanation:
    The expression startOfNext above returns start of the immediate successor of qtasks[i] on quayCrane. If qtasks[i] is the last task on quayCrane then the expression returns 1000000.

    I'm sorry about that.

    Petr
    Dear Petr, is it possibble to improve the following constraint?
    
    forall(i, j in  1..n: i !=j) 
    { (qcranediff[i][j] > maxl(0, (l[j]-l[i]) div (s+1))) => endOf(tasks[j]) +  delta[i][j]*t <= startOf(tasks[i]) || endOf(tasks[i]) + delta[i][j]*t <= startOf(tasks[j])  ; 
    }
    

    Multiple quay cranes unload containers.
    Here,
    tasks[i]:Task of unloading container i.
    l[i]: bay number of container i.
    qcranediff[i][j] id defined by

    
    
    // Crane number allocated to task i dvar 
    
    int qcrane[i in 1..n] in 1..q; dexpr 
    
    int qcranediff[i in 1..n][j in 1..n] = qcrane[j]-qcrane[i];
    

    others are constant.
  • SystemAdmin
    SystemAdmin
    623 Posts

    Re: how to refomulate this meta-constraint to direct consraint?

    ‏2012-10-13T09:28:56Z  
    • qtbgo
    • ‏2012-10-12T23:00:42Z
    Dear Petr, is it possibble to improve the following constraint?
    <pre class="jive-pre"> forall(i, j in 1..n: i !=j) { (qcranediff[i][j] > maxl(0, (l[j]-l[i]) div (s+1))) => endOf(tasks[j]) + delta[i][j]*t <= startOf(tasks[i]) || endOf(tasks[i]) + delta[i][j]*t <= startOf(tasks[j]) ; } </pre>
    Multiple quay cranes unload containers.
    Here,
    tasks[i]:Task of unloading container i.
    l[i]: bay number of container i.
    qcranediff[i][j] id defined by

    <pre class="jive-pre"> // Crane number allocated to task i dvar int qcrane[i in 1..n] in 1..q; dexpr int qcranediff[i in 1..n][j in 1..n] = qcrane[j]-qcrane[i]; </pre>
    others are constant.
    Hello.

    Again, I would need a bit more information. The following:
    
    l[i] s t delta[i][j]
    

    are constants?

    What is qcrane[i], is it a crane chosen for task i? Can tasks[i] overlap?

    It seems to me that typeOfNext could help. Also, notion of optional interval variables and alternatives may be useful.

    Best regards, Petr
  • qtbgo
    qtbgo
    134 Posts

    Re: how to refomulate this meta-constraint to direct consraint?

    ‏2012-10-13T09:43:46Z  
    Hello.

    Again, I would need a bit more information. The following:
    <pre class="jive-pre"> l[i] s t delta[i][j] </pre>
    are constants?

    What is qcrane[i], is it a crane chosen for task i? Can tasks[i] overlap?

    It seems to me that typeOfNext could help. Also, notion of optional interval variables and alternatives may be useful.

    Best regards, Petr
    Thank you Petr.
    Yes, qcrane[i] is a crane chosen for task i.
    
    l[i] s t delta[i][j]
    

    are all constants.
    tasks[i] can overlap.
  • qtbgo
    qtbgo
    134 Posts

    Re: how to refomulate this meta-constraint to direct consraint?

    ‏2012-10-13T09:50:01Z  
    Hello.

    Again, I would need a bit more information. The following:
    <pre class="jive-pre"> l[i] s t delta[i][j] </pre>
    are constants?

    What is qcrane[i], is it a crane chosen for task i? Can tasks[i] overlap?

    It seems to me that typeOfNext could help. Also, notion of optional interval variables and alternatives may be useful.

    Best regards, Petr
    And I have used optional interval variables and alternatives elsewhere in the model, for example
    
    forall(i in 1..n) alternative(tasks[i], all(k in 1..q ) qcTasks[k][i]);  
    //quay assignment
    


    For now, I just wonder if the flolowing constraint can be improved
    
    forall(i, j in  1..n: i !=j) 
    { (qcranediff[i][j] > maxl(0, (l[j]-l[i]) div (s+1))) => endOf(tasks[j]) +  delta[i][j]*t <= startOf(tasks[i]) || endOf(tasks[i]) + delta[i][j]*t <= startOf(tasks[j])  ; 
    }
    
  • SystemAdmin
    SystemAdmin
    623 Posts

    Re: how to refomulate this meta-constraint to direct consraint?

    ‏2012-10-15T08:05:10Z  
    • qtbgo
    • ‏2012-10-13T09:50:01Z
    And I have used optional interval variables and alternatives elsewhere in the model, for example <pre class="jive-pre"> forall(i in 1..n) alternative(tasks[i], all(k in 1..q ) qcTasks[k][i]); //quay assignment </pre>

    For now, I just wonder if the flolowing constraint can be improved
    <pre class="jive-pre"> forall(i, j in 1..n: i !=j) { (qcranediff[i][j] > maxl(0, (l[j]-l[i]) div (s+1))) => endOf(tasks[j]) + delta[i][j]*t <= startOf(tasks[i]) || endOf(tasks[i]) + delta[i][j]*t <= startOf(tasks[j]) ; } </pre>
    I'm afraid that there is no equivalent constraint in CP Optimizer. However I still do not understand what exactly the constraint means. Maybe the constraint can be replaced by something what is not equivalent but achieves the desired result.

    Let's forget the math for a while. What the constraint means? From what I understand, if two cranes are working on two different tasks and they are "far enough" then there must be certain minimum delay between them. But why? Is there another resource(s) in play? Cannot the constraint be reformulated using state functions for cranes I mentioned in another post?

    Best regards, Petr