Generated on Wed Jan 1 2020 10:37:59 for Gecode by doxygen 1.8.16
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  * This file is part of Gecode, the generic constraint
12  * development environment:
13  * http://www.gecode.org
14  *
15  * Permission is hereby granted, free of charge, to any person obtaining
16  * a copy of this software and associated documentation files (the
17  * "Software"), to deal in the Software without restriction, including
18  * without limitation the rights to use, copy, modify, merge, publish,
19  * distribute, sublicense, and/or sell copies of the Software, and to
20  * permit persons to whom the Software is furnished to do so, subject to
21  * the following conditions:
22  *
23  * The above copyright notice and this permission notice shall be
24  * included in all copies or substantial portions of the Software.
25  *
26  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33  *
34  */
35 
36 #include <gecode/int/cumulative.hh>
37 
38 #include <algorithm>
39 
40 namespace Gecode { namespace Int { namespace Cumulative {
41 
42  template<class Cap>
43  void
44  cumulative(Home home, Cap c, const TaskTypeArgs& t,
45  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
46  IntPropLevel ipl) {
47  if ((s.size() != p.size()) || (s.size() != u.size()) ||
48  (s.size() != t.size()))
49  throw ArgumentSizeMismatch("Int::cumulative");
50  long long int w = 0;
51  for (int i=0; i<p.size(); i++) {
52  Limits::nonnegative(p[i],"Int::cumulative");
53  Limits::nonnegative(u[i],"Int::cumulative");
54  Limits::check(static_cast<long long int>(s[i].max()) + p[i],
55  "Int::cumulative");
56  mul_check(p[i],u[i]);
57  w += s[i].width();
58  }
59  mul_check(c.max(),w,s.size());
61 
62  int minU = INT_MAX; int minU2 = INT_MAX; int maxU = INT_MIN;
63  for (int i=0; i<u.size(); i++) {
64  if (u[i] < minU) {
65  minU2 = minU;
66  minU = u[i];
67  } else if (u[i] < minU2)
68  minU2 = u[i];
69  if (u[i] > maxU)
70  maxU = u[i];
71  }
72  bool disjunctive =
73  (minU > c.max()/2) || (minU2 > c.max()/2 && minU+minU2>c.max());
74  if (disjunctive) {
75  GECODE_ME_FAIL(c.gq(home,maxU));
76  unary(home,t,s,p,ipl);
77  } else {
78  bool fixp = true;
79  for (int i=0; i<t.size(); i++)
80  if (t[i] != TT_FIXP) {
81  fixp = false; break;
82  }
83  int nonOptionals = 0;
84  for (int i=0; i<u.size(); i++)
85  if (u[i]>0) nonOptionals++;
86  if (fixp) {
87  TaskArray<ManFixPTask> tasks(home,nonOptionals);
88  int cur = 0;
89  for (int i=0; i<s.size(); i++)
90  if (u[i] > 0)
91  tasks[cur++].init(s[i],p[i],u[i]);
92  GECODE_ES_FAIL(manpost(home,c,tasks,ipl));
93  } else {
94  TaskArray<ManFixPSETask> tasks(home,nonOptionals);
95  int cur = 0;
96  for (int i=0; i<s.size(); i++)
97  if (u[i] > 0)
98  tasks[cur++].init(t[i],s[i],p[i],u[i]);
99  GECODE_ES_FAIL(manpost(home,c,tasks,ipl));
100  }
101  }
102  }
103 
104  template<class Cap>
105  void
106  cumulative(Home home, Cap c, const TaskTypeArgs& t,
107  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
108  const BoolVarArgs& m, IntPropLevel ipl) {
109  using namespace Gecode::Int;
110  using namespace Gecode::Int::Cumulative;
111  if ((s.size() != p.size()) || (s.size() != u.size()) ||
112  (s.size() != t.size()) || (s.size() != m.size()))
113  throw Int::ArgumentSizeMismatch("Int::cumulative");
114  long long int w = 0;
115  for (int i=0; i<p.size(); i++) {
116  Limits::nonnegative(p[i],"Int::cumulative");
117  Limits::nonnegative(u[i],"Int::cumulative");
118  Limits::check(static_cast<long long int>(s[i].max()) + p[i],
119  "Int::cumulative");
120  mul_check(p[i],u[i]);
121  w += s[i].width();
122  }
123  mul_check(c.max(),w,s.size());
124  GECODE_POST;
125 
126  bool allMandatory = true;
127  for (int i=0; i<m.size(); i++) {
128  if (!m[i].one()) {
129  allMandatory = false;
130  break;
131  }
132  }
133  if (allMandatory) {
134  cumulative(home,c,t,s,p,u,ipl);
135  } else {
136  bool fixp = true;
137  for (int i=0; i<t.size(); i++)
138  if (t[i] != TT_FIXP) {
139  fixp = false; break;
140  }
141  int nonOptionals = 0;
142  for (int i=0; i<u.size(); i++)
143  if (u[i]>0) nonOptionals++;
144  if (fixp) {
145  TaskArray<OptFixPTask> tasks(home,nonOptionals);
146  int cur = 0;
147  for (int i=0; i<s.size(); i++)
148  if (u[i]>0)
149  tasks[cur++].init(s[i],p[i],u[i],m[i]);
150  GECODE_ES_FAIL(optpost(home,c,tasks,ipl));
151  } else {
152  TaskArray<OptFixPSETask> tasks(home,nonOptionals);
153  int cur = 0;
154  for (int i=0; i<s.size(); i++)
155  if (u[i]>0)
156  tasks[cur++].init(t[i],s[i],p[i],u[i],m[i]);
157  GECODE_ES_FAIL(optpost(home,c,tasks,ipl));
158  }
159  }
160  }
161 
162  template<class Cap>
163  void
164  cumulative(Home home, Cap c, const IntVarArgs& s,
165  const IntArgs& p, const IntArgs& u, IntPropLevel ipl) {
166  using namespace Gecode::Int;
167  using namespace Gecode::Int::Cumulative;
168  if ((s.size() != p.size()) || (s.size() != u.size()))
169  throw Int::ArgumentSizeMismatch("Int::cumulative");
170  long long int w = 0;
171  for (int i=0; i<p.size(); i++) {
172  Limits::nonnegative(p[i],"Int::cumulative");
173  Limits::nonnegative(u[i],"Int::cumulative");
174  Limits::check(static_cast<long long int>(s[i].max()) + p[i],
175  "Int::cumulative");
176  mul_check(p[i],u[i]);
177  w += s[i].width();
178  }
179  mul_check(c.max(),w,s.size());
180  GECODE_POST;
181 
182  int minU = INT_MAX; int minU2 = INT_MAX; int maxU = INT_MIN;
183  for (int i=0; i<u.size(); i++) {
184  if (u[i] < minU) {
185  minU2 = minU;
186  minU = u[i];
187  } else if (u[i] < minU2)
188  minU2 = u[i];
189  if (u[i] > maxU)
190  maxU = u[i];
191  }
192  bool disjunctive =
193  (minU > c.max()/2) || (minU2 > c.max()/2 && minU+minU2>c.max());
194  if (disjunctive) {
195  GECODE_ME_FAIL(c.gq(home,maxU));
196  unary(home,s,p,ipl);
197  } else {
198  int nonOptionals = 0;
199  for (int i=0; i<u.size(); i++)
200  if (u[i]>0) nonOptionals++;
201  TaskArray<ManFixPTask> t(home,nonOptionals);
202  int cur = 0;
203  for (int i=0; i<s.size(); i++)
204  if (u[i]>0)
205  t[cur++].init(s[i],p[i],u[i]);
206  GECODE_ES_FAIL(manpost(home,c,t,ipl));
207  }
208  }
209 
210  template<class Cap>
211  void
212  cumulative(Home home, Cap c, const IntVarArgs& s, const IntArgs& p,
213  const IntArgs& u, const BoolVarArgs& m, IntPropLevel ipl) {
214  using namespace Gecode::Int;
215  using namespace Gecode::Int::Cumulative;
216  if ((s.size() != p.size()) || (s.size() != u.size()) ||
217  (s.size() != m.size()))
218  throw Int::ArgumentSizeMismatch("Int::cumulative");
219  long long int w = 0;
220  for (int i=0; i<p.size(); i++) {
221  Limits::nonnegative(p[i],"Int::cumulative");
222  Limits::nonnegative(u[i],"Int::cumulative");
223  Limits::check(static_cast<long long int>(s[i].max()) + p[i],
224  "Int::cumulative");
225  mul_check(p[i],u[i]);
226  w += s[i].width();
227  }
228  mul_check(c.max(),w,s.size());
229  GECODE_POST;
230 
231  bool allMandatory = true;
232  for (int i=0; i<m.size(); i++) {
233  if (!m[i].one()) {
234  allMandatory = false;
235  break;
236  }
237  }
238  if (allMandatory) {
239  cumulative(home,c,s,p,u,ipl);
240  } else {
241  int nonOptionals = 0;
242  for (int i=0; i<u.size(); i++)
243  if (u[i]>0) nonOptionals++;
244  TaskArray<OptFixPTask> t(home,nonOptionals);
245  int cur = 0;
246  for (int i=0; i<s.size(); i++)
247  if (u[i]>0)
248  t[cur++].init(s[i],p[i],u[i],m[i]);
249  GECODE_ES_FAIL(optpost(home,c,t,ipl));
250  }
251  }
252 
253  template<class Cap>
254  void
255  cumulative(Home home, Cap c, const IntVarArgs& s,
256  const IntVarArgs& p, const IntVarArgs& e,
257  const IntArgs& u, IntPropLevel ipl) {
258  using namespace Gecode::Int;
259  using namespace Gecode::Int::Cumulative;
260  if ((s.size() != p.size()) || (s.size() != e.size()) ||
261  (s.size() != u.size()))
262  throw Int::ArgumentSizeMismatch("Int::cumulative");
263  long long int w = 0;
264  for (int i=0; i<p.size(); i++) {
265  Limits::nonnegative(u[i],"Int::cumulative");
266  Limits::check(static_cast<long long int>(s[i].max()) + p[i].max(),
267  "Int::cumulative");
268  mul_check(p[i].max(),u[i]);
269  w += s[i].width();
270  }
271  mul_check(c.max(),w,s.size());
272 
273  GECODE_POST;
274  for (int i=0; i<p.size(); i++)
275  GECODE_ME_FAIL(IntView(p[i]).gq(home,0));
276 
277  bool fixP = true;
278  for (int i=0; i<p.size(); i++) {
279  if (!p[i].assigned()) {
280  fixP = false;
281  break;
282  }
283  }
284  if (fixP) {
285  IntArgs pp(p.size());
286  for (int i=0; i<p.size(); i++)
287  pp[i] = p[i].val();
288  cumulative(home,c,s,pp,u,ipl);
289  } else {
290  int nonOptionals = 0;
291  for (int i=0; i<u.size(); i++)
292  if (u[i]>0) nonOptionals++;
293  TaskArray<ManFlexTask> t(home,nonOptionals);
294  int cur = 0;
295  for (int i=0; i<s.size(); i++)
296  if (u[i]>0)
297  t[cur++].init(s[i],p[i],e[i],u[i]);
298  GECODE_ES_FAIL(manpost(home,c,t,ipl));
299  }
300  }
301 
302  template<class Cap>
303  void
304  cumulative(Home home, Cap c, const IntVarArgs& s, const IntVarArgs& p,
305  const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
306  IntPropLevel ipl) {
307  using namespace Gecode::Int;
308  using namespace Gecode::Int::Cumulative;
309  if ((s.size() != p.size()) || (s.size() != u.size()) ||
310  (s.size() != e.size()) || (s.size() != m.size()))
311  throw Int::ArgumentSizeMismatch("Int::cumulative");
312 
313  long long int w = 0;
314  for (int i=0; i<p.size(); i++) {
315  Limits::nonnegative(u[i],"Int::cumulative");
316  Limits::check(static_cast<long long int>(s[i].max()) + p[i].max(),
317  "Int::cumulative");
318  mul_check(p[i].max(),u[i]);
319  w += s[i].width();
320  }
321  mul_check(c.max(),w,s.size());
322 
323  GECODE_POST;
324  for (int i=0; i<p.size(); i++)
325  GECODE_ME_FAIL(IntView(p[i]).gq(home,0));
326 
327  bool allMandatory = true;
328  for (int i=0; i<m.size(); i++) {
329  if (!m[i].one()) {
330  allMandatory = false;
331  break;
332  }
333  }
334  if (allMandatory) {
335  cumulative(home,c,s,p,e,u,ipl);
336  } else {
337  int nonOptionals = 0;
338  for (int i=0; i<u.size(); i++)
339  if (u[i]>0) nonOptionals++;
340  TaskArray<OptFlexTask> t(home,nonOptionals);
341  int cur = 0;
342  for (int i=0; i<s.size(); i++)
343  if (u[i]>0)
344  t[cur++].init(s[i],p[i],e[i],u[i],m[i]);
345  GECODE_ES_FAIL(optpost(home,c,t,ipl));
346  }
347  }
348 
349 }}}
350 
351 namespace Gecode {
352 
353  void
354  cumulative(Home home, int c, const TaskTypeArgs& t,
355  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
356  IntPropLevel ipl) {
357  Int::Limits::nonnegative(c,"Int::cumulative");
359  }
360 
361  void
363  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
364  IntPropLevel ipl) {
365  if (c.assigned())
366  cumulative(home,c.val(),t,s,p,u,ipl);
367  else
369  }
370 
371 
372  void
373  cumulative(Home home, int c, const TaskTypeArgs& t,
374  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
375  const BoolVarArgs& m, IntPropLevel ipl) {
376  Int::Limits::nonnegative(c,"Int::cumulative");
378  }
379 
380  void
382  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
383  const BoolVarArgs& m, IntPropLevel ipl) {
384  if (c.assigned())
385  cumulative(home,c.val(),t,s,p,u,m,ipl);
386  else
388  }
389 
390 
391  void
392  cumulative(Home home, int c, const IntVarArgs& s,
393  const IntArgs& p, const IntArgs& u, IntPropLevel ipl) {
394  Int::Limits::nonnegative(c,"Int::cumulative");
396  }
397 
398  void
399  cumulative(Home home, IntVar c, const IntVarArgs& s,
400  const IntArgs& p, const IntArgs& u, IntPropLevel ipl) {
401  if (c.assigned())
402  cumulative(home,c.val(),s,p,u,ipl);
403  else
405  }
406 
407 
408  void
409  cumulative(Home home, int c, const IntVarArgs& s, const IntArgs& p,
410  const IntArgs& u, const BoolVarArgs& m, IntPropLevel ipl) {
411  Int::Limits::nonnegative(c,"Int::cumulative");
413  }
414 
415  void
416  cumulative(Home home, IntVar c, const IntVarArgs& s, const IntArgs& p,
417  const IntArgs& u, const BoolVarArgs& m, IntPropLevel ipl) {
418  if (c.assigned())
419  cumulative(home,c.val(),s,p,u,m,ipl);
420  else
422  }
423 
424 
425  void
426  cumulative(Home home, int c, const IntVarArgs& s,
427  const IntVarArgs& p, const IntVarArgs& e,
428  const IntArgs& u, IntPropLevel ipl) {
429  Int::Limits::nonnegative(c,"Int::cumulative");
431  }
432 
433  void
434  cumulative(Home home, IntVar c, const IntVarArgs& s,
435  const IntVarArgs& p, const IntVarArgs& e,
436  const IntArgs& u, IntPropLevel ipl) {
437  if (c.assigned())
438  cumulative(home,c.val(),s,p,e,u,ipl);
439  else
441  }
442 
443 
444  void
445  cumulative(Home home, int c, const IntVarArgs& s, const IntVarArgs& p,
446  const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
447  IntPropLevel ipl) {
448  Int::Limits::nonnegative(c,"Int::cumulative");
450  }
451 
452  void
453  cumulative(Home home, IntVar c, const IntVarArgs& s, const IntVarArgs& p,
454  const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
455  IntPropLevel ipl) {
456  if (c.assigned())
457  cumulative(home,c.val(),s,p,e,u,m,ipl);
458  else
459  Int::Cumulative::cumulative(home,Int::IntView(c),s,p,e,u,m,ipl);
460  }
461 
462 }
463 
464 // STATISTICS: int-post
ExecStatus manpost(Home home, Cap c, TaskArray< ManTask > &t, IntPropLevel ipl)
Definition: post.hpp:38
Exception: Arguments are of different size
Definition: exception.hpp:73
Constant integer view.
Definition: view.hpp:851
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:103
ExecStatus optpost(Home home, Cap c, TaskArray< OptTask > &t, IntPropLevel ipl)
Definition: post.hpp:53
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
Create c
Definition: cumulative.cpp:579
Passing integer variables.
Definition: int.hh:656
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
void cumulative(Home home, Cap c, const TaskTypeArgs &t, const IntVarArgs &s, const IntArgs &p, const IntArgs &u, IntPropLevel ipl)
Definition: cumulative.cpp:44
NodeType t
Type of node.
Definition: bool-expr.cpp:230
void check(int n, const char *l)
Check whether n is in range, otherwise throw out of limits with information l.
Definition: limits.hpp:46
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:974
union Gecode::@602::NNF::@65 u
Union depending on nodetype t.
Gecode toplevel namespace
Argument array for non-primitive types.
Definition: array.hpp:656
void mul_check(long long int x, long long int y)
Throw exception if multiplication of x and y overflows.
Definition: limits.hpp:37
Passing Boolean variables.
Definition: int.hh:712
Home class for posting propagators
Definition: core.hpp:856
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:68
bool one(const Gecode::FloatValArgs &a)
Check whether has only one coefficients.
Definition: linear.cpp:46
Integer variables.
Definition: int.hh:371
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1607
#define GECODE_POST
Check for failure in a constraint post function.
Definition: macros.hpp:40
Integer view for integer variables.
Definition: view.hpp:129
Task array.
Definition: task.hh:165
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition: macros.hpp:77
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:139
Definition: int.hh:1005
Passing integer arguments.
Definition: int.hh:628
Gecode::IntArgs i({1, 2, 3, 4})
void unary(Home home, const IntVarArgs &s, const IntArgs &p, IntPropLevel ipl)
Post propagators for scheduling tasks on unary resources.
Definition: unary.cpp:44
Scheduling for cumulative resources
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
Finite domain integers.
Definition: abs.hpp:38