[gecode-users] Cutting holes within a view optimally

[Mikael Zayenz Lagerkvist]

Just as a side-note, you can do propagation earlier than when a variable is
fixed for this constraint. In the ground case, an offset1 of 5 and a value v
of x0 gives a forbidden region
    [-----v-----]
for the variable x1. If the difference between min (a) and max (b) of a
non-ground x0 is less than offset1, then all potential forbidden regions
will overlap. Consider the case where b-a=3
    [-----a---[==]---b-----]
The doubly marked values are forbidden for x1 regardless of the final value
of x0.

Whether modifying the propagation helps for solving your problem is another
issue of course.

Cheers,
Mikael

2010/4/13 Zaremby, David <david.zaremby at lmco.com>

>  Thanks. That did the trick.  I knew it was easy.  I just couldn’t seem to
> find it…
>
>
>
> virtual ExecStatus propagate(Space& home, const ModEventDelta&)  {
>
>             if (x0.assigned())
>
>             {
>
>                   Iter::Ranges::Singleton r0(x0.val() - offset1 > 0 ?
> x0.val() - offset1 : 0, x0.val() + offset0);
>
>                   GECODE_ME_CHECK(x1.minus_r(home, r0, false));
>
>             }
>
>             else if (x1.assigned())
>
>             {
>
>                   Iter::Ranges::Singleton r1(x1.val() - offset0 > 0 ?
> x1.val() - offset0 : 0, x1.val() + offset1);
>
>                   GECODE_ME_CHECK(x0.minus_r(home, r1, false));
>
>             }
>
>
>
>             if (x0.max() + offset0 < x1.min() || x1.max() + offset1 <
> x0.min())
>
>                   return home.ES_SUBSUMED(*this);
>
>             else
>
>                   return ES_FIX;
>
>       }
>
>
>
> *David Zaremby*
>
> Senior Software Engineer
>
> LSS / Strategic Products
>
>
>
> *Lockheed Martin Simulation, Training & Support*
>
> 12506 Lake Underhill Road, MP-823
>
> Orlando, FL 32825
>
> *From:* Christian Schulte [mailto:cschulte at kth.se]
> *Sent:* Tuesday, April 13, 2010 2:11 PM
> *To:* Zaremby, David; users at gecode.org
> *Subject:* RE: [gecode-users] Cutting holes within a view optimally
>
>
>
> Check the minus_r member function and the range iterator
>
>                 Iter::Ranges::Singleton
>
> The latter allows to specify a single range.
>
>
>
> That should do the trick!
>
>
>
> Cheers
>
> Christian
>
>
>
> --
>
> Christian Schulte, web.ict.kth.se/~cschulte/
>
>
>
> *From:* users-bounces at gecode.org [mailto:users-bounces at gecode.org] *On
> Behalf Of *Zaremby, David
> *Sent:* Tuesday, April 13, 2010 7:34 PM
> *To:* users at gecode.org gecode
> *Subject:* [gecode-users] Cutting holes within a view optimally
>
>
>
> Gecoders,
>
>
>
> I am struggling with finding the best way to cut a hole in a view during
> propegation without doing a simple for loop. I originally thought I should
> use a Range and Iterator and execute the minus_v method, but I can’t find an
> easy way to construct one easily using specific values other than using a
> value array of ints but I would still need a loop to initialize the array.
> What is the best way to do this with the least computation?
>
>
>
> The end goal of this propagator is to put a gap between two domains however
> there is no guarantee that x0 < x1  so you really can’t reduce much on the
> domain until one is assigned a start. Additionally you can’t use an offset
> view because you only want the offset to apply if the task is the earlier
> one one.
>
>
>
> virtual ExecStatus propagate(Space& home, const ModEventDelta&)  {
>
>             if (x0.assigned())
>
>             {
>
>                   //create a range that x1 cant equal over (x0.val -
> offset1, x0.val + offset0)
>
>                   for (int i = x0.val() - offset1; i < x0.val() + offset0;
> ++i)
>
>                   {
>
>                         GECODE_ME_CHECK(x1.nq(home, i));
>
>                   }
>
>             }
>
>             else if (x1.assigned())
>
>             {
>
>                   //create a range that x0 cant equal over (x1.val -
> offset0, x1.val + offset1)
>
>                   for (int i = x1.val() - offset0; i < x1.val() + offset1;
> ++i)
>
>                   {
>
>                         GECODE_ME_CHECK(x0.nq(home, i));
>
>                   }
>
>             }
>
>
>
>             if (x0.max() + offset0 <= x1.min() || x1.max() + offset1 <=
> x0.min())
>
>                   return home.ES_SUBSUMED(*this);
>
>             else
>
>                   return ES_FIX;
>
>       }
>
>
>
> *David Zaremby*
>
> Senior Software Engineer
>
> LSS / Strategic Products
>
>
>
> *Lockheed Martin Simulation, Training & Support*
>
> 12506 Lake Underhill Road, MP-823
>
> Orlando, FL 32825
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>
>


-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20100414/10af8348/attachment.htm>