1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  *  Main authors:
4  *     Christian Schulte <schulte@gecode.org>
5  *     Vincent Barichard <Vincent.Barichard@univ-angers.fr>
6  *
7  *  Copyright:
8  *     Christian Schulte, 2012
9  *     Vincent Barichard, 2012
10  *
11  *  This file is part of Gecode, the generic constraint
12  *  development environment:
13  *     http://www.gecode.org
14  *
15  *  Permission is hereby granted, free of charge, to any person obtaining
16  *  a copy of this software and associated documentation files (the
17  *  "Software"), to deal in the Software without restriction, including
18  *  without limitation the rights to use, copy, modify, merge, publish,
19  *  distribute, sublicense, and/or sell copies of the Software, and to
20  *  permit persons to whom the Software is furnished to do so, subject to
21  *  the following conditions:
22  *
23  *  The above copyright notice and this permission notice shall be
24  *  included in all copies or substantial portions of the Software.
25  *
26  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33  *
34  */
35 
36 #ifndef GECODE_FLOAT_BRANCH_HH
37 #define GECODE_FLOAT_BRANCH_HH
38 
39 #include <gecode/float.hh>
40 
41 /**
42  * \namespace Gecode::Float::Branch
43  * \brief Float branchers
44  */
45 
46 namespace Gecode { namespace Float { namespace Branch {
47 
48   /**
49    * \defgroup FuncFloatViewSel Merit-based float view selection for branchers
50    *
51    * Contains merit-based view selection strategies on float
52    * views that can be used together with the generic view/value
53    * brancher classes.
54    *
55    * All merit-based float view selection classes require
56    * \code #include <gecode/float/branch.hh> \endcode
57    * \ingroup Other
58    */
59 
60   /**
61    * \brief Merit class for mimimum
62    *
63    * Requires \code #include <gecode/float/branch.hh> \endcode
64    * \ingroup FuncFloatViewSel
65    */
66   class MeritMin : public MeritBase<FloatView,double> {
67   public:
68     /// Constructor for initialization
69     MeritMin(Space& home, const VarBranch<Var>& vb);
70     /// Constructor for cloning
71     MeritMin(Space& home, MeritMin& m);
72     /// Return minimum as merit for view \a x at position \a i
73     double operator ()(const Space& home, FloatView x, int i);
74   };
75 
76   /**
77    * \brief Merit class for maximum of float view
78    *
79    * Requires \code #include <gecode/float/branch.hh> \endcode
80    * \ingroup FuncFloatViewSel
81    */
82   class MeritMax : public MeritBase<FloatView,double> {
83   public:
84     /// Constructor for initialization
85     MeritMax(Space& home, const VarBranch<Var>& vb);
86     /// Constructor for cloning
87     MeritMax(Space& home, MeritMax& m);
88     /// Return maximum as merit for view \a x at position \a i
89     double operator ()(const Space& home, FloatView x, int i);
90   };
91 
92   /**
93    * \brief Merit class for size of float view
94    *
95    * Requires \code #include <gecode/float/branch.hh> \endcode
96    * \ingroup FuncFloatViewSel
97    */
98   class MeritSize : public MeritBase<FloatView,double> {
99   public:
100     /// Constructor for initialization
101     MeritSize(Space& home, const VarBranch<Var>& vb);
102     /// Constructor for cloning
103     MeritSize(Space& home, MeritSize& m);
104     /// Return size as merit for view \a x at position \a i
105     double operator ()(const Space& home, FloatView x, int i);
106   };
107 
108   /**
109    * \brief Merit class for degree over size
110    *
111    * Requires \code #include <gecode/float/branch.hh> \endcode
112    * \ingroup FuncFloatViewSel
113    */
114   class MeritDegreeSize : public MeritBase<FloatView,double> {
115   public:
116     /// Constructor for initialization
117     MeritDegreeSize(Space& home, const VarBranch<Var>& vb);
118     /// Constructor for cloning
119     MeritDegreeSize(Space& home, MeritDegreeSize& m);
120     /// Return degree over size as merit for view \a x at position \a i
121     double operator ()(const Space& home, FloatView x, int i);
122   };
123 
124   /**
125    * \brief Merit class for AFC over size
126    *
127    * Requires \code #include <gecode/float/branch.hh> \endcode
128    * \ingroup FuncFloatViewSel
129    */
130   class MeritAFCSize : public MeritBase<FloatView,double> {
131   protected:
132     /// AFC information
133     AFC afc;
134   public:
135     /// Constructor for initialization
136     MeritAFCSize(Space& home, const VarBranch<Var>& vb);
137     /// Constructor for cloning
138     MeritAFCSize(Space& home, MeritAFCSize& m);
139     /// Return AFC over size as merit for view \a x at position \a i
140     double operator ()(const Space& home, FloatView x, int i);
141     /// Whether dispose must always be called (that is, notice is needed)
142     bool notice(void) const;
143     /// Dispose view selection
144     void dispose(Space& home);
145   };
146 
147   /**
148    * \brief Merit class for action over size
149    *
150    * Requires \code #include <gecode/float/branch.hh> \endcode
151    * \ingroup FuncFloatViewSel
152    */
153   class MeritActionSize : public MeritBase<FloatView,double> {
154   protected:
155     /// Action information
156     Action action;
157   public:
158     /// Constructor for initialization
159     MeritActionSize(Space& home, const VarBranch<Var>& vb);
160     /// Constructor for cloning
161     MeritActionSize(Space& home, MeritActionSize& m);
162     /// Return action over size as merit for view \a x at position \a i
163     double operator ()(const Space& home, FloatView x, int i);
164     /// Whether dispose must always be called (that is, notice is needed)
165     bool notice(void) const;
166     /// Dispose view selection
167     void dispose(Space& home);
168   };
169 
170   /**
171    * \brief Merit class for CHB Q-score over size
172    *
173    * Requires \code #include <gecode/float/branch.hh> \endcode
174    * \ingroup FuncFloatViewSel
175    */
176   class MeritCHBSize : public MeritBase<FloatView,double> {
177   protected:
178     /// CHB information
179     CHB chb;
180   public:
181     /// Constructor for initialization
182     MeritCHBSize(Space& home, const VarBranch<Var>& vb);
183     /// Constructor for cloning
184     MeritCHBSize(Space& home, MeritCHBSize& m);
185     /// Return CHB Q-score over size as merit for view \a x at position \a i
186     double operator ()(const Space& home, FloatView x, int i);
187     /// Whether dispose must always be called (that is, notice is needed)
188     bool notice(void) const;
189     /// Dispose view selection
190     void dispose(Space& home);
191   };
192 
193 }}}
194 
195 #include <gecode/float/branch/merit.hpp>
196 
197 namespace Gecode { namespace Float { namespace Branch {
198 
199   /// Return view selectors for float views
200   GECODE_FLOAT_EXPORT
201   ViewSel<FloatView>* viewsel(Space& home, const FloatVarBranch& fvb);
202 
203 }}}
204 
205 namespace Gecode { namespace Float { namespace Branch {
206 
207   /**
208    * \defgroup FuncFloatValSel Float value selection for brancher
209    *
210    * Contains a description of value selection strategies on float
211    * views that can be used together with the generic view/value
212    * branchers.
213    *
214    * All value selection classes require
215    * \code #include <gecode/float/branch.hh> \endcode
216    * \ingroup Other
217    */
218 
219   /**
220    * \brief Value selection class for values smaller than median of view
221    *
222    * Requires \code #include <gecode/float/branch.hh> \endcode
223    * \ingroup FuncFloatValSel
224    */
225   class ValSelLq : public ValSel<FloatView,FloatNumBranch> {
226   public:
227     /// Constructor for initialization
228     ValSelLq(Space& home, const ValBranch<Var>& vb);
229     /// Constructor for cloning
230     ValSelLq(Space& home, ValSelLq& vs);
231     /// Return value of view \a x at position \a i
232     FloatNumBranch val(const Space& home, FloatView x, int i);
233   };
234 
235   /**
236    * \brief Value selection class for values smaller than median of view
237    *
238    * Requires \code #include <gecode/float/branch.hh> \endcode
239    * \ingroup FuncFloatValSel
240    */
241   class ValSelGq : public ValSel<FloatView,FloatNumBranch> {
242   public:
243     /// Constructor for initialization
244     ValSelGq(Space& home, const ValBranch<Var>& vb);
245     /// Constructor for cloning
246     ValSelGq(Space& home, ValSelGq& vs);
247     /// Return value of view \a x at position \a i
248     FloatNumBranch val(const Space& home, FloatView x, int i);
249   };
250 
251   /**
252    * \brief Value selection class for random value of view
253    *
254    * Requires \code #include <gecode/float/branch.hh> \endcode
255    * \ingroup FuncFloatValSel
256    */
257   class ValSelRnd : public ValSel<FloatView,FloatNumBranch> {
258   protected:
259     /// The used random number generator
260     Rnd r;
261   public:
262     /// Constructor for initialization
263     ValSelRnd(Space& home, const ValBranch<Var>& vb);
264     /// Constructor for cloning
265     ValSelRnd(Space& home, ValSelRnd& vs);
266     /// Return value of view \a x at position \a i
267     FloatNumBranch val(const Space& home, FloatView x, int i);
268     /// Whether dispose must always be called (that is, notice is needed)
269     bool notice(void) const;
270     /// Delete value selection
271     void dispose(Space& home);
272   };
273 
274 }}}
275 
276 #include <gecode/float/branch/val-sel.hpp>
277 
278 namespace Gecode { namespace Float { namespace Branch {
279 
280   /**
281    * \defgroup FuncFloatValCommit Float value commit classes
282    *
283    * Contains the value commit classes for float
284    * views that can be used together with the generic view/value
285    * branchers.
286    *
287    * All value commit classes require
288    * \code #include <gecode/float/branch.hh> \endcode
289    * \ingroup Other
290    */
291 
292   /**
293    * \brief Value commit class for less or equal or greater or equal
294    *
295    * Requires \code #include <gecode/float/branch.hh> \endcode
296    * \ingroup FuncFloatValCommit
297    */
298   class ValCommitLqGq  : public ValCommit<FloatView,FloatVal> {
299   public:
300     /// Constructor for initialization
301     ValCommitLqGq(Space& home, const ValBranch<Var>& vb);
302     /// Constructor for cloning
303     ValCommitLqGq(Space& home, ValCommitLqGq& vc);
304     /// Commit view \a x at position \a i to value \a n for alternative \a a
305     ModEvent commit(Space& home, unsigned int a, FloatView x, int i,
306                     FloatNumBranch n);
307     /// Create no-good literal for alternative \a a
308     NGL* ngl(Space& home, unsigned int a, FloatView x, FloatNumBranch n) const;
309     /// Print on \a o the alternative \a with view \a x at position \a i and value \a n
310     void print(const Space& home, unsigned int a, FloatView x, int i,
311                FloatNumBranch n,
312                std::ostream& o) const;
313   };
314 
315 }}}
316 
317 #include <gecode/float/branch/val-commit.hpp>
318 
319 namespace Gecode { namespace Float { namespace Branch {
320 
321   /// Return value and commit for float views
322   GECODE_FLOAT_EXPORT
323   ValSelCommitBase<FloatView,FloatNumBranch>*
324   valselcommit(Space& home, const FloatValBranch& svb);
325 
326   /// Return value and commit for float views
327   GECODE_FLOAT_EXPORT
328   ValSelCommitBase<FloatView,FloatNumBranch>*
329   valselcommit(Space& home, const FloatAssign& ia);
330 
331 }}}
332 
333 #endif
334 
335 // STATISTICS: float-branch
336