← Back to branch summary

~ubuntu-branches/ubuntu/natty/gecode/natty

« back to all changes in this revision

Viewing changes to int/linear.hh

  • Committer: Bazaar Package Importer
  • Author(s): Kari Pahula
  • Date: 2005-12-24 07:51:25 UTC
  • Revision ID: james.westby@ubuntu.com-20051224075125-klkiqofvbfvusfvt
Tags: upstream-1.0.0.dfsg.1
Import upstream version 1.0.0.dfsg.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
int/linear.hh
 
1
/*
 
2
 *  Main authors:
 
3
 *     Christian Schulte <schulte@gecode.org>
 
4
 *     Guido Tack <tack@gecode.org>
 
5
 *
 
6
 *  Copyright:
 
7
 *     Christian Schulte, 2002
 
8
 *     Guido Tack, 2004
 
9
 *
 
10
 *  Last modified:
 
11
 *     $Date: 2005-11-01 16:35:02 +0100 (Tue, 01 Nov 2005) $ by $Author: schulte $
 
12
 *     $Revision: 2467 $
 
13
 *
 
14
 *  This file is part of Gecode, the generic constraint
 
15
 *  development environment:
 
16
 *     http://www.gecode.org
 
17
 *
 
18
 *  See the file "LICENSE" for information on usage and
 
19
 *  redistribution of this file, and for a
 
20
 *     DISCLAIMER OF ALL WARRANTIES.
 
21
 *
 
22
 */
 
23
 
 
24
#ifndef __GECODE_INT_LINEAR_HH__
 
25
#define __GECODE_INT_LINEAR_HH__
 
26
 
 
27
#include "int.hh"
 
28
 
 
29
/**
 
30
 * \namespace Gecode::Int::Linear
 
31
 * \brief %Linear propagators
 
32
 */
 
