Generated on Sat Jan 20 2018 22:21:14 for Gecode by doxygen 1.8.13
cumulative.hh
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Guido Tack <tack@gecode.org>
6  *
7  * Copyright:
8  * Christian Schulte, 2009
9  * Guido Tack, 2010
10  *
11  * Last modified:
12  * $Date: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
13  * $Revision: 14967 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #ifndef __GECODE_INT_CUMULATIVE_HH__
41 #define __GECODE_INT_CUMULATIVE_HH__
42 
43 #include <gecode/int/task.hh>
44 #include <gecode/int/unary.hh>
45 
59 namespace Gecode { namespace Int { namespace Cumulative {
60 
62  void mul_check(long long int x, long long int y);
63 
65  void mul_check(long long int x, long long int y, long long int z);
66 
67 }}}
68 
70 
71 namespace Gecode { namespace Int { namespace Cumulative {
72 
75  protected:
77  int _c;
78  public:
80 
81  ManFixPTask(void);
84  ManFixPTask(IntVar s, int p, int c);
86  void init(IntVar s, int p, int c);
88  void init(const ManFixPTask& t);
90 
92 
93  int c(void) const;
96  long long int e(void) const;
98 
100 
101  void update(Space& home, bool share, ManFixPTask& t);
104 
105  };
106 
111  template<class Char, class Traits>
112  std::basic_ostream<Char,Traits>&
113  operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTask& t);
114 
117  protected:
119  int _c;
120  public:
122 
123  ManFixPSETask(void);
132  ManFixPSETask(TaskType t, IntVar s, int p, int c);
140  void init(TaskType t, IntVar s, int p, int c);
142  void init(const ManFixPSETask& t);
144 
146 
147  int c(void) const;
150  long long int e(void) const;
152 
154 
155  void update(Space& home, bool share, ManFixPSETask& t);
158 
159  };
160 
165  template<class Char, class Traits>
166  std::basic_ostream<Char,Traits>&
167  operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETask& t);
168 
171  protected:
173  int _c;
174  public:
176 
177  ManFlexTask(void);
180  ManFlexTask(IntVar s, IntVar p, IntVar e, int c);
182  void init(IntVar s, IntVar p, IntVar e, int c);
184  void init(const ManFlexTask& t);
186 
188 
189  int c(void) const;
192  long long int e(void) const;
194 
196 
197  void update(Space& home, bool share, ManFlexTask& t);
200 
201  };
202 
207  template<class Char, class Traits>
208  std::basic_ostream<Char,Traits>&
209  operator <<(std::basic_ostream<Char,Traits>& os, const ManFlexTask& t);
210 
211 
213  class OptFixPTask : public ManToOptTask<ManFixPTask> {
214  protected:
216  public:
218 
219  OptFixPTask(void);
222  OptFixPTask(IntVar s, int p, int c, BoolVar m);
224  void init(IntVar s, int p, int c, BoolVar m);
226  operator Unary::OptFixPTask (void);
228  };
229 
234  template<class Char, class Traits>
235  std::basic_ostream<Char,Traits>&
236  operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTask& t);
237 
239  class OptFixPSETask : public ManToOptTask<ManFixPSETask> {
240  protected:
242  public:
244 
245  OptFixPSETask(void);
248  OptFixPSETask(TaskType t, IntVar s, int p, int c, BoolVar m);
250  void init(TaskType t, IntVar s, int p, int c, BoolVar m);
252  operator Unary::OptFixPSETask (void);
254  };
255 
260  template<class Char, class Traits>
261  std::basic_ostream<Char,Traits>&
262  operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETask& t);
263 
265  class OptFlexTask : public ManToOptTask<ManFlexTask> {
266  protected:
268  public:
270 
271  OptFlexTask(void);
274  OptFlexTask(IntVar s, IntVar p, IntVar e, int c, BoolVar m);
276  void init(IntVar s, IntVar p, IntVar e, int c, BoolVar m);
278  operator Unary::OptFlexTask (void);
280  };
281 
286  template<class Char, class Traits>
287  std::basic_ostream<Char,Traits>&
288  operator <<(std::basic_ostream<Char,Traits>& os, const OptFlexTask& t);
289 
290 }}}
291 
293 
294 namespace Gecode { namespace Int { namespace Cumulative {
295 
298 
301 
304 
307 
310 
313 
316 
319 
322 
325 
328 
331 
332 
337  template<class Char, class Traits>
338  std::basic_ostream<Char,Traits>&
339  operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTaskBwd& t);
340 
345  template<class Char, class Traits>
346  std::basic_ostream<Char,Traits>&
347  operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETaskBwd& t);
348 
353  template<class Char, class Traits>
354  std::basic_ostream<Char,Traits>&
355  operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTaskBwd& t);
356 
361  template<class Char, class Traits>
362  std::basic_ostream<Char,Traits>&
363  operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETaskBwd& t);
364 
365 }}}
366 
368 
369 namespace Gecode { namespace Int {
370 
372  template<>
373  class TaskViewTraits<Cumulative::ManFixPTaskFwd> {
374  public:
377  };
378 
380  template<>
381  class TaskViewTraits<Cumulative::ManFixPTaskBwd> {
382  public:
385  };
386 
388  template<>
389  class TaskViewTraits<Cumulative::ManFixPSETaskFwd> {
390  public:
393  };
394 
396  template<>
397  class TaskViewTraits<Cumulative::ManFixPSETaskBwd> {
398  public:
401  };
402 
404  template<>
405  class TaskViewTraits<Cumulative::OptFixPTaskFwd> {
406  public:
409  };
410 
412  template<>
413  class TaskViewTraits<Cumulative::OptFixPTaskBwd> {
414  public:
417  };
418 
420  template<>
421  class TaskViewTraits<Cumulative::OptFixPSETaskFwd> {
422  public:
425  };
426 
428  template<>
429  class TaskViewTraits<Cumulative::OptFixPSETaskBwd> {
430  public:
433  };
434 
436  template<>
437  class TaskViewTraits<Cumulative::ManFlexTaskFwd> {
438  public:
441  };
442 
444  template<>
445  class TaskViewTraits<Cumulative::ManFlexTaskBwd> {
446  public:
449  };
450 
452  template<>
453  class TaskViewTraits<Cumulative::OptFlexTaskFwd> {
454  public:
457  };
458 
460  template<>
461  class TaskViewTraits<Cumulative::OptFlexTaskBwd> {
462  public:
465  };
466 
467 
469  template<>
470  class TaskTraits<Cumulative::ManFixPTask> {
471  public:
478  };
479 
481  template<>
482  class TaskTraits<Cumulative::ManFixPSETask> {
483  public:
490  };
491 
493  template<>
494  class TaskTraits<Cumulative::OptFixPTask> {
495  public:
504  };
505 
507  template<>
508  class TaskTraits<Cumulative::OptFixPSETask> {
509  public:
518  };
519 
521  template<>
522  class TaskTraits<Cumulative::ManFlexTask> {
523  public:
530  };
531 
533  template<>
534  class TaskTraits<Cumulative::OptFlexTask> {
535  public:
544  };
545 
546 }}
547 
548 namespace Gecode { namespace Int { namespace Cumulative {
549 
551  class OmegaNode {
552  public:
554  long long int e;
556  long long int env;
558  void init(const OmegaNode& l, const OmegaNode& r);
560  void update(const OmegaNode& l, const OmegaNode& r);
561  };
562 
564  template<class TaskView>
565  class OmegaTree : public TaskTree<TaskView,OmegaNode> {
566  protected:
573  int c;
574  public:
576  OmegaTree(Region& r, int c, const TaskViewArray<TaskView>& t);
578  void insert(int i);
580  void remove(int i);
582  long long int env(void) const;
583  };
584 
586  class ExtOmegaNode : public OmegaNode {
587  public:
589  long long int cenv;
591  void init(const ExtOmegaNode& l, const ExtOmegaNode& r);
593  void update(const ExtOmegaNode& l, const ExtOmegaNode& r);
594  };
595 
597  template<class TaskView>
598  class ExtOmegaTree : public TaskTree<TaskView,ExtOmegaNode> {
599  protected:
616  int c, ci;
617  public:
619  template<class Node>
620  ExtOmegaTree(Region& r, int c, const TaskTree<TaskView,Node>& t);
622  void init(int ci);
624  long long int env(int i);
625  };
626 
627 
629  class OmegaLambdaNode : public OmegaNode {
630  public:
632  static const int undef = -1;
634  long long int le;
636  long long int lenv;
638  int resLe;
640  int resLenv;
642  void init(const OmegaLambdaNode& l, const OmegaLambdaNode& r);
644  void update(const OmegaLambdaNode& l, const OmegaLambdaNode& r);
645  };
646 
648  template<class TaskView>
649  class OmegaLambdaTree : public TaskTree<TaskView,OmegaLambdaNode> {
650  protected:
657  int c;
658  public:
662  void shift(int i);
664  void lremove(int i);
666  bool lempty(void) const;
668  int responsible(void) const;
670  long long int env(void) const;
672  long long int lenv(void) const;
673  };
674 
675 }}}
676 
678 
679 namespace Gecode { namespace Int { namespace Cumulative {
680 
682  template<class Task>
683  ExecStatus
684  subsumed(Space& home, Propagator& p, int c, TaskArray<Task>& t);
685 
687  template<class ManTask>
689 
691  template<class Task, class Cap>
692  ExecStatus timetabling(Space& home, Propagator& p, Cap c,
693  TaskArray<Task>& t);
694 
696  template<class Task>
698 
705  template<class ManTask, class Cap, class PL>
706  class ManProp : public TaskProp<ManTask,PL> {
707  protected:
710  Cap c;
712  ManProp(Home home, Cap c, TaskArray<ManTask>& t);
714  ManProp(Space& home, bool shared, ManProp& p);
715  public:
717  virtual Actor* copy(Space& home, bool share);
719  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
721  static ExecStatus post(Home home, Cap c, TaskArray<ManTask>& t);
723  virtual size_t dispose(Space& home);
724  };
725 
732  template<class OptTask, class Cap, class PL>
733  class OptProp : public TaskProp<OptTask,PL> {
734  protected:
737  Cap c;
739  OptProp(Home home, Cap c, TaskArray<OptTask>& t);
741  OptProp(Space& home, bool shared, OptProp& p);
742  public:
744  virtual Actor* copy(Space& home, bool share);
746  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
748  static ExecStatus post(Home home, Cap c, TaskArray<OptTask>& t);
750  virtual size_t dispose(Space& home);
751  };
752 
754  template<class ManTask, class Cap>
755  ExecStatus
756  cmanpost(Home home, Cap c, TaskArray<ManTask>& t, IntPropLevel ipl);
757 
759  template<class OptTask, class Cap>
760  ExecStatus
761  coptpost(Home home, Cap c, TaskArray<OptTask>& t, IntPropLevel ipl);
762 
763 }}}
764 
772 
773 #endif
774 
775 // STATISTICS: int-prop
Unary (mandatory) task with fixed processing, start or end time
Definition: unary.hh:152
Cumulative (mandatory) task with flexible processing time.
Definition: cumulative.hh:170
long long int cenv
Energy envelope for subtree.
Definition: cumulative.hh:589
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Cumulative::OptFixPSETaskBwd TaskViewBwd
The backward task view type.
Definition: cumulative.hh:513
Cumulative::ManFixPTaskFwd TaskViewFwd
The forward task view type.
Definition: cumulative.hh:473
Cumulative (mandatory) task with fixed processing, start or end time.
Definition: cumulative.hh:116
Task view array.
Definition: task.hh:237
Omega-lambda trees for computing ect of task sets.
Definition: cumulative.hh:649
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
TaskType
Type of task for scheduling constraints.
Definition: int.hh:990
Unary optional task with flexible processing time
Definition: unary.hh:374
Cumulative::OptFixPTask Task
The task type.
Definition: cumulative.hh:416
FwdToBwd< OptFlexTaskFwd > OptFlexTaskBwd
Backward (dual) optional flexible task view.
Definition: cumulative.hh:330
Cumulative::OptFixPSETaskFwd TaskViewFwd
The forward task view type.
Definition: cumulative.hh:511
Cumulative::OptFixPTaskFwd TaskViewFwd
The forward task view type.
Definition: cumulative.hh:497
Cumulative::ManFlexTaskFwd TaskViewFwd
The forward task view type.
Definition: cumulative.hh:525
ExecStatus subsumed(Space &home, Propagator &p, int c, TaskArray< Task > &t)
Check for subsumption (all tasks must be assigned)
Definition: subsumption.hpp:42
Node for an omega lambda tree.
Definition: cumulative.hh:629
Cumulative::ManFlexTask Task
The task type.
Definition: cumulative.hh:448
Cap c
Resource capacity.
Definition: cumulative.hh:710
Unary::ManFixPSETask UnaryTask
The corresponding unary task type.
Definition: cumulative.hh:489
Omega trees for computing ect of task sets.
Definition: cumulative.hh:565
Unary (mandatory) task with fixed processing time
Definition: unary.hh:58
long long int env
Energy envelope for subtree.
Definition: cumulative.hh:556
Omega trees for computing ect of task sets.
Definition: cumulative.hh:598
FwdToBwd< ManFlexTaskFwd > ManFlexTaskBwd
Backward (dual) mandatory flexible task view.
Definition: cumulative.hh:324
ExecStatus overload(Space &home, int c, TaskArray< ManTask > &t)
Check mandatory tasks t for overload.
Definition: overload.hpp:45
FwdToBwd< ManFixPTaskFwd > ManFixPTaskBwd
Backward (dual) mandatory fixed task view.
Definition: cumulative.hh:300
Base-class for propagators.
Definition: core.hpp:1092
Propagator for tasks
Definition: task.hh:428
Cumulative optional task with flexible processing time
Definition: cumulative.hh:265
FwdToBwd< OptFixPTaskFwd > OptFixPTaskBwd
Backward (dual) optional fixed task view.
Definition: cumulative.hh:312
Task array.
Definition: task.hh:169
Cumulative::ManFixPSETaskBwd TaskViewBwd
The backward task view type.
Definition: cumulative.hh:487
Handle to region.
Definition: region.hpp:61
Scheduling propagator for cumulative resource with optional tasks.
Definition: cumulative.hh:733
Computation spaces.
Definition: core.hpp:1748
Traits class for mapping tasks to task views.
Definition: task.hh:161
Base-class for both propagators and branchers.
Definition: core.hpp:696
Cumulative::ManFixPSETask ManTask
The corresponding mandatory task.
Definition: cumulative.hh:515
Cumulative::ManFlexTask Task
The task type.
Definition: cumulative.hh:440
Cumulative::OptFixPSETask Task
The task type.
Definition: cumulative.hh:432
Gecode::FloatVal c(-8, 8)
Unary optional task with fixed processing time
Definition: unary.hh:226
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
Cumulative::OptFlexTask Task
The task type.
Definition: cumulative.hh:464
Cumulative::OptFixPTask Task
The task type.
Definition: cumulative.hh:408
Cumulative::OptFixPTaskBwd TaskViewBwd
The backward task view type.
Definition: cumulative.hh:499
Cumulative (mandatory) task with fixed processing time.
Definition: cumulative.hh:74
int resLe
Node which is responsible for le.
Definition: cumulative.hh:638
Cumulative::ManFixPSETask Task
The task type.
Definition: cumulative.hh:392
Cumulative::ManFixPTask Task
The task type.
Definition: cumulative.hh:376
int resLenv
Node which is responsible for lenv.
Definition: cumulative.hh:640
Unary::OptFixPSETask UnaryTask
The corresponding unary task type.
Definition: cumulative.hh:517
ManFixPSETask ManFixPSETaskFwd
Forward mandatory fixed task view.
Definition: cumulative.hh:303
Class to define an optional from a mandatory task.
Definition: task.hh:47
Unary::OptFlexTask UnaryTask
The corresponding unary task type.
Definition: cumulative.hh:543
Cumulative::ManFixPSETask Task
The task type.
Definition: cumulative.hh:400
Cumulative::OptFlexTaskBwd TaskViewBwd
The backward task view type.
Definition: cumulative.hh:539
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition: set.hh:784
FwdToBwd< OptFixPSETaskFwd > OptFixPSETaskBwd
Backward (dual) optional fixed task view.
Definition: cumulative.hh:318
OptFixPTask OptFixPTaskFwd
Forward optional fixed task view.
Definition: cumulative.hh:309
OptFixPSETask OptFixPSETaskFwd
Forward optional fixed task view.
Definition: cumulative.hh:315
Boolean integer variables.
Definition: int.hh:494
Task mapper: turns a task view into its dual.
Definition: task.hh:106
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
Cumulative optional task with fixed processing time.
Definition: cumulative.hh:213
Cumulative::ManFixPTaskBwd TaskViewBwd
The backward task view type.
Definition: cumulative.hh:475
Unary::ManFixPTask UnaryTask
The corresponding unary task type.
Definition: cumulative.hh:477
Unary::OptFixPTask UnaryTask
The corresponding unary task type.
Definition: cumulative.hh:503
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:955
Cumulative::OptFlexTaskFwd TaskViewFwd
The forward task view type.
Definition: cumulative.hh:537
Cumulative::ManFixPSETaskFwd TaskViewFwd
The forward task view type.
Definition: cumulative.hh:485
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
long long int le
Energy for subtree.
Definition: cumulative.hh:634
OptFlexTask OptFlexTaskFwd
Forward optional flexible task view.
Definition: cumulative.hh:327
ExecStatus coptpost(Home home, Cap c, TaskArray< OptTask > &t, IntPropLevel ipl)
Post optional task propagator according to propagation level.
ExecStatus timetabling(Space &home, Propagator &p, Cap c, TaskArray< Task > &t)
Perform time-tabling propagation.
ExecStatus
Definition: core.hpp:540
Integer variables.
Definition: int.hh:353
ManFixPTask ManFixPTaskFwd
Forward mandatory fixed task view.
Definition: cumulative.hh:297
Node for an extended omega tree.
Definition: cumulative.hh:586
void mul_check(long long int x, long long int y)
Throw exception if multiplication of x and y overflows.
Definition: limits.hpp:41
Unary optional task with fixed processing, start or end time.
Definition: unary.hh:250
Cumulative::OptFlexTask Task
The task type.
Definition: cumulative.hh:456
Post propagator for SetVar x
Definition: set.hh:784
ManFlexTask ManFlexTaskFwd
Forward mandatory flexible task view.
Definition: cumulative.hh:321
Traits class for mapping task views to tasks.
Definition: task.hh:152
Scheduling propagator for cumulative resource with mandatory tasks.
Definition: cumulative.hh:706
bool shared(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether views share same variable.
Definition: view.hpp:702
FwdToBwd< ManFixPSETaskFwd > ManFixPSETaskBwd
Backward (dual) mandatory fixed task view.
Definition: cumulative.hh:306
Gecode toplevel namespace
Cumulative::ManFixPTask ManTask
The corresponding mandatory task.
Definition: cumulative.hh:501
Unary (mandatory) task with flexible processing time
Definition: unary.hh:274
Cumulative optional task with fixed processing, start or end time.
Definition: cumulative.hh:239
Node for an omega tree.
Definition: cumulative.hh:551
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Cumulative::ManFlexTask ManTask
The corresponding mandatory task.
Definition: cumulative.hh:541
Home class for posting propagators
Definition: core.hpp:922
Task trees for task views with node type Node.
Definition: task.hh:369
Cumulative::ManFlexTaskBwd TaskViewBwd
The backward task view type.
Definition: cumulative.hh:527
Cap c
Resource capacity.
Definition: cumulative.hh:737
Unary::ManFlexTask UnaryTask
The corresponding unary task type.
Definition: cumulative.hh:529
long long int e
Energy for subtree.
Definition: cumulative.hh:554
Cumulative::OptFixPSETask Task
The task type.
Definition: cumulative.hh:424
long long int lenv
Energy envelope for subtree.
Definition: cumulative.hh:636
Cumulative::ManFixPTask Task
The task type.
Definition: cumulative.hh:384
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
ExecStatus edgefinding(Space &home, int c, TaskViewArray< TaskView > &t)
ExecStatus cmanpost(Home home, Cap c, TaskArray< ManTask > &t, IntPropLevel ipl)
Post mandatory task propagator according to propagation level.