Topic
5 replies Latest Post - ‏2013-02-05T10:05:35Z by SystemAdmin
SystemAdmin
SystemAdmin
1883 Posts
ACCEPTED ANSWER

Pinned topic Global Cardinality Constraints (GCCs) in OPL

‏2012-12-11T15:29:41Z |
Say that we have an array of integer variables with the same domain, and we want to enforce each variable to have a different value from the others. One way to do it is the following:


range D = 1..10000; range R = 1..100;   dvar 

int x[r in R] in D;   subject to 
{   c: forall(d in D) count(all(r in R) x[r], d) <= 1; 
}


To me, using


c: forall(d in D) sum(r in R) (x[r] == d) <= 1;


Is completely equivalent here. Indeed, the semantic of "counting" and "summing" seem to be exactly the same. Which is more efficient between count and sum? How does the solving engine handle them at a lower level?
Both the versions of this model post 10000 constraints, and in general, the number of constraints raises as the domain of x gets larger.

However, there is what I think is a more efficient solution:


c: allDifferent(all(r in R) x[r]);


Again, my conjecture supposes that within CP/CPLEX the allDifferent constraint isn't simply translated into its equivalent formulation using sum/count, but I couldn't find any information about this details in the ILOG guide.
What if now we want to state that at most k variables in x should have the same value? The only thing that came into my mind is stating the constraint in the inefficient way using either sum or count:


c: forall(d in D) sum(r in R) (x[r] == d) <= k;



c: forall(d in D) count(all(r in R) x[r], d) <= k;


However, in the CP theory there exists a generalization of the allDifferent constraint known as Global Cardinality Constraint, or GCC (see for instance Decompositions of All Different, Global Cardinality and Related Constraints, p.421). The constraint GCC(x1..xn, l1..ln, u1..un) states that the value of xi should occur in x at least li and at most ui times. In this way, I could write something like


c: gcc(all(r in R), x[r], all(r in R) k[r], all(r in R) k[r]);


or even, having defined k as an integer


c: gcc(all(r in R), x[r], k, k);


Are global cardinality constraints somehow supported in OPL?

Regards,
Stefano
Updated on 2013-02-05T10:05:35Z at 2013-02-05T10:05:35Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    1883 Posts
    ACCEPTED ANSWER

    Re: Global Cardinality Constraints (GCCs) in OPL

    ‏2012-12-13T16:23:29Z  in response to SystemAdmin
    Using count or a sum of (x[r] == d) expression is equivalent in terms of solutions set of the problem but it can be very different in terms of performance. The count expressions that are stated on the same array of variables are aggregated by CP Optimizer to generate distribute constraints (an instance of a gcc constraint). This can be seen in the log of the engine that displays aggregated and generated constraints.

    You can also use the distribute constraints directly if you wish, and the performance will roughly be the same.

    The distribute constraint as well as the allDifferent constraint provide a "perfect" domain reduction (that is every value remaining in a domain belongs to a solution of the constraint) if you set the inference level of the constraints to "Extended" in the OPL parameters window. If you set it to lower values then the domain reduction process is faster but less domain reductions are performed. There is a balance to find here depending on your problem.

    Regards,

    Philippe
    • SystemAdmin
      SystemAdmin
      1883 Posts
      ACCEPTED ANSWER

      Re: Global Cardinality Constraints (GCCs) in OPL

      ‏2012-12-13T17:40:14Z  in response to SystemAdmin
      Thank you Philippe for your hint about the question regarding sum and count. My main concerns were about the performance of these two operators (because it was clear to me that they were logically equivalent), and some tests showed that indeed the performance of count is generally much better than the performance of sums.

      Regarding the second part of my question, some tests that I ran also showed that the formulation with allDifferent has a better performance than the formulation with count. It looked like there was a sensible difference in terms of performance between

      
      c: forall(d in D) count(x, d) <= 1;
      


      and

      
      c: allDifferent(x);
      

      In your post you mentioned a distribute constraint, that seems to be deprecated from OPL 6.x on (reference: http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.studio.help%2FOPL_Studio%2Foplmigration%2Ftopics%2Fopl_mig_prev_3x4x_3xCP_constr_distrib.html) and indeed replaced by count. But still, in the generalized case, a count is just an instance of a gcc like you said: that's why you need indeed to post it multiple times, i.e., in a forall loop for each value in the variables domain, and this can slow the computation time. That's why I imagine that the formulation

      
      c: forall(d in D) count(x, d) <= k;
      


      would have a worse performance than an hypothetical formulation like

      
      c: gcc(x, 0, k);
      


      Does OPL have an operator like allDifferent, but for the generalized case of a gcc (like the one I wrote in my last code snippet)? Or is the formulation with forall and count the best we can do in this generalized case?

      Regards,
      Stefano
      • SystemAdmin
        SystemAdmin
        1883 Posts
        ACCEPTED ANSWER

        Re: Global Cardinality Constraints (GCCs) in OPL

        ‏2012-12-14T08:29:02Z  in response to SystemAdmin
        Unless you have a huge amount of count constraints, you should not be able to see a significant difference in runtime compared to a distribute constraints. distribute is now deprecated because count is easier to use and provide the same performance, but it helps to understand the underlying preprocessing operations.

        With the same inference level, an allDifferent constraint will provide the same domain reduction as an equivalent set of counts but the allDifferent constraints algorithm being more specialized, it will run faster.

        Cheers,

        Philippe
        • SystemAdmin
          SystemAdmin
          1883 Posts
          ACCEPTED ANSWER

          Re: Global Cardinality Constraints (GCCs) in OPL

          ‏2012-12-14T09:28:37Z  in response to SystemAdmin
          I see. Indeed, what I am interested in is performance (computation speed), because I am solving a very large model and can incur in a huge amount of count constraints. That's why I would like to avoid having a number of count constraints equal to the cardinality of the domains variable.

          Unfortunately, allDifference(x) has a semantic of "at most 1 variables in x can have the same value", while I would need a version of allDifferent (which in my previous example I called gcc, because it's indeed a global cardinality constraint as stated in the paper I linked in the first post) with the semantic "at most k variables in x can have the same value", with k being an integer parameter I choose.

          What is the most efficient way to implement this in OPL? Is just using count and playing with the inference level for a tradeoff between speed and domain reduction the best I can do? Thank you for your patience, understanding and support.

          Regards,
          Stefano
          • SystemAdmin
            SystemAdmin
            1883 Posts
            ACCEPTED ANSWER

            Re: Global Cardinality Constraints (GCCs) in OPL

            ‏2013-02-05T10:05:35Z  in response to SystemAdmin
            So, do I have to conclude that using count is the best possible way to do it, because there is no better generalization of allDifferent in OPL?

            Regards,
            Stefano