Topic
IC4NOTICE: developerWorks Community will be offline May 29-30, 2015 while we upgrade to the latest version of IBM Connections. For more information, read our upgrade FAQ.
10 replies Latest Post - ‏2012-10-15T08:05:10Z by SystemAdmin
qtbgo
qtbgo
116 Posts
ACCEPTED ANSWER

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
    ACCEPTED ANSWER

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

    ‏2012-10-12T07:12:46Z  in response to qtbgo
    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
      116 Posts
      ACCEPTED ANSWER

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

      ‏2012-10-12T08:51:50Z  in response to SystemAdmin
      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
        ACCEPTED ANSWER

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

        ‏2012-10-12T11:54:13Z  in response to qtbgo
        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
          ACCEPTED ANSWER

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

          ‏2012-10-12T12:08:18Z  in response to SystemAdmin
          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
            116 Posts
            ACCEPTED ANSWER

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

            ‏2012-10-12T13:08:12Z  in response to SystemAdmin
            It's great. The performance have been improved greatly.
            Thank you, Petr.
          • qtbgo
            qtbgo
            116 Posts
            ACCEPTED ANSWER

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

            ‏2012-10-12T23:00:42Z  in response to SystemAdmin
            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
              ACCEPTED ANSWER

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

              ‏2012-10-13T09:28:56Z  in response to qtbgo
              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
                116 Posts
                ACCEPTED ANSWER

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

                ‏2012-10-13T09:43:46Z  in response to SystemAdmin
                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
                116 Posts
                ACCEPTED ANSWER

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

                ‏2012-10-13T09:50:01Z  in response to SystemAdmin
                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
                  ACCEPTED ANSWER

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

                  ‏2012-10-15T08:05:10Z  in response to qtbgo
                  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