Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
edge-finding.hpp
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 * Contributing authors:
8 * Joseph Scott <joseph.scott@it.uu.se>
9 *
10 * Copyright:
11 * Christian Schulte, 2009
12 * Guido Tack, 2010
13 * Joseph Scott, 2011
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 <algorithm>
41
42namespace Gecode { namespace Int { namespace Cumulative {
43
45 template<class TaskView, bool inc>
46 class StoCap {
47 public:
49 bool operator ()(const TaskView& t1, const TaskView& t2) const {
50 return inc ? (t1.c() < t2.c()) : (t2.c() < t1.c());
51 }
52 };
53
55 class PrecOrder {
56 public:
57 int* prec;
59 PrecOrder(int* prec0) : prec(prec0) {}
61 bool operator ()(int i, int j) const {
62 return prec[i] > prec[j];
63 }
64 };
65
66 template<class TaskView>
70
71 Region r;
72
74 // Detection
75
76 int* prec = r.alloc<int>(t.size());
77 for (int i=0; i<t.size(); i++)
78 prec[i] = t[i].ect();
79
81
82 for (int j=0; j<t.size(); j++) {
83 while (!ol.lempty() &&
84 (ol.lenv() > static_cast<long long int>(c)*t[j].lct())) {
85 int i = ol.responsible();
86 prec[i] = std::max(prec[i], t[j].lct());
87 ol.lremove(i);
88 }
89 ol.shift(j);
90 }
91
93 // Propagation
94
95 // Compute array of unique capacities and a mapping
96 // from the task array to the corresponding entry in
97 // the capacity array
98
99 int* cap = r.alloc<int>(t.size());
100 for (int i=0; i<t.size(); i++)
101 cap[i] = i;
103 Support::quicksort(cap, t.size(), o);
104
105 int* capacities = r.alloc<int>(t.size());
106 int* capInv = r.alloc<int>(t.size());
107 for (int i=t.size(); i--;) {
108 capacities[cap[i]] = t[i].c();
109 capInv[cap[i]] = i;
110 }
111
112 int n_c = 0;
113 for (int i=0, cur_c=INT_MIN; i<t.size(); i++) {
114 if (capacities[i] != cur_c)
115 capacities[n_c++] = cur_c = capacities[i];
116 cap[capInv[i]] = n_c-1;
117 }
118 r.free<int>(capInv, t.size());
119
120 // Compute update values for each capacity and LCut
121
122 int* update = r.alloc<int>(t.size()*n_c);
123 for (int i=0; i<t.size()*n_c; i++)
125
126 ExtOmegaTree<TaskView> eo(r,c,ol);
127 for (int i=0; i<n_c; i++) {
128 eo.init(capacities[i]);
129 int u = -Limits::infinity;
130 for (int j=t.size(); j--;) {
131 long long int lctj =
132 static_cast<long long int>(c-capacities[i])*t[j].lct();
133 long long int eml = plus(eo.env(j), -lctj);
134 long long int diff_l;
135 if (eml == -Limits::llinfinity)
136 diff_l = -Limits::llinfinity;
137 else
138 diff_l = ceil_div_xx(eml,
139 static_cast<long long int>(capacities[i]));
140 int diff = (diff_l <= -Limits::infinity) ?
141 -Limits::infinity : static_cast<int>(diff_l);
142 u = std::max(u,diff);
143 update[i*t.size()+j] = u;
144 }
145 }
146
147 // Update est by iterating in parallel over the prec array
148 // and the task array, both sorted by lct
149
150 int* precMap = r.alloc<int>(t.size());
151 for (int i=0; i<t.size(); i++)
152 precMap[i] = i;
153 PrecOrder po(prec);
154 Support::quicksort(precMap, t.size(), po);
155
156 int curJ = 0;
157 for (int i=0; i<t.size(); i++) {
158 // discard any curJ with lct > prec[i]:
159 while (curJ < t.size() && t[curJ].lct() > prec[precMap[i]])
160 curJ++;
161 if (curJ >= t.size())
162 break;
163 // if lct[curJ] == prec[i], then LCut(T,j) <= i, so update est[i]
164 int locJ = curJ;
165 do {
166 if (t[locJ].lct() != t[precMap[i]].lct()) {
167 GECODE_ME_CHECK(t[precMap[i]].est(home,update[cap[precMap[i]]*t.size()+locJ]));
168 break;
169 }
170 } while (t[locJ].lct() == prec[precMap[i]] && locJ++ < t.size() - 1);
171 }
172
173 return ES_OK;
174 }
175
176 template<class Task>
185
186}}}
187
188// STATISTICS: int-prop
Omega trees for computing ect of task sets.
long long int env(int i)
Compute update for task with index i.
Definition tree.hpp:120
void init(int ci)
Initialize tasks for current capacity ci.
Definition tree.hpp:104
Omega-lambda trees for computing ect of task sets.
int responsible(void) const
Return responsible task.
Definition tree.hpp:254
long long int lenv(void) const
Return energy envelope of all tasks excluding lambda tasks.
Definition tree.hpp:266
void shift(int i)
Shift task with index i from omega to lambda.
Definition tree.hpp:221
void lremove(int i)
Remove task with index i from lambda.
Definition tree.hpp:235
bool lempty(void) const
Whether has responsible task.
Definition tree.hpp:248
PrecOrder(int *prec0)
Constructor.
bool operator()(int i, int j) const
Sort order.
bool operator()(const TaskView &t1, const TaskView &t2) const
Sort order.
Sorting maps rather than tasks.
Definition sort.hpp:72
Task array.
Definition task.hh:165
Task view array.
Definition task.hh:233
int size(void) const
Return size of array (number of elements)
Definition array.hpp:142
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1744
void update(const NoOffset &)
Integer-precision integer scale view.
Definition view.hpp:638
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
Scheduling for cumulative resources
ExecStatus edgefinding(Space &home, int c, TaskArray< Task > &t)
Propagate by edge-finding.
const int infinity
Infinity for integers.
Definition int.hh:120
const long long int llinfinity
Infinity for long long integers.
Definition int.hh:126
Finite domain integers.
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing)
Definition sort.hpp:133
int plus(int x, int y)
Safe addition in case x is -Int::Limits::infinity.
Definition tree.hpp:39
IntType ceil_div_xx(IntType x, IntType y)
Compute .
Definition div.hpp:82
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
#define forceinline
Definition config.hpp:194