← Back to branch summary

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

« back to all changes in this revision

Viewing changes to int/branch.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/branch.hh
 
1
/*
 
2
 *  Main authors:
 
3
 *     Christian Schulte <schulte@gecode.org>
 
4
 *
 
5
 *  Copyright:
 
6
 *     Christian Schulte, 2002
 
7
 *
 
8
 *  Last modified:
 
9
 *     $Date: 2005-10-19 18:05:44 +0200 (Wed, 19 Oct 2005) $ by $Author: tack $
 
10
 *     $Revision: 2381 $
 
11
 *
 
12
 *  This file is part of Gecode, the generic constraint
 
13
 *  development environment:
 
14
 *     http://www.gecode.org
 
15
 *
 
16
 *  See the file "LICENSE" for information on usage and
 
17
 *  redistribution of this file, and for a
 
18
 *     DISCLAIMER OF ALL WARRANTIES.
 
19
 *
 
20
 */
 
21
 
 
22
#ifndef __GECODE_INT_BRANCH_HH__
 
23
#define __GECODE_INT_BRANCH_HH__
 
24
 
 
25
#include "int.hh"
 
26
 
 
27
/**
 
28
 * \namespace Gecode::Int::Branch
 
29
 * \brief Integer branchings
 
30
 */
 
31
 
 
32
namespace Gecode { namespace Int { namespace Branch {
 
33
 
 
34
  /*
 
35
   * Value selection classes
 
36
   *
 
37
   */
 
38
  /**
 
39
   * \brief Class for selecting minimum value
 
40
   *
 
41
   * All value selection classes require 
 
42
   * \code #include "int/branch.hh" \endcode
 
43
   * \ingroup FuncIntSelVal
 
44
   */
 
45
  class ValMin {
 
46
  public:
 
47
    /// Return minimum value of view \a x
 
48
    int val(IntView x);
 
49
    /// Tell \f$x=n\f$ (\a a = 0) or \f$x\neq n\f$ (\a a = 1)
 
50
    ModEvent tell(Space* home, unsigned int a, IntView x, int n);
 
51
  };
 
52
 
 
53
  /**
 
54
   * \brief Class for selecting maximum value
 
55
   *
 
56
   * Requires 
 
57
   * \code #include "int/branch.hh" \endcode
 
58
   * \ingroup FuncIntSelVal
 
59
   */
 
60
  class ValMed {
 
61
  public:
 
62
    /// Return maximum value of view \a x
 
63
    int val(IntView x);
 
64
    /// Tell \f$x=n\f$ (\a a = 0) or \f$x\neq n\f$ (\a a = 1)
 
65
    ModEvent tell(Space* home, unsigned int a, IntView x, int n);
 
66
  };
 
67
 
 
68
  /**
 
69
   * \brief Class for selecting median value
 
70
   *
 
71
   * Requires 
 
72
   * \code #include "int/branch.hh" \endcode
 
73
   * \ingroup FuncIntSelVal
 
74
   */
 
75
  class ValMax {
 
76
  public:
 
77
    /// Return median value of view \a x
 
78
    int val(IntView x);
 
79
    /// Tell \f$x=n\f$ (\a a = 0) or \f$x\neq n\f$ (\a a = 1)
 
80
    ModEvent tell(Space* home, unsigned int a, IntView x, int n);
 
81
  };
 
82
 
 
83
  /**
 
84
   * \brief Class for splitting domain (lower half first)
 
85
   *
 
86
   * Requires 
 
87
   * \code #include "int/branch.hh" \endcode
 
88
   * \ingroup FuncIntSelVal
 
89
   */
 
90
  class ValSplitMin {
 
91
  public:
 
92
    /// Return minimum value of view \a x
 
93
    int val(IntView x);
 
94
    /// Tell \f$x\leq n\f$ (\a a = 0) or \f$x >n\f$ (\a a = 1)
 
95
    ModEvent tell(Space* home, unsigned int a, IntView x, int n);
 
96
  };
 
97
 
 
98
  /**
 
99
   * \brief Class for splitting domain (upper half first)
 
100
   *
 
101
   * Requires 
 
102
   * \code #include "int/branch.hh" \endcode
 
103
   * \ingroup FuncIntSelVal
 
104
   */
 
105
  class ValSplitMax {
 
106
  public:
 
107
    /// Return minimum value of view \a x
 
108
    int val(IntView x);
 
109
    /// Tell \f$x>n\f$ (\a a = 0) or \f$x\leq n\f$ (\a a = 1)
 
110
    ModEvent tell(Space* home, unsigned int a, IntView x, int n);
 
111
  };
 
112
 
 
113
  /// Create branchings for a given view selection strategy \a ViewSel
 
114
  template <class SelView>
 
115
  static void
 
116
  create(Space* home, ViewArray<IntView>&, BvalSel);
 
117
 
 
118
 
 
119
  /*
 
120
   * Variable selection classes
 
121
   *
 
122
   */
 
123
 
 
124
  /**
 
125
   * \brief View selection class for first variable
 
126
   *
 
127
   * Requires \code #include "int/branch.hh" \endcode
 
128
   * \ingroup FuncIntSelView
 
129
   */
 
130
  class ByNone {
 
131
  public:
 
132
    /// Intialize with view \a x
 
133
    ViewSelStatus init(IntView x);
 
134
    /// Possibly select better view \a x
 
135
    ViewSelStatus select(IntView x);
 
136
  };
 
137
 
 
138
  /**
 
139
   * \brief View selection class for view with smallest min
 
140
   *
 
141
   * Requires \code #include "int/branch.hh" \endcode
 
142
   * \ingroup FuncIntSelView
 
143
   */
 
144
  class ByMinMin {
 
145
  protected:
 
146
    /// So-far smallest minimum
 
147
    int min;
 
148
  public:
 
149
    /// Intialize with view \a x
 
150
    ViewSelStatus init(IntView x);
 
151
    /// Possibly select better view \a x
 
152
    ViewSelStatus select(IntView x);
 
153
  };
 
154
 
 
155
  /**
 
156
   * \brief View selection class for view with largest min
 
157
   *
 
158
   * Requires \code #include "int/branch.hh" \endcode
 
159
   * \ingroup FuncIntSelView
 
160
   */
 
161
  class ByMinMax {
 
162
  protected:
 
163
    /// So-far largest minimum
 
164
    int min;
 
165
  public:
 
166
    /// Intialize with view \a x
 
167
    ViewSelStatus init(IntView x);
 
168
    /// Possibly select better view \a x
 
169
    ViewSelStatus select(IntView x);
 
170
  };
 
171
 
 
172
  /**
 
173
   * \brief View selection class for view with smallest max
 
174
   *
 
175
   * Requires \code #include "int/branch.hh" \endcode
 
176
   * \ingroup FuncIntSelView
 
177
   */
 
178
  class ByMaxMin {
 
179
  protected:
 
180
    /// So-far smallest maximum
 
181
    int max;
 
182
  public:
 
183
    /// Intialize with view \a x
 
184
    ViewSelStatus init(IntView x);
 
185
    /// Possibly select better view \a x
 
186
    ViewSelStatus select(IntView x);
 
187
  };
 
188
 
 
189
  /**
 
190
   * \brief View selection class for view with largest max
 
191
   *
 
192
   * Requires \code #include "int/branch.hh" \endcode
 
193
   * \ingroup FuncIntSelView
 
194
   */
 
195
  class ByMaxMax {
 
196
  protected:
 
197
    /// So-far largest maximum
 
198
    int max;
 
199
  public:
 
200
    /// Intialize with view \a x
 
201
    ViewSelStatus init(IntView x);
 
202
    /// Possibly select better view \a x
 
203
    ViewSelStatus select(IntView x);
 
204
  };
 
205
 
 
206
  /**
 
207
   * \brief View selection class for view with smallest size
 
208
   *
 
209
   * Requires \code #include "int/branch.hh" \endcode
 
210
   * \ingroup FuncIntSelView
 
211
   */
 
212
  class BySizeMin {
 
213
  protected:
 
214
    /// So-far smallest size
 
215
    unsigned int size;
 
216
  public:
 
217
    /// Intialize with view \a x
 
218
    ViewSelStatus init(IntView x);
 
219
    /// Possibly select better view \a x
 
220
    ViewSelStatus select(IntView x);
 
221
  };
 
222
 
 
223
  /**
 
224
   * \brief View selection class for view with largest size
 
225
   *
 
226
   * Requires \code #include "int/branch.hh" \endcode
 
227
   * \ingroup FuncIntSelView
 
228
   */
 
229
  class BySizeMax {
 
230
  protected:
 
231
    /// So-far largest size
 
232
    unsigned int size;
 
233
  public:
 
234
    /// Intialize with view \a x
 
235
    ViewSelStatus init(IntView x);
 
236
    /// Possibly select better view \a x
 
237
    ViewSelStatus select(IntView x);
 
238
  };
 
239
 
 
240
  /**
 
241
   * \brief View selection class for view with smallest degree (and smallest size in case of ties)
 
242
   *
 
243
   * Requires \code #include "int/branch.hh" \endcode
 
244
   * \ingroup FuncIntSelView
 
245
   */
 
246
  class ByDegreeMin {
 
247
  protected:
 
248
    /// So-far smallest degree
 
249
    unsigned int degree;
 
250
    /// So-far smallest size for degree
 
251
    unsigned int size;
 
252
  public:
 
253
    /// Intialize with view \a x
 
254
    ViewSelStatus init(IntView x);
 
255
    /// Possibly select better view \a x
 
256
    ViewSelStatus select(IntView x);
 
257
  };
 
258
 
 
259
  /**
 
260
   * \brief View selection class for view with largest degree (and smallest size in case of ties)
 
261
   *
 
262
   * Requires \code #include "int/branch.hh" \endcode
 
263
   * \ingroup FuncIntSelView
 
264
   */
 
265
  class ByDegreeMax {
 
266
  protected:
 
267
    /// So-far largest degree
 
268
    unsigned int degree;
 
269
    /// So-far smallest size for degree
 
270
    unsigned int size;
 
271
  public:
 
272
    /// Intialize with view \a x
 
273
    ViewSelStatus init(IntView x);
 
274
    /// Possibly select better view \a x
 
275
    ViewSelStatus select(IntView x);
 
276
  };
 
277
 
 
278
  /**
 
279
   * \brief View selection class for view with smallest min-regret
 
280
   *
 
281
   * Requires \code #include "int/branch.hh" \endcode
 
282
   * \ingroup FuncIntSelView
 
283
   */
 
284
  class ByRegretMinMin {
 
285
  protected:
 
286
    /// So-far smallest regret
 
287
    unsigned int regret;
 
288
  public:
 
289
    /// Intialize with view \a x
 
290
    ViewSelStatus init(IntView x);
 
291
    /// Possibly select better view \a x
 
292
    ViewSelStatus select(IntView x);
 
293
  };
 
294
 
 
295
  /**
 
296
   * \brief View selection class for view with largest min-regret
 
297
   *
 
298
   * Requires \code #include "int/branch.hh" \endcode
 
299
   * \ingroup FuncIntSelView
 
300
   */
 
301
  class ByRegretMinMax {
 
302
  protected:
 
303
    /// So-far largest regret
 
304
    unsigned int regret;
 
305
  public:
 
306
    /// Intialize with view \a x
 
307
    ViewSelStatus init(IntView x);
 
308
    /// Possibly select better view \a x
 
309
    ViewSelStatus select(IntView x);
 
310
  };
 
311
 
 
312
  /**
 
313
   * \brief View selection class for view with smallest max-regret
 
314
   *
 
315
   * Requires \code #include "int/branch.hh" \endcode
 
316
   * \ingroup FuncIntSelView
 
317
   */
 
318
  class ByRegretMaxMin {
 
319
  protected:
 
320
    /// So-far smallest regret
 
321
    unsigned int regret;
 
322
  public:
 
323
    /// Intialize with view \a x
 
324
    ViewSelStatus init(IntView x);
 
325
    /// Possibly select better view \a x
 
326
    ViewSelStatus select(IntView x);
 
327
  };
 
328
 
 
329
  /**
 
330
   * \brief View selection class for view with largest max-regret
 
331
   *
 
332
   * Requires \code #include "int/branch.hh" \endcode
 
333
   * \ingroup FuncIntSelView
 
334
   */
 
335
  class ByRegretMaxMax {
 
336
  protected:
 
337
    /// So-far largest regret
 
338
    unsigned int regret;
 
339
  public:
 
340
    /// Intialize with view \a x
 
341
    ViewSelStatus init(IntView x);
 
342
    /// Possibly select better view \a x
 
343
    ViewSelStatus select(IntView x);
 
344
  };
 
345
 
 
346
 
 
347
  /*
 
348
   * Classes for assignment
 
349
   *
 
350
   */
 
351
 
 
352
  /// Assignment (single-alternative branching) base-class
 
353
  class Assign : public Branching {
 
354
  protected:
 
355
    /// Views to assign
 
356
    ViewArray<IntView> x;
 
357
    /// Next position to be assigned
 
358
    int pos;
 
359
    /// Constructor for cloning \a b
 
360
    Assign(Space* home, bool share, Assign& b);
 
361
  public:
 
362
    /// Constructor for creation
 
363
    Assign(Space* home, ViewArray<IntView>& x);
 
364
    /// Perform branching (selects view)
 
365
    virtual unsigned int branch(void);
 
366
  };
 
367
 
 
368
 
 
369
  /// Minimum assignment (single-alternative branching)
 
370
  class AssignMin : public Assign {
 
371
  protected:
 
372
    /// Constructor for cloning \a b
 
373
    AssignMin(Space* home, bool share, AssignMin& b);
 
374
  public:
 
375
    /// Constructor for creation
 
376
    AssignMin(Space* home, ViewArray<IntView>& x);
 
377
    /// Perform cloning
 
378
    virtual Actor* copy(Space* home, bool share);
 
379
    /// Return branching description (of type Gecode::PosValDesc)
 
380
    virtual BranchingDesc* description(void);
 
381
    /// Perform commit for alternative \a a and branching description \a d
 
382
    virtual ExecStatus commit(Space* home, unsigned int a, BranchingDesc* d);
 
383
  };
 
384
 
 
385
  /// Median assignment (single-alternative branching)
 
386
  class AssignMed : public Assign {
 
387
  protected:
 
388
    /// Constructor for cloning \a b
 
389
    AssignMed(Space* home, bool share, AssignMed& b);
 
390
  public:
 
391
    /// Constructor for creation
 
392
    AssignMed(Space* home, ViewArray<IntView>& x);
 
393
    /// Perform cloning
 
394
    virtual Actor* copy(Space* home, bool share);
 
395
    /// Return branching description (of type Gecode::PosValDesc)
 
396
    virtual BranchingDesc* description(void);
 
397
    /// Perform commit for alternative \a a and branching description \a d
 
398
    virtual ExecStatus commit(Space* home, unsigned int a, BranchingDesc* d);
 
399
  };
 
400
 
 
401
  /// Maximum assignment (single-alternative branching)
 
402
  class AssignMax : public Assign {
 
403
  protected:
 
404
    /// Constructor for cloning \a b
 
405
    AssignMax(Space* home, bool share, AssignMax& b);
 
406
  public:
 
407
    /// Constructor for creation
 
408
    AssignMax(Space* home, ViewArray<IntView>& x);
 
409
    /// Perform cloning
 
410
    virtual Actor* copy(Space* home, bool share);
 
411
    /// Return branching description (of type Gecode::PosValDesc)
 
412
    virtual BranchingDesc* description(void);
 
413
    /// Perform commit for alternative \a a and branching description \a d
 
414
    virtual ExecStatus commit(Space* home, unsigned int a, BranchingDesc* d);
 
415
  };
 
416
 
 
417
}}}
 
418
 
 
419
#include "int/branch/select-val.icc"
 
420
#include "int/branch/select-view.icc"
 
421
 
 
422
#include "int/branch/assign.icc"
 
423
 
 
424
#endif
 
425
 
 
426
// STATISTICS: int-branch
 
427