33
 
 
34
namespace Gecode { namespace Int { namespace Linear {
 
35
 
 
36
  /*
 
37
   * Binary propagators
 
38
   *
 
39
   */
 
40
 
 
41
  /**
 
42
   * \brief Base-class for binary linear propagators
 
43
   *
 
44
   * The type \a Val can be either \c double or \c int, defining the
 
45
   * numerical precision during propagation. The types \a A and \a B
 
46
   * give the types of the views.
 
47
   *
 
48
   * The propagation condition \a pc refers to both views.
 
49
   */
 
50
  template <class Val, class A, class B, PropCond pc>
 
51
  class LinBin : public Propagator {
 
52
  protected:
 
53
    /// View of type \a A
 
54
    A x0;
 
55
    /// View of type \a B
 
56
    B x1; 
 
57
    /// Value of type \a Val
 
58
    Val c;
 
59
    /// Constructor for cloning \a p
 
60
    LinBin(Space* home, bool share, LinBin& p);
 
61
    /// Constructor for creation
 
62
    LinBin(Space* home, A x0, B x1, Val c);
 
63
  public:
 
64
    /// Cost function (defined as PC_BINARY_LO)
 
65
    virtual PropCost cost(void) const;
 
66
    /// Destructor
 
67
    virtual ~LinBin(void);
 
68
  };
 
69
 
 
70
  /**
 
71
   * \brief Base-class for reified binary linear propagators
 
72
   *
 
73
   * The type \a Val can be either \c double or \c int, defining the
 
74
   * numerical precision during propagation. The types \a A and \a B
 
75
   * give the types of the views.
 
76
   *
 
77
   * The propagation condition \a pc refers to both views.
 
78
   */
 
79
  template <class Val, class A, class B, PropCond pc, class Ctrl>
 
80
  class ReLinBin : public Propagator {
 
81
  protected:
 
82
    /// View of type \a A
 
83
    A x0;
 
84
    /// View of type \a B
 
85
    B x1; 
 
86
    /// Value of type \a Val
 
87
    Val c;
 
88
    /// Control view for reification
 
89
    Ctrl b;
 
90
    /// Constructor for cloning \a p
 
91
    ReLinBin(Space* home, bool share, ReLinBin& p);
 
92
    /// Constructor for creation
 
93
    ReLinBin(Space* home, A x0, B x1, Val c, Ctrl b);
 
94
  public:
 
95
    /// Cost function (defined as PC_BINARY_LO)
 
96
    virtual PropCost cost(void) const;
 
97
    /// Destructor
 
98
    virtual ~ReLinBin(void);
 
99
  };
 
100
 
 
101
  /**
 
102
   * \brief %Propagator for bounds-consistent binary linear equality
 
103
   *
 
104
   * The type \a Val can be either \c double or \c int, defining the
 
105
   * numerical precision during propagation. The types \a A and \a B
 
106
   * give the types of the views.
 
107
   *
 
108
   * The propagation condition \a pc refers to both views.
 
109
   *
 
110
   * Requires \code #include "int/linear.hh" \endcode
 
111
   * \ingroup FuncIntProp
 
112
   */
 
113
  template <class Val, class A, class B>
 
114
  class EqBin : public LinBin<Val,A,B,PC_INT_BND> {
 
115
  protected:
 
116
    using LinBin<Val,A,B,PC_INT_BND>::x0;
 
117
    using LinBin<Val,A,B,PC_INT_BND>::x1;
 
118
    using LinBin<Val,A,B,PC_INT_BND>::c;
 
119
 
 
120
    /// Constructor for cloning \a p
 
121
    EqBin(Space* home, bool share, EqBin& p);
 
122
    /// Constructor for creation
 
123
    EqBin(Space* home, A x0, B x1, Val c);
 
124
  public:
 
125
    /// Create copy during cloning
 
126
    virtual Actor* copy(Space* home, bool share);
 
127
    /// Perform propagation
 
128
    virtual ExecStatus propagate(Space* home);
 
129
    /// Post propagator for \f$x_0+x_1 = c\f$
 
130
    static ExecStatus post(Space* home, A x0, B x1, Val c);
 
131
  };
 
132
 
 
133
  /**
 
134
   * \brief %Propagator for reified bounds-consistent binary linear equality
 
135
   *
 
136
   * The type \a Val can be either \c double or \c int, defining the
 
137
   * numerical precision during propagation. The types \a A and \a B
 
138
   * give the types of the views.
 
139
   *
 
140
   * The propagation condition \a pc refers to both views.
 
141
   *
 
142
   * Requires \code #include "int/linear.hh" \endcode
 
143
   * \ingroup FuncIntProp
 
144
   */
 
145
  template <class Val, class A, class B, class Ctrl>
 
146
  class ReEqBin : public ReLinBin<Val,A,B,PC_INT_BND,Ctrl> {
 
147
  protected:
 
148
    using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::x0;
 
149
    using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::x1;
 
150
    using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::c;
 
151
    using ReLinBin<Val,A,B,PC_INT_BND,Ctrl>::b;
 
152
 
 
153
    /// Constructor for cloning \a p
 
154
    ReEqBin(Space* home, bool share, ReEqBin& p);
 
155
    /// Constructor for creation
 
156
    ReEqBin(Space* home,A,B,Val,Ctrl);
 
157
  public:
 
158
    /// Create copy during cloning
 
159
    virtual Actor* copy(Space* home, bool share);
 
160
    /// Perform propagation
 
161
    virtual ExecStatus propagate(Space* home);
 
162
    /// Post propagator for \f$(x_0+x_1 = c)\Leftrightarrow b\f$
 
163
    static ExecStatus post(Space* home, A x0, B x1, Val c, Ctrl b);
 
164
  };
 
165
 
 
166
  /**
 
167
   * \brief %Propagator for bounds-consistent binary linear disequality
 
168
   *
 
169
   * The type \a Val can be either \c double or \c int, defining the
 
170
   * numerical precision during propagation. The types \a A and \a B
 
171
   * give the types of the views.
 
172
   *
 
173
   * The propagation condition \a pc refers to both views.
 
174
   *
 
175
   * Requires \code #include "int/linear.hh" \endcode
 
176
   * \ingroup FuncIntProp
 
177
   */
 
178
  template <class Val, class A, class B>
 
179
  class NqBin : public LinBin<Val,A,B,PC_INT_VAL> {
 
180
  protected:
 
181
    using LinBin<Val,A,B,PC_INT_VAL>::x0;
 
182
    using LinBin<Val,A,B,PC_INT_VAL>::x1;
 
183
    using LinBin<Val,A,B,PC_INT_VAL>::c;
 
184
 
 
185
    /// Constructor for cloning \a p
 
186
    NqBin(Space* home, bool share, NqBin& p);
 
187
    /// Constructor for creation
 
188
    NqBin(Space* home,A,B,Val);
 
189
  public:
 
190
    /// Create copy during cloning
 
191
    virtual Actor* copy(Space* home, bool share);
 
192
    /// Perform propagation
 
193
    virtual ExecStatus propagate(Space* home);
 
194
    /// Cost function (defined as PC_UNARY_LO)
 
195
    virtual PropCost cost(void) const;
 
196
    /// Post propagator for \f$x_0+x_1 \neq c\f$
 
197
    static ExecStatus post(Space* home, A x0, B x1, Val c);
 
198
  };
 
199
 
 
200
  /**
 
201
   * \brief %Propagator for bounds-consistent binary linear less or equal
 
202
   *
 
203
   * The type \a Val can be either \c double or \c int, defining the
 
204
   * numerical precision during propagation. The types \a A and \a B
 
205
   * give the types of the views.
 
206
   *
 
207
   * The propagation condition \a pc refers to both views.
 
208
   *
 
209
   * Requires \code #include "int/linear.hh" \endcode
 
210
   * \ingroup FuncIntProp
 
211
   */
 
212
  template <class Val, class A, class B>
 
213
  class LqBin : public LinBin<Val,A,B,PC_INT_BND> {
 
214
  protected:
 
215
    using LinBin<Val,A,B,PC_INT_BND>::x0;
 
216
    using LinBin<Val,A,B,PC_INT_BND>::x1;
 
217
    using LinBin<Val,A,B,PC_INT_BND>::c;
 
218
 
 
219
    /// Constructor for cloning \a p
 
220
    LqBin(Space* home, bool share, LqBin& p);
 
221
    /// Constructor for creation
 
222
    LqBin(Space* home, A x0, B x1, Val c);
 
223
  public:
 
224
    /// Create copy during cloning
 
225
    virtual Actor* copy(Space* home, bool share);
 
226
    /// Perform propagation
 
227
    virtual ExecStatus propagate(Space* home);
 
228
    /// Post propagator for \f$x_0+x_1 \leq c\f$
 
229
    static ExecStatus post(Space* home, A x0, B x1, Val c);
 
230
  };
 
231
 
 
232
  /**
 
233
   * \brief %Propagator for bounds-consistent binary linear greater or equal
 
234
   *
 
235
   * The type \a Val can be either \c double or \c int, defining the
 
236
   * numerical precision during propagation. The types \a A and \a B
 
237
   * give the types of the views.
 
238
   *
 
239
   * The propagation condition \a pc refers to both views.
 
240
   *
 
241
   * Requires \code #include "int/linear.hh" \endcode
 
242
   * \ingroup FuncIntProp
 
243
   */
 
244
  template <class Val, class A, class B>
 
245
  class GqBin : public LinBin<Val,A,B,PC_INT_BND> {
 
246
  protected:
 
247
    using LinBin<Val,A,B,PC_INT_BND>::x0;
 
248
    using LinBin<Val,A,B,PC_INT_BND>::x1;
 
249
    using LinBin<Val,A,B,PC_INT_BND>::c;
 
250
 
 
251
    /// Constructor for cloning \a p
 
252
    GqBin(Space* home, bool share, GqBin& p);
 
253
    /// Constructor for creation
 
254
    GqBin(Space* home, A x0, B x1, Val c);
 
255
  public:
 
256
    /// Create copy during cloning
 
257
    virtual Actor* copy(Space* home, bool share);
 
258
    /// Perform propagation
 
259
    virtual ExecStatus propagate(Space* home);
 
260
    /// Post propagator for \f$x_0+x_1 \geq c\f$
 
261
    static ExecStatus post(Space* home, A x0, B x1, Val c);
 
262
  };
 
263
 
 
264
  /**
 
265
   * \brief %Propagator for reified bounds-consistent binary linear less or equal
 
266
   *
 
267
   * The type \a Val can be either \c double or \c int, defining the
 
268
   * numerical precision during propagation. The types \a A and \a B
 
269
   * give the types of the views.
 
270
   *
 
271
   * The propagation condition \a pc refers to both views.
 
272
   *
 
273
   * Requires \code #include "int/linear.hh" \endcode
 
274
   * \ingroup FuncIntProp
 
275
   */
 
276
  template <class Val, class A, class B>
 
277
  class ReLqBin : public ReLinBin<Val,A,B,PC_INT_BND,BoolView> {
 
278
  protected:
 
279
    using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::x0;
 
280
    using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::x1;
 
281
    using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::c;
 
282
    using ReLinBin<Val,A,B,PC_INT_BND,BoolView>::b;
 
283
 
 
284
    /// Constructor for cloning \a p
 
285
    ReLqBin(Space* home, bool share, ReLqBin& p);
 
286
    /// Constructor for creation
 
287
    ReLqBin(Space* home, A x0, B x1, Val c, BoolView b);
 
288
  public:
 
289
    /// Create copy during cloning
 
290
    virtual Actor* copy(Space* home, bool share);
 
291
    /// Perform propagation
 
292
    virtual ExecStatus propagate(Space* home);
 
293
    /// Post propagator for \f$(x_0+x_1 \leq c)\Leftrightarrow b\f$
 
294
    static ExecStatus post(Space* home, A x0, B x1, Val c, BoolView b);
 
295
  };
 
296
 
 
297
}}}
 
