Generated on Sat Feb 7 2015 02:01:21 for Gecode by doxygen 1.8.9.1
cumulative.cpp
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: 2013-09-17 13:54:20 +0200 (Tue, 17 Sep 2013) $ by $Author: tack $
13  * $Revision: 14006 $
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 #include <gecode/int/cumulative.hh>
41 
42 #include <algorithm>
43 
44 namespace Gecode {
45 
46  template<class Cap>
47  void
48  cumulative(Home home, Cap c, const TaskTypeArgs& t,
49  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
50  IntConLevel icl) {
51  using namespace Gecode::Int;
52  using namespace Gecode::Int::Cumulative;
53  if ((s.size() != p.size()) || (s.size() != u.size()) ||
54  (s.size() != t.size()))
55  throw Int::ArgumentSizeMismatch("Int::cumulative");
56  long long int w = 0;
57  for (int i=p.size(); i--; ) {
58  Limits::nonnegative(p[i],"Int::cumulative");
59  Limits::nonnegative(u[i],"Int::cumulative");
60  Limits::check(static_cast<long long int>(s[i].max()) + p[i],
61  "Int::cumulative");
62  mul_check(p[i],u[i]);
63  w += s[i].width();
64  }
65  mul_check(c.max(),w,s.size());
66  if (home.failed()) return;
67 
68  int minU = INT_MAX; int minU2 = INT_MAX; int maxU = INT_MIN;
69  for (int i=u.size(); i--;) {
70  if (u[i] < minU) {
71  minU2 = minU;
72  minU = u[i];
73  } else if (u[i] < minU2)
74  minU2 = u[i];
75  if (u[i] > maxU)
76  maxU = u[i];
77  }
78  bool disjunctive =
79  (minU > c.max()/2) || (minU2 > c.max()/2 && minU+minU2>c.max());
80  if (disjunctive) {
81  GECODE_ME_FAIL(c.gq(home,maxU));
82  unary(home,t,s,p,icl);
83  } else {
84  bool fixp = true;
85  for (int i=t.size(); i--;)
86  if (t[i] != TT_FIXP) {
87  fixp = false; break;
88  }
89  int nonOptionals = 0;
90  for (unsigned int i=u.size(); i--;)
91  if (u[i]>0) nonOptionals++;
92  if (fixp) {
93  TaskArray<ManFixPTask> tasks(home,nonOptionals);
94  int cur = 0;
95  for (int i=0; i<s.size(); i++)
96  if (u[i] > 0)
97  tasks[cur++].init(s[i],p[i],u[i]);
99  } else {
100  TaskArray<ManFixPSETask> tasks(home,nonOptionals);
101  int cur = 0;
102  for (int i=s.size(); i--;)
103  if (u[i] > 0)
104  tasks[cur++].init(t[i],s[i],p[i],u[i]);
106  }
107  }
108  }
109 
110  void
111  cumulative(Home home, int c, const TaskTypeArgs& t,
112  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
113  IntConLevel icl) {
114  Int::Limits::nonnegative(c,"Int::cumulative");
115  cumulative(home,Int::ConstIntView(c),t,s,p,u,icl);
116  }
117  void
119  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
120  IntConLevel icl) {
121  if (c.assigned())
122  cumulative(home,c.val(),t,s,p,u,icl);
123  else
124  cumulative(home,Int::IntView(c),t,s,p,u,icl);
125  }
126 
127  template<class Cap>
128  void
129  cumulative(Home home, Cap c, const TaskTypeArgs& t,
130  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
131  const BoolVarArgs& m, IntConLevel icl) {
132  using namespace Gecode::Int;
133  using namespace Gecode::Int::Cumulative;
134  if ((s.size() != p.size()) || (s.size() != u.size()) ||
135  (s.size() != t.size()) || (s.size() != m.size()))
136  throw Int::ArgumentSizeMismatch("Int::cumulative");
137  long long int w = 0;
138  for (int i=p.size(); i--; ) {
139  Limits::nonnegative(p[i],"Int::cumulative");
140  Limits::nonnegative(u[i],"Int::cumulative");
141  Limits::check(static_cast<long long int>(s[i].max()) + p[i],
142  "Int::cumulative");
143  mul_check(p[i],u[i]);
144  w += s[i].width();
145  }
146  mul_check(c.max(),w,s.size());
147  if (home.failed()) return;
148 
149  bool allMandatory = true;
150  for (int i=m.size(); i--;) {
151  if (!m[i].one()) {
152  allMandatory = false;
153  break;
154  }
155  }
156  if (allMandatory) {
157  cumulative(home,c,t,s,p,u,icl);
158  } else {
159  bool fixp = true;
160  for (int i=t.size(); i--;)
161  if (t[i] != TT_FIXP) {
162  fixp = false; break;
163  }
164  int nonOptionals = 0;
165  for (unsigned int i=u.size(); i--;)
166  if (u[i]>0) nonOptionals++;
167  if (fixp) {
168  TaskArray<OptFixPTask> tasks(home,nonOptionals);
169  int cur = 0;
170  for (int i=0; i<s.size(); i++)
171  if (u[i]>0)
172  tasks[cur++].init(s[i],p[i],u[i],m[i]);
174  } else {
175  TaskArray<OptFixPSETask> tasks(home,nonOptionals);
176  int cur = 0;
177  for (int i=s.size(); i--;)
178  if (u[i]>0)
179  tasks[cur++].init(t[i],s[i],p[i],u[i],m[i]);
181  }
182  }
183  }
184 
185  void
186  cumulative(Home home, int c, const TaskTypeArgs& t,
187  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
188  const BoolVarArgs& m, IntConLevel icl) {
189  Int::Limits::nonnegative(c,"Int::cumulative");
190  cumulative(home,Int::ConstIntView(c),t,s,p,u,m,icl);
191  }
192  void
194  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
195  const BoolVarArgs& m, IntConLevel icl) {
196  if (c.assigned())
197  cumulative(home,c.val(),t,s,p,u,m,icl);
198  else
199  cumulative(home,Int::IntView(c),t,s,p,u,m,icl);
200  }
201 
202  template<class Cap>
203  void
204  cumulative(Home home, Cap c, const IntVarArgs& s,
205  const IntArgs& p, const IntArgs& u, IntConLevel icl) {
206  using namespace Gecode::Int;
207  using namespace Gecode::Int::Cumulative;
208  if ((s.size() != p.size()) || (s.size() != u.size()))
209  throw Int::ArgumentSizeMismatch("Int::cumulative");
210  long long int w = 0;
211  for (int i=p.size(); i--; ) {
212  Limits::nonnegative(p[i],"Int::cumulative");
213  Limits::nonnegative(u[i],"Int::cumulative");
214  Limits::check(static_cast<long long int>(s[i].max()) + p[i],
215  "Int::cumulative");
216  mul_check(p[i],u[i]);
217  w += s[i].width();
218  }
219  mul_check(c.max(),w,s.size());
220  if (home.failed()) return;
221 
222  int minU = INT_MAX; int minU2 = INT_MAX; int maxU = INT_MIN;
223  for (int i=u.size(); i--;) {
224  if (u[i] < minU) {
225  minU2 = minU;
226  minU = u[i];
227  } else if (u[i] < minU2)
228  minU2 = u[i];
229  if (u[i] > maxU)
230  maxU = u[i];
231  }
232  bool disjunctive =
233  (minU > c.max()/2) || (minU2 > c.max()/2 && minU+minU2>c.max());
234  if (disjunctive) {
235  GECODE_ME_FAIL(c.gq(home,maxU));
236  unary(home,s,p,icl);
237  } else {
238  int nonOptionals = 0;
239  for (unsigned int i=u.size(); i--;)
240  if (u[i]>0) nonOptionals++;
241  TaskArray<ManFixPTask> t(home,nonOptionals);
242  int cur = 0;
243  for (int i=0; i<s.size(); i++)
244  if (u[i]>0)
245  t[cur++].init(s[i],p[i],u[i]);
247  }
248  }
249 
250  void
251  cumulative(Home home, int c, const IntVarArgs& s,
252  const IntArgs& p, const IntArgs& u, IntConLevel icl) {
253  Int::Limits::nonnegative(c,"Int::cumulative");
254  cumulative(home,Int::ConstIntView(c),s,p,u,icl);
255  }
256  void
257  cumulative(Home home, IntVar c, const IntVarArgs& s,
258  const IntArgs& p, const IntArgs& u, IntConLevel icl) {
259  if (c.assigned())
260  cumulative(home,c.val(),s,p,u,icl);
261  else
262  cumulative(home,Int::IntView(c),s,p,u,icl);
263  }
264 
265  template<class Cap>
266  void
267  cumulative(Home home, Cap c, const IntVarArgs& s, const IntArgs& p,
268  const IntArgs& u, const BoolVarArgs& m, IntConLevel icl) {
269  using namespace Gecode::Int;
270  using namespace Gecode::Int::Cumulative;
271  if ((s.size() != p.size()) || (s.size() != u.size()) ||
272  (s.size() != m.size()))
273  throw Int::ArgumentSizeMismatch("Int::cumulative");
274  long long int w = 0;
275  for (int i=p.size(); i--; ) {
276  Limits::nonnegative(p[i],"Int::cumulative");
277  Limits::nonnegative(u[i],"Int::cumulative");
278  Limits::check(static_cast<long long int>(s[i].max()) + p[i],
279  "Int::cumulative");
280  mul_check(p[i],u[i]);
281  w += s[i].width();
282  }
283  mul_check(c.max(),w,s.size());
284  if (home.failed()) return;
285 
286  bool allMandatory = true;
287  for (int i=m.size(); i--;) {
288  if (!m[i].one()) {
289  allMandatory = false;
290  break;
291  }
292  }
293  if (allMandatory) {
294  cumulative(home,c,s,p,u,icl);
295  } else {
296  int nonOptionals = 0;
297  for (unsigned int i=u.size(); i--;)
298  if (u[i]>0) nonOptionals++;
299  TaskArray<OptFixPTask> t(home,nonOptionals);
300  int cur = 0;
301  for (int i=0; i<s.size(); i++)
302  if (u[i]>0)
303  t[cur++].init(s[i],p[i],u[i],m[i]);
305  }
306  }
307 
308  void
309  cumulative(Home home, int c, const IntVarArgs& s, const IntArgs& p,
310  const IntArgs& u, const BoolVarArgs& m, IntConLevel icl) {
311  Int::Limits::nonnegative(c,"Int::cumulative");
312  cumulative(home,Int::ConstIntView(c),s,p,u,m,icl);
313  }
314  void
315  cumulative(Home home, IntVar c, const IntVarArgs& s, const IntArgs& p,
316  const IntArgs& u, const BoolVarArgs& m, IntConLevel icl) {
317  if (c.assigned())
318  cumulative(home,c.val(),s,p,u,m,icl);
319  else
320  cumulative(home,Int::IntView(c),s,p,u,m,icl);
321  }
322 
323  template<class Cap>
324  void
325  cumulative(Home home, Cap c, const IntVarArgs& s,
326  const IntVarArgs& p, const IntVarArgs& e,
327  const IntArgs& u, IntConLevel icl) {
328  using namespace Gecode::Int;
329  using namespace Gecode::Int::Cumulative;
330  if ((s.size() != p.size()) || (s.size() != e.size()) ||
331  (s.size() != u.size()))
332  throw Int::ArgumentSizeMismatch("Int::cumulative");
333  long long int w = 0;
334  for (int i=p.size(); i--; ) {
335  rel(home, p[i], IRT_GQ, 0);
336  }
337  for (int i=p.size(); i--; ) {
338  Limits::nonnegative(u[i],"Int::cumulative");
339  Limits::check(static_cast<long long int>(s[i].max()) + p[i].max(),
340  "Int::cumulative");
341  mul_check(p[i].max(),u[i]);
342  w += s[i].width();
343  }
344  mul_check(c.max(),w,s.size());
345  if (home.failed()) return;
346 
347  bool fixP = true;
348  for (int i=p.size(); i--;) {
349  if (!p[i].assigned()) {
350  fixP = false;
351  break;
352  }
353  }
354  if (fixP) {
355  IntArgs pp(p.size());
356  for (int i=p.size(); i--;)
357  pp[i] = p[i].val();
358  cumulative(home,c,s,pp,u,icl);
359  } else {
360  int nonOptionals = 0;
361  for (unsigned int i=u.size(); i--;)
362  if (u[i]>0) nonOptionals++;
363  TaskArray<ManFlexTask> t(home,nonOptionals);
364  int cur = 0;
365  for (int i=0; i<s.size(); i++)
366  if (u[i]>0)
367  t[cur++].init(s[i],p[i],e[i],u[i]);
369  }
370  }
371 
372  void
373  cumulative(Home home, int c, const IntVarArgs& s,
374  const IntVarArgs& p, const IntVarArgs& e,
375  const IntArgs& u, IntConLevel icl) {
376  Int::Limits::nonnegative(c,"Int::cumulative");
377  cumulative(home,Int::ConstIntView(c),s,p,e,u,icl);
378  }
379  void
380  cumulative(Home home, IntVar c, const IntVarArgs& s,
381  const IntVarArgs& p, const IntVarArgs& e,
382  const IntArgs& u, IntConLevel icl) {
383  if (c.assigned())
384  cumulative(home,c.val(),s,p,e,u,icl);
385  else
386  cumulative(home,Int::IntView(c),s,p,e,u,icl);
387  }
388 
389  template<class Cap>
390  void
391  cumulative(Home home, Cap c, const IntVarArgs& s, const IntVarArgs& p,
392  const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
393  IntConLevel icl) {
394  using namespace Gecode::Int;
395  using namespace Gecode::Int::Cumulative;
396  if ((s.size() != p.size()) || (s.size() != u.size()) ||
397  (s.size() != e.size()) || (s.size() != m.size()))
398  throw Int::ArgumentSizeMismatch("Int::cumulative");
399  for (int i=p.size(); i--; ) {
400  rel(home, p[i], IRT_GQ, 0);
401  }
402  long long int w = 0;
403  for (int i=p.size(); i--; ) {
404  Limits::nonnegative(u[i],"Int::cumulative");
405  Limits::check(static_cast<long long int>(s[i].max()) + p[i].max(),
406  "Int::cumulative");
407  mul_check(p[i].max(),u[i]);
408  w += s[i].width();
409  }
410  mul_check(c.max(),w,s.size());
411  if (home.failed()) return;
412 
413  bool allMandatory = true;
414  for (int i=m.size(); i--;) {
415  if (!m[i].one()) {
416  allMandatory = false;
417  break;
418  }
419  }
420  if (allMandatory) {
421  cumulative(home,c,s,p,e,u,icl);
422  } else {
423  int nonOptionals = 0;
424  for (unsigned int i=u.size(); i--;)
425  if (u[i]>0) nonOptionals++;
426  TaskArray<OptFlexTask> t(home,nonOptionals);
427  int cur = 0;
428  for (int i=s.size(); i--; )
429  if (u[i]>0)
430  t[cur++].init(s[i],p[i],e[i],u[i],m[i]);
432  }
433  }
434 
435  void
436  cumulative(Home home, int c, const IntVarArgs& s, const IntVarArgs& p,
437  const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
438  IntConLevel icl) {
439  Int::Limits::nonnegative(c,"Int::cumulative");
440  cumulative(home,Int::ConstIntView(c),s,p,e,u,m,icl);
441  }
442  void
443  cumulative(Home home, IntVar c, const IntVarArgs& s, const IntVarArgs& p,
444  const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
445  IntConLevel icl) {
446  if (c.assigned())
447  cumulative(home,c.val(),s,p,e,u,m,icl);
448  else
449  cumulative(home,Int::IntView(c),s,p,e,u,m,icl);
450  }
451 
452 }
453 
454 // STATISTICS: int-post
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:3446
void cumulative(Home home, Cap c, const TaskTypeArgs &t, const IntVarArgs &s, const IntArgs &p, const IntArgs &u, IntConLevel icl)
Definition: cumulative.cpp:48
NodeType t
Type of node.
Definition: bool-expr.cpp:234
IntConLevel
Consistency levels for integer propagators.
Definition: int.hh:937
bool one(const Gecode::FloatValArgs &a)
Check whether has only one coefficients.
Definition: linear.cpp:50
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
Argument array for primtive types.
Definition: array.hpp:640
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
void nonnegative(int n, const char *l)
Check whether n is in range and nonnegative, otherwise throw out of limits with information l...
Definition: limits.hpp:72
Task array.
Definition: task.hh:167
Scheduling propagator for cumulative resource with optional tasks.
Definition: cumulative.hh:727
Greater or equal ( )
Definition: int.hh:908
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
Passing integer variables.
Definition: int.hh:636
Passing integer arguments.
Definition: int.hh:607
Passing Boolean variables.
Definition: int.hh:690
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
Constant integer view.
Definition: view.hpp:804
Integer view for integer variables.
Definition: view.hpp:129
Integer variables.
Definition: int.hh:350
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
void mul_check(long long int x, long long int y)
Throw exception if multiplication of x and y overflows.
Definition: limits.hpp:41
int val(void) const
Return assigned value.
Definition: int.hpp:60
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition: macros.hpp:70
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:123
Scheduling propagator for cumulative resource with mandatory tasks.
Definition: cumulative.hh:700
Gecode toplevel namespace
Finite domain integers.
Definition: abs.hpp:42
Scheduling for cumulative resources
Definition: basic.hpp:40
void check(int n, const char *l)
Check whether n is in range, otherwise throw out of limits with information l.
Definition: limits.hpp:50
Home class for posting propagators
Definition: core.hpp:717
Exception: Arguments are of different size
Definition: exception.hpp:77
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:96
void unary(Home home, const IntVarArgs &s, const IntArgs &p, IntConLevel icl)
Post propagators for scheduling tasks on unary resources.
Definition: unary.cpp:48