main page modules namespaces classes files
Gecode home

search for 

val.icc

Go to the documentation of this file.

/*
 *  Main authors:
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *
 *  Copyright:
 *     Mikael Lagerkvist, 2005
 *
 *  Last modified:
 *     $Date: 2006-08-04 16:03:26 +0200 (Fri, 04 Aug 2006) $ by $Author: schulte $
 *     $Revision: 3512 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  See the file "LICENSE" for information on usage and
 *  redistribution of this file, and for a
 *     DISCLAIMER OF ALL WARRANTIES.
 *
 */

/* This is the propagation algorithm of the cumulatives constraint as presented in
   @inproceedings{DBLP:conf/cp/BeldiceanuC02,
     author    = {Nicolas Beldiceanu and Mats Carlsson},
     title     = {A New Multi-resource cumulatives Constraint with Negative Heights.},
     booktitle = {CP},
     year      = {2002},
     pages     = {63-79},
     ee        = {http://link.springer.de/link/service/series/0558/bibs/2470/24700063.htm},
     crossref  = {DBLP:conf/cp/2002},
     bibsource = {DBLP, http://dblp.uni-trier.de}
   }
   @proceedings{DBLP:conf/cp/2002,
     editor    = {Pascal Van Hentenryck},
     title     = {Principles and Practice of Constraint Programming - CP 2002,
                  8th International Conference, CP 2002,
                  Ithaca, NY, USA, September 9-13, 2002, Proceedings},
     booktitle = {CP},
     publisher = {Springer},
     series    = {Lecture Notes in Computer Science},
     volume    = {2470},
     year      = {2002},
     isbn      = {3-540-44120-4},
     bibsource = {DBLP, http://dblp.uni-trier.de}
   }

 */

#include <vector>
#include <list>
#include <algorithm>


namespace Gecode { namespace Int { namespace Cumulatives {

  template <class ViewM, class ViewD, class ViewH, class View>
  forceinline
  Val<ViewM,ViewD,ViewH,View>::Val(Space* home, const ViewArray<ViewM>& _machine,
                                   const ViewArray<View>& _start,
                                   const ViewArray<ViewD>& _duration,
                                   const ViewArray<View>& _end,
                                   const ViewArray<ViewH>& _height,
                                   const IntArgs& _limit,
                                   bool _at_most) :
    Propagator(home,true),
    machine(_machine), start(_start), duration(_duration),
    end(_end), height(_height), limit(_limit.size()), at_most(_at_most) {
    for(int i = _limit.size(); i--; ) {
      limit[i] = _limit[i];
    }

    machine.subscribe(home,this,PC_INT_DOM);
    start.subscribe(home,this,PC_INT_BND);
    duration.subscribe(home,this,PC_INT_BND);
    end.subscribe(home,this,PC_INT_BND);
    height.subscribe(home,this,PC_INT_BND);
  }

  template <class ViewM, class ViewD, class ViewH, class View>
  ExecStatus
  Val<ViewM,ViewD,ViewH,View>
  ::post(Space* home, const ViewArray<ViewM>& machine,
         const ViewArray<View>& start, const ViewArray<ViewD>& duration,
         const ViewArray<View>& end, const ViewArray<ViewH>& height,
         const IntArgs& limit, bool at_most) {
    (void) new (home) Val(home, machine, start, duration,
                          end, height, limit, at_most);

    return ES_OK;
  }

  template <class ViewM, class ViewD, class ViewH, class View>
  forceinline
  Val<ViewM,ViewD,ViewH,View>::Val(Space* home, bool share,
                                   Val<ViewM,ViewD,ViewH,View>& p)
    : Propagator(home,share,p), at_most(p.at_most) {
    machine.update(home,share,p.machine);
    start.update(home, share, p.start);
    duration.update(home, share, p.duration);
    end.update(home, share, p.end);
    height.update(home, share, p.height);
    limit.update(share, p.limit);
  }

  template <class ViewM, class ViewD, class ViewH, class View>
  size_t
  Val<ViewM,ViewD,ViewH,View>::dispose(Space* home) {
    if (!home->failed()) {
      machine.cancel(home,this,PC_INT_DOM);
      start.cancel(home,this,PC_INT_BND);
      duration.cancel(home,this,PC_INT_BND);
      end.cancel(home,this,PC_INT_BND);
      height.cancel(home,this,PC_INT_BND);
    }
    limit.~SharedArray();
    (void) Propagator::dispose(home);
    return sizeof(*this);
  }