298
 
 
299
#include "int/linear/binary.icc"
 
300
 
 
301
namespace Gecode { namespace Int { namespace Linear {
 
302
 
 
303
  /*
 
304
   * Ternary propagators
 
305
   *
 
306
   */
 
307
 
 
308
  /**
 
309
   * \brief Base-class for ternary linear propagators
 
310
   *
 
311
   * The type \a Val can be either \c double or \c int, defining the
 
312
   * numerical precision during propagation. The types \a A, \a B,
 
313
   * and \a C give the types of the views.
 
314
   *
 
315
   * The propagation condition \a pc refers to all three views.
 
316
   */
 
317
  template <class Val, class A, class B, class C, PropCond pc>
 
318
  class LinTer : public Propagator {
 
319
  protected:
 
320
    /// View of type \a A
 
321
    A x0;
 
322
    /// View of type \a B
 
323
    B x1; 
 
324
    /// View of type \a C
 
325
    C x2; 
 
326
    /// Value of type \a Val
 
327
    Val c;
 
328
    /// Constructor for cloning \a p
 
329
    LinTer(Space* home, bool share, LinTer& p);
 
330
    /// Constructor for creation
 
331
    LinTer(Space* home, A x0, B x1, C x2, Val c);
 
332
  public:
 
333
    /// Cost function (defined as PC_TERNARY_LO)
 
334
    virtual PropCost cost(void) const;
 
335
    /// Destructor
 
336
    virtual ~LinTer(void);
 
337
  };
 
338
 
 
339
  /**
 
340
   * \brief %Propagator for bounds-consistent ternary linear equality
 
341
   *
 
342
   * The type \a Val can be either \c double or \c int, defining the
 
343
   * numerical precision during propagation. The types \a A, \a B, 
 
344
   * and \a C give the types of the views.
 
345
   *
 
346
   * The propagation condition \a pc refers to all three views.
 
347
   *
 
348
   * Requires \code #include "int/linear.hh" \endcode
 
349
   * \ingroup FuncIntProp
 
350
   */
 
351
  template <class Val, class A, class B, class C>
 
352
  class EqTer : public LinTer<Val,A,B,C,PC_INT_BND> {
 
353
  protected:
 
354
    using LinTer<Val,A,B,C,PC_INT_BND>::x0;
 
355
    using LinTer<Val,A,B,C,PC_INT_BND>::x1;
 
356
    using LinTer<Val,A,B,C,PC_INT_BND>::x2;
 
357
    using LinTer<Val,A,B,C,PC_INT_BND>::c;
 
358
 
 
359
    /// Constructor for cloning \a p
 
360
    EqTer(Space* home, bool share, EqTer& p);
 
361
    /// Constructor for creation
 
362
    EqTer(Space* home, A x0, B x1, C x2, Val c);
 
363
  public:
 
364
    /// Create copy during cloning
 
365
    virtual Actor* copy(Space* home, bool share);
 
366
    /// Perform propagation
 
367
    virtual ExecStatus propagate(Space* home);
 
368
    /// Post propagator for \f$x_0+x_1+x_2 = c\f$
 
369
    static ExecStatus post(Space* home, A x0, B x1, C x2, Val c);
 
370
  };
 
371
 
 
372
  /**
 
373
   * \brief %Propagator for bounds-consistent ternary linear disquality
 
374
   *
 
375
   * The type \a Val can be either \c double or \c int, defining the
 
376
   * numerical precision during propagation. The types \a A, \a B, 
 
377
   * and \a C give the types of the views.
 
378
   *
 
379
   * The propagation condition \a pc refers to all three views.
 
380
   *
 
381
   * Requires \code #include "int/linear.hh" \endcode
 
382
   * \ingroup FuncIntProp
 
383
   */
 
384
  template <class Val, class A, class B, class C>
 
385
  class NqTer : public LinTer<Val,A,B,C,PC_INT_VAL> {
 
386
  protected:
 
387
    using LinTer<Val,A,B,C,PC_INT_VAL>::x0;
 
388
    using LinTer<Val,A,B,C,PC_INT_VAL>::x1;
 
389
    using LinTer<Val,A,B,C,PC_INT_VAL>::x2;
 
390
    using LinTer<Val,A,B,C,PC_INT_VAL>::c;
 
391
 
 
392
    /// Constructor for cloning \a p
 
393
    NqTer(Space* home, bool share, NqTer& p);
 
394
    /// Constructor for creation
 
395
    NqTer(Space* home, A x0, B x1, C x2, Val c);
 
396
  public:
 
397
    /// Create copy during cloning
 
398
    virtual Actor* copy(Space* home, bool share);
 
399
    /// Perform propagation
 
400
    virtual ExecStatus propagate(Space* home);
 
401
    /// Post propagator for \f$x_0+x_1+x_2 \neq c\f$
 
402
    static ExecStatus post(Space* home, A x0, B x1, C x2, Val c);
 
403
  };
 
404
 
 
405
  /**
 
406
   * \brief %Propagator for bounds-consistent ternary linear less or equal
 
407
   *
 
408
   * The type \a Val can be either \c double or \c int, defining the
 
409
   * numerical precision during propagation. The types \a A, \a B, 
 
410
   * and \a C give the types of the views.
 
411
   *
 
412
   * The propagation condition \a pc refers to all three views.
 
413
   *
 
414
   * Requires \code #include "int/linear.hh" \endcode
 
415
   * \ingroup FuncIntProp
 
416
   */
 
417
  template <class Val, class A, class B, class C>
 
418
  class LqTer : public LinTer<Val,A,B,C,PC_INT_BND> {
 
419
  protected:
 
420
    using LinTer<Val,A,B,C,PC_INT_BND>::x0;
 
421
    using LinTer<Val,A,B,C,PC_INT_BND>::x1;
 
422
    using LinTer<Val,A,B,C,PC_INT_BND>::x2;
 
423
    using LinTer<Val,A,B,C,PC_INT_BND>::c;
 
424
 
 
425
    /// Constructor for cloning \a p
 
426
    LqTer(Space* home, bool share, LqTer& p);
 
427
    /// Constructor for creation
 
428
    LqTer(Space* home, A x0, B x1, C x2, Val c);
 
429
  public:
 
430
    /// Create copy during cloning
 
431
    virtual Actor* copy(Space* home, bool share);
 
432
    /// Perform propagation
 
433
    virtual ExecStatus propagate(Space* home);
 
434
    /// Post propagator for \f$x_0+x_1+x_2 \leq c\f$
 
435
    static ExecStatus post(Space* home, A x0, B x1, C x2, Val c);
 
436
  };
 
437
 
 
438
}}}
 
