Generated on Mon Sep 17 2012 22:20:37 for Gecode by doxygen 1.8.1.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: 2011-07-14 02:56:36 +1000 (Thu, 14 Jul 2011) $ by $Author: tack $
13  * $Revision: 12195 $
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  double w = 0.0;
57  for (int i=p.size(); i--; ) {
58  Int::Limits::nonnegative(p[i],"Int::cumulative");
59  Int::Limits::nonnegative(u[i],"Int::cumulative");
60  Int::Limits::check(static_cast<double>(s[i].max()) + p[i],
61  "Int::cumulative");
62  Int::Limits::double_check(static_cast<double>(p[i]) * u[i],
63  "Int::cumulative");
64  w += s[i].width();
65  }
66  Int::Limits::double_check(c.max() * w * s.size(),
67  "Int::cumulative");
68  if (home.failed()) return;
69 
70  int minU = INT_MAX; int minU2 = INT_MAX; int maxU = INT_MIN;
71  for (int i=u.size(); i--;) {
72  if (u[i] < minU)
73  minU = u[i];
74  else if (u[i] < minU2)
75  minU2 = u[i];
76  if (u[i] > maxU)
77  maxU = u[i];
78  }
79  bool disjunctive =
80  (minU > c.max()/2) || (minU2 > c.max()/2 && minU+minU2>c.max());
81  if (disjunctive) {
82  GECODE_ME_FAIL(c.gq(home,maxU));
83  unary(home,t,s,p,icl);
84  } else {
85  bool fixp = true;
86  for (int i=t.size(); i--;)
87  if (t[i] != TT_FIXP) {
88  fixp = false; break;
89  }
90  if (fixp) {
91  TaskArray<ManFixPTask> tasks(home,s.size());
92  for (int i=0; i<s.size(); i++)
93  tasks[i].init(s[i],p[i],u[i]);
95  } else {
96  TaskArray<ManFixPSETask> tasks(home,s.size());
97  for (int i=s.size(); i--;)
98  tasks[i].init(t[i],s[i],p[i],u[i]);
100  }
101  }
102  }
103 
104  void
105  cumulative(Home home, int c, const TaskTypeArgs& t,
106  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
107  IntConLevel icl) {
108  Int::Limits::nonnegative(c,"Int::cumulative");
109  cumulative(home,Int::ConstIntView(c),t,s,p,u,icl);
110  }
111  void
113  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
114  IntConLevel icl) {
115  if (c.assigned())
116  cumulative(home,c.val(),t,s,p,u,icl);
117  else
118  cumulative(home,Int::IntView(c),t,s,p,u,icl);
119  }
120 
121  template<class Cap>
122  void
123  cumulative(Home home, Cap c, const TaskTypeArgs& t,
124  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
125  const BoolVarArgs& m, IntConLevel icl) {
126  using namespace Gecode::Int;
127  using namespace Gecode::Int::Cumulative;
128  if ((s.size() != p.size()) || (s.size() != u.size()) ||
129  (s.size() != t.size()) || (s.size() != m.size()))
130  throw Int::ArgumentSizeMismatch("Int::cumulative");
131  double w = 0.0;
132  for (int i=p.size(); i--; ) {
133  Int::Limits::nonnegative(p[i],"Int::cumulative");
134  Int::Limits::nonnegative(u[i],"Int::cumulative");
135  Int::Limits::check(static_cast<double>(s[i].max()) + p[i],
136  "Int::cumulative");
137  Int::Limits::double_check(static_cast<double>(p[i]) * u[i],
138  "Int::cumulative");
139  w += s[i].width();
140  }
141  Int::Limits::double_check(c.max() * w * s.size(),
142  "Int::cumulative");
143  if (home.failed()) return;
144 
145  bool allMandatory = true;
146  for (int i=m.size(); i--;) {
147  if (!m[i].one()) {
148  allMandatory = false;
149  break;
150  }
151  }
152  if (allMandatory) {
153  cumulative(home,c,t,s,p,u,icl);
154  } else {
155  bool fixp = true;
156  for (int i=t.size(); i--;)
157  if (t[i] != TT_FIXP) {
158  fixp = false; break;
159  }
160  if (fixp) {
161  TaskArray<OptFixPTask> tasks(home,s.size());
162  for (int i=0; i<s.size(); i++)
163  tasks[i].init(s[i],p[i],u[i],m[i]);
165  } else {
166  TaskArray<OptFixPSETask> tasks(home,s.size());
167  for (int i=s.size(); i--;)
168  tasks[i].init(t[i],s[i],p[i],u[i],m[i]);
170  }
171  }
172  }
173 
174  void
175  cumulative(Home home, int c, const TaskTypeArgs& t,
176  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
177  const BoolVarArgs& m, IntConLevel icl) {
178  Int::Limits::nonnegative(c,"Int::cumulative");
179  cumulative(home,Int::ConstIntView(c),t,s,p,u,m,icl);
180  }
181  void
183  const IntVarArgs& s, const IntArgs& p, const IntArgs& u,
184  const BoolVarArgs& m, IntConLevel icl) {
185  if (c.assigned())
186  cumulative(home,c.val(),t,s,p,u,m,icl);
187  else
188  cumulative(home,Int::IntView(c),t,s,p,u,m,icl);
189  }
190 
191  template<class Cap>
192  void
193  cumulative(Home home, Cap c, const IntVarArgs& s,
194  const IntArgs& p, const IntArgs& u, IntConLevel icl) {
195  using namespace Gecode::Int;
196  using namespace Gecode::Int::Cumulative;
197  if ((s.size() != p.size()) || (s.size() != u.size()))
198  throw Int::ArgumentSizeMismatch("Int::cumulative");
199  double w = 0.0;
200  for (int i=p.size(); i--; ) {
201  Int::Limits::nonnegative(p[i],"Int::cumulative");
202  Int::Limits::nonnegative(u[i],"Int::cumulative");
203  Int::Limits::check(static_cast<double>(s[i].max()) + p[i],
204  "Int::cumulative");
205  Int::Limits::double_check(static_cast<double>(p[i]) * u[i],
206  "Int::cumulative");
207  w += s[i].width();
208  }
209  Int::Limits::double_check(c.max() * w * s.size(),
210  "Int::cumulative");
211  if (home.failed()) return;
212 
213  int minU = INT_MAX; int minU2 = INT_MAX; int maxU = INT_MIN;
214  for (int i=u.size(); i--;) {
215  if (u[i] < minU)
216  minU = u[i];
217  else if (u[i] < minU2)
218  minU2 = u[i];
219  if (u[i] > maxU)
220  maxU = u[i];
221  }
222  bool disjunctive =
223  (minU > c.max()/2) || (minU2 > c.max()/2 && minU+minU2>c.max());
224  if (disjunctive) {
225  GECODE_ME_FAIL(c.gq(home,maxU));
226  unary(home,s,p,icl);
227  } else {
228  TaskArray<ManFixPTask> t(home,s.size());
229  for (int i=0; i<s.size(); i++) {
230  t[i].init(s[i],p[i],u[i]);
231  }
233  }
234  }
235 
236  void
237  cumulative(Home home, int c, const IntVarArgs& s,
238  const IntArgs& p, const IntArgs& u, IntConLevel icl) {
239  Int::Limits::nonnegative(c,"Int::cumulative");
240  cumulative(home,Int::ConstIntView(c),s,p,u,icl);
241  }
242  void
243  cumulative(Home home, IntVar c, const IntVarArgs& s,
244  const IntArgs& p, const IntArgs& u, IntConLevel icl) {
245  if (c.assigned())
246  cumulative(home,c.val(),s,p,u,icl);
247  else
248  cumulative(home,Int::IntView(c),s,p,u,icl);
249  }
250 
251  template<class Cap>
252  void
253  cumulative(Home home, Cap c, const IntVarArgs& s, const IntArgs& p,
254  const IntArgs& u, const BoolVarArgs& m, IntConLevel icl) {
255  using namespace Gecode::Int;
256  using namespace Gecode::Int::Cumulative;
257  if ((s.size() != p.size()) || (s.size() != u.size()) ||
258  (s.size() != m.size()))
259  throw Int::ArgumentSizeMismatch("Int::cumulative");
260  double w = 0.0;
261  for (int i=p.size(); i--; ) {
262  Int::Limits::nonnegative(p[i],"Int::cumulative");
263  Int::Limits::nonnegative(u[i],"Int::cumulative");
264  Int::Limits::check(static_cast<double>(s[i].max()) + p[i],
265  "Int::cumulative");
266  Int::Limits::double_check(static_cast<double>(p[i]) * u[i],
267  "Int::cumulative");
268  w += s[i].width();
269  }
270  Int::Limits::double_check(c.max() * w * s.size(),
271  "Int::cumulative");
272  if (home.failed()) return;
273 
274  bool allMandatory = true;
275  for (int i=m.size(); i--;) {
276  if (!m[i].one()) {
277  allMandatory = false;
278  break;
279  }
280  }
281  if (allMandatory) {
282  cumulative(home,c,s,p,u,icl);
283  } else {
284  TaskArray<OptFixPTask> t(home,s.size());
285  for (int i=0; i<s.size(); i++) {
286  t[i].init(s[i],p[i],u[i],m[i]);
287  }
289  }
290  }
291 
292  void
293  cumulative(Home home, int c, const IntVarArgs& s, const IntArgs& p,
294  const IntArgs& u, const BoolVarArgs& m, IntConLevel icl) {
295  Int::Limits::nonnegative(c,"Int::cumulative");
296  cumulative(home,Int::ConstIntView(c),s,p,u,m,icl);
297  }
298  void
299  cumulative(Home home, IntVar c, const IntVarArgs& s, const IntArgs& p,
300  const IntArgs& u, const BoolVarArgs& m, IntConLevel icl) {
301  if (c.assigned())
302  cumulative(home,c.val(),s,p,u,m,icl);
303  else
304  cumulative(home,Int::IntView(c),s,p,u,m,icl);
305  }
306 
307  template<class Cap>
308  void
309  cumulative(Home home, Cap c, const IntVarArgs& s,
310  const IntVarArgs& p, const IntVarArgs& e,
311  const IntArgs& u, IntConLevel icl) {
312  using namespace Gecode::Int;
313  using namespace Gecode::Int::Cumulative;
314  if ((s.size() != p.size()) || (s.size() != e.size()) ||
315  (s.size() != u.size()))
316  throw Int::ArgumentSizeMismatch("Int::cumulative");
317  double w = 0.0;
318  for (int i=p.size(); i--; ) {
319  rel(home, p[i], IRT_GQ, 0);
320  }
321  for (int i=p.size(); i--; ) {
322  Int::Limits::nonnegative(u[i],"Int::cumulative");
323  Int::Limits::check(static_cast<double>(s[i].max()) + p[i].max(),
324  "Int::cumulative");
325  Int::Limits::double_check(static_cast<double>(p[i].max()) * u[i],
326  "Int::cumulative");
327  w += s[i].width();
328  }
329  Int::Limits::double_check(c.max() * w * s.size(),
330  "Int::cumulative");
331  if (home.failed()) return;
332 
333  bool fixP = true;
334  for (int i=p.size(); i--;) {
335  if (!p[i].assigned()) {
336  fixP = false;
337  break;
338  }
339  }
340  if (fixP) {
341  IntArgs pp(p.size());
342  for (int i=p.size(); i--;)
343  pp[i] = p[i].val();
344  cumulative(home,c,s,pp,u,icl);
345  } else {
346  TaskArray<ManFlexTask> t(home,s.size());
347  for (int i=s.size(); i--; )
348  t[i].init(s[i],p[i],e[i],u[i]);
350  }
351  }
352 
353  void
354  cumulative(Home home, int c, const IntVarArgs& s,
355  const IntVarArgs& p, const IntVarArgs& e,
356  const IntArgs& u, IntConLevel icl) {
357  Int::Limits::nonnegative(c,"Int::cumulative");
358  cumulative(home,Int::ConstIntView(c),s,p,e,u,icl);
359  }
360  void
361  cumulative(Home home, IntVar c, const IntVarArgs& s,
362  const IntVarArgs& p, const IntVarArgs& e,
363  const IntArgs& u, IntConLevel icl) {
364  if (c.assigned())
365  cumulative(home,c.val(),s,p,e,u,icl);
366  else
367  cumulative(home,Int::IntView(c),s,p,e,u,icl);
368  }
369 
370  template<class Cap>
371  void
372  cumulative(Home home, Cap c, const IntVarArgs& s, const IntVarArgs& p,
373  const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
374  IntConLevel icl) {
375  using namespace Gecode::Int;
376  using namespace Gecode::Int::Cumulative;
377  if ((s.size() != p.size()) || (s.size() != u.size()) ||
378  (s.size() != e.size()) || (s.size() != m.size()))
379  throw Int::ArgumentSizeMismatch("Int::cumulative");
380  for (int i=p.size(); i--; ) {
381  rel(home, p[i], IRT_GQ, 0);
382  }
383  double w = 0.0;
384  for (int i=p.size(); i--; ) {
385  Int::Limits::nonnegative(u[i],"Int::cumulative");
386  Int::Limits::check(static_cast<double>(s[i].max()) + p[i].max(),
387  "Int::cumulative");
388  Int::Limits::double_check(static_cast<double>(p[i].max()) * u[i],
389  "Int::cumulative");
390  w += s[i].width();
391  }
392  Int::Limits::double_check(c.max() * w * s.size(),
393  "Int::cumulative");
394  if (home.failed()) return;
395 
396  bool allMandatory = true;
397  for (int i=m.size(); i--;) {
398  if (!m[i].one()) {
399  allMandatory = false;
400  break;
401  }
402  }
403  if (allMandatory) {
404  cumulative(home,c,s,p,e,u,icl);
405  } else {
406  TaskArray<OptFlexTask> t(home,s.size());
407  for (int i=s.size(); i--; )
408  t[i].init(s[i],p[i],e[i],u[i],m[i]);
410  }
411  }
412 
413  void
414  cumulative(Home home, int c, const IntVarArgs& s, const IntVarArgs& p,
415  const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
416  IntConLevel icl) {
417  Int::Limits::nonnegative(c,"Int::cumulative");
418  cumulative(home,Int::ConstIntView(c),s,p,e,u,m,icl);
419  }
420  void
421  cumulative(Home home, IntVar c, const IntVarArgs& s, const IntVarArgs& p,
422  const IntVarArgs& e, const IntArgs& u, const BoolVarArgs& m,
423  IntConLevel icl) {
424  if (c.assigned())
425  cumulative(home,c.val(),s,p,e,u,m,icl);
426  else
427  cumulative(home,Int::IntView(c),s,p,e,u,m,icl);
428  }
429 
430 }
431 
432 // STATISTICS: int-post