Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
argmax.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 *
6 * Copyright:
7 * Christian Schulte, 2015
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/int/rel.hh>
35
36namespace Gecode { namespace Int { namespace Arithmetic {
37
38 template<class VA, class VB, bool tiebreak>
41 : Propagator(home), x(x0), y(y0) {
42 x.subscribe(home,*this,PC_INT_BND);
43 y.subscribe(home,*this,PC_INT_DOM);
44 }
45
46 template<class VA, class VB, bool tiebreak>
49 assert(x.size() > 0);
50 if (x.size() == 1) {
51 GECODE_ME_CHECK(y.eq(home,x[0].idx));
52 } else if (y.assigned()) {
53 int max=0;
54 while (x[max].idx < y.val())
55 max++;
56 assert(x[max].idx == y.val());
57 if (tiebreak)
58 for (int i=0; i<max; i++)
60 x[i].view,x[max].view)));
61 else
62 for (int i=0; i<max; i++)
64 x[i].view,x[max].view)));
65 for (int i=max+1; i<x.size(); i++)
67 x[i].view,x[max].view)));
68 } else {
69 (void) new (home) ArgMax<VA,VB,tiebreak>(home,x,y);
70 }
71 return ES_OK;
72 }
73
74 template<class VA, class VB, bool tiebreak>
77 : Propagator(home,p) {
78 x.update(home,p.x);
79 y.update(home,p.y);
80 }
81
82 template<class VA, class VB, bool tiebreak>
83 Actor*
85 return new (home) ArgMax<VA,VB,tiebreak>(home,*this);
86 }
87
88 template<class VA, class VB, bool tiebreak>
91 return PropCost::linear(PropCost::LO,x.size()+1);
92 }
93
94 template<class VA, class VB, bool tiebreak>
95 void
97 x.reschedule(home,*this,PC_INT_BND);
98 y.reschedule(home,*this,PC_INT_DOM);
99 }
100
101 template<class VA, class VB, bool tiebreak>
104 /*
105 * A key invariant is as follows: for each value i in the domain
106 * of y there is an index-value pair with index i in x.
107 */
108
109 // Compute lower and upper bounds for the maximum and its first position.
110 int p = x[0].idx;
111 int l = x[0].view.min();
112 int u = x[0].view.max();
113 for (int i=1; i<x.size(); i++) {
114 if (l < x[i].view.min()) {
115 p = x[i].idx; l = x[i].view.min();
116 }
117 if (u < x[i].view.max())
118 u = x[i].view.max();
119 }
120
121 // Eliminate elements from x and y that are too small
122 {
123 Region r;
124
125 // Values to delete from y
126 int* d=r.alloc<int>(y.size());
127 // Number of values to delete
128 int n = 0;
129
130 int i=0, j=0;
131 ViewValues<VB> iy(y);
132
133 while ((i < x.size()) && iy()) {
134 if (x[i].idx == iy.val()) {
135 if (x[i].view.max() < l) {
136 x[i].view.cancel(home,*this,PC_INT_BND);
137 d[n++]=x[i].idx;
138 } else {
139 x[j++]=x[i];
140 }
141 ++iy;
142 } else {
143 assert(x[i].idx < iy.val());
144 if (x[i].view.max() < l) {
145 x[i].view.cancel(home,*this,PC_INT_BND);
146 } else {
147 x[j++]=x[i];
148 }
149 }
150 i++;
151 }
152 while (i < x.size())
153 if (x[i].view.max() < l) {
154 x[i].view.cancel(home,*this,PC_INT_BND); i++;
155 } else {
156 x[j++]=x[i++];
157 }
158 x.size(j);
159
160 if (static_cast<unsigned int>(n) == y.size())
161 return ES_FAILED;
163 GECODE_ME_CHECK(y.minus_v(home,id,false));
164 }
165
166 /*
167 * Now the following invariant holds:
168 * - for all q in y: u >= x(q).max() >= l
169 * - if l==u, then exists q in y: x(q).max = u
170 */
171
172 if (tiebreak && (l == u))
173 GECODE_ME_CHECK(y.lq(home,p));
174
175 if (y.assigned()) {
176 int max=0;
177 while (x[max].idx < y.val())
178 max++;
179 assert(x[max].idx == y.val());
180 if (tiebreak)
181 for (int i=0; i<max; i++)
183 x[i].view,x[max].view)));
184 else
185 for (int i=0; i<max; i++)
187 x[i].view,x[max].view)));
188 for (int i=max+1; i<x.size(); i++)
190 x[i].view,x[max].view)));
191 return home.ES_SUBSUMED(*this);
192 }
193
194 // Recompute the upper bound for elements in y
195 {
196 ViewValues<VB> iy(y);
197 int i=0;
198 // Skip smaller elements
199 while (x[i].idx < y.min())
200 i++;
201 u=x[i].view.max();
202 // Skip the minimal element
203 i++; ++iy;
204 while (iy()) {
205 if (x[i].idx == iy.val()) {
206 u = std::max(u,x[i].view.max());
207 ++iy;
208 } else {
209 assert(x[i].idx < iy.val());
210 }
211 i++;
212 }
213 }
214
215 // Constrain elements in x but not in y
216 {
217 int i = 0;
218 // Elements which must be smaller (for tiebreaking)
219 if (tiebreak)
220 while ((i < x.size()) && (x[i].idx < y.min())) {
221 GECODE_ME_CHECK(x[i].view.le(home,u));
222 i++;
223 }
224 else
225 while ((i < x.size()) && (x[i].idx < y.min())) {
226 GECODE_ME_CHECK(x[i].view.lq(home,u));
227 i++;
228 }
229 assert(x[i].idx == y.min());
230
231 // Elements which cannot be larger
232 ViewValues<VB> iy(y);
233 // Skip the minimal element
234 i++; ++iy;
235 while ((i < x.size()) && iy()) {
236 if (x[i].idx == iy.val()) {
237 ++iy;
238 } else {
239 assert(x[i].idx < iy.val());
240 GECODE_ME_CHECK(x[i].view.lq(home,u));
241 }
242 i++;
243 }
244 while (i < x.size()) {
245 assert(x[i].idx > y.max());
246 GECODE_ME_CHECK(x[i].view.lq(home,u));
247 i++;
248 }
249 }
250 return tiebreak ? ES_NOFIX : ES_FIX;
251 }
252
253 template<class VA, class VB, bool tiebreak>
254 forceinline size_t
256 x.cancel(home,*this,PC_INT_BND);
257 y.cancel(home,*this,PC_INT_DOM);
258 (void) Propagator::dispose(home);
259 return sizeof(*this);
260 }
261
262}}}
263
264// STATISTICS: int-prop
265
NNF * l
Left subtree.
union Gecode::@603::NNF::@65 u
Union depending on nodetype t.
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
Base-class for both propagators and branchers.
Definition core.hpp:628
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3252
Home class for posting propagators
Definition core.hpp:856
Argument maximum propagator.
IdxViewArray< VA > x
Map of index and views.
VB y
Position of maximum view (maximal argument)
ArgMax(Space &home, ArgMax &p)
Constructor for cloning p.
Definition argmax.hpp:76
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition argmax.hpp:103
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition argmax.hpp:84
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition argmax.hpp:90
static ExecStatus post(Home home, IdxViewArray< VA > &x, VB y)
Post propagator .
Definition argmax.hpp:48
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition argmax.hpp:255
virtual void reschedule(Space &home)
Schedule function.
Definition argmax.hpp:96
An array of IdxView pairs.
Definition idx-view.hh:67
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Definition idx-view.hpp:131
void update(Space &home, IdxViewArray< View > &x)
Cloning.
Definition idx-view.hpp:153
Less propagator.
Definition rel.hh:517
Less or equal propagator.
Definition rel.hh:493
Value iterator for integer views.
Definition view.hpp:94
int val(void) const
Return current value.
Value iterator for array of integers
Propagation cost.
Definition core.hpp:486
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:4796
Base-class for propagators.
Definition core.hpp:1064
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1742
bool assigned(void) const
Test whether view is assigned.
Definition var.hpp:111
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#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
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:91
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
Definition tiebreak.hpp:80
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:767
#define forceinline
Definition config.hpp:187