439
 
 
440
#include "int/linear/ternary.icc"
 
441
 
 
442
namespace Gecode { namespace Int { namespace Linear {
 
443
 
 
444
  /*
 
445
   * n-ary propagators
 
446
   *
 
447
   */
 
448
 
 
449
  /**
 
450
   * \brief Base-class for n-ary linear propagators
 
451
   *
 
452
   * The type \a Val can be either \c double or \c int, defining the
 
453
   * numerical precision during propagation. Positive views are of
 
454
   * type \a P whereas negative views are of type \a N.
 
455
   *
 
456
   * The propagation condition \a pc refers to all views.
 
457
   */
 
458
  template <class Val, class P, class N, PropCond pc>
 
459
  class Lin : public Propagator {
 
460
  protected:
 
461
    /// Array of positive views
 
462
    ViewArray<P> x; 
 
463
    /// Array of negative views
 
464
    ViewArray<N> y; 
 
465
    /// Constant value
 
466
    Val c;
 
467
 
 
468
    /// Constructor for cloning \a p
 
469
    Lin(Space* home, bool share, Lin& p);
 
470
    /// Constructor for creation
 
471
    Lin(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
 
472
  public:
 
473
    /// Cost function (defined as dynamic PC_LINEAR_LO)
 
474
    virtual PropCost cost(void) const;
 
475
    /// Destructor
 
476
    virtual ~Lin(void);
 
477
  };
 
478
 
 
479
  /**
 
480
   * \brief Base-class for reified n-ary linear propagators
 
481
   *
 
482
   * The type \a Val can be either \c double or \c int, defining the
 
483
   * numerical precision during propagation. Positive views are of
 
484
   * type \a P whereas negative views are of type \a N.
 
485
   *
 
486
   * The propagation condition \a pc refers to all views.
 
487
   */
 
488
  template <class Val, class P, class N, PropCond pc, class Ctrl>
 
489
  class ReLin : public Lin<Val,P,N,pc> {
 
490
  protected:
 
491
    /// Control view for reification
 
492
    Ctrl b;
 
493
    /// Constructor for cloning \a p
 
494
    ReLin(Space* home, bool share, ReLin& p);
 
495
    /// Constructor for creation
 
496
    ReLin(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b);
 
497
  public:
 
498
    /// Destructor
 
499
    virtual ~ReLin(void);
 
500
  };
 
501
 
 
502
  /**
 
503
   * \brief Compute bounds information for positive views
 
504
   *
 
505
   * \relates Lin
 
506
   */
 
507
  template <class Val, class View>
 
508
  void bounds_p(const Propagator*, ViewArray<View>& x, 
 
509
                Val& c, Val& sl, Val& su);
 
510
 
 
511
  /**
 
512
   * \brief Compute bounds information for negative views
 
513
   *
 
514
   * \relates Lin
 
515
   */
 
516
  template <class Val, class View>
 
517
  void bounds_n(const Propagator*, ViewArray<View>& y, 
 
518
                Val& c, Val& sl, Val& su);
 
519
 
 
520
  /**
 
521
   * \brief %Propagator for bounds-consistent n-ary linear equality
 
522
   *
 
523
   * The type \a Val can be either \c double or \c int, defining the
 
524
   * numerical precision during propagation. The types \a A, \a B, 
 
525
   * and \a C give the types of the views.
 
526
   *
 
527
   * The propagation condition \a pc refers to all three views.
 
528
   *
 
529
   * Requires \code #include "int/linear.hh" \endcode
 
530
   * \ingroup FuncIntProp
 
531
   */
 
532
  template <class Val, class P, class N>
 
533
  class Eq : public Lin<Val,P,N,PC_INT_BND> {
 
534
  protected:
 
535
    using Lin<Val,P,N,PC_INT_BND>::x;
 
536
    using Lin<Val,P,N,PC_INT_BND>::y;
 
537
    using Lin<Val,P,N,PC_INT_BND>::c;
 
538
 
 
539
    /// Constructor for cloning \a p
 
540
    Eq(Space* home, bool share, Eq& p);
 
541
  public:
 
542
    /// Constructor for creation
 
543
    Eq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
 
544
    /// Create copy during cloning
 
545
    virtual Actor* copy(Space* home, bool share);
 
546
    /// Perform propagation
 
547
    virtual ExecStatus propagate(Space* home);
 
548
    /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i-\sum_{i=0}^{|y|-1}y_i=c\f$
 
549
    static ExecStatus
 
550
    post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
 
551
  };
 
552
 
 
553
  /**
 
554
   * \brief %Propagator for reified bounds-consistent n-ary linear equality
 
555
   *
 
556
   * The type \a Val can be either \c double or \c int, defining the
 
557
   * numerical precision during propagation. The types \a A, \a B, 
 
558
   * and \a C give the types of the views.
 
559
   *
 
560
   * The propagation condition \a pc refers to all three views.
 
561
   *
 
562
   * Requires \code #include "int/linear.hh" \endcode
 
563
   * \ingroup FuncIntProp
 
564
   */
 
565
  template <class Val, class P, class N, class Ctrl>
 
566
  class ReEq : public ReLin<Val,P,N,PC_INT_BND,Ctrl> {
 
567
  protected:
 
568
    using ReLin<Val,P,N,PC_INT_BND,Ctrl>::x;
 
569
    using ReLin<Val,P,N,PC_INT_BND,Ctrl>::y;
 
570
    using ReLin<Val,P,N,PC_INT_BND,Ctrl>::c;
 
571
    using ReLin<Val,P,N,PC_INT_BND,Ctrl>::b;
 
572
 
 
573
    /// Constructor for cloning \a p
 
574
    ReEq(Space* home, bool share, ReEq& p);
 
575
  public:
 
576
    /// Constructor for creation
 
577
    ReEq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b);
 
578
    /// Create copy during cloning
 
579
    virtual Actor* copy(Space* home, bool share);
 
580
    /// Perform propagation
 
581
    virtual ExecStatus propagate(Space* home);
 
582
    /// Post propagator for \f$\left(\sum_{i=0}^{|x|-1}x_i-\sum_{i=0}^{|y|-1}y_i=c\right)\Leftrightarrow b\f$
 
583
    static ExecStatus 
 
584
    post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b);
 
585
  };
 
586
 
 
587
  /**
 
588
   * \brief %Propagator for bounds-consistent n-ary linear disequality
 
589
   *
 
590
   * The type \a Val can be either \c double or \c int, defining the
 
591
   * numerical precision during propagation. The types \a A, \a B, 
 
592
   * and \a C give the types of the views.
 
593
   *
 
594
   * The propagation condition \a pc refers to all three views.
 
595
   *
 
596
   * Requires \code #include "int/linear.hh" \endcode
 
597
   * \ingroup FuncIntProp
 
598
   */
 
599
  template <class Val, class P, class N>
 
600
  class Nq : public Lin<Val,P,N,PC_INT_VAL> {
 
601
  protected:
 
602
    using Lin<Val,P,N,PC_INT_VAL>::x;
 
603
    using Lin<Val,P,N,PC_INT_VAL>::y;
 
604
    using Lin<Val,P,N,PC_INT_VAL>::c;
 
605
 
 
606
    /// Constructor for cloning \a p
 
607
    Nq(Space* home, bool share, Nq& p);
 
608
  public:
 
609
    /// Constructor for creation
 
610
    Nq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
 
611
    /// Create copy during cloning
 
612
    virtual Actor* copy(Space* home, bool share);
 
613
    /// Perform propagation
 
614
    virtual ExecStatus propagate(Space* home);
 
615
    /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i-\sum_{i=0}^{|y|-1}y_i\neq c\f$
 
616
    static ExecStatus 
 
617
    post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
 
618
  };
 
619
 
 
620
  /**
 
621
   * \brief %Propagator for bounds-consistent n-ary linear less or equal
 
622
   *
 
623
   * The type \a Val can be either \c double or \c int, defining the
 
624
   * numerical precision during propagation. The types \a A, \a B, 
 
625
   * and \a C give the types of the views.
 
626
   *
 
627
   * The propagation condition \a pc refers to all three views.
 
628
   *
 
629
   * Requires \code #include "int/linear.hh" \endcode
 
630
   * \ingroup FuncIntProp
 
631
   */
 
632
  template <class Val, class P, class N>
 
633
  class Lq : public Lin<Val,P,N,PC_INT_BND> {
 
634
  protected:
 
635
    using Lin<Val,P,N,PC_INT_BND>::x;
 
636
    using Lin<Val,P,N,PC_INT_BND>::y;
 
637
    using Lin<Val,P,N,PC_INT_BND>::c;
 
638
 
 
639
    /// Constructor for cloning \a p
 
640
    Lq(Space* home, bool share, Lq& p);
 
641
  public:
 
642
    /// Constructor for creation
 
643
    Lq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
 
644
    /// Create copy during cloning
 
645
    virtual Actor* copy(Space* home, bool share);
 
646
    /// Perform propagation
 
647
    virtual ExecStatus propagate(Space* home);
 
648
    /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i-\sum_{i=0}^{|y|-1}y_i\leq c\f$
 
649
    static ExecStatus 
 
650
    post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c);
 
651
  };
 
652
 
 
653
  /**
 
654
   * \brief %Propagator for reified bounds-consistent n-ary linear less or equal
 
655
   *
 
656
   * The type \a Val can be either \c double or \c int, defining the
 
657
   * numerical precision during propagation. The types \a A, \a B, 
 
658
   * and \a C give the types of the views.
 
659
   *
 
660
   * The propagation condition \a pc refers to all three views.
 
661
   *
 
662
   * Requires \code #include "int/linear.hh" \endcode
 
663
   * \ingroup FuncIntProp
 
664
   */
 
665
  template <class Val, class P, class N>
 
666
  class ReLq : public ReLin<Val,P,N,PC_INT_BND,BoolView> {
 
667
  protected:
 
668
    using ReLin<Val,P,N,PC_INT_BND,BoolView>::x;
 
669
    using ReLin<Val,P,N,PC_INT_BND,BoolView>::y;
 
670
    using ReLin<Val,P,N,PC_INT_BND,BoolView>::c;
 
671
    using ReLin<Val,P,N,PC_INT_BND,BoolView>::b;
 
672
 
 
673
    /// Constructor for cloning \a p
 
674
    ReLq(Space* home, bool share, ReLq& p);
 
675
  public:
 
676
    /// Constructor for creation
 
677
    ReLq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b);
 
678
    /// Create copy during cloning
 
679
    virtual Actor* copy(Space* home, bool share);
 
680
    /// Perform propagation
 
681
    virtual ExecStatus propagate(Space* home);
 
682
    /// Post propagator for \f$\left(\sum_{i=0}^{|x|-1}x_i-\sum_{i=0}^{|y|-1}y_i\leq c\right)\Leftrightarrow b\f$
 
683
    static ExecStatus
 
684
    post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b);
 
