Topic
  • 5 replies
  • Latest Post - ‏2013-08-01T12:58:51Z by PhilippeLaborie
JorisK
JorisK
18 Posts

Pinned topic Rewriting a constraint

‏2013-07-04T16:06:25Z |

Dear,

Propagation in the CP model I'm working on is relatively poor. It seems that this can mainly be attributed to a single constraint. I was wondering whether there exists a better way to express this constraint. My model is implemented using the Java interface.

\\Variable defs:

c_i: Optional interval variable, i \in C
d_ij: Optional interval variable, i\in C, j\in J

\\Constants:
q_i: Integer, i\in C
r_j: Integer, j\in J

Problematic Constraint:

forall(i\in C):
   presenceOf(c_i) == ( \sum_{j\in J} r_j* presenceOf(d_ij) >= q_i )

So, put in words, the constraint should do the following:

For each i \in C, the interval c_i may only be present if and only if the following holds: summed over all *present* variables d_ij multiplied by a constant r_j, the sum must be larger or equal than constant q_i. Any suggestions on how to reformulate this constraint? Perhaps some kind of cumul or sum function could be used instead?

Updated on 2013-07-04T16:06:40Z at 2013-07-04T16:06:40Z by JorisK
  • PhilippeLaborie
    PhilippeLaborie
    47 Posts

    Re: Rewriting a constraint

    ‏2013-07-05T06:49:39Z  

    Hello,

    Beside the constraint you describe on the presence status, do the selected interval variables d_ij have to be synchronized (same start, same end) ? If not, is there some sort of precedence constraints between the selected intervals d_ij ?

    Philippe

  • JorisK
    JorisK
    18 Posts

    Re: Rewriting a constraint

    ‏2013-07-05T08:40:56Z  

    Hello,

    Beside the constraint you describe on the presence status, do the selected interval variables d_ij have to be synchronized (same start, same end) ? If not, is there some sort of precedence constraints between the selected intervals d_ij ?

    Philippe

    Dear Philippe,

    I presume the easiest way to answer your question is to post a larger part of my CP model. See the following link: https://www.dropbox.com/s/7lk7lpwbntz33op/test.pdf

    The constraint I was referring to, is written on line 11. In my earlier post, I slightly simplified the variables, i.e. I removed one of the indices.
    In the variable definitions, all variables are optional interval variables, except for the s, t variables. The variable declarations use the following syntax: var={earliest start, latest end time, minimum duration of interval, optional or obligatory}. The constraints basically use the OPL syntax. The last constraint, noOverlapSequence( set of vars, distance matrix) is not a new constraint but simply an abbreviation for a sequence variable, with a noOverlap constraint. Furthermore, for each pair of intervals, the distance matrix specifies a sequence dependent setup time. Finally, the first( var, set of vars) indicates that var needs to be scheduled before any of the variables defined by the second parameter. Similar for last(var, set of vars).

  • PhilippeLaborie
    PhilippeLaborie
    47 Posts

    Re: Rewriting a constraint

    ‏2013-07-05T12:03:20Z  

    Hello,

    There are indeed ways to strengthen the formulation of this constraint indeed.

    First, if you are using a version earlier than V12.5, I would suggest you move to V12.5 or the latest V12.5.1. Indeed, we improved the propagation of expressions of the form sum_i qi * presenceOf(ai) in case some of the ai or members of an alternative constraint. In your model, this is the case for the intervals d_ijk, they are member of alternatives with master d_ij.

    Second, one thing that is not seen at the level of propagation in the present model is the fact that as d_{i}{j+1} => d_{i}{j} for a given amount d_i required by c_i, if c_i is present, some of the first intervals d_{i}{j} in the span will have to be present. If q_ij is the expression representing the contribution of d_ij: q_ij = sum_k (q_k * presenceOf(d_ijk)), you could write some additional redundant constraints like this for a given i:

    forall(l = 1 2 3 ... in Ji) {
      presenceOf(c_i) && ((sum_{j in 1..l} q_ij) < q_i) => presenceOf(d_i{l+1});
    }


    It means that if c_i is present and if the first l interval vars q_i1, ..., q_il in the chain cannot provide more than the total demand q_i of c_i, then necessarily, the (l+1)th interval needs to be present.

    There is a special case for "l=0":

    presenceOf(c_i) && (0 < q_i) => presenceOf(d_i1);

    Philippe

  • JorisK
    JorisK
    18 Posts

    Re: Rewriting a constraint

    ‏2013-07-31T08:31:28Z  

    Hello,

    There are indeed ways to strengthen the formulation of this constraint indeed.

    First, if you are using a version earlier than V12.5, I would suggest you move to V12.5 or the latest V12.5.1. Indeed, we improved the propagation of expressions of the form sum_i qi * presenceOf(ai) in case some of the ai or members of an alternative constraint. In your model, this is the case for the intervals d_ijk, they are member of alternatives with master d_ij.

    Second, one thing that is not seen at the level of propagation in the present model is the fact that as d_{i}{j+1} => d_{i}{j} for a given amount d_i required by c_i, if c_i is present, some of the first intervals d_{i}{j} in the span will have to be present. If q_ij is the expression representing the contribution of d_ij: q_ij = sum_k (q_k * presenceOf(d_ijk)), you could write some additional redundant constraints like this for a given i:

    forall(l = 1 2 3 ... in Ji) {
      presenceOf(c_i) && ((sum_{j in 1..l} q_ij) < q_i) => presenceOf(d_i{l+1});
    }


    It means that if c_i is present and if the first l interval vars q_i1, ..., q_il in the chain cannot provide more than the total demand q_i of c_i, then necessarily, the (l+1)th interval needs to be present.

    There is a special case for "l=0":

    presenceOf(c_i) && (0 < q_i) => presenceOf(d_i1);

    Philippe

     

    Dear Philippe Laborie,
     
    I finally found some time to implement your suggestions. Initial results show some good speed improvements for a number of instances.
     
    First your last suggestion:
    "There is a special case for "l=0": 
    presenceOf(c_i) && (0 < q_i) => presenceOf(d_i1); "
     
    I made this slightly stronger. For a given c_i, I first pre-compute the minimum number of d_ij variables that must be present. Say this number is m. Then there are 3 ways to express this constraint:
     
    A.
    for all i:
    for all j=1..m:
      presenceOf(c_i)==presenceOf(d_ij)
     
    B.
    for all i:
      presenceOf(c_i) == (presenceOf(d_i1) && presenceOf(d_i2) && presenceOf(d_i3) &&... && presenceOf(d_im))
     
    C.
    for all i:
      presenceOf(c_i) == presenceOf(d_i1) == presenceOf(d_i2) == presenceOf(d_i3) ==... == presenceOf(d_im)
     
    Approach A, although equivalent to approach B, seems to yield much better results, i.e. solutions are found much faster. Isn't this strange as approach A results in many more constraints whereas approach B should not be weaker? Approach C doesn't seem to work; my warm start calculated via a heuristic becomes invalid with this constraint. Not sure why.
     
    As per your suggestions, I have also added this constraint:
    "forall(l = 1 2 3 ... in Ji) { 
      presenceOf(c_i) && ((sum_{j in 1..l} q_ij) < q_i) => presenceOf(d_i{l+1}); 
    }"
     
    Although I understand the validity of the constraint, I don't see why it would help the solver? The same information is in constraints 11 and 15 in the model right, so propagating both constraints would yield the same result? How could I have known that the constraint suggested by you would actually be beneficial to the solver?
  • PhilippeLaborie
    PhilippeLaborie
    47 Posts

    Re: Rewriting a constraint

    ‏2013-08-01T12:58:51Z  
    • JorisK
    • ‏2013-07-31T08:31:28Z

     

    Dear Philippe Laborie,
     
    I finally found some time to implement your suggestions. Initial results show some good speed improvements for a number of instances.
     
    First your last suggestion:
    "There is a special case for "l=0": 
    presenceOf(c_i) && (0 < q_i) => presenceOf(d_i1); "
     
    I made this slightly stronger. For a given c_i, I first pre-compute the minimum number of d_ij variables that must be present. Say this number is m. Then there are 3 ways to express this constraint:
     
    A.
    for all i:
    for all j=1..m:
      presenceOf(c_i)==presenceOf(d_ij)
     
    B.
    for all i:
      presenceOf(c_i) == (presenceOf(d_i1) && presenceOf(d_i2) && presenceOf(d_i3) &&... && presenceOf(d_im))
     
    C.
    for all i:
      presenceOf(c_i) == presenceOf(d_i1) == presenceOf(d_i2) == presenceOf(d_i3) ==... == presenceOf(d_im)
     
    Approach A, although equivalent to approach B, seems to yield much better results, i.e. solutions are found much faster. Isn't this strange as approach A results in many more constraints whereas approach B should not be weaker? Approach C doesn't seem to work; my warm start calculated via a heuristic becomes invalid with this constraint. Not sure why.
     
    As per your suggestions, I have also added this constraint:
    "forall(l = 1 2 3 ... in Ji) { 
      presenceOf(c_i) && ((sum_{j in 1..l} q_ij) < q_i) => presenceOf(d_i{l+1}); 
    }"
     
    Although I understand the validity of the constraint, I don't see why it would help the solver? The same information is in constraints 11 and 15 in the model right, so propagating both constraints would yield the same result? How could I have known that the constraint suggested by you would actually be beneficial to the solver?

    Hello,

    Let me first answer your more general question about the impact of adding additional redundant constraint to the model. Adding redundant constraints is a very common way to strengthen the formulation of a problem and speed-up its resolution in Constraint Programming. The reason is that during the search, CP filters the domains of variables by considering each constraint individually. Let's consider your model. You have something like:

    presenceOf(c) == (sum(j in 1..n) q_j presenceOf(d_j) >= q); // C1: Line 11
    forall(j in 1..n-1) presenceOf(d_{j+1})=>presenceOf(d_j);   // C2: Line 13


    Suppose n=5, all the q_j are 1 and q==3. If you consider constraint C1 only, it just says that if c is present, then 3 of the d_j must be present but there is no way to infer which ones if we consider C1 alone. It is only when considering the conjunction of C1 and C2 that you can infer that the first 3 interval variables q_1,q_2 and q_3 are necessarily present if c is present.

    Making this inference possible in the engine is precisely the purpose of the redundant constraint I proposed.

    Now, let's have a look at the differences between formulations A, B. The explanation why formulation A is better than formulation B is probably related to the fact CP Optimizer performs a special treatment for binary constraints on "presenceOf" constraints. These constraints are aggregated into a logical network (you can see [1] for more details) which results in stronger inference in the engine. Constraints of formulation B are not aggregated.

    I'm not sure what happens with formulation C. How exactly did you write it in the OPL model?

    [1] P. Laborie, J. Rogerie. "Reasoning with conditional time-intervals". Proceedings of the Twenty-First International FLAIRS Conference, 555-560.

    Philippe