this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 * Guido Tack <tack@gecode.org>
6 * Vincent Barichard <Vincent.Barichard@univ-angers.fr>
7 *
8 * Copyright:
9 * Christian Schulte, 2002
10 * Guido Tack, 2004
11 * Vincent Barichard, 2012
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.org
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38#ifndef GECODE_FLOAT_LINEAR_HH
39#define GECODE_FLOAT_LINEAR_HH
40
41#include <gecode/int.hh>
42#include <gecode/float.hh>
43
44/**
45 * \namespace Gecode::Float::Linear
46 * \brief %Linear propagators
47 */
48
49namespace Gecode { namespace Float { namespace Linear {
50
51 /**
52 * \brief Base-class for n-ary linear propagators
53 *
54 * Positive views are of type \a P whereas negative views are of type \a N.
55 */
56 template<class P, class N, PropCond pc>
57 class Lin : public Propagator {
58 protected:
59 /// Array of positive views
60 ViewArray<P> x;
61 /// Array of negative views
62 ViewArray<N> y;
63 /// Constant value
64 FloatVal c;
65
66 /// Constructor for cloning \a p
67 Lin(Space& home, Lin<P,N,pc>& p);
68 /// Constructor for creation
69 Lin(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c);
70 public:
71 /// Cost function (defined as low linear)
72 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
73 /// Schedule function
74 virtual void reschedule(Space& home);
75 /// Delete propagator and return its size
76 virtual size_t dispose(Space& home);
77 };
78
79 /**
80 * \brief Compute bounds information for positive views
81 *
82 * \relates Lin
83 */
84 template<class View>
85 void bounds_p(ModEventDelta med, ViewArray<View>& x,
86 FloatVal& c, FloatNum& sl, FloatNum& su);
87
88 /**
89 * \brief Compute bounds information for negative views
90 *
91 * \relates Lin
92 */
93 template<class View>
94 void bounds_n(ModEventDelta med, ViewArray<View>& y,
95 FloatVal& c, FloatNum& sl, FloatNum& su);
96
97 /**
98 * \brief %Propagator for bounds consistent n-ary linear equality
99 *
100 * Positive views are of type \a P whereas negative views are of type \a N.
101 *
102 * Requires \code #include <gecode/float/linear.hh> \endcode
103 * \ingroup FuncFloatProp
104 */
105 template<class P, class N>
106 class Eq : public Lin<P,N,PC_FLOAT_BND> {
107 protected:
108 using Lin<P,N,PC_FLOAT_BND>::x;
109 using Lin<P,N,PC_FLOAT_BND>::y;
110 using Lin<P,N,PC_FLOAT_BND>::c;
111
112 /// Constructor for cloning \a p
113 Eq(Space& home, Eq& p);
114 public:
115 /// Constructor for creation
116 Eq(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c);
117 /// Create copy during cloning
118 virtual Actor* copy(Space& home);
119 /// Perform propagation
120 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
121 /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i-\sum_{i=0}^{|y|-1}y_i=c\f$
122 static ExecStatus
123 post(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c);
124 };
125
126
127 /**
128 * \brief %Propagator for bounds consistent n-ary linear less or equal
129 *
130 * Positive views are of type \a P whereas negative views are of type \a N.
131 *
132 * Requires \code #include <gecode/float/linear.hh> \endcode
133 * \ingroup FuncFloatProp
134 */
135 template<class P, class N>
136 class Lq : public Lin<P,N,PC_FLOAT_BND> {
137 protected:
138 using Lin<P,N,PC_FLOAT_BND>::x;
139 using Lin<P,N,PC_FLOAT_BND>::y;
140 using Lin<P,N,PC_FLOAT_BND>::c;
141
142 /// Constructor for cloning \a p
143 Lq(Space& home, Lq& p);
144 public:
145 /// Constructor for creation
146 Lq(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c);
147 /// Create copy during cloning
148 virtual Actor* copy(Space& home);
149 /// Perform propagation
150 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
151 /// Post propagator for \f$\sum_{i=0}^{|x|-1}x_i-\sum_{i=0}^{|y|-1}y_i\leq c\f$
152 static ExecStatus
153 post(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c);
154 };
155
156}}}
157
158#include <gecode/float/linear/nary.hpp>
159
160namespace Gecode { namespace Float { namespace Linear {
161
162 /**
163 * \brief Class for describing linear term \f$a\cdot x\f$
164 *
165 */
166 class Term {
167 public:
168 /// Coefficient
169 FloatVal a;
170 /// View
171 FloatView x;
172 };
173
174 /** \brief Estimate lower and upper bounds
175 *
176 * Estimates the boundaries for a linear expression
177 * \f$\sum_{i=0}^{n-1}t_i + c\f$. If the boundaries exceed
178 * the limits as defined in Limits::Float, these boundaries
179 * are returned.
180 *
181 * \param t array of linear terms
182 * \param n size of array
183 * \param c constant
184 * \param l lower bound
185 * \param u upper bound
186 *
187 */
188 GECODE_FLOAT_EXPORT void
189 estimate(Term* t, int n, FloatVal c, FloatNum& l, FloatNum& u);
190
191 /**
192 * \brief Post propagator for linear constraint over floats
193 * \param home current space
194 * \param t array of linear terms over floats
195 * \param n size of array
196 * \param frt type of relation
197 * \param c result of linear constraint
198 *
199 * All variants for linear constraints share the following properties:
200 * - Variables occuring multiply in the term array are replaced
201 * by a single occurence: for example, \f$ax+bx\f$ becomes
202 * \f$(a+b)x\f$.
203 *
204 * Requires \code #include <gecode/float/linear.hh> \endcode
205 * \ingroup FuncFloatProp
206 */
207 GECODE_FLOAT_EXPORT void
208 post(Home home, Term* t, int n, FloatRelType frt, FloatVal c);
209
210 /**
211 * \brief Post propagator for reified linear constraint over floats
212 * \param home current space
213 * \param t array of linear terms over Booleans
214 * \param n size of array
215 * \param frt type of relation
216 * \param c result of linear constraint
217 * \param r reification specification
218 *
219 * All variants for linear constraints share the following properties:
220 * - Variables occuring multiply in the term array are replaced
221 * by a single occurence: for example, \f$ax+bx\f$ becomes
222 * \f$(a+b)x\f$.
223 *
224 * Requires \code #include <gecode/float/linear.hh> \endcode
225 * \ingroup FuncFloatProp
226 */
227 GECODE_FLOAT_EXPORT void
228 post(Home home, Term* t, int n, FloatRelType frt, FloatVal c, Reify r);
229
230}}}
231
232#endif
233
234// STATISTICS: float-prop