685
  };
 
686
 
 
687
}}}
 
688
 
 
689
#include "int/linear/nary.icc"
 
690
 
 
691
namespace Gecode { namespace Int { namespace Linear {
 
692
 
 
693
  /*
 
694
   * Boolean linear propagators
 
695
   *
 
696
   */
 
697
 
 
698
  /**
 
699
   * \brief Base-class for Boolean linear propagators
 
700
   *
 
701
   */
 
702
  template <class View>
 
703
  class LinBool : public Propagator {
 
704
  protected:
 
705
    /// Boolean views
 
706
    ViewArray<BoolView> x;
 
707
    /// Number of Boolean views assigned to 1
 
708
    int n;
 
709
    /// View to compare number of assigned Boolean views to
 
710
    View y;
 
711
 
 
712
    /// Eliminate assigned Boolean views
 
713
    void eliminate(void);
 
714
    /// Post that all remaining Boolean views must be one
 
715
    void all_one(Space* home);
 
716
    /// Post that all remaining Boolean views must be zero
 
717
    void all_zero(Space* home);
 
718
 
 
719
    /// Constructor for cloning \a p
 
720
    LinBool(Space* home, bool share, LinBool& p);
 
721
    /// Constructor for creation
 
722
    LinBool(Space* home, ViewArray<BoolView>& x, int n, View y);
 
723
  public:
 
724
    /// Cost function (defined as dynamic PC_LINEAR_LO)
 
725
    virtual PropCost cost(void) const;
 
726
    /// Destructor
 
727
    virtual ~LinBool(void);
 
728
  };
 
729
 
 
730
 
 
731
  /**
 
732
   * \brief %Propagator for equality to Boolean sum (cardinality)
 
733
   *
 
734
   * Requires \code #include "int/linear.hh" \endcode
 
735
   * \ingroup FuncIntProp
 
736
   */
 
737
  template <class View>
 
738
  class EqBool : public LinBool<View> {
 
739
  protected:
 
740
    using LinBool<View>::x;
 
741
    using LinBool<View>::n;
 
742
    using LinBool<View>::y;
 
743
 
 
744
    /// Constructor for cloning \a p
 
745
    EqBool(Space* home, bool share, EqBool& p);
 
746
    /// Constructor for creation
 
747
    EqBool(Space* home, ViewArray<BoolView>& x, int n, View y);
 
748
  public:
 
749
    /// Create copy during cloning
 
750
    virtual Actor* copy(Space* home, bool share);
 
751
    /// Perform propagation
 
752
    virtual ExecStatus propagate(Space* home);
 
753
    /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i+n = y\f$
 
754
    static ExecStatus post(Space* home, ViewArray<BoolView>& x, int n, View y);
 
755
  };
 
756
 
 
757
  /**
 
758
   * \brief %Propagator for disequality to Boolean sum (cardinality)
 
759
   *
 
760
   * Requires \code #include "int/linear.hh" \endcode
 
761
   * \ingroup FuncIntProp
 
762
   */
 
763
  template <class View>
 
764
  class NqBool : public LinBool<View> {
 
765
  protected:
 
766
    using LinBool<View>::x;
 
767
    using LinBool<View>::n;
 
768
    using LinBool<View>::y;
 
769
 
 
770
    /// Constructor for cloning \a p
 
771
    NqBool(Space* home, bool share, NqBool& p);
 
772
    /// Constructor for creation
 
773
    NqBool(Space* home, ViewArray<BoolView>& x, int n, View y);
 
774
  public:
 
775
    /// Create copy during cloning
 
776
    virtual Actor* copy(Space* home, bool share);
 
777
    /// Perform propagation
 
778
    virtual ExecStatus propagate(Space* home);
 
779
    /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i+n \neq y\f$
 
780
    static ExecStatus post(Space* home, ViewArray<BoolView>& x, int n, View y);
 
781
  };
 
782
 
 
783
  /**
 
784
   * \brief %Propagator for less or equal to Boolean sum (cardinality)
 
785
   *
 
786
   * Requires \code #include "int/linear.hh" \endcode
 
787
   * \ingroup FuncIntProp
 
788
   */
 
789
  template <class View>
 
790
  class LqBool : public LinBool<View> {
 
791
  protected:
 
792
    using LinBool<View>::x;
 
793
    using LinBool<View>::n;
 
794
    using LinBool<View>::y;
 
795
 
 
796
    /// Constructor for cloning \a p
 
797
    LqBool(Space* home, bool share, LqBool& p);
 
798
    /// Constructor for creation
 
799
    LqBool(Space* home, ViewArray<BoolView>& x, int n, View y);
 
800
  public:
 
801
    /// Create copy during cloning
 
802
    virtual Actor* copy(Space* home, bool share);
 
803
    /// Perform propagation
 
804
    virtual ExecStatus propagate(Space* home);
 
805
    /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i+n \leq y\f$
 
806
    static ExecStatus post(Space* home, ViewArray<BoolView>& x, int n, View y);
 
807
  };
 
808
 
 
809
  /**
 
810
   * \brief %Propagator for greater or equal to Boolean sum (cardinality)
 
811
   *
 
812
   * Requires \code #include "int/linear.hh" \endcode
 
813
   * \ingroup FuncIntProp
 
814
   */
 
815
  template <class View>
 
816
  class GqBool : public LinBool<View> {
 
817
  protected:
 
818
    using LinBool<View>::x;
 
819
    using LinBool<View>::n;
 
820
    using LinBool<View>::y;
 
821
 
 
822
    /// Constructor for cloning \a p
 
823
    GqBool(Space* home, bool share, GqBool& p);
 
824
    /// Constructor for creation
 
825
    GqBool(Space* home, ViewArray<BoolView>& x, int n, View y);
 
826
  public:
 
827
    /// Create copy during cloning
 
828
    virtual Actor* copy(Space* home, bool share);
 
829
    /// Perform propagation
 
830
    virtual ExecStatus propagate(Space* home);
 
831
    /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i+n \geq y\f$
 
832
    static ExecStatus post(Space* home, ViewArray<BoolView>& x, int n, View y);
 
833
  };
 
834
 
 
835
}}}
 
