Topic
5 replies Latest Post - ‏2013-11-07T19:33:00Z by Petr Vilím
Oskar Wigstrom
Oskar Wigstrom
8 Posts
ACCEPTED ANSWER

Pinned topic How do I limit the execution of costly propagators?

‏2013-11-05T16:18:26Z |

So I've started using the CP Optimizer Extensions. Some details of my project are described in https://www.ibm.com/developerworks/community/forums/html/topic?id=0c976a32-d78c-4c76-a1ec-45694fed104b&ps=25, but I think you'll be able to answer my question without looking there.

In any case, I would like to know if it is possible to influence the order in which constraints are scheduled for propagation. The details are as follows:

 

There are three types of variables:

- An integer variable cost, which is the cost to minimize

- Boolean array boolArray, these are key decision variables which are branched upon

- Interval array intervalArray, some scheduling variables

 

The constraints are:

- Set of standard scheduling constraints acting on boolArray and intervalArray, if these have not failed once all the variables in boolArray have been assigned, then everything is fine.

- A user defined constraint which updates the domain of cost based on boolArray, this constraint will reduce and finally fix the domain of cost based on the assignment to boolArray.

 

I've defined a search phase which branches on the variables boolArray, and every time a value in boolArray is modified, the user defined constraint is scheduled for propagation.

My problem is, performing propagation on the custom constraint is highly computationally costly, and many times, CP optimizer will schedule it for propagation several times in each node. This is because the scheduling constraints may fix the values of the decision variables in boolArray.

Is there some way to have the user defined constraint be propagated last (and by doing so only once) in each node?

 

Thank you for your help!

Best regards,
Oskar Wigström

 

Updated on 2013-11-05T16:20:12Z at 2013-11-05T16:20:12Z by Oskar Wigstrom
  • Petr Vilím
    Petr Vilím
    11 Posts
    ACCEPTED ANSWER

    Re: How do I limit the execution of costly propagators?

    ‏2013-11-07T15:11:45Z  in response to Oskar Wigstrom

    Dear Oskar,

    it is not possible to guarantee that user defined constraint will be called last, but it is possible to decrease its priority so that it is called less often (only when constraints with higher priority reached a fixpoint). The trick is to use function IloConstraintI::push(IlcInt priority).

    User defined constraints react on changes using demons derived from class IlcDemonI. Those demons are usually defined using ILCDEMONn macros. In the demon, you have choice to (1) either propagate the constraint immediatelly, or (2) to push the constraint to be propagated later. In your case, I recommend to do (2). Note that push adds the constraint into propagation queue only if it is not there already.

    Advantage of approach (1) is that it is possible to query delta domain of the variable that triggered the propagation (using functions such as IlcIntVar::getOldMin, IlcIntVar::isInDelta). On the other hand, it means that the constraint reacts on changes of its variables one by one, so the propagation can be called quite often. In approach (2), delta domains are no longer available at the time when IlcConstraintI::propagate() is called.

    If it helps, there's also some older discussion about the subject here: https://www.ibm.com/developerworks/community/forums/html/topic?id=77777777-0000-0000-0000-000014639305

    Best regards, Petr

  • Oskar Wigstrom
    Oskar Wigstrom
    8 Posts
    ACCEPTED ANSWER

    Re: How do I limit the execution of costly propagators?

    ‏2013-11-07T15:37:18Z  in response to Oskar Wigstrom

    Thank you for your quick answer Petr. Your suggestion works perfectly!

     

    Best regards,
    Oskar

    • Petr Vilím
      Petr Vilím
      11 Posts
      ACCEPTED ANSWER

      Re: How do I limit the execution of costly propagators?

      ‏2013-11-07T15:54:50Z  in response to Oskar Wigstrom

      I'm glad I could help!

      Just out of curiosity, you were pushing already and change in priority helped? Or you switched from (1) to (2)?

      Thanks, Petr

      Updated on 2013-11-07T15:55:16Z at 2013-11-07T15:55:16Z by Petr Vilím
      • Oskar Wigstrom
        Oskar Wigstrom
        8 Posts
        ACCEPTED ANSWER

        Re: How do I limit the execution of costly propagators?

        ‏2013-11-07T16:23:10Z  in response to Petr Vilím

        Switching from (1) to (2) did the trick. Previously I had subscriped to variables by simply using:

        b[i].whenValue(this);

        Which resulted in 640 branches and 1284 calls to the propagator.

         

        When I added my own demon and used push() the number of propagator calls was reduced to 416.

         

        Changing priority = 1 resulted in 486 calls, priority >= 3 would result in 416 calls (I guess the default priority is >= 3).

         

        I also figured out that by including

        cp.setParamters(IloCP::NoOverlapInferenceLevel, IloCp::Extended)

        and setting priority = 5, only 254 branches and 165 (!) propagator calls were needed.

         

        I'm only using a temporary dummy-objective so far, so not sure what final performance will be yet.

         

        Thanks for your help again!

        Best regards,
        Oskar

        Updated on 2013-11-07T16:24:46Z at 2013-11-07T16:24:46Z by Oskar Wigstrom