1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  *  Main authors:
4  *     Guido Tack <tack@gecode.org>
5  *     Christian Schulte <schulte@gecode.org>
6  *
7  *  Contributing authors:
8  *     Gabor Szokoli <szokoli@gecode.org>
9  *
10  *  Copyright:
11  *     Guido Tack, 2004
12  *     Christian Schulte, 2004
13  *     Gabor Szokoli, 2004
14  *
15  *  This file is part of Gecode, the generic constraint
16  *  development environment:
17  *     http://www.gecode.org
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 #ifndef GECODE_SET_BRANCH_HH
41 #define GECODE_SET_BRANCH_HH
42 
43 #include <gecode/set.hh>
44 
45 /**
46  * \namespace Gecode::Set::Branch
47  * \brief %Set branchings
48  */
49 
50 namespace Gecode { namespace Set { namespace Branch {
51 
52   /**
53    * \defgroup FuncSetViewSel Merit-based set view selection for branchers
54    *
55    * Contains merit-based view selection strategies on set
56    * views that can be used together with the generic view/value
57    * brancher classes.
58    *
59    * All merit-based set view selection classes require
60    * \code #include <gecode/set/branch.hh> \endcode
61    * \ingroup Other
62    */
63 
64   /**
65    * \brief Merit class for mimimum of set views
66    *
67    * Requires \code #include <gecode/set/branch.hh> \endcode
68    * \ingroup FuncSetViewSel
69    */
70   class MeritMin : public MeritBase<SetView,int> {
71   public:
72     /// Constructor for initialization
73     MeritMin(Space& home, const VarBranch<Var>& vb);
74     /// Constructor for cloning
75     MeritMin(Space& home, MeritMin& m);
76     /// Return minimum as merit for view \a x at position \a i
77     int operator ()(const Space& home, SetView x, int i);
78   };
79 
80   /**
81    * \brief Merit class for maximum of set view
82    *
83    * Requires \code #include <gecode/set/branch.hh> \endcode
84    * \ingroup FuncSetViewSel
85    */
86   class MeritMax : public MeritBase<SetView,int> {
87   public:
88     /// Constructor for initialization
89     MeritMax(Space& home, const VarBranch<Var>& vb);
90     /// Constructor for cloning
91     MeritMax(Space& home, MeritMax& m);
92     /// Return maximum as merit for view \a x at position \a i
93     int operator ()(const Space& home, SetView x, int i);
94   };
95 
96   /**
97    * \brief Merit class for size of set view
98    *
99    * Requires \code #include <gecode/set/branch.hh> \endcode
100    * \ingroup FuncSetViewSel
101    */
102   class MeritSize : public MeritBase<SetView,unsigned int> {
103   public:
104     /// Constructor for initialization
105     MeritSize(Space& home, const VarBranch<Var>& vb);
106     /// Constructor for cloning
107     MeritSize(Space& home, MeritSize& m);
108     /// Return size as merit for view \a x at position \a i
109     unsigned int operator ()(const Space& home, SetView x, int i);
110   };
111 
112   /**
113    * \brief Merit class for degree over size
114    *
115    * Requires \code #include <gecode/set/branch.hh> \endcode
116    * \ingroup FuncSetViewSel
117    */
118   class MeritDegreeSize : public MeritBase<SetView,double> {
119   public:
120     /// Constructor for initialization
121     MeritDegreeSize(Space& home, const VarBranch<Var>& vb);
122     /// Constructor for cloning
123     MeritDegreeSize(Space& home, MeritDegreeSize& m);
124     /// Return degree over size as merit for view \a x at position \a i
125     double operator ()(const Space& home, SetView x, int i);
126   };
127 
128   /**
129    * \brief Merit class for AFC over size
130    *
131    * Requires \code #include <gecode/set/branch.hh> \endcode
132    * \ingroup FuncSetViewSel
133    */
134   class MeritAFCSize : public MeritBase<SetView,double> {
135   protected:
136     /// AFC information
137     AFC afc;
138   public:
139     /// Constructor for initialization
140     MeritAFCSize(Space& home, const VarBranch<Var>& vb);
141     /// Constructor for cloning
142     MeritAFCSize(Space& home, MeritAFCSize& m);
143     /// Return AFC over size as merit for view \a x at position \a i
144     double operator ()(const Space& home, SetView x, int i);
145     /// Whether dispose must always be called (that is, notice is needed)
146     bool notice(void) const;
147     /// Dispose view selection
148     void dispose(Space& home);
149   };
150 
151   /**
152    * \brief Merit class for action over size
153    *
154    * Requires \code #include <gecode/set/branch.hh> \endcode
155    * \ingroup FuncSetViewSel
156    */
157   class MeritActionSize : public MeritBase<SetView,double> {
158   protected:
159     /// Action information
160     Action action;
161   public:
162     /// Constructor for initialization
163     MeritActionSize(Space& home, const VarBranch<Var>& vb);
164     /// Constructor for cloning
165     MeritActionSize(Space& home, MeritActionSize& m);
166     /// Return action over size as merit for view \a x at position \a i
167     double operator ()(const Space& home, SetView x, int i);
168     /// Whether dispose must always be called (that is, notice is needed)
169     bool notice(void) const;
170     /// Dispose view selection
171     void dispose(Space& home);
172   };
173 
174   /**
175    * \brief Merit class for CHB Q-score over size
176    *
177    * Requires \code #include <gecode/set/branch.hh> \endcode
178    * \ingroup FuncSetViewSel
179    */
180   class MeritCHBSize : public MeritBase<SetView,double> {
181   protected:
182     /// CHB information
183     CHB chb;
184   public:
185     /// Constructor for initialization
186     MeritCHBSize(Space& home, const VarBranch<Var>& vb);
187     /// Constructor for cloning
188     MeritCHBSize(Space& home, MeritCHBSize& m);
189     /// Return CHB Q-score over size as merit for view \a x at position \a i
190     double operator ()(const Space& home, SetView x, int i);
191     /// Whether dispose must always be called (that is, notice is needed)
192     bool notice(void) const;
193     /// Dispose view selection
194     void dispose(Space& home);
195   };
196 
197 }}}
198 
199 #include <gecode/set/branch/merit.hpp>
200 
201 namespace Gecode { namespace Set { namespace Branch {
202 
203   /// Return view selectors for set views
204   GECODE_SET_EXPORT
205   ViewSel<SetView>* viewsel(Space& home, const SetVarBranch& svb);
206 
207 }}}
208 
209 namespace Gecode { namespace Set { namespace Branch {
210 
211   /**
212    * \defgroup FuncSetValSel Set value selection for brancher
213    *
214    * Contains a description of value selection strategies on set
215    * views that can be used together with the generic view/value
216    * branchers.
217    *
218    * All value selection classes require
219    * \code #include <gecode/set/branch.hh> \endcode
220    * \ingroup Other
221    */
222 
223   /**
224    * \brief Value selection class for mimimum of view
225    *
226    * Requires \code #include <gecode/set/branch.hh> \endcode
227    * \ingroup FuncSetValSel
228    */
229   class ValSelMin : public ValSel<SetView,int> {
230   public:
231     /// Constructor for initialization
232     ValSelMin(Space& home, const ValBranch<Var>& vb);
233     /// Constructor for cloning
234     ValSelMin(Space& home, ValSelMin& vs);
235     /// Return value of view \a x at position \a i
236     int val(const Space& home, SetView x, int i);
237   };
238 
239   /**
240    * \brief Value selection class for maximum of view
241    *
242    * Requires \code #include <gecode/set/branch.hh> \endcode
243    * \ingroup FuncSetValSel
244    */
245   class ValSelMax : public ValSel<SetView,int> {
246   public:
247     /// Constructor for initialization
248     ValSelMax(Space& home, const ValBranch<Var>& vb);
249     /// Constructor for cloning
250     ValSelMax(Space& home, ValSelMax& vs);
251     /// Return value of view \a x at position \a i
252     int val(const Space& home, SetView x, int i);
253   };
254 
255   /**
256    * \brief Value selection class for median of view
257    *
258    * Requires \code #include <gecode/set/branch.hh> \endcode
259    * \ingroup FuncSetValSel
260    */
261   class ValSelMed : public ValSel<SetView,int> {
262   public:
263     /// Constructor for initialization
264     ValSelMed(Space& home, const ValBranch<Var>& vb);
265     /// Constructor for cloning
266     ValSelMed(Space& home, ValSelMed& vs);
267     /// Return value of view \a x at position \a i
268     int val(const Space& home, SetView x, int i);
269   };
270 
271   /**
272    * \brief Value selection class for random value of view
273    *
274    * Requires \code #include <gecode/set/branch.hh> \endcode
275    * \ingroup FuncSetValSel
276    */
277   class ValSelRnd : public ValSel<SetView,int> {
278   protected:
279     /// The used random number generator
280     Rnd r;
281   public:
282     /// Constructor for initialization
283     ValSelRnd(Space& home, const ValBranch<Var>& vb);
284     /// Constructor for cloning
285     ValSelRnd(Space& home, ValSelRnd& vs);
286     /// Return value of view \a x at position \a i
287     int val(const Space& home, SetView x, int i);
288     /// Whether dispose must always be called (that is, notice is needed)
289     bool notice(void) const;
290     /// Delete value selection
291     void dispose(Space& home);
292   };
293 
294 }}}
295 
296 #include <gecode/set/branch/val-sel.hpp>
297 
298 namespace Gecode { namespace Set { namespace Branch {
299 
300   /// No-good literal for inclusion
301   class IncNGL : public ViewValNGL<SetView,int,PC_SET_ANY> {
302   public:
303     /// Constructor for creation
304     IncNGL(Space& home, SetView x, int n);
305     /// Constructor for cloning \a ngl
306     IncNGL(Space& home, IncNGL& ngl);
307     /// Test the status of the no-good literal
308     GECODE_SET_EXPORT
309     virtual NGL::Status status(const Space& home) const;
310     /// Propagate the negation of the no-good literal
311     GECODE_SET_EXPORT
312     virtual ExecStatus prune(Space& home);
313     /// Create copy
314     GECODE_SET_EXPORT
315     virtual NGL* copy(Space& home);
316   };
317 
318   /// No-good literal for exclusion
319   class ExcNGL : public ViewValNGL<SetView,int,PC_SET_ANY> {
320   public:
321     /// Constructor for creation
322     ExcNGL(Space& home, SetView x, int n);
323     /// Constructor for cloning \a ngl
324     ExcNGL(Space& home, ExcNGL& ngl);
325     /// Test the status of the no-good literal
326     GECODE_SET_EXPORT
327     virtual NGL::Status status(const Space& home) const;
328     /// Propagate the negation of the no-good literal
329     GECODE_SET_EXPORT
330     virtual ExecStatus prune(Space& home);
331     /// Create copy
332     GECODE_SET_EXPORT
333     virtual NGL* copy(Space& home);
334   };
335 
336 }}}
337 
338 #include <gecode/set/branch/ngl.hpp>
339 
340 namespace Gecode { namespace Set { namespace Branch {
341 
342   /**
343    * \defgroup FuncSetValCommit Set value commit classes
344    *
345    * Contains the value commit classes for set
346    * views that can be used together with the generic view/value
347    * branchers.
348    *
349    * All value commit classes require
350    * \code #include <gecode/set/branch.hh> \endcode
351    * \ingroup Other
352    */
353 
354   /**
355    * \brief Value commit class for inclusion
356    *
357    * Requires \code #include <gecode/set/branch.hh> \endcode
358    * \ingroup FuncSetValCommit
359    */
360   class ValCommitInc : public ValCommit<SetView,int> {
361   public:
362     /// Constructor for initialization
363     ValCommitInc(Space& home, const ValBranch<Var>& vb);
364     /// Constructor for cloning
365     ValCommitInc(Space& home, ValCommitInc& vc);
366     /// Commit view \a x at position \a i to value \a n for alternative \a a
367     ModEvent commit(Space& home, unsigned int a, SetView x, int i, int n);
368     /// Create no-good literal for alternative \a a
369     NGL* ngl(Space& home, unsigned int a, View x, int n) const;
370     /// Print on \a o the alternative \a with view \a x at position \a i and value \a n
371     void print(const Space& home, unsigned int a, SetView x, int i, int n,
372                std::ostream& o) const;
373   };
374 
375   /**
376    * \brief Value commit class for exclusion
377    *
378    * Requires \code #include <gecode/set/branch.hh> \endcode
379    * \ingroup FuncSetValCommit
380    */
381   class ValCommitExc : public ValCommit<SetView,int> {
382   public:
383     /// Constructor for initialization
384     ValCommitExc(Space& home, const ValBranch<Var>& vb);
385     /// Constructor for cloning
386     ValCommitExc(Space& home, ValCommitExc& vc);
387     /// Commit view \a x at position \a i to value \a n for alternative \a a
388     ModEvent commit(Space& home, unsigned int a, SetView x, int i, int n);
389     /// Create no-good literal for alternative \a a
390     NGL* ngl(Space& home, unsigned int a, View x, int n) const;
391     /// Print on \a o the alternative \a with view \a x at position \a i and value \a n
392     void print(const Space& home, unsigned int a, SetView x, int i, int n,
393                std::ostream& o) const;
394   };
395 
396 }}}
397 
398 #include <gecode/set/branch/val-commit.hpp>
399 
400 namespace Gecode { namespace Set { namespace Branch {
401 
402   /// Return value and commit for set views
403   GECODE_SET_EXPORT
404   ValSelCommitBase<SetView,int>*
405   valselcommit(Space& home, const SetValBranch& svb);
406 
407   /// Return value and commit for set views
408   GECODE_SET_EXPORT
409   ValSelCommitBase<SetView,int>*
410   valselcommit(Space& home, const SetAssign& ia);
411 
412 }}}
413 
414 #endif
415 
416 // STATISTICS: set-branch
417 
418