836
 
 
837
#include "int/linear/bool.icc"
 
838
 
 
839
namespace Gecode { namespace Int { namespace Linear {
 
840
 
 
841
 
 
842
  /*
 
843
   * Support for preprocessing and posting
 
844
   *
 
845
   */
 
846
 
 
847
  /**
 
848
   * \brief Class for describing linear term \f$a\cdot x\f$
 
849
   *
 
850
   */
 
851
  class Term {
 
852
  public:
 
853
    /// Coefficient
 
854
    int a; 
 
855
    /// View
 
856
    IntView x;
 
857
  };
 
858
 
 
859
  /**
 
860
   * \brief Post propagator for linear constraint
 
861
   * \param e array of linear terms
 
862
   * \param n size of array
 
863
   * \param r type of relation
 
864
   * \param c result of linear constraint
 
865
   *
 
866
   * All variants for linear constraints share the following properties:
 
867
   *  - Only bounds-consistency is supported.
 
868
   *  - Variables occuring multiply in the term array are replaced
 
869
   *    by a single occurence: for example, \f$ax+bx\f$ becomes 
 
870
   *    \f$(a+b)x\f$.
 
871
   *  - If in the above simplification the value for \f$(a+b)\f$ (or for
 
872
   *    \f$a\f$ and \f$b\f$) exceeds the limits for integers as
 
873
   *    defined in Limits::Int, an exception of type 
 
874
   *    Int::NumericalOverflow is thrown.
 
875
   *  - Assume linear terms for the constraint 
 
876
   *    \f$\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_r c\f$.
 
877
   *    If  \f$|c|+\sum_{i=0}^{|x|-1}a_i\cdot x_i\f$ exceeds the limits
 
878
   *    for doubles as defined in Limits::Int, an exception of
 
879
   *    type Int::NumericalOverflow is thrown.
 
880
   *  - In all other cases, the created propagators are accurate (that
 
881
   *    is, they will not silently overflow during propagation).
 
882
   *
 
883
   * Requires \code #include "int/linear.hh" \endcode
 
884
   * \ingroup FuncIntProp
 
885
   */
 
886
  GECODE_INT_EXPORT void
 
887
  post(Space* home, Term t[], int n, IntRelType r, int c);
 
888
 
 
889
  /**
 
890
   * \brief Post reified propagator for linear constraint
 
891
   * \param e array of linear terms
 
892
   * \param n size of array
 
893
   * \param r type of relation
 
894
   * \param c result of linear constraint
 
895
   * \param b Boolean control view
 
896
   *
 
897
   * All variants for linear constraints share the following properties:
 
898
   *  - Only bounds-consistency is supported.
 
899
   *  - Variables occuring multiply in the term array are replaced
 
900
   *    by a single occurence: for example, \f$ax+bx\f$ becomes 
 
901
   *    \f$(a+b)x\f$.
 
902
   *  - If in the above simplification the value for \f$(a+b)\f$ (or for
 
903
   *    \f$a\f$ and \f$b\f$) exceeds the limits for integers as
 
904
   *    defined in Limits::Int, an exception of type 
 
905
   *    Int::NumericalOverflow is thrown.
 
906
   *  - Assume linear terms for the constraint 
 
907
   *    \f$\sum_{i=0}^{|x|-1}a_i\cdot x_i\sim_r c\f$.
 
908
   *    If  \f$|c|+\sum_{i=0}^{|x|-1}a_i\cdot x_i\f$ exceeds the limits
 
909
   *    for doubles as defined in Limits::Int, an exception of
 
910
   *    type Int::NumericalOverflow is thrown.
 
911
   *  - In all other cases, the created propagators are accurate (that
 
912
   *    is, they will not silently overflow during propagation).
 
913
   *
 
914
   * Requires \code #include "int/linear.hh" \endcode
 
915
   * \ingroup FuncIntProp
 
916
   */
 
917
  GECODE_INT_EXPORT void
 
918
  post(Space* home, Term t[], int n, IntRelType r, int c, BoolView b);
 
919
 
 
920
}}}
 
921
 
 
922
#endif
 
923
 
 
924
// STATISTICS: int-prop
 
925