  template <class ViewM, class ViewD, class ViewH, class View>
  PropCost
  Val<ViewM,ViewD,ViewH,View>::cost(void) const {
    return cost_hi(start.size(), PC_QUADRATIC_LO);
  }

  template <class ViewM, class ViewD, class ViewH, class View>
  Actor*
  Val<ViewM,ViewD,ViewH,View>::copy(Space* home, bool share) {
    return new (home) Val<ViewM,ViewD,ViewH,View>(home,share,*this);
  }

  typedef enum {EVENT_CHCK, EVENT_PROF, EVENT_PRUN} ev_t;
  class Event
  {
  public:
    ev_t e;
    int task;
    int date;
    int inc;
    bool first_prof;

    Event(ev_t _e, int _task, int _date, int _inc = 0, bool _first_prof = false)
      : e(_e), task(_task), date(_date), inc(_inc), first_prof(_first_prof)
    {}

    bool operator<(const Event& e) {
      return date < e.date;
    }
  };


  template <class ViewM, class ViewD, class ViewH, class View>
  ExecStatus
  Val<ViewM,ViewD,ViewH,View>::prune(Space * home, int low, int up, int r,
                   int ntask, int sheight,
                   const std::vector<int>& contribution,
                   std::list<int>& prune_tasks) {

    if (ntask > 0 &&
        (at_most ? sheight > limit[r]
         : sheight < limit[r])) {
      return ES_FAILED;
    }

    std::list<int>::iterator it = prune_tasks.begin();
    while (it != prune_tasks.end()) {
      int t = *it;
      // Algorithm 2.
      // Prune the machine, start, and end for required
      // tasks for machine r that have heights possibly greater than 0.
      if (ntask != 0 &&
          (at_most ? height[t].min() < 0
           : height[t].max() > 0) &&
          (at_most ? sheight-contribution[t] > limit[r]
           : sheight-contribution[t] < limit[r])) {
        if (me_failed(machine[t].eq(home, r))||
            me_failed(start[t].gq(home, up-duration[t].max()+1))||
            me_failed(start[t].lq(home, low))||
            me_failed(end[t].lq(home,low+duration[t].max()))||
            me_failed(end[t].gq(home, up+1))||
            me_failed(duration[t].gq(home,std::min(up-start[t].max()+1,
                                                   end[t].min()-low)))
            )
          return ES_FAILED;
      }

      // Algorithm 3.
      // Remove values that prevent us from reaching the limit
      if (at_most ? height[t].min() < std::min(0, limit[r])
          : height[t].max() < std::max(0, limit[r])) {
        if (at_most ? sheight-contribution[t]+height[t].min() > limit[r]
            : sheight-contribution[t]+height[t].max() < limit[r]) {
          if (end[t].min() > low  &&
              start[t].max() <= up &&
              duration[t].min() > 0) {
            if (me_failed(machine[t].nq(home, r)))
              return ES_FAILED;
          } else if (machine[t].assigned()) {
            int dtmin = duration[t].min();
            if (dtmin > 0) {
              Iter::Ranges::Singleton
                a(low-dtmin+1, up), b(low+1, up+dtmin);
              if (me_failed(start[t].minus(home,a)) ||
                  me_failed(end[t].minus(home, b)))
                return ES_FAILED;
            }
            if (me_failed(duration[t].lq(home,
                                         std::max(std::max(low-start[t].min(),
                                                           end[t].max()-up-1),
                                                  0))))
              return ES_FAILED;
          }
        }
      }

      // Algorithm 4.
      // Remove bad negative values from for-sure heights.
      /* \note "It is not sufficient to only test for assignment of machine[t]
       *         since Algorithm 3 can remove the value." Check this against
       *         the conditions for Alg3.
       */
      if (machine[t].assigned() &&
          machine[t].val() == r &&
          end[t].min() > low    &&
          start[t].max() <= up  &&
          duration[t].min() > 0 ) {
        if (me_failed(at_most
                      ? height[t].lq(home, limit[r]-sheight+contribution[t])
                      : height[t].gq(home, limit[r]-sheight+contribution[t])))
          return ES_FAILED;
      }

      // Remove tasks that are no longer relevant.
      /* @todo check condition more thouroughly - is
       *        \f$max(end_r)\geq up+1\f$  CORRECT?
       */
      if ((!machine[t].in(r)) ||
          end[t].max() <= up+1) {
        // @todo more than one *it (probably not) ? ==> remove(*it)
        std::list<int>::iterator old = it++;
        prune_tasks.erase(old);
      } else {
        ++it;
      }
    }

    return ES_OK;
  }

  template <class ViewM, class ViewD, class ViewH, class View>
  ExecStatus
  Val<ViewM,ViewD,ViewH,View>::propagate(Space* home) {
    ExecStatus res = ES_NOFIX;
    // Check for subsumption
    bool nnft = true; // no non-fixed tasks.
    for (int t = start.size(); t--; )
      if(!(duration[t].assigned() && end[t].assigned()   &&
           machine[t].assigned()  && start[t].assigned() &&
           height[t].assigned())) {
        nnft = false;
        break;
      }
    if(nnft) res = ES_SUBSUMED;


    // Propagate information for machine r
    for (int r = limit.size(); r--; ) {
      std::list<Event> events;

      // Find events for sweep-line
      for (int t = start.size(); t--; ) {
        if (machine[t].assigned() &&
            machine[t].val() == r &&
            start[t].max() < end[t].min()) {
          if (at_most
              ? height[t].min() > std::min(0, limit[r])
              : height[t].max() < std::max(0, limit[r])) {
            events.push_back(Event(EVENT_CHCK, t, start[t].max(), 1));
            events.push_back(Event(EVENT_CHCK, t, end[t].min(), -1));
          }
          if (at_most
              ? height[t].min() > 0
              : height[t].max() < 0) {
            events.push_back(Event(EVENT_PROF, t, start[t].max(),
                                   at_most ? height[t].min()
                                   : height[t].max(), true));
            events.push_back(Event(EVENT_PROF, t, end[t].min(),
                                   at_most ? -height[t].min()
                                   : -height[t].max()));
          }
        }
        
        if (machine[t].in(r)) {
          if (at_most
              ? height[t].min() < 0
              : height[t].max() > 0) {
            events.push_back(Event(EVENT_PROF, t, start[t].min(),
                                   at_most ? height[t].min()
                                   : height[t].max(), true));
            events.push_back(Event(EVENT_PROF, t, end[t].max(),
                                   at_most ? -height[t].min()
                                   : -height[t].max()));
          }
          if (!(machine[t].assigned() &&
                 height[t].assigned() &&
                  start[t].assigned() &&
                    end[t].assigned())) {
            events.push_back(Event(EVENT_PRUN, t, start[t].min()));
          }
        }
      }

      // If there are no events, continue with next machine
      if (events.size() == 0)
        continue;

      // Sort the events according to date
      events.sort();

      // Sweep line along d, starting at 0
      int d        = 0;
      int ntask    = 0;
      int sheight  = 0;
      std::list<Event>::iterator it = events.begin();
      std::list<int> prune_tasks;
      std::vector<int> contribution(start.size(), at_most
                                    ? Limits::Int::int_max
                                    : Limits::Int::int_min);

      d = it->date;
      while (it != events.end()) {
        if (it->e != EVENT_PRUN) {
          if (d != it->date) {
            GECODE_ES_CHECK(prune(home, d, it->date-1, r,
                                  ntask, sheight,
                                  contribution, prune_tasks));
            d = it->date;
          }
          if (it->e == EVENT_CHCK) {
            ntask += it->inc;
          } else /* if (it->e == EVENT_PROF) */ {
            sheight += it->inc;
            if(it->first_prof)
              contribution[it->task] = at_most
                ? std::min(contribution[it->task], it->inc)
                : std::max(contribution[it->task], it->inc);
          }
        } else /* if (it->e == EVENT_PRUN) */ {
          prune_tasks.push_back(it->task);
        }
        ++it;
      }

      GECODE_ES_CHECK(prune(home, d, d, r,
                            ntask, sheight,
                            contribution, prune_tasks));
    }

    return res;
  }

}}}

// STATISTICS: int-prop