Generated on for Gecode by doxygen 1.17.0
registry-scheduling.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.dev>
5 *
6 * Contributing authors:
7 * Mikael Zayenz Lagerkvist <lagerkvist@gmail.com>
8 *
9 * Copyright:
10 * Guido Tack, 2007
11 * Mikael Zayenz Lagerkvist, 2009
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.dev
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
39#include <gecode/minimodel.hh>
40
41namespace Gecode { namespace FlatZinc { namespace RegistryDetail {
42
44 AST::Node* ann) {
45 if (ce.size() == 6 || ce.size() == 7) {
46 // The seven-argument interface supplies end variables explicitly.
47 int offset = ce.size() == 7 ? 1 : 0;
48 IntVarArgs start = s.arg2intvarargs(ce[0]);
49 IntVarArgs duration = s.arg2intvarargs(ce[1]);
50 IntVarArgs resources = s.arg2intvarargs(ce[2+offset]);
51 IntVarArgs machine = s.arg2intvarargs(ce[3+offset]);
52 IntArgs bound = s.arg2intargs(ce[4+offset]);
53 bool upper = ce[5+offset]->getBool();
54 int n = start.size();
55
56 IntVarArgs end;
57 if (offset) {
58 end = s.arg2intvarargs(ce[2]);
59 } else {
60 end = IntVarArgs(n);
61 for (int i=n; i--;)
62 end[i] = expr(s, start[i] + duration[i]);
63 }
64
65 if (duration.assigned()) {
66 IntArgs durationI(n);
67 for (int i = n; (i--) != 0;) {
68 durationI[i] = duration[i].val();
69 }
70 if (machine.assigned()) {
71 IntArgs machineI(n);
72 for (int i = n; (i--) != 0;) {
73 machineI[i] = machine[i].val();
74 }
75 if (resources.assigned()) {
76 IntArgs resourcesI(n);
77 for (int i = n; (i--) != 0;) {
78 resourcesI[i] = resources[i].val();
79 }
80 cumulatives(s, machineI, start, durationI, end, resourcesI, bound, upper, s.ann2ipl(ann));
81 } else {
82 cumulatives(s, machineI, start, durationI, end, resources, bound, upper, s.ann2ipl(ann));
83 }
84 } else if (resources.assigned()) {
85 IntArgs resourcesI(n);
86 for (int i = n; (i--) != 0;) {
87 resourcesI[i] = resources[i].val();
88 }
89 cumulatives(s, machine, start, durationI, end, resourcesI, bound, upper, s.ann2ipl(ann));
90 } else {
91 cumulatives(s, machine, start, durationI, end, resources, bound, upper, s.ann2ipl(ann));
92 }
93 } else {
94 if (machine.assigned()) {
95 IntArgs machineI(n);
96 for (int i = n; (i--) != 0;) {
97 machineI[i] = machine[i].val();
98 }
99 if (resources.assigned()) {
100 IntArgs resourcesI(n);
101 for (int i = n; (i--) != 0;) {
102 resourcesI[i] = resources[i].val();
103 }
104 cumulatives(s, machineI, start, duration, end, resourcesI, bound, upper, s.ann2ipl(ann));
105 } else {
106 cumulatives(s, machineI, start, duration, end, resources, bound, upper, s.ann2ipl(ann));
107 }
108 } else if (resources.assigned()) {
109 IntArgs resourcesI(n);
110 for (int i = n; (i--) != 0;) {
111 resourcesI[i] = resources[i].val();
112 }
113 cumulatives(s, machine, start, duration, end, resourcesI, bound, upper, s.ann2ipl(ann));
114 } else {
115 cumulatives(s, machine, start, duration, end, resources, bound, upper, s.ann2ipl(ann));
116 }
117 }
118 return;
119 }
120
121 IntVarArgs start = s.arg2intvarargs(ce[0]);
122 IntVarArgs duration = s.arg2intvarargs(ce[1]);
123 IntVarArgs height = s.arg2intvarargs(ce[2]);
124 int n = start.size();
125 IntVar bound = s.arg2IntVar(ce[3]);
126
127 if (n==0)
128 return;
129
130 if (n == 1) {
131 rel(s, (duration[0] > 0) >> (height[0] <= bound));
132 return;
133 }
134
135 bool nonzeroDuration = true;
136 for (int i=0; i<n; i++) {
137 if (duration[i].min() <= 0) {
138 nonzeroDuration = false;
139 break;
140 }
141 }
142
143 int minHeight = std::min(height[0].min(),height[1].min());
144 int minHeight2 = std::max(height[0].min(),height[1].min());
145 for (int i=2; i<n; i++) {
146 if (height[i].min() < minHeight) {
147 minHeight2 = minHeight;
148 minHeight = height[i].min();
149 } else if (height[i].min() < minHeight2) {
150 minHeight2 = height[i].min();
151 }
152 }
153 bool disjunctive = nonzeroDuration && (
154 (minHeight > bound.max()/2) ||
155 (minHeight2 > bound.max()/2 && minHeight+minHeight2>bound.max()));
156 if (disjunctive) {
157 rel(s, bound >= max(height));
158 // Unary
159 if (duration.assigned()) {
160 IntArgs durationI(n);
161 for (int i=n; i--;)
162 durationI[i] = duration[i].val();
163 unshare(s,start);
164 unary(s,start,durationI,s.ann2ipl(ann));
165 } else {
166 IntVarArgs end(n);
167 for (int i=n; i--;)
168 end[i] = expr(s,start[i]+duration[i]);
169 unshare(s,start);
170 unary(s,start,duration,end,s.ann2ipl(ann));
171 }
172 } else if (nonzeroDuration && height.assigned()) {
173 IntArgs heightI(n);
174 for (int i=n; i--;)
175 heightI[i] = height[i].val();
176 if (duration.assigned()) {
177 IntArgs durationI(n);
178 for (int i=n; i--;)
179 durationI[i] = duration[i].val();
180 cumulative(s, bound, start, durationI, heightI, s.ann2ipl(ann));
181 } else {
182 IntVarArgs end(n);
183 for (int i = n; i--; )
184 end[i] = expr(s,start[i]+duration[i]);
185 cumulative(s, bound, start, duration, end, heightI, s.ann2ipl(ann));
186 }
187 } else if (nonzeroDuration && bound.assigned()) {
188 IntArgs machine = IntArgs::create(n,0,0);
189 IntArgs limit({bound.val()});
190 IntVarArgs end(n);
191 for (int i=n; i--;)
192 end[i] = expr(s,start[i]+duration[i]);
193 cumulatives(s, machine, start, duration, end, height, limit, true,
194 s.ann2ipl(ann));
195 } else {
198 IntVarArgs end(start.size());
199 for (int i = start.size(); i--; ) {
200 min = std::min(min, start[i].min());
201 max = std::max(max, start[i].max() + duration[i].max());
202 end[i] = expr(s, start[i] + duration[i]);
203 }
204 for (int time = min; time < max; ++time) {
205 IntVarArgs x(start.size());
206 for (int i = start.size(); i--; ) {
207 IntVar overlaps = channel(s, expr(s, (start[i] <= time) &&
208 (time < end[i])));
209 x[i] = expr(s, overlaps * height[i]);
210 }
211 linear(s, x, IRT_LQ, bound);
212 }
213 }
214 }
215
216}}}
217
218// STATISTICS: flatzinc-any
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1606
A node in a FlatZinc abstract syntax tree.
Definition ast.hh:67
Abstract representation of a constraint.
Definition conexpr.hh:43
int size(void) const
Return number of arguments.
Definition conexpr.hh:69
A space that can be initialized with a FlatZinc model.
Definition flatzinc.hh:424
IntVarArgs arg2intvarargs(AST::Node *arg, int offset=0)
Convert arg to IntVarArgs.
IntVar arg2IntVar(AST::Node *n)
Convert n to IntVar.
IntPropLevel ann2ipl(AST::Node *ann)
Convert ann to integer propagation level.
IntArgs arg2intargs(AST::Node *arg, int offset=0)
Convert arg (array of integers) to IntArgs.
Passing integer arguments.
Definition int.hh:653
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Definition array.hpp:76
Passing integer variables.
Definition int.hh:681
Integer variables.
Definition int.hh:390
int val(void) const
Return assigned value.
Definition int.hpp:56
int max(void) const
Return maximum of domain.
Definition int.hpp:70
bool assigned(void) const
Test if all variables are assigned.
Definition array.hpp:1922
bool assigned(void) const
Test whether view is assigned.
Definition var.hpp:111
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition linear.cpp:41
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
@ IRT_LQ
Less or equal ( ).
Definition int.hh:1228
void post_cumulatives(FlatZincSpace &s, const ConExpr &ce, AST::Node *ann)
Interpreter for the FlatZinc language.
const int min
Smallest allowed integer value.
Definition int.hh:123
const int max
Largest allowed integer value.
Definition int.hh:121
Gecode toplevel namespace
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition channel.cpp:41
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:988
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void cumulative(Home home, int c, const TaskTypeArgs &t, const IntVarArgs &flex, const IntArgs &fix, const IntArgs &u, IntPropLevel ipl=IPL_DEF)
Post propagators for scheduling tasks on cumulative resources.
void cumulatives(Home home, const IntVarArgs &m, const IntVarArgs &s, const IntVarArgs &p, const IntVarArgs &e, const IntVarArgs &u, const IntArgs &c, bool at_most, IntPropLevel ipl=IPL_DEF)
Post propagators for the cumulatives constraint.
void unshare(Home home, IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Replace multiple variable occurrences in x by fresh variables.
Definition unshare.cpp:136
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void unary(Home home, const IntVarArgs &s, const IntArgs &p, IntPropLevel ipl=IPL_DEF)
Post propagators for scheduling tasks on unary resources.
Definition unary.cpp:44