Generated on Sat Jun 2 2018 07:17:44 for Gecode by doxygen 1.8.13
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=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=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=t.size(); i--;)
80  if (t[i] != TT_FIXP) {
81  fixp = false; break;
82  }
83  int nonOptionals = 0;
84  for (int 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=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=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=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=t.size(); i--;)
138  if (t[i] != TT_FIXP) {
139  fixp = false; break;
140  }
141  int nonOptionals = 0;
142  for (int 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=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=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=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=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=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=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=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=p.size(); i--; ) {
265  rel(home, p[i], IRT_GQ, 0);
266  }
267  for (int i=p.size(); i--; ) {
268  Limits::nonnegative(u[i],"Int::cumulative");
269  Limits::check(static_cast<long long int>(s[i].max()) + p[i].max(),
270  "Int::cumulative");
271  mul_check(p[i].max(),u[i]);
272  w += s[i].width();
273  }
274  mul_check(c.max(),w,s.size());
275  GECODE_POST;
276 
277  bool fixP = true;
278  for (int 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=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=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  for (int i=p.size(); i--; ) {
313  rel(home, p[i], IRT_GQ, 0);
314  }
315  long long int w = 0;
316  for (int i=p.size(); i--; ) {
317  Limits::nonnegative(u[i],"Int::cumulative");
318  Limits::check(static_cast<long long int>(s[i].max()) + p[i].max(),
319  "Int::cumulative");
320  mul_check(p[i].max(),u[i]);
321  w += s[i].width();
322  }
323  mul_check(c.max(),w,s.size());
324  GECODE_POST;
325 
326  bool allMandatory = true;
327  for (int i=m.size(); i--;) {
328  if (!m[i].one()) {
329  allMandatory = false;
330  break;
331  }
332  }
333  if (allMandatory) {
334  cumulative(home,c,s,p,e,u,ipl);
335  } else {
336  int nonOptionals = 0;
337  for (int i=u.size(); i--;)
338  if (u[i]>0) nonOptionals++;
339  TaskArray<OptFlexTask> t(home,nonOptionals);
340  int cur = 0;
341  for (int i=s.size(); i--; )
342  if (u[i]>0)
343  t[cur++].init(s[i],p[i],e[i],u[i],m[i]);
344  GECODE_ES_FAIL(optpost(home,c,t,ipl));
345  }
346  }
347 
348 }}}
349 
350 namespace Gecode {
351 
352  void
353  cumulative(Home home, int c, const TaskTypeArgs& t,
354  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
355  IntPropLevel ipl) {
356  Int::Limits::nonnegative(c,"Int::cumulative");
357  Int::Cumulative::cumulative(home,Int::ConstIntView(c),t,s,p,u,ipl);
358  }
359 
360  void
362  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
363  IntPropLevel ipl) {
364  if (c.assigned())
365  cumulative(home,c.val(),t,s,p,u,ipl);
366  else
367  Int::Cumulative::cumulative(home,Int::IntView(c),t,s,p,u,ipl);
368  }
369 
370 
371  void
372  cumulative(Home home, int c, const TaskTypeArgs& t,
373  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
374  const BoolVarArgs& m, IntPropLevel ipl) {
375  Int::Limits::nonnegative(c,"Int::cumulative");
376  Int::Cumulative::cumulative(home,Int::ConstIntView(c),t,s,p,u,m,ipl);
377  }
378 
379  void
381  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
382  const BoolVarArgs& m, IntPropLevel ipl) {
383  if (c.assigned())
384  cumulative(home,c.val(),t,s,p,u,m,ipl);
385  else
386  Int::Cumulative::cumulative(home,Int::IntView(c),t,s,p,u,m,ipl);
387  }
388 
389 
390  void
391  cumulative(Home home, int c, const IntVarArgs& s,
392  const IntArgs& p, const IntArgs& u, IntPropLevel ipl) {
393  Int::Limits::nonnegative(c,"Int::cumulative");
395  }
396 
397  void
398  cumulative(Home home, IntVar c, const IntVarArgs& s,
399  const IntArgs& p, const IntArgs& u, IntPropLevel ipl) {
400  if (c.assigned())
401  cumulative(home,c.val(),s,p,u,ipl);
402  else
403  Int::Cumulative::cumulative(home,Int::IntView(c),s,p,u,ipl);
404  }
405 
406 
407  void
408  cumulative(Home home, int c, const IntVarArgs& s, const IntArgs& p,
409  const IntArgs& u, const BoolVarArgs& m, IntPropLevel ipl) {
410  Int::Limits::nonnegative(c,"Int::cumulative");
411  Int::Cumulative::cumulative(home,Int::ConstIntView(c),s,p,u,m,ipl);
412  }
413 
414  void
415  cumulative(Home home, IntVar c, const IntVarArgs& s, const IntArgs& p,
416  const IntArgs& u, const BoolVarArgs& m, IntPropLevel ipl) {
417  if (c.assigned())
418  cumulative(home,c.val(),s,p,u,m,ipl);
419  else
420  Int::Cumulative::cumulative(home,Int::IntView(c),s,p,u,m,ipl);
421  }
422 
423 
424  void
425  cumulative(Home home, int c, const IntVarArgs& s,
426  const IntVarArgs& p, const IntVarArgs& e,
427  const IntArgs& u, IntPropLevel ipl) {
428  Int::Limits::nonnegative(c,"Int::cumulative");
429  Int::Cumulative::cumulative(home,Int::ConstIntView(c),s,p,e,u,ipl);
430  }
431 
432  void
433  cumulative(Home home, IntVar c, const IntVarArgs& s,
434  const IntVarArgs& p, const IntVarArgs& e,
435  const IntArgs& u, IntPropLevel ipl) {
436  if (c.assigned())
437  cumulative(home,c.val(),s,p,e,u,ipl);
438  else
439  Int::Cumulative::cumulative(home,Int::IntView(c),s,p,e,u,ipl);
440  }
441 
442 
443  void
444  cumulative(Home home, int c, const IntVarArgs& s, const IntVarArgs& p,
445  const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
446  IntPropLevel ipl) {
447  Int::Limits::nonnegative(c,"Int::cumulative");
448  Int::Cumulative::cumulative(home,Int::ConstIntView(c),s,p,e,u,m,ipl);
449  }
450 
451  void
452  cumulative(Home home, IntVar c, const IntVarArgs& s, const IntVarArgs& p,
453  const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
454  IntPropLevel ipl) {
455  if (c.assigned())
456  cumulative(home,c.val(),s,p,e,u,m,ipl);
457  else
458  Int::Cumulative::cumulative(home,Int::IntView(c),s,p,e,u,m,ipl);
459  }
460 
461 }
462 
463 // STATISTICS: int-post
ExecStatus optpost(Home home, Cap c, TaskArray< OptTask > &t, IntPropLevel ipl)
Definition: post.hpp:53
NodeType t
Type of node.
Definition: bool-expr.cpp:230
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1653
bool one(const Gecode::FloatValArgs &a)
Check whether has only one coefficients.
Definition: linear.cpp:46
Argument array for primtive types.
Definition: array.hpp:624
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:119
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
Task array.
Definition: task.hh:165
Greater or equal ( )
Definition: int.hh:905
void cumulative(Home home, Cap c, const TaskTypeArgs &t, const IntVarArgs &s, const IntArgs &p, const IntArgs &u, IntPropLevel ipl)
Definition: cumulative.cpp:44
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
Gecode::IntArgs i(4, 1, 2, 3, 4)
int val(void) const
Return assigned value.
Definition: int.hpp:56
ExecStatus manpost(Home home, Cap c, TaskArray< ManTask > &t, IntPropLevel ipl)
Definition: post.hpp:38
union Gecode::@585::NNF::@62 u
Union depending on nodetype t.
Passing integer variables.
Definition: int.hh:633
Passing integer arguments.
Definition: int.hh:604
Passing Boolean variables.
Definition: int.hh:687
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:949
Constant integer view.
Definition: view.hpp:828
Integer view for integer variables.
Definition: view.hpp:129
Integer variables.
Definition: int.hh:347
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
void mul_check(long long int x, long long int y)
Throw exception if multiplication of x and y overflows.
Definition: limits.hpp:37
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition: macros.hpp:77
Gecode toplevel namespace
Finite domain integers.
Definition: abs.hpp:38
Scheduling for cumulative resources
#define GECODE_POST
Check for failure in a constraint post function.
Definition: macros.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:46
Home class for posting propagators
Definition: core.hpp:853
Exception: Arguments are of different size
Definition: exception.hpp:73
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:103
void unary(Home home, const IntVarArgs &s, const IntArgs &p, IntPropLevel ipl)
Post propagators for scheduling tasks on unary resources.
Definition: unary.cpp:44