Generated on for Gecode by doxygen 1.15.0
int-expr.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.dev>
5 *
6 * Contributing authors:
7 * Alexander Shepil <alexander.shepil@sap.com>
8 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
9 *
10 * Copyright:
11 * Christian Schulte, 2010
12 * Alexander Shepil, 2024
13 * Mikael Zayenz Lagerkvist, 2026
14 *
15 * This file is part of Gecode, the generic constraint
16 * development environment:
17 * http://www.gecode.dev
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/minimodel.hh>
41#include <gecode/int/linear.hh>
42
43namespace Gecode {
44
46 class LinIntExpr::Node {
47 public:
49 unsigned int use;
51 int n_int;
53 int n_bool;
55 NodeType t;
57 Node *l, *r;
59 union {
61 Int::Linear::Term<Int::IntView>* ti;
63 Int::Linear::Term<Int::BoolView>* tb;
65 NonLinIntExpr* ne;
66 } sum;
68 int a, c;
70 IntVar x_int;
72 BoolVar x_bool;
74 Node(void);
76 void fill(Home home, const IntPropLevels& ipls,
77 Int::Linear::Term<Int::IntView>*& ti,
78 Int::Linear::Term<Int::BoolView>*& tb,
79 long long int m, long long int& d) const;
81 int fill(Home home, const IntPropLevels& ipls,
82 Int::Linear::Term<Int::IntView>* ti,
83 Int::Linear::Term<Int::BoolView>* tb) const;
85 bool decrement(void);
87 ~Node(void);
89 static void* operator new(size_t size);
91 static void operator delete(void* p,size_t size);
92#ifdef GECODE_HAS_FAULT_INJECTION
94 static std::atomic<int> fault_live_nodes;
95#endif
96 };
97
98 /*
99 * Operations for nodes
100 *
101 */
102 forceinline
103 LinIntExpr::Node::Node(void) : use(1) {
104 }
105
106#ifdef GECODE_HAS_FAULT_INJECTION
107 std::atomic<int> LinIntExpr::Node::fault_live_nodes{0};
108
109 void
110 LinIntExpr::fault_reset_allocations(void) {
111 Node::fault_live_nodes.store(0, std::memory_order_relaxed);
112 }
113
114 int
115 LinIntExpr::fault_live_allocations(void) {
116 return Node::fault_live_nodes.load(std::memory_order_relaxed);
117 }
118#endif
119
120 forceinline
121 LinIntExpr::Node::~Node(void) {
122 switch (t) {
123 case NT_SUM_INT:
124 if (n_int > 0)
125 heap.free<Int::Linear::Term<Int::IntView> >(sum.ti,n_int);
126 break;
127 case NT_SUM_BOOL:
128 if (n_bool > 0)
129 heap.free<Int::Linear::Term<Int::BoolView> >(sum.tb,n_bool);
130 break;
131 case NT_NONLIN:
132 delete sum.ne;
133 break;
134 default: ;
135 }
136 }
137
138 forceinline void*
139 LinIntExpr::Node::operator new(size_t size) {
140#ifdef GECODE_HAS_FAULT_INJECTION
141 Support::FailPoint::check(Support::FailPoint::Phase::MiniModel);
142#endif
143 void* p = heap.ralloc(size);
144#ifdef GECODE_HAS_FAULT_INJECTION
145 fault_live_nodes.fetch_add(1, std::memory_order_relaxed);
146#endif
147 return p;
148 }
149
150 forceinline void
151 LinIntExpr::Node::operator delete(void* p, size_t) {
152#ifdef GECODE_HAS_FAULT_INJECTION
153 fault_live_nodes.fetch_sub(1, std::memory_order_relaxed);
154#endif
155 heap.rfree(p);
156 }
157 bool
158 LinIntExpr::Node::decrement(void) {
159 if (--use == 0) {
160 if ((l != nullptr) && l->decrement())
161 delete l;
162 if ((r != nullptr) && r->decrement())
163 delete r;
164 return true;
165 }
166 return false;
167 }
168
169 /*
170 * Operations for expressions
171 *
172 */
173
174 LinIntExpr::LinIntExpr(const LinIntExpr& e)
175 : n(e.n) {
176 if (n != nullptr)
177 n->use++;
178 }
179
180 int
181 LinIntExpr::Node::fill(Home home, const IntPropLevels& ipls,
182 Int::Linear::Term<Int::IntView>* ti,
183 Int::Linear::Term<Int::BoolView>* tb) const {
184 long long int d=0;
185 fill(home,ipls,ti,tb,1,d);
186 Int::Limits::check(d,"MiniModel::LinIntExpr");
187 return static_cast<int>(d);
188 }
189
190 void
191 LinIntExpr::post(Home home, IntRelType irt,
192 const IntPropLevels& ipls) const {
193 if (home.failed()) return;
194 Region r;
195 if (n->n_bool == 0) {
196 // Only integer variables
197 if (n->t==NT_ADD && n->l == nullptr && n->r->t==NT_NONLIN) {
198 n->r->sum.ne->post(home,irt,-n->c,ipls);
199 } else if (n->t==NT_SUB && n->r->t==NT_NONLIN && n->l==nullptr) {
200 switch (irt) {
201 case IRT_LQ: irt=IRT_GQ; break;
202 case IRT_LE: irt=IRT_GR; break;
203 case IRT_GQ: irt=IRT_LQ; break;
204 case IRT_GR: irt=IRT_LE; break;
205 default: break;
206 }
207 n->r->sum.ne->post(home,irt,n->c,ipls);
208 } else if (irt==IRT_EQ &&
209 n->t==NT_SUB && n->r->t==NT_NONLIN &&
210 n->l != nullptr && n->l->t==NT_VAR_INT
211 && n->l->a==1) {
212 (void) n->r->sum.ne->post(home,&n->l->x_int,ipls);
213 } else if (irt==IRT_EQ &&
214 n->t==NT_SUB && n->r->t==NT_VAR_INT &&
215 n->l != nullptr && n->l->t==NT_NONLIN
216 && n->r->a==1) {
217 (void) n->l->sum.ne->post(home,&n->r->x_int,ipls);
218 } else {
219 Int::Linear::Term<Int::IntView>* its =
220 r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int);
221 int c = n->fill(home,ipls,its,nullptr);
222 Int::Linear::post(home, its, n->n_int, irt, -c,
223 (n->n_int > 2) ? ipls.linear() : ipls.linear2());
224 }
225 } else if (n->n_int == 0) {
226 // Only Boolean variables
227 Int::Linear::Term<Int::BoolView>* bts =
228 r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
229 int c = n->fill(home,ipls,nullptr,bts);
230 Int::Linear::post(home, bts, n->n_bool, irt, -c,
231 (n->n_bool > 2) ? ipls.linear() : ipls.linear2());
232 } else if (n->n_bool == 1) {
233 // Integer variables and only one Boolean variable
234 Int::Linear::Term<Int::IntView>* its =
235 r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
236 Int::Linear::Term<Int::BoolView>* bts =
237 r.alloc<Int::Linear::Term<Int::BoolView> >(1);
238 int c = n->fill(home,ipls,its,bts);
239 IntVar x(home,0,1);
240 channel(home,bts[0].x,x);
241 its[n->n_int].x = x;
242 its[n->n_int].a = bts[0].a;
243 Int::Linear::post(home, its, n->n_int+1, irt, -c,
244 (n->n_int > 1) ? ipls.linear() : ipls.linear2());
245 } else {
246 // Both integer and Boolean variables
247 Int::Linear::Term<Int::IntView>* its =
248 r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
249 Int::Linear::Term<Int::BoolView>* bts =
250 r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
251 int c = n->fill(home,ipls,its,bts);
252 int min, max;
253 Int::Linear::estimate(&bts[0],n->n_bool,0,min,max);
254 IntVar x(home,min,max);
255 its[n->n_int].x = x; its[n->n_int].a = 1;
256 Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, 0,
257 (n->n_bool > 2) ? ipls.linear() : ipls.linear2());
258 Int::Linear::post(home, its, n->n_int+1, irt, -c,
259 (n->n_int > 1) ? ipls.linear() : ipls.linear2());
260 }
261 }
262
263 void
264 LinIntExpr::post(Home home, IntRelType irt, const BoolVar& b,
265 const IntPropLevels& ipls) const {
266 if (home.failed()) return;
267 Region r;
268 if (n->n_bool == 0) {
269 // Only integer variables
270 if (n->t==NT_ADD && n->l==nullptr && n->r->t==NT_NONLIN) {
271 n->r->sum.ne->post(home,irt,-n->c,b,ipls);
272 } else if (n->t==NT_SUB && n->l==nullptr && n->r->t==NT_NONLIN) {
273 switch (irt) {
274 case IRT_LQ: irt=IRT_GQ; break;
275 case IRT_LE: irt=IRT_GR; break;
276 case IRT_GQ: irt=IRT_LQ; break;
277 case IRT_GR: irt=IRT_LE; break;
278 default: break;
279 }
280 n->r->sum.ne->post(home,irt,n->c,b,ipls);
281 } else {
282 Int::Linear::Term<Int::IntView>* its =
283 r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int);
284 int c = n->fill(home,ipls,its,nullptr);
285 Int::Linear::post(home, its, n->n_int, irt, -c, b,
286 (n->n_int > 2) ? ipls.linear() : ipls.linear2());
287 }
288 } else if (n->n_int == 0) {
289 // Only Boolean variables
290 Int::Linear::Term<Int::BoolView>* bts =
291 r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
292 int c = n->fill(home,ipls,nullptr,bts);
293 Int::Linear::post(home, bts, n->n_bool, irt, -c, b,
294 (n->n_bool > 2) ? ipls.linear() : ipls.linear2());
295 } else if (n->n_bool == 1) {
296 // Integer variables and only one Boolean variable
297 Int::Linear::Term<Int::IntView>* its =
298 r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
299 Int::Linear::Term<Int::BoolView>* bts =
300 r.alloc<Int::Linear::Term<Int::BoolView> >(1);
301 int c = n->fill(home,ipls,its,bts);
302 IntVar x(home,0,1);
303 channel(home,bts[0].x,x);
304 its[n->n_int].x = x;
305 its[n->n_int].a = bts[0].a;
306 Int::Linear::post(home, its, n->n_int+1, irt, -c, b,
307 (n->n_int > 1) ? ipls.linear() : ipls.linear2());
308 } else {
309 // Both integer and Boolean variables
310 Int::Linear::Term<Int::IntView>* its =
311 r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
312 Int::Linear::Term<Int::BoolView>* bts =
313 r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
314 int c = n->fill(home,ipls,its,bts);
315 int min, max;
316 Int::Linear::estimate(&bts[0],n->n_bool,0,min,max);
317 IntVar x(home,min,max);
318 its[n->n_int].x = x; its[n->n_int].a = 1;
319 Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, 0,
320 (n->n_int > 1) ? ipls.linear() : ipls.linear2());
321 Int::Linear::post(home, its, n->n_int+1, irt, -c, b,
322 (n->n_bool > 2) ? ipls.linear() : ipls.linear2());
323 }
324 }
325
326 IntVar
327 LinIntExpr::post(Home home, const IntPropLevels& ipls) const {
328 if (home.failed()) return IntVar(home,0,0);
329 Region r;
330 if (n->n_bool == 0) {
331 // Only integer variables
332 Int::Linear::Term<Int::IntView>* its =
333 r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
334 int c = n->fill(home,ipls,its,nullptr);
335 if ((n->n_int == 1) && (c == 0) && (its[0].a == 1))
336 return its[0].x;
337 int min, max;
338 Int::Linear::estimate(&its[0],n->n_int,c,min,max);
339 IntVar x(home, min, max);
340 its[n->n_int].x = x; its[n->n_int].a = -1;
341 Int::Linear::post(home, its, n->n_int+1, IRT_EQ, -c,
342 (n->n_int > 1) ? ipls.linear() : ipls.linear2());
343 return x;
344 } else if (n->n_int == 0) {
345 // Only Boolean variables
346 Int::Linear::Term<Int::BoolView>* bts =
347 r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
348 int c = n->fill(home,ipls,nullptr,bts);
349 int min, max;
350 Int::Linear::estimate(&bts[0],n->n_bool,c,min,max);
351 IntVar x(home, min, max);
352 Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, -c,
353 (n->n_bool > 2) ? ipls.linear() : ipls.linear2());
354 return x;
355 } else if (n->n_bool == 1) {
356 // Integer variables and single Boolean variable
357 Int::Linear::Term<Int::IntView>* its =
358 r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+2);
359 Int::Linear::Term<Int::BoolView>* bts =
360 r.alloc<Int::Linear::Term<Int::BoolView> >(1);
361 int c = n->fill(home,ipls,its,bts);
362 IntVar x(home, 0, 1);
363 channel(home, x, bts[0].x);
364 its[n->n_int].x = x; its[n->n_int].a = bts[0].a;
365 int y_min, y_max;
366 Int::Linear::estimate(&its[0],n->n_int+1,c,y_min,y_max);
367 IntVar y(home, y_min, y_max);
368 its[n->n_int+1].x = y; its[n->n_int+1].a = -1;
369 Int::Linear::post(home, its, n->n_int+2, IRT_EQ, -c, ipls.linear());
370 return y;
371 } else {
372 // Both integer and Boolean variables
373 Int::Linear::Term<Int::IntView>* its =
374 r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+2);
375 Int::Linear::Term<Int::BoolView>* bts =
376 r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
377 int c = n->fill(home,ipls,its,bts);
378 int x_min, x_max;
379 Int::Linear::estimate(&bts[0],n->n_bool,0,x_min,x_max);
380 IntVar x(home, x_min, x_max);
381 Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, 0,
382 (n->n_bool > 2) ? ipls.linear() : ipls.linear2());
383 its[n->n_int].x = x; its[n->n_int].a = 1;
384 int y_min, y_max;
385 Int::Linear::estimate(&its[0],n->n_int+1,c,y_min,y_max);
386 IntVar y(home, y_min, y_max);
387 its[n->n_int+1].x = y; its[n->n_int+1].a = -1;
388 Int::Linear::post(home, its, n->n_int+2, IRT_EQ, -c, ipls.linear());
389 return y;
390 }
391 }
392
393 NonLinIntExpr*
394 LinIntExpr::nle(void) const {
395 return ((n != nullptr) && (n->t == NT_NONLIN)) ? n->sum.ne : nullptr;
396 }
397
398 LinIntExpr::LinIntExpr(NoNode) :
399 n(nullptr) {}
400
401 LinIntExpr::LinIntExpr(void) :
402 n(new Node) {
403 n->n_int = n->n_bool = 0;
404 n->t = NT_CONST;
405 n->l = n->r = nullptr;
406 n->a = 0;
407 n->c = 0;
408 }
409
410 LinIntExpr::LinIntExpr(int c) :
411 n(new Node) {
412 n->n_int = n->n_bool = 0;
413 n->t = NT_CONST;
414 n->l = n->r = nullptr;
415 n->a = 0;
416 Int::Limits::check(c,"MiniModel::LinIntExpr");
417 n->c = c;
418 }
419
420 LinIntExpr::LinIntExpr(const IntVar& x, int a) :
421 n(new Node) {
422 n->n_int = 1;
423 n->n_bool = 0;
424 n->t = NT_VAR_INT;
425 n->l = n->r = nullptr;
426 n->a = a;
427 n->x_int = x;
428 }
429
430 LinIntExpr::LinIntExpr(const BoolVar& x, int a) :
431 n(new Node) {
432 n->n_int = 0;
433 n->n_bool = 1;
434 n->t = NT_VAR_BOOL;
435 n->l = n->r = nullptr;
436 n->a = a;
437 n->x_bool = x;
438 }
439
440 LinIntExpr::LinIntExpr(const IntVarArgs& x) :
441 n(new Node) {
442 n->n_int = 0;
443 n->n_bool = 0;
444 n->t = NT_SUM_INT;
445 n->l = n->r = nullptr;
446 try {
447 if (x.size() > 0) {
448 n->sum.ti = heap.alloc<Int::Linear::Term<Int::IntView> >(x.size());
449 n->n_int = x.size();
450 for (int i=x.size(); i--; ) {
451 n->sum.ti[i].x = x[i];
452 n->sum.ti[i].a = 1;
453 }
454 }
455 } catch (...) {
456 delete n;
457 throw;
458 }
459 }
460
461 LinIntExpr::LinIntExpr(const IntArgs& a, const IntVarArgs& x) :
462 n(nullptr) {
463 if (a.size() != x.size())
464 throw Int::ArgumentSizeMismatch("MiniModel::LinIntExpr");
465 n = new Node;
466 n->n_int = 0;
467 n->n_bool = 0;
468 n->t = NT_SUM_INT;
469 n->l = n->r = nullptr;
470 try {
471 if (x.size() > 0) {
472 n->sum.ti = heap.alloc<Int::Linear::Term<Int::IntView> >(x.size());
473 n->n_int = x.size();
474 for (int i=x.size(); i--; ) {
475 n->sum.ti[i].x = x[i];
476 n->sum.ti[i].a = a[i];
477 }
478 }
479 } catch (...) {
480 delete n;
481 throw;
482 }
483 }
484
485 LinIntExpr::LinIntExpr(const BoolVarArgs& x) :
486 n(new Node) {
487 n->n_int = 0;
488 n->n_bool = 0;
489 n->t = NT_SUM_BOOL;
490 n->l = n->r = nullptr;
491 try {
492 if (x.size() > 0) {
493 n->sum.tb = heap.alloc<Int::Linear::Term<Int::BoolView> >(x.size());
494 n->n_bool = x.size();
495 for (int i=x.size(); i--; ) {
496 n->sum.tb[i].x = x[i];
497 n->sum.tb[i].a = 1;
498 }
499 }
500 } catch (...) {
501 delete n;
502 throw;
503 }
504 }
505
506 LinIntExpr::LinIntExpr(const IntArgs& a, const BoolVarArgs& x) :
507 n(nullptr) {
508 if (a.size() != x.size())
509 throw Int::ArgumentSizeMismatch("MiniModel::LinIntExpr");
510 n = new Node;
511 n->n_int = 0;
512 n->n_bool = 0;
513 n->t = NT_SUM_BOOL;
514 n->l = n->r = nullptr;
515 try {
516 if (x.size() > 0) {
517 n->sum.tb = heap.alloc<Int::Linear::Term<Int::BoolView> >(x.size());
518 n->n_bool = x.size();
519 for (int i=x.size(); i--; ) {
520 n->sum.tb[i].x = x[i];
521 n->sum.tb[i].a = a[i];
522 }
523 }
524 } catch (...) {
525 delete n;
526 throw;
527 }
528 }
529
530 LinIntExpr::LinIntExpr(const LinIntExpr& e0, NodeType t, const LinIntExpr& e1) :
531 n(new Node) {
532 n->n_int = e0.n->n_int + e1.n->n_int;
533 n->n_bool = e0.n->n_bool + e1.n->n_bool;
534 n->t = t;
535 n->l = e0.n; n->l->use++;
536 n->r = e1.n; n->r->use++;
537 }
538
539 LinIntExpr::LinIntExpr(const LinIntExpr& e, NodeType t, int c) :
540 n(new Node) {
541 n->n_int = e.n->n_int;
542 n->n_bool = e.n->n_bool;
543 n->t = t;
544 n->l = nullptr;
545 n->r = e.n; n->r->use++;
546 n->c = c;
547 }
548
549 LinIntExpr::LinIntExpr(int a, const LinIntExpr& e) :
550 n(new Node) {
551 n->n_int = e.n->n_int;
552 n->n_bool = e.n->n_bool;
553 n->t = NT_MUL;
554 n->l = e.n; n->l->use++;
555 n->r = nullptr;
556 n->a = a;
557 }
558
559 LinIntExpr::LinIntExpr(NonLinIntExpr* e) :
560 n(nullptr) {
561 try {
562 n = new Node;
563 } catch (...) {
564 delete e;
565 throw;
566 }
567 n->n_int = 1;
568 n->n_bool = 0;
569 n->t = NT_NONLIN;
570 n->l = n->r = nullptr;
571 n->a = 0;
572 n->sum.ne = e;
573 }
574
575 const LinIntExpr&
576 LinIntExpr::operator =(const LinIntExpr& e) {
577 if (this != &e) {
578 if ((n != nullptr) && n->decrement())
579 delete n;
580 n = e.n;
581 if (n != nullptr)
582 n->use++;
583 }
584 return *this;
585 }
586
587 LinIntExpr::~LinIntExpr(void) {
588 if ((n != nullptr) && n->decrement())
589 delete n;
590 }
591
592
593 void
594 LinIntExpr::Node::fill(Home home, const IntPropLevels& ipls,
595 Int::Linear::Term<Int::IntView>*& ti,
596 Int::Linear::Term<Int::BoolView>*& tb,
597 long long int m, long long int& d) const {
598 switch (this->t) {
599 case NT_CONST:
600 Int::Limits::check(m*c,"MiniModel::LinIntExpr");
601 d += m*c;
602 break;
603 case NT_VAR_INT:
604 Int::Limits::check(m*a,"MiniModel::LinIntExpr");
605 ti->a=static_cast<int>(m*a); ti->x=x_int; ti++;
606 break;
607 case NT_NONLIN:
608 ti->a=static_cast<int>(m); ti->x=sum.ne->post(home, nullptr, ipls); ti++;
609 break;
610 case NT_VAR_BOOL:
611 Int::Limits::check(m*a,"MiniModel::LinIntExpr");
612 tb->a=static_cast<int>(m*a); tb->x=x_bool; tb++;
613 break;
614 case NT_SUM_INT:
615 for (int i=n_int; i--; ) {
616 Int::Limits::check(m*sum.ti[i].a,"MiniModel::LinIntExpr");
617 ti[i].x = sum.ti[i].x; ti[i].a = static_cast<int>(m*sum.ti[i].a);
618 }
619 ti += n_int;
620 break;
621 case NT_SUM_BOOL:
622 for (int i=n_bool; i--; ) {
623 Int::Limits::check(m*sum.tb[i].a,"MiniModel::LinIntExpr");
624 tb[i].x = sum.tb[i].x; tb[i].a = static_cast<int>(m*sum.tb[i].a);
625 }
626 tb += n_bool;
627 break;
628 case NT_ADD:
629 if (l == nullptr) {
630 Int::Limits::check(m*c,"MiniModel::LinIntExpr");
631 d += m*c;
632 } else {
633 l->fill(home,ipls,ti,tb,m,d);
634 }
635 r->fill(home,ipls,ti,tb,m,d);
636 break;
637 case NT_SUB:
638 if (l == nullptr) {
639 Int::Limits::check(m*c,"MiniModel::LinIntExpr");
640 d += m*c;
641 } else {
642 l->fill(home,ipls,ti,tb,m,d);
643 }
644 r->fill(home,ipls,ti,tb,-m,d);
645 break;
646 case NT_MUL:
647 Int::Limits::check(m*a,"MiniModel::LinIntExpr");
648 l->fill(home,ipls,ti,tb,m*a,d);
649 break;
650 default:
651 GECODE_NEVER;
652 }
653 }
654
655
656 /*
657 * Operators
658 *
659 */
660 LinIntExpr
661 operator +(int c, const IntVar& x) {
662 if (x.assigned() &&
663 Int::Limits::valid(static_cast<long long int>(c)+x.val()))
664 return LinIntExpr(c+x.val());
665 else
666 return LinIntExpr(x,LinIntExpr::NT_ADD,c);
667 }
668 LinIntExpr
669 operator +(int c, const BoolVar& x) {
670 if (x.assigned() &&
671 Int::Limits::valid(static_cast<long long int>(c)+x.val()))
672 return LinIntExpr(c+x.val());
673 else
674 return LinIntExpr(x,LinIntExpr::NT_ADD,c);
675 }
676 LinIntExpr
677 operator +(int c, const LinIntExpr& e) {
678 return LinIntExpr(e,LinIntExpr::NT_ADD,c);
679 }
680 LinIntExpr
681 operator +(const IntVar& x, int c) {
682 if (x.assigned() &&
683 Int::Limits::valid(static_cast<long long int>(c)+x.val()))
684 return LinIntExpr(c+x.val());
685 else
686 return LinIntExpr(x,LinIntExpr::NT_ADD,c);
687 }
688 LinIntExpr
689 operator +(const BoolVar& x, int c) {
690 if (x.assigned() &&
691 Int::Limits::valid(static_cast<long long int>(c)+x.val()))
692 return LinIntExpr(c+x.val());
693 else
694 return LinIntExpr(x,LinIntExpr::NT_ADD,c);
695 }
696 LinIntExpr
697 operator +(const LinIntExpr& e, int c) {
698 return LinIntExpr(e,LinIntExpr::NT_ADD,c);
699 }
700 LinIntExpr
701 operator +(const IntVar& x, const IntVar& y) {
702 if (x.assigned())
703 return x.val() + y;
704 else if (y.assigned())
705 return x + y.val();
706 else
707 return LinIntExpr(x,LinIntExpr::NT_ADD,y);
708 }
709 LinIntExpr
710 operator +(const IntVar& x, const BoolVar& y) {
711 if (x.assigned())
712 return x.val() + y;
713 else if (y.assigned())
714 return x + y.val();
715 else
716 return LinIntExpr(x,LinIntExpr::NT_ADD,y);
717 }
718 LinIntExpr
719 operator +(const BoolVar& x, const IntVar& y) {
720 if (x.assigned())
721 return x.val() + y;
722 else if (y.assigned())
723 return x + y.val();
724 else
725 return LinIntExpr(x,LinIntExpr::NT_ADD,y);
726 }
727 LinIntExpr
728 operator +(const BoolVar& x, const BoolVar& y) {
729 if (x.assigned())
730 return x.val() + y;
731 else if (y.assigned())
732 return x + y.val();
733 else
734 return LinIntExpr(x,LinIntExpr::NT_ADD,y);
735 }
736 LinIntExpr
737 operator +(const IntVar& x, const LinIntExpr& e) {
738 if (x.assigned())
739 return x.val() + e;
740 else
741 return LinIntExpr(x,LinIntExpr::NT_ADD,e);
742 }
743 LinIntExpr
744 operator +(const BoolVar& x, const LinIntExpr& e) {
745 if (x.assigned())
746 return x.val() + e;
747 else
748 return LinIntExpr(x,LinIntExpr::NT_ADD,e);
749 }
750 LinIntExpr
751 operator +(const LinIntExpr& e, const IntVar& x) {
752 if (x.assigned())
753 return e + x.val();
754 else
755 return LinIntExpr(e,LinIntExpr::NT_ADD,x);
756 }
757 LinIntExpr
758 operator +(const LinIntExpr& e, const BoolVar& x) {
759 if (x.assigned())
760 return e + x.val();
761 else
762 return LinIntExpr(e,LinIntExpr::NT_ADD,x);
763 }
764 LinIntExpr
765 operator +(const LinIntExpr& e1, const LinIntExpr& e2) {
766 return LinIntExpr(e1,LinIntExpr::NT_ADD,e2);
767 }
768
769 LinIntExpr
770 operator -(int c, const IntVar& x) {
771 if (x.assigned() &&
772 Int::Limits::valid(static_cast<long long int>(c)-x.val()))
773 return LinIntExpr(c-x.val());
774 else
775 return LinIntExpr(x,LinIntExpr::NT_SUB,c);
776 }
777 LinIntExpr
778 operator -(int c, const BoolVar& x) {
779 if (x.assigned() &&
780 Int::Limits::valid(static_cast<long long int>(c)-x.val()))
781 return LinIntExpr(c-x.val());
782 else
783 return LinIntExpr(x,LinIntExpr::NT_SUB,c);
784 }
785 LinIntExpr
786 operator -(int c, const LinIntExpr& e) {
787 return LinIntExpr(e,LinIntExpr::NT_SUB,c);
788 }
789 LinIntExpr
790 operator -(const IntVar& x, int c) {
791 if (x.assigned() &&
792 Int::Limits::valid(x.val()-static_cast<long long int>(c)))
793 return LinIntExpr(x.val()-c);
794 else
795 return LinIntExpr(x,LinIntExpr::NT_ADD,-c);
796 }
797 LinIntExpr
798 operator -(const BoolVar& x, int c) {
799 if (x.assigned() &&
800 Int::Limits::valid(x.val()-static_cast<long long int>(c)))
801 return LinIntExpr(x.val()-c);
802 else
803 return LinIntExpr(x,LinIntExpr::NT_ADD,-c);
804 }
805 LinIntExpr
806 operator -(const LinIntExpr& e, int c) {
807 return LinIntExpr(e,LinIntExpr::NT_ADD,-c);
808 }
809 LinIntExpr
810 operator -(const IntVar& x, const IntVar& y) {
811 if (x.assigned())
812 return x.val() - y;
813 else if (y.assigned())
814 return x - y.val();
815 else
816 return LinIntExpr(x,LinIntExpr::NT_SUB,y);
817 }
818 LinIntExpr
819 operator -(const IntVar& x, const BoolVar& y) {
820 if (x.assigned())
821 return x.val() - y;
822 else if (y.assigned())
823 return x - y.val();
824 else
825 return LinIntExpr(x,LinIntExpr::NT_SUB,y);
826 }
827 LinIntExpr
828 operator -(const BoolVar& x, const IntVar& y) {
829 if (x.assigned())
830 return x.val() - y;
831 else if (y.assigned())
832 return x - y.val();
833 else
834 return LinIntExpr(x,LinIntExpr::NT_SUB,y);
835 }
836 LinIntExpr
837 operator -(const BoolVar& x, const BoolVar& y) {
838 if (x.assigned())
839 return x.val() - y;
840 else if (y.assigned())
841 return x - y.val();
842 else
843 return LinIntExpr(x,LinIntExpr::NT_SUB,y);
844 }
845 LinIntExpr
846 operator -(const IntVar& x, const LinIntExpr& e) {
847 if (x.assigned())
848 return x.val() - e;
849 else
850 return LinIntExpr(x,LinIntExpr::NT_SUB,e);
851 }
852 LinIntExpr
853 operator -(const BoolVar& x, const LinIntExpr& e) {
854 if (x.assigned())
855 return x.val() - e;
856 else
857 return LinIntExpr(x,LinIntExpr::NT_SUB,e);
858 }
859 LinIntExpr
860 operator -(const LinIntExpr& e, const IntVar& x) {
861 if (x.assigned())
862 return e - x.val();
863 else
864 return LinIntExpr(e,LinIntExpr::NT_SUB,x);
865 }
866 LinIntExpr
867 operator -(const LinIntExpr& e, const BoolVar& x) {
868 if (x.assigned())
869 return e - x.val();
870 else
871 return LinIntExpr(e,LinIntExpr::NT_SUB,x);
872 }
873 LinIntExpr
874 operator -(const LinIntExpr& e1, const LinIntExpr& e2) {
875 return LinIntExpr(e1,LinIntExpr::NT_SUB,e2);
876 }
877
878 LinIntExpr
879 operator -(const IntVar& x) {
880 if (x.assigned())
881 return LinIntExpr(-x.val());
882 else
883 return LinIntExpr(x,LinIntExpr::NT_SUB,0);
884 }
885 LinIntExpr
886 operator -(const BoolVar& x) {
887 if (x.assigned())
888 return LinIntExpr(-x.val());
889 else
890 return LinIntExpr(x,LinIntExpr::NT_SUB,0);
891 }
892 LinIntExpr
893 operator -(const LinIntExpr& e) {
894 return LinIntExpr(e,LinIntExpr::NT_SUB,0);
895 }
896
897 LinIntExpr
898 operator *(int a, const IntVar& x) {
899 if (a == 0)
900 return LinIntExpr(0);
901 else if (x.assigned() &&
902 Int::Limits::valid(static_cast<long long int>(a)*x.val()))
903 return LinIntExpr(a*x.val());
904 else
905 return LinIntExpr(x,a);
906 }
907 LinIntExpr
908 operator *(int a, const BoolVar& x) {
909 if (a == 0)
910 return LinIntExpr(0);
911 else if (x.assigned() &&
912 Int::Limits::valid(static_cast<long long int>(a)*x.val()))
913 return LinIntExpr(a*x.val());
914 else
915 return LinIntExpr(x,a);
916 }
917 LinIntExpr
918 operator *(const IntVar& x, int a) {
919 if (a == 0)
920 return LinIntExpr(0);
921 else if (x.assigned() &&
922 Int::Limits::valid(static_cast<long long int>(a)*x.val()))
923 return LinIntExpr(a*x.val());
924 else
925 return LinIntExpr(x,a);
926 }
927 LinIntExpr
928 operator *(const BoolVar& x, int a) {
929 if (a == 0)
930 return LinIntExpr(0);
931 else if (x.assigned() &&
932 Int::Limits::valid(static_cast<long long int>(a)*x.val()))
933 return LinIntExpr(a*x.val());
934 else
935 return LinIntExpr(x,a);
936 }
937 LinIntExpr
938 operator *(const LinIntExpr& e, int a) {
939 if (a == 0)
940 return LinIntExpr(0);
941 else
942 return LinIntExpr(a,e);
943 }
944 LinIntExpr
945 operator *(int a, const LinIntExpr& e) {
946 if (a == 0)
947 return LinIntExpr(0);
948 else
949 return LinIntExpr(a,e);
950 }
951
952 LinIntExpr
953 sum(const IntVarArgs& x) {
954 return LinIntExpr(x);
955 }
956 LinIntExpr
957 sum(const IntArgs& a, const IntVarArgs& x) {
958 return LinIntExpr(a,x);
959 }
960 LinIntExpr
961 sum(const BoolVarArgs& x) {
962 return LinIntExpr(x);
963 }
964 LinIntExpr
965 sum(const IntArgs& a, const BoolVarArgs& x) {
966 return LinIntExpr(a,x);
967 }
968 LinIntExpr
969 sum(const Slice<IntArgs>& slice) {
970 const Slice<IntArgs>::ArgsType & args = slice;
971 return sum(args);
972 }
973 LinIntExpr
974 sum(const Matrix<IntArgs>& matrix) {
975 const Matrix<IntArgs>::ArgsType & args = matrix.get_array();
976 return sum(args);
977 }
978 LinIntExpr
979 sum(const IntArgs& args) {
980 int sum = 0;
981 for (int i = 0; i<args.size(); i++)
982 sum += args[i];
983 return LinIntExpr(sum);
984 }
985
986
987 IntVar
988 expr(Home home, const LinIntExpr& e, const IntPropLevels& ipls) {
989 PostInfo pi(home);
990 if (!home.failed())
991 return e.post(home,ipls);
992 IntVar x(home,Int::Limits::min,Int::Limits::max);
993 return x;
994 }
995
996}
997
998// STATISTICS: minimodel-any
Gecode::ArgArrayBase::a
T * a
Element array.
Definition array.hpp:548
Gecode::ArgArrayBase::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1597
Gecode::BoolVarArgs
Passing Boolean variables.
Definition int.hh:738
Gecode::BoolVar
Boolean integer variables.
Definition int.hh:533
Gecode::BoolVar::val
int val(void) const
Return assigned value.
Definition bool.hpp:57
Gecode::FloatVal::size
FloatNum size(void) const
Return size of float value (distance between maximum and minimum).
Definition val.hpp:78
Gecode::Home
Home class for posting propagators
Definition core.hpp:863
Gecode::Home::failed
bool failed(void) const
Check whether corresponding space is failed.
Definition core.hpp:4185
Gecode::IntArgs
Passing integer arguments.
Definition int.hh:652
Gecode::IntPropLevels
Class for specifying integer propagation levels used by minimodel.
Definition minimodel.hh:109
Gecode::IntPropLevels::linear
IntPropLevel linear(void) const
Return integer propagation level for non-binary linear constraints.
Definition ipl.hpp:55
Gecode::IntPropLevels::linear2
IntPropLevel linear2(void) const
Return integer propagation level for binary linear constraints.
Definition ipl.hpp:47
Gecode::IntVarArgs
Passing integer variables.
Definition int.hh:680
Gecode::IntVar
Integer variables.
Definition int.hh:389
Gecode::IntVar::val
int val(void) const
Return assigned value.
Definition int.hpp:56
Gecode::Int::ArgumentSizeMismatch
Exception: Arguments are of different size
Definition exception.hpp:73
Gecode::Int::Linear::Term
Class for describing linear term .
Definition linear.hh:1336
Gecode::Int::Linear::Term::a
int a
Coefficient.
Definition linear.hh:1339
Gecode::LinIntExpr::Node
Nodes for linear expressions.
Definition int-expr.cpp:46
Gecode::LinIntExpr::Node::decrement
bool decrement(void)
Decrement reference count and possibly free memory.
Definition int-expr.cpp:158
Gecode::LinIntExpr::Node::l
Node * l
Subexpressions.
Definition int-expr.cpp:57
Gecode::LinIntExpr::Node::sum
union Gecode::LinIntExpr::Node::@261231010026300320017355123073322333035126115356 sum
Sum of integer or Boolean variables, or non-linear expression.
Gecode::LinIntExpr::Node::ti
Int::Linear::Term< Int::IntView > * ti
Integer views and coefficients.
Definition int-expr.cpp:61
Gecode::LinIntExpr::Node::use
unsigned int use
Nodes are reference counted.
Definition int-expr.cpp:49
Gecode::LinIntExpr::Node::n_int
int n_int
Integer variables in tree.
Definition int-expr.cpp:51
Gecode::LinIntExpr::Node::x_int
IntVar x_int
Integer variable (potentially).
Definition int-expr.cpp:70
Gecode::LinIntExpr::Node::t
NodeType t
Type of expression.
Definition int-expr.cpp:55
Gecode::LinIntExpr::Node::ne
NonLinIntExpr * ne
Non-linear expression.
Definition int-expr.cpp:65
Gecode::LinIntExpr::Node::x_bool
BoolVar x_bool
Boolean variable (potentially).
Definition int-expr.cpp:72
Gecode::LinIntExpr::Node::fill
void fill(Home home, const IntPropLevels &ipls, Int::Linear::Term< Int::IntView > *&ti, Int::Linear::Term< Int::BoolView > *&tb, long long int m, long long int &d) const
Generate linear terms from expression.
Definition int-expr.cpp:594
Gecode::LinIntExpr::Node::~Node
~Node(void)
Destructor.
Definition int-expr.cpp:121
Gecode::LinIntExpr::Node::tb
Int::Linear::Term< Int::BoolView > * tb
Bool views and coefficients.
Definition int-expr.cpp:63
Gecode::LinIntExpr::Node::a
int a
Coefficient and offset.
Definition int-expr.cpp:68
Gecode::LinIntExpr::Node::n_bool
int n_bool
Boolean variables in tree.
Definition int-expr.cpp:53
Gecode::LinIntExpr::Node::Node
Node(void)
Default constructor.
Definition int-expr.cpp:103
Gecode::LinIntExpr
Linear expressions over integer variables.
Definition minimodel.hh:257
Gecode::LinIntExpr::NodeType
NodeType
Type of linear expression.
Definition minimodel.hh:268
Gecode::LinIntExpr::NT_CONST
@ NT_CONST
Integer constant.
Definition minimodel.hh:269
Gecode::LinIntExpr::NT_SUB
@ NT_SUB
Subtraction of linear terms.
Definition minimodel.hh:276
Gecode::LinIntExpr::NT_SUM_BOOL
@ NT_SUM_BOOL
Sum of Boolean variables.
Definition minimodel.hh:274
Gecode::LinIntExpr::NT_ADD
@ NT_ADD
Addition of linear terms.
Definition minimodel.hh:275
Gecode::LinIntExpr::NT_SUM_INT
@ NT_SUM_INT
Sum of integer variables.
Definition minimodel.hh:273
Gecode::LinIntExpr::NT_VAR_BOOL
@ NT_VAR_BOOL
Linear term with Boolean variable.
Definition minimodel.hh:271
Gecode::LinIntExpr::NT_MUL
@ NT_MUL
Multiplication by coefficient.
Definition minimodel.hh:277
Gecode::LinIntExpr::NT_NONLIN
@ NT_NONLIN
Non-linear expression.
Definition minimodel.hh:272
Gecode::LinIntExpr::NT_VAR_INT
@ NT_VAR_INT
Linear term with integer variable.
Definition minimodel.hh:270
Gecode::LinIntExpr::LinIntExpr
LinIntExpr(void)
Default constructor.
Definition int-expr.cpp:401
Gecode::LinIntExpr::~LinIntExpr
~LinIntExpr(void)
Destructor.
Definition int-expr.cpp:587
Gecode::LinIntExpr::post
void post(Home home, IntRelType irt, const IntPropLevels &ipls) const
Post propagator.
Definition int-expr.cpp:191
Gecode::LinIntExpr::operator=
const LinIntExpr & operator=(const LinIntExpr &e)
Assignment operator.
Definition int-expr.cpp:576
Gecode::LinIntExpr::nle
NonLinIntExpr * nle(void) const
Return non-linear expression inside, or null if not non-linear.
Definition int-expr.cpp:394
Gecode::Matrix
Matrix-interface for arrays.
Definition minimodel.hh:2208
Gecode::Matrix::get_array
ArgsType const get_array(void) const
Return an Args-array of the contents of the matrix.
Definition matrix.hpp:149
Gecode::Matrix::ArgsType
ArrayTraits< A >::ArgsType ArgsType
The type of the Args-array type for ValueType values.
Definition minimodel.hh:2213
Gecode::NonLinIntExpr
Base class for non-linear expressions over integer variables.
Definition minimodel.hh:223
Gecode::PostInfo
Class to set group information when a post function is executed.
Definition core.hpp:957
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Slice
A slice of a matrix.
Definition minimodel.hh:2144
Gecode::Slice::ArgsType
ArrayTraits< A >::ArgsType ArgsType
The type of the Args-array type for ValueType values.
Definition minimodel.hh:2147
Gecode::VarImpVar::assigned
bool assigned(void) const
Test whether view is assigned.
Definition var.hpp:111
pi
const int * pi[]
Definition photo.cpp:14262
Gecode::Int::Linear::post
void post(Home home, Term< IntView > *t, int n, IntRelType irt, int c, IntPropLevel ipl=IPL_DEF)
Post propagator for linear constraint over integers.
Definition int-post.cpp:219
Gecode::heap
Heap heap
The single global heap.
Definition heap.cpp:44
Gecode::IntRelType
IntRelType
Relation types for integers.
Definition int.hh:959
Gecode::IRT_EQ
@ IRT_EQ
Equality ( ).
Definition int.hh:960
Gecode::IRT_GQ
@ IRT_GQ
Greater or equal ( ).
Definition int.hh:964
Gecode::IRT_LE
@ IRT_LE
Less ( ).
Definition int.hh:963
Gecode::IRT_GR
@ IRT_GR
Greater ( ).
Definition int.hh:965
Gecode::IRT_LQ
@ IRT_LQ
Less or equal ( ).
Definition int.hh:962
Gecode::Int::Limits::check
void check(int n, const char *l)
Check whether n is in range, otherwise throw out of limits with information l.
Definition limits.hpp:46
Gecode::Int::Limits::min
const int min
Smallest allowed integer value.
Definition int.hh:122
Gecode::Int::Limits::valid
bool valid(int n)
Return whether n is in range.
Definition limits.hpp:37
Gecode::Int::Limits::max
const int max
Largest allowed integer value.
Definition int.hh:120
Gecode::Int::Linear::estimate
void estimate(Term< View > *t, int n, int c, int &l, int &u)
Estimate lower and upper bounds.
Definition post.hpp:41
Gecode::Support::FailPoint::check
void check(Phase p)
Check failpoint for phase p.
Gecode
Gecode toplevel namespace
Gecode::operator-
FloatVal operator-(const FloatVal &x)
Definition val.hpp:185
Gecode::operator+
FloatVal operator+(const FloatVal &x)
Definition val.hpp:181
Gecode::channel
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition channel.cpp:41
Gecode::expr
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:988
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
Gecode::sum
LinIntExpr sum(const IntVarArgs &x)
Construct linear expression as sum of integer variables.
Definition int-expr.cpp:953
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
Gecode::operator*
FloatVal operator*(const FloatVal &x, const FloatVal &y)
Definition val.hpp:217
forceinline
#define forceinline
Definition config.hpp:141
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56