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