1 |
|
/****************************************************************************** |
2 |
|
* Top contributors (to current version): |
3 |
|
* Andrew Reynolds, Aina Niemetz, Andres Noetzli |
4 |
|
* |
5 |
|
* This file is part of the cvc5 project. |
6 |
|
* |
7 |
|
* Copyright (c) 2009-2021 by the authors listed in the file AUTHORS |
8 |
|
* in the top-level source directory and their institutional affiliations. |
9 |
|
* All rights reserved. See the file COPYING in the top-level source |
10 |
|
* directory for licensing information. |
11 |
|
* **************************************************************************** |
12 |
|
* |
13 |
|
* Arithmetic instantiator. |
14 |
|
*/ |
15 |
|
|
16 |
|
#include "theory/quantifiers/cegqi/ceg_arith_instantiator.h" |
17 |
|
|
18 |
|
#include "expr/node_algorithm.h" |
19 |
|
#include "options/quantifiers_options.h" |
20 |
|
#include "theory/arith/arith_msum.h" |
21 |
|
#include "theory/arith/partial_model.h" |
22 |
|
#include "theory/arith/theory_arith.h" |
23 |
|
#include "theory/arith/theory_arith_private.h" |
24 |
|
#include "theory/quantifiers/term_util.h" |
25 |
|
#include "theory/rewriter.h" |
26 |
|
#include "util/random.h" |
27 |
|
|
28 |
|
using namespace std; |
29 |
|
using namespace cvc5::kind; |
30 |
|
using namespace cvc5::context; |
31 |
|
|
32 |
|
namespace cvc5 { |
33 |
|
namespace theory { |
34 |
|
namespace quantifiers { |
35 |
|
|
36 |
1616 |
ArithInstantiator::ArithInstantiator(TypeNode tn, VtsTermCache* vtc) |
37 |
1616 |
: Instantiator(tn), d_vtc(vtc) |
38 |
|
{ |
39 |
1616 |
d_zero = NodeManager::currentNM()->mkConst(Rational(0)); |
40 |
1616 |
d_one = NodeManager::currentNM()->mkConst(Rational(1)); |
41 |
1616 |
} |
42 |
|
|
43 |
11904 |
void ArithInstantiator::reset(CegInstantiator* ci, |
44 |
|
SolvedForm& sf, |
45 |
|
Node pv, |
46 |
|
CegInstEffort effort) |
47 |
|
{ |
48 |
11904 |
d_vts_sym[0] = d_vtc->getVtsInfinity(d_type, false, false); |
49 |
11904 |
d_vts_sym[1] = d_vtc->getVtsDelta(false, false); |
50 |
35712 |
for (unsigned i = 0; i < 2; i++) |
51 |
|
{ |
52 |
23808 |
d_mbp_bounds[i].clear(); |
53 |
23808 |
d_mbp_coeff[i].clear(); |
54 |
71424 |
for (unsigned j = 0; j < 2; j++) |
55 |
|
{ |
56 |
47616 |
d_mbp_vts_coeff[i][j].clear(); |
57 |
|
} |
58 |
23808 |
d_mbp_lit[i].clear(); |
59 |
|
} |
60 |
11904 |
} |
61 |
|
|
62 |
11546 |
bool ArithInstantiator::hasProcessEquality(CegInstantiator* ci, |
63 |
|
SolvedForm& sf, |
64 |
|
Node pv, |
65 |
|
CegInstEffort effort) |
66 |
|
{ |
67 |
11546 |
return true; |
68 |
|
} |
69 |
|
|
70 |
15288 |
bool ArithInstantiator::processEquality(CegInstantiator* ci, |
71 |
|
SolvedForm& sf, |
72 |
|
Node pv, |
73 |
|
std::vector<TermProperties>& term_props, |
74 |
|
std::vector<Node>& terms, |
75 |
|
CegInstEffort effort) |
76 |
|
{ |
77 |
15288 |
NodeManager* nm = NodeManager::currentNM(); |
78 |
30576 |
Node eq_lhs = terms[0]; |
79 |
30576 |
Node eq_rhs = terms[1]; |
80 |
30576 |
Node lhs_coeff = term_props[0].d_coeff; |
81 |
30576 |
Node rhs_coeff = term_props[1].d_coeff; |
82 |
|
// make the same coefficient |
83 |
15288 |
if (rhs_coeff != lhs_coeff) |
84 |
|
{ |
85 |
|
if (!rhs_coeff.isNull()) |
86 |
|
{ |
87 |
|
Trace("cegqi-arith-debug") << "...mult lhs by " << rhs_coeff << std::endl; |
88 |
|
eq_lhs = nm->mkNode(MULT, rhs_coeff, eq_lhs); |
89 |
|
eq_lhs = Rewriter::rewrite(eq_lhs); |
90 |
|
} |
91 |
|
if (!lhs_coeff.isNull()) |
92 |
|
{ |
93 |
|
Trace("cegqi-arith-debug") << "...mult rhs by " << lhs_coeff << std::endl; |
94 |
|
eq_rhs = nm->mkNode(MULT, lhs_coeff, eq_rhs); |
95 |
|
eq_rhs = Rewriter::rewrite(eq_rhs); |
96 |
|
} |
97 |
|
} |
98 |
30576 |
Node eq = eq_lhs.eqNode(eq_rhs); |
99 |
15288 |
eq = Rewriter::rewrite(eq); |
100 |
30576 |
Node val; |
101 |
30576 |
TermProperties pv_prop; |
102 |
30576 |
Node vts_coeff_inf; |
103 |
30576 |
Node vts_coeff_delta; |
104 |
|
// isolate pv in the equality |
105 |
30576 |
CegTermType ires = solve_arith( |
106 |
15288 |
ci, pv, eq, pv_prop.d_coeff, val, vts_coeff_inf, vts_coeff_delta); |
107 |
15288 |
if (ires != CEG_TT_INVALID) |
108 |
|
{ |
109 |
4971 |
pv_prop.d_type = CEG_TT_EQUAL; |
110 |
4971 |
if (ci->constructInstantiationInc(pv, val, pv_prop, sf)) |
111 |
|
{ |
112 |
4163 |
return true; |
113 |
|
} |
114 |
|
} |
115 |
11125 |
return false; |
116 |
|
} |
117 |
|
|
118 |
6579 |
bool ArithInstantiator::hasProcessAssertion(CegInstantiator* ci, |
119 |
|
SolvedForm& sf, |
120 |
|
Node pv, |
121 |
|
CegInstEffort effort) |
122 |
|
{ |
123 |
6579 |
return effort != CEG_INST_EFFORT_FULL; |
124 |
|
} |
125 |
|
|
126 |
137485 |
Node ArithInstantiator::hasProcessAssertion(CegInstantiator* ci, |
127 |
|
SolvedForm& sf, |
128 |
|
Node pv, |
129 |
|
Node lit, |
130 |
|
CegInstEffort effort) |
131 |
|
{ |
132 |
274970 |
Node atom = lit.getKind() == NOT ? lit[0] : lit; |
133 |
|
// arithmetic inequalities and disequalities |
134 |
274970 |
if (atom.getKind() == GEQ |
135 |
274970 |
|| (atom.getKind() == EQUAL && atom[0].getType().isReal())) |
136 |
|
{ |
137 |
137485 |
return lit; |
138 |
|
} |
139 |
|
return Node::null(); |
140 |
|
} |
141 |
|
|
142 |
7186 |
bool ArithInstantiator::processAssertion(CegInstantiator* ci, |
143 |
|
SolvedForm& sf, |
144 |
|
Node pv, |
145 |
|
Node lit, |
146 |
|
Node alit, |
147 |
|
CegInstEffort effort) |
148 |
|
{ |
149 |
7186 |
NodeManager* nm = NodeManager::currentNM(); |
150 |
14372 |
Node atom = lit.getKind() == NOT ? lit[0] : lit; |
151 |
7186 |
bool pol = lit.getKind() != NOT; |
152 |
|
// arithmetic inequalities and disequalities |
153 |
7186 |
Assert(atom.getKind() == GEQ |
154 |
|
|| (atom.getKind() == EQUAL && atom[0].getType().isReal())); |
155 |
|
// get model value for pv |
156 |
14372 |
Node pv_value = ci->getModelValue(pv); |
157 |
|
// cannot contain infinity? |
158 |
14372 |
Node vts_coeff_inf; |
159 |
14372 |
Node vts_coeff_delta; |
160 |
14372 |
Node val; |
161 |
14372 |
TermProperties pv_prop; |
162 |
|
// isolate pv in the inequality |
163 |
14372 |
CegTermType ires = solve_arith( |
164 |
7186 |
ci, pv, atom, pv_prop.d_coeff, val, vts_coeff_inf, vts_coeff_delta); |
165 |
7186 |
if (ires == CEG_TT_INVALID) |
166 |
|
{ |
167 |
716 |
return false; |
168 |
|
} |
169 |
|
// compute how many bounds we will consider |
170 |
6470 |
unsigned rmax = 1; |
171 |
6470 |
if (atom.getKind() == EQUAL && (pol || !options::cegqiModel())) |
172 |
|
{ |
173 |
|
rmax = 2; |
174 |
|
} |
175 |
12940 |
for (unsigned r = 0; r < rmax; r++) |
176 |
|
{ |
177 |
6470 |
CegTermType uires = ires; |
178 |
12940 |
Node uval = val; |
179 |
6470 |
if (atom.getKind() == GEQ) |
180 |
|
{ |
181 |
|
// push negation downwards |
182 |
4838 |
if (!pol) |
183 |
|
{ |
184 |
2215 |
uires = mkNegateCTT(ires); |
185 |
2215 |
if (d_type.isInteger()) |
186 |
|
{ |
187 |
1858 |
uval = nm->mkNode( |
188 |
|
PLUS, |
189 |
|
val, |
190 |
3716 |
nm->mkConst(Rational(isUpperBoundCTT(uires) ? 1 : -1))); |
191 |
1858 |
uval = Rewriter::rewrite(uval); |
192 |
|
} |
193 |
|
else |
194 |
|
{ |
195 |
357 |
Assert(d_type.isReal()); |
196 |
|
// now is strict inequality |
197 |
357 |
uires = mkStrictCTT(uires); |
198 |
|
} |
199 |
|
} |
200 |
|
} |
201 |
1632 |
else if (pol) |
202 |
|
{ |
203 |
|
// equalities are both non-strict upper and lower bounds |
204 |
|
uires = r == 0 ? CEG_TT_UPPER : CEG_TT_LOWER; |
205 |
|
} |
206 |
|
else |
207 |
|
{ |
208 |
|
// disequalities are either strict upper or lower bounds |
209 |
|
bool is_upper; |
210 |
1632 |
if (options::cegqiModel()) |
211 |
|
{ |
212 |
|
// disequality is a disjunction : only consider the bound in the |
213 |
|
// direction of the model |
214 |
|
// first check if there is an infinity... |
215 |
1632 |
if (!vts_coeff_inf.isNull()) |
216 |
|
{ |
217 |
|
// coefficient or val won't make a difference, just compare with zero |
218 |
|
Trace("cegqi-arith-debug") << "Disequality : check infinity polarity " |
219 |
|
<< vts_coeff_inf << std::endl; |
220 |
|
Assert(vts_coeff_inf.isConst()); |
221 |
|
is_upper = (vts_coeff_inf.getConst<Rational>().sgn() == 1); |
222 |
|
} |
223 |
|
else |
224 |
|
{ |
225 |
3264 |
Node rhs_value = ci->getModelValue(val); |
226 |
3264 |
Node lhs_value = pv_prop.getModifiedTerm(pv_value); |
227 |
1632 |
if (!pv_prop.isBasic()) |
228 |
|
{ |
229 |
10 |
lhs_value = pv_prop.getModifiedTerm(pv_value); |
230 |
10 |
lhs_value = Rewriter::rewrite(lhs_value); |
231 |
|
} |
232 |
3264 |
Trace("cegqi-arith-debug") |
233 |
1632 |
<< "Disequality : check model values " << lhs_value << " " |
234 |
1632 |
<< rhs_value << std::endl; |
235 |
|
// it generally should be the case that lhs_value!=rhs_value |
236 |
|
// however, this assertion is violated e.g. if non-linear is enabled |
237 |
|
// since the quantifier-free arithmetic solver may pass full |
238 |
|
// effort with no lemmas even when we are not guaranteed to have a |
239 |
|
// model. By convention, we use GEQ to compare the values here. |
240 |
|
// It also may be the case that cmp is non-constant, in the case |
241 |
|
// where lhs or rhs contains a transcendental function. We consider |
242 |
|
// the bound to be an upper bound in this case. |
243 |
3264 |
Node cmp = nm->mkNode(GEQ, lhs_value, rhs_value); |
244 |
1632 |
cmp = Rewriter::rewrite(cmp); |
245 |
1632 |
is_upper = !cmp.isConst() || !cmp.getConst<bool>(); |
246 |
|
} |
247 |
|
} |
248 |
|
else |
249 |
|
{ |
250 |
|
// since we are not using the model, we try both. |
251 |
|
is_upper = (r == 0); |
252 |
|
} |
253 |
1632 |
Assert(atom.getKind() == EQUAL && !pol); |
254 |
1632 |
if (d_type.isInteger()) |
255 |
|
{ |
256 |
1479 |
uires = is_upper ? CEG_TT_LOWER : CEG_TT_UPPER; |
257 |
1479 |
uval = nm->mkNode( |
258 |
2958 |
PLUS, val, nm->mkConst(Rational(isUpperBoundCTT(uires) ? 1 : -1))); |
259 |
1479 |
uval = Rewriter::rewrite(uval); |
260 |
|
} |
261 |
|
else |
262 |
|
{ |
263 |
153 |
Assert(d_type.isReal()); |
264 |
153 |
uires = is_upper ? CEG_TT_LOWER_STRICT : CEG_TT_UPPER_STRICT; |
265 |
|
} |
266 |
|
} |
267 |
6470 |
if (Trace.isOn("cegqi-arith-bound-inf")) |
268 |
|
{ |
269 |
|
Node pvmod = pv_prop.getModifiedTerm(pv); |
270 |
|
Trace("cegqi-arith-bound-inf") << "From " << lit << ", got : "; |
271 |
|
Trace("cegqi-arith-bound-inf") |
272 |
|
<< pvmod << " -> " << uval << ", styp = " << uires << std::endl; |
273 |
|
} |
274 |
|
// take into account delta |
275 |
6470 |
if (uires == CEG_TT_UPPER_STRICT || uires == CEG_TT_LOWER_STRICT) |
276 |
|
{ |
277 |
510 |
if (options::cegqiModel()) |
278 |
|
{ |
279 |
|
Node delta_coeff = |
280 |
1020 |
nm->mkConst(Rational(isUpperBoundCTT(uires) ? 1 : -1)); |
281 |
510 |
if (vts_coeff_delta.isNull()) |
282 |
|
{ |
283 |
510 |
vts_coeff_delta = delta_coeff; |
284 |
|
} |
285 |
|
else |
286 |
|
{ |
287 |
|
vts_coeff_delta = nm->mkNode(PLUS, vts_coeff_delta, delta_coeff); |
288 |
|
vts_coeff_delta = Rewriter::rewrite(vts_coeff_delta); |
289 |
|
} |
290 |
|
} |
291 |
|
else |
292 |
|
{ |
293 |
|
Node delta = d_vtc->getVtsDelta(); |
294 |
|
uval = nm->mkNode( |
295 |
|
uires == CEG_TT_UPPER_STRICT ? PLUS : MINUS, uval, delta); |
296 |
|
uval = Rewriter::rewrite(uval); |
297 |
|
} |
298 |
|
} |
299 |
6470 |
if (options::cegqiModel()) |
300 |
|
{ |
301 |
|
// just store bounds, will choose based on tighest bound |
302 |
6470 |
unsigned index = isUpperBoundCTT(uires) ? 0 : 1; |
303 |
6470 |
d_mbp_bounds[index].push_back(uval); |
304 |
6470 |
d_mbp_coeff[index].push_back(pv_prop.d_coeff); |
305 |
12940 |
Trace("cegqi-arith-debug") |
306 |
6470 |
<< "Store bound " << index << " " << uval << " " << pv_prop.d_coeff |
307 |
6470 |
<< " " << vts_coeff_inf << " " << vts_coeff_delta << " " << lit |
308 |
6470 |
<< std::endl; |
309 |
19410 |
for (unsigned t = 0; t < 2; t++) |
310 |
|
{ |
311 |
12940 |
d_mbp_vts_coeff[index][t].push_back(t == 0 ? vts_coeff_inf |
312 |
|
: vts_coeff_delta); |
313 |
|
} |
314 |
6470 |
d_mbp_lit[index].push_back(lit); |
315 |
|
} |
316 |
|
else |
317 |
|
{ |
318 |
|
// try this bound |
319 |
|
pv_prop.d_type = isUpperBoundCTT(uires) ? CEG_TT_UPPER : CEG_TT_LOWER; |
320 |
|
if (ci->constructInstantiationInc(pv, uval, pv_prop, sf)) |
321 |
|
{ |
322 |
|
return true; |
323 |
|
} |
324 |
|
} |
325 |
|
} |
326 |
6470 |
return false; |
327 |
|
} |
328 |
|
|
329 |
5928 |
bool ArithInstantiator::processAssertions(CegInstantiator* ci, |
330 |
|
SolvedForm& sf, |
331 |
|
Node pv, |
332 |
|
CegInstEffort effort) |
333 |
|
{ |
334 |
5928 |
if (!options::cegqiModel()) |
335 |
|
{ |
336 |
|
return false; |
337 |
|
} |
338 |
5928 |
NodeManager* nm = NodeManager::currentNM(); |
339 |
|
bool use_inf = |
340 |
11868 |
d_type.isInteger() ? options::cegqiUseInfInt() : options::cegqiUseInfReal(); |
341 |
5928 |
bool upper_first = Random::getRandom().pickWithProb(0.5); |
342 |
11856 |
if (options::cegqiMinBounds()) |
343 |
|
{ |
344 |
|
upper_first = d_mbp_bounds[1].size() < d_mbp_bounds[0].size(); |
345 |
|
} |
346 |
|
int best_used[2]; |
347 |
11856 |
std::vector<Node> t_values[3]; |
348 |
11856 |
Node pv_value = ci->getModelValue(pv); |
349 |
|
// try optimal bounds |
350 |
13230 |
for (unsigned r = 0; r < 2; r++) |
351 |
|
{ |
352 |
9989 |
int rr = upper_first ? (1 - r) : r; |
353 |
9989 |
best_used[rr] = -1; |
354 |
9989 |
if (d_mbp_bounds[rr].empty()) |
355 |
|
{ |
356 |
7316 |
if (use_inf) |
357 |
|
{ |
358 |
304 |
Trace("cegqi-arith-bound") |
359 |
152 |
<< "No " << (rr == 0 ? "lower" : "upper") << " bounds for " << pv |
360 |
152 |
<< " (type=" << d_type << ")" << std::endl; |
361 |
|
// no bounds, we do +- infinity |
362 |
152 |
Node val = d_vtc->getVtsInfinity(d_type); |
363 |
|
// could get rho value for infinity here |
364 |
152 |
if (rr == 0) |
365 |
|
{ |
366 |
96 |
val = nm->mkNode(UMINUS, val); |
367 |
96 |
val = Rewriter::rewrite(val); |
368 |
|
} |
369 |
152 |
TermProperties pv_prop_no_bound; |
370 |
152 |
if (ci->constructInstantiationInc(pv, val, pv_prop_no_bound, sf)) |
371 |
|
{ |
372 |
152 |
return true; |
373 |
|
} |
374 |
33076 |
else if (!options::cegqiMultiInst()) |
375 |
|
{ |
376 |
|
return false; |
377 |
|
} |
378 |
|
} |
379 |
|
} |
380 |
|
else |
381 |
|
{ |
382 |
5346 |
Trace("cegqi-arith-bound") |
383 |
2673 |
<< (rr == 0 ? "Lower" : "Upper") << " bounds for " << pv |
384 |
2673 |
<< " (type=" << d_type << ") : " << std::endl; |
385 |
2673 |
int best = -1; |
386 |
10692 |
Node best_bound_value[3]; |
387 |
7319 |
for (unsigned j = 0, nbounds = d_mbp_bounds[rr].size(); j < nbounds; j++) |
388 |
|
{ |
389 |
9292 |
Node value[3]; |
390 |
4646 |
if (Trace.isOn("cegqi-arith-bound")) |
391 |
|
{ |
392 |
|
Assert(!d_mbp_bounds[rr][j].isNull()); |
393 |
|
Trace("cegqi-arith-bound") |
394 |
|
<< " " << j << ": " << d_mbp_bounds[rr][j]; |
395 |
|
if (!d_mbp_vts_coeff[rr][0][j].isNull()) |
396 |
|
{ |
397 |
|
Trace("cegqi-arith-bound") |
398 |
|
<< " (+ " << d_mbp_vts_coeff[rr][0][j] << " * INF)"; |
399 |
|
} |
400 |
|
if (!d_mbp_vts_coeff[rr][1][j].isNull()) |
401 |
|
{ |
402 |
|
Trace("cegqi-arith-bound") |
403 |
|
<< " (+ " << d_mbp_vts_coeff[rr][1][j] << " * DELTA)"; |
404 |
|
} |
405 |
|
if (!d_mbp_coeff[rr][j].isNull()) |
406 |
|
{ |
407 |
|
Trace("cegqi-arith-bound") << " (div " << d_mbp_coeff[rr][j] << ")"; |
408 |
|
} |
409 |
|
Trace("cegqi-arith-bound") << ", value = "; |
410 |
|
} |
411 |
4646 |
t_values[rr].push_back(Node::null()); |
412 |
|
// check if it is better than the current best bound : lexicographic |
413 |
|
// order infinite/finite/infinitesimal parts |
414 |
4646 |
bool new_best_set = false; |
415 |
4646 |
bool new_best = true; |
416 |
16917 |
for (unsigned t = 0; t < 3; t++) |
417 |
|
{ |
418 |
|
// get the value |
419 |
13106 |
if (t == 0) |
420 |
|
{ |
421 |
4646 |
value[0] = d_mbp_vts_coeff[rr][0][j]; |
422 |
4646 |
if (!value[0].isNull()) |
423 |
|
{ |
424 |
|
Trace("cegqi-arith-bound") << "( " << value[0] << " * INF ) + "; |
425 |
|
} |
426 |
|
else |
427 |
|
{ |
428 |
4646 |
value[0] = d_zero; |
429 |
|
} |
430 |
|
} |
431 |
8460 |
else if (t == 1) |
432 |
|
{ |
433 |
9292 |
Node t_value = ci->getModelValue(d_mbp_bounds[rr][j]); |
434 |
4646 |
t_values[rr][j] = t_value; |
435 |
4646 |
value[1] = t_value; |
436 |
4646 |
Trace("cegqi-arith-bound") << value[1]; |
437 |
|
} |
438 |
|
else |
439 |
|
{ |
440 |
3814 |
value[2] = d_mbp_vts_coeff[rr][1][j]; |
441 |
3814 |
if (!value[2].isNull()) |
442 |
|
{ |
443 |
198 |
Trace("cegqi-arith-bound") << " + ( " << value[2] << " * DELTA )"; |
444 |
|
} |
445 |
|
else |
446 |
|
{ |
447 |
3616 |
value[2] = d_zero; |
448 |
|
} |
449 |
|
} |
450 |
|
// multiply by coefficient |
451 |
13106 |
if (value[t] != d_zero && !d_mbp_coeff[rr][j].isNull()) |
452 |
|
{ |
453 |
112 |
Assert(d_mbp_coeff[rr][j].isConst()); |
454 |
448 |
value[t] = nm->mkNode( |
455 |
|
MULT, |
456 |
448 |
nm->mkConst(Rational(1) |
457 |
336 |
/ d_mbp_coeff[rr][j].getConst<Rational>()), |
458 |
112 |
value[t]); |
459 |
112 |
value[t] = Rewriter::rewrite(value[t]); |
460 |
|
} |
461 |
|
// check if new best, if we have not already set it. |
462 |
13106 |
if (best != -1 && !new_best_set) |
463 |
|
{ |
464 |
4704 |
Assert(!value[t].isNull() && !best_bound_value[t].isNull()); |
465 |
4704 |
if (value[t] != best_bound_value[t]) |
466 |
|
{ |
467 |
1226 |
Kind k = rr == 0 ? GEQ : LEQ; |
468 |
1617 |
Node cmp_bound = nm->mkNode(k, value[t], best_bound_value[t]); |
469 |
1226 |
cmp_bound = Rewriter::rewrite(cmp_bound); |
470 |
|
// Should be comparing two constant values which should rewrite |
471 |
|
// to a constant. If a step failed, we assume that this is not |
472 |
|
// the new best bound. We might not be comparing constant |
473 |
|
// values (for instance if transcendental functions are |
474 |
|
// involved), in which case we do update the best bound value. |
475 |
1226 |
if (!cmp_bound.isConst() || !cmp_bound.getConst<bool>()) |
476 |
|
{ |
477 |
835 |
new_best = false; |
478 |
835 |
break; |
479 |
|
} |
480 |
|
// indicate that the value of new_best is now established. |
481 |
391 |
new_best_set = true; |
482 |
|
} |
483 |
|
} |
484 |
|
} |
485 |
4646 |
Trace("cegqi-arith-bound") << std::endl; |
486 |
4646 |
if (new_best) |
487 |
|
{ |
488 |
15244 |
for (unsigned t = 0; t < 3; t++) |
489 |
|
{ |
490 |
11433 |
best_bound_value[t] = value[t]; |
491 |
|
} |
492 |
3811 |
best = j; |
493 |
|
} |
494 |
|
} |
495 |
2673 |
if (best != -1) |
496 |
|
{ |
497 |
2673 |
Trace("cegqi-arith-bound") << "...best bound is " << best << " : "; |
498 |
2673 |
if (best_bound_value[0] != d_zero) |
499 |
|
{ |
500 |
|
Trace("cegqi-arith-bound") |
501 |
|
<< "( " << best_bound_value[0] << " * INF ) + "; |
502 |
|
} |
503 |
2673 |
Trace("cegqi-arith-bound") << best_bound_value[1]; |
504 |
2673 |
if (best_bound_value[2] != d_zero) |
505 |
|
{ |
506 |
330 |
Trace("cegqi-arith-bound") |
507 |
165 |
<< " + ( " << best_bound_value[2] << " * DELTA )"; |
508 |
|
} |
509 |
2673 |
Trace("cegqi-arith-bound") << std::endl; |
510 |
2673 |
best_used[rr] = best; |
511 |
|
// if using cbqiMidpoint, only add the instance based on one bound if |
512 |
|
// the bound is non-strict |
513 |
5829 |
if (!options::cegqiMidpoint() || d_type.isInteger() |
514 |
2742 |
|| d_mbp_vts_coeff[rr][1][best].isNull()) |
515 |
|
{ |
516 |
2695 |
Node val = d_mbp_bounds[rr][best]; |
517 |
13075 |
val = getModelBasedProjectionValue(ci, |
518 |
|
pv, |
519 |
|
val, |
520 |
|
rr == 0, |
521 |
2615 |
d_mbp_coeff[rr][best], |
522 |
|
pv_value, |
523 |
2615 |
t_values[rr][best], |
524 |
5230 |
sf.getTheta(), |
525 |
2615 |
d_mbp_vts_coeff[rr][0][best], |
526 |
2615 |
d_mbp_vts_coeff[rr][1][best]); |
527 |
2615 |
if (!val.isNull()) |
528 |
|
{ |
529 |
2695 |
TermProperties pv_prop_bound; |
530 |
2615 |
pv_prop_bound.d_coeff = d_mbp_coeff[rr][best]; |
531 |
2615 |
pv_prop_bound.d_type = rr == 0 ? CEG_TT_UPPER : CEG_TT_LOWER; |
532 |
2615 |
if (ci->constructInstantiationInc(pv, val, pv_prop_bound, sf)) |
533 |
|
{ |
534 |
1764 |
return true; |
535 |
|
} |
536 |
851 |
else if (!options::cegqiMultiInst()) |
537 |
|
{ |
538 |
771 |
return false; |
539 |
|
} |
540 |
|
} |
541 |
|
} |
542 |
|
} |
543 |
|
} |
544 |
|
} |
545 |
|
// if not using infinity, use model value of zero |
546 |
3241 |
if (!use_inf && d_mbp_bounds[0].empty() && d_mbp_bounds[1].empty()) |
547 |
|
{ |
548 |
3146 |
Node val = d_zero; |
549 |
3146 |
TermProperties pv_prop_zero; |
550 |
3146 |
Node theta = sf.getTheta(); |
551 |
3146 |
val = getModelBasedProjectionValue(ci, |
552 |
|
pv, |
553 |
|
val, |
554 |
|
true, |
555 |
|
pv_prop_zero.d_coeff, |
556 |
|
pv_value, |
557 |
|
d_zero, |
558 |
6292 |
sf.getTheta(), |
559 |
6292 |
Node::null(), |
560 |
6292 |
Node::null()); |
561 |
3146 |
if (!val.isNull()) |
562 |
|
{ |
563 |
3146 |
if (ci->constructInstantiationInc(pv, val, pv_prop_zero, sf)) |
564 |
|
{ |
565 |
2969 |
return true; |
566 |
|
} |
567 |
177 |
else if (!options::cegqiMultiInst()) |
568 |
|
{ |
569 |
177 |
return false; |
570 |
|
} |
571 |
|
} |
572 |
|
} |
573 |
95 |
if (options::cegqiMidpoint() && !d_type.isInteger()) |
574 |
|
{ |
575 |
165 |
Node vals[2]; |
576 |
55 |
bool bothBounds = true; |
577 |
55 |
Trace("cegqi-arith-bound") << "Try midpoint of bounds..." << std::endl; |
578 |
165 |
for (unsigned rr = 0; rr < 2; rr++) |
579 |
|
{ |
580 |
110 |
int best = best_used[rr]; |
581 |
110 |
if (best == -1) |
582 |
|
{ |
583 |
52 |
bothBounds = false; |
584 |
|
} |
585 |
|
else |
586 |
|
{ |
587 |
58 |
vals[rr] = d_mbp_bounds[rr][best]; |
588 |
348 |
vals[rr] = getModelBasedProjectionValue(ci, |
589 |
|
pv, |
590 |
|
vals[rr], |
591 |
|
rr == 0, |
592 |
116 |
Node::null(), |
593 |
|
pv_value, |
594 |
58 |
t_values[rr][best], |
595 |
116 |
sf.getTheta(), |
596 |
58 |
d_mbp_vts_coeff[rr][0][best], |
597 |
174 |
Node::null()); |
598 |
|
} |
599 |
110 |
Trace("cegqi-arith-bound") << "Bound : " << vals[rr] << std::endl; |
600 |
|
} |
601 |
55 |
Node val; |
602 |
55 |
if (bothBounds) |
603 |
|
{ |
604 |
3 |
Assert(!vals[0].isNull() && !vals[1].isNull()); |
605 |
3 |
if (vals[0] == vals[1]) |
606 |
|
{ |
607 |
|
val = vals[0]; |
608 |
|
} |
609 |
|
else |
610 |
|
{ |
611 |
9 |
val = nm->mkNode(MULT, |
612 |
6 |
nm->mkNode(PLUS, vals[0], vals[1]), |
613 |
6 |
nm->mkConst(Rational(1) / Rational(2))); |
614 |
3 |
val = Rewriter::rewrite(val); |
615 |
|
} |
616 |
|
} |
617 |
|
else |
618 |
|
{ |
619 |
52 |
if (!vals[0].isNull()) |
620 |
|
{ |
621 |
22 |
val = nm->mkNode(PLUS, vals[0], d_one); |
622 |
22 |
val = Rewriter::rewrite(val); |
623 |
|
} |
624 |
30 |
else if (!vals[1].isNull()) |
625 |
|
{ |
626 |
30 |
val = nm->mkNode(MINUS, vals[1], d_one); |
627 |
30 |
val = Rewriter::rewrite(val); |
628 |
|
} |
629 |
|
} |
630 |
55 |
Trace("cegqi-arith-bound") << "Midpoint value : " << val << std::endl; |
631 |
55 |
if (!val.isNull()) |
632 |
|
{ |
633 |
55 |
TermProperties pv_prop_midpoint; |
634 |
55 |
if (ci->constructInstantiationInc(pv, val, pv_prop_midpoint, sf)) |
635 |
|
{ |
636 |
42 |
return true; |
637 |
|
} |
638 |
13 |
else if (!options::cegqiMultiInst()) |
639 |
|
{ |
640 |
13 |
return false; |
641 |
|
} |
642 |
|
} |
643 |
|
} |
644 |
|
// generally should not make it to this point, unless we are using a |
645 |
|
// non-monotonic selection function |
646 |
|
|
647 |
80 |
if (!options::cegqiNopt()) |
648 |
|
{ |
649 |
|
// if not trying non-optimal bounds, return |
650 |
|
return false; |
651 |
|
} |
652 |
|
// try non-optimal bounds (heuristic, may help when nested quantification) ? |
653 |
40 |
Trace("cegqi-arith-bound") << "Try non-optimal bounds..." << std::endl; |
654 |
120 |
for (unsigned r = 0; r < 2; r++) |
655 |
|
{ |
656 |
80 |
int rr = upper_first ? (1 - r) : r; |
657 |
200 |
for (unsigned j = 0, nbounds = d_mbp_bounds[rr].size(); j < nbounds; j++) |
658 |
|
{ |
659 |
240 |
if ((int)j != best_used[rr] |
660 |
120 |
&& (!options::cegqiMidpoint() || d_mbp_vts_coeff[rr][1][j].isNull())) |
661 |
|
{ |
662 |
|
Node val = getModelBasedProjectionValue(ci, |
663 |
|
pv, |
664 |
40 |
d_mbp_bounds[rr][j], |
665 |
|
rr == 0, |
666 |
40 |
d_mbp_coeff[rr][j], |
667 |
|
pv_value, |
668 |
40 |
t_values[rr][j], |
669 |
80 |
sf.getTheta(), |
670 |
40 |
d_mbp_vts_coeff[rr][0][j], |
671 |
280 |
d_mbp_vts_coeff[rr][1][j]); |
672 |
40 |
if (!val.isNull()) |
673 |
|
{ |
674 |
80 |
TermProperties pv_prop_nopt_bound; |
675 |
40 |
pv_prop_nopt_bound.d_coeff = d_mbp_coeff[rr][j]; |
676 |
40 |
pv_prop_nopt_bound.d_type = rr == 0 ? CEG_TT_UPPER : CEG_TT_LOWER; |
677 |
40 |
if (ci->constructInstantiationInc(pv, val, pv_prop_nopt_bound, sf)) |
678 |
|
{ |
679 |
|
return true; |
680 |
|
} |
681 |
40 |
else if (!options::cegqiMultiInst()) |
682 |
|
{ |
683 |
|
return false; |
684 |
|
} |
685 |
|
} |
686 |
|
} |
687 |
|
} |
688 |
|
} |
689 |
40 |
return false; |
690 |
|
} |
691 |
|
|
692 |
11984 |
bool ArithInstantiator::needsPostProcessInstantiationForVariable( |
693 |
|
CegInstantiator* ci, SolvedForm& sf, Node pv, CegInstEffort effort) |
694 |
|
{ |
695 |
23968 |
return std::find(sf.d_non_basic.begin(), sf.d_non_basic.end(), pv) |
696 |
35952 |
!= sf.d_non_basic.end(); |
697 |
|
} |
698 |
|
|
699 |
201 |
bool ArithInstantiator::postProcessInstantiationForVariable( |
700 |
|
CegInstantiator* ci, SolvedForm& sf, Node pv, CegInstEffort effort) |
701 |
|
{ |
702 |
201 |
Assert(std::find(sf.d_non_basic.begin(), sf.d_non_basic.end(), pv) |
703 |
|
!= sf.d_non_basic.end()); |
704 |
201 |
Assert(std::find(sf.d_vars.begin(), sf.d_vars.end(), pv) != sf.d_vars.end()); |
705 |
|
unsigned index = |
706 |
201 |
std::find(sf.d_vars.begin(), sf.d_vars.end(), pv) - sf.d_vars.begin(); |
707 |
201 |
Assert(!sf.d_props[index].isBasic()); |
708 |
402 |
Node eq_lhs = sf.d_props[index].getModifiedTerm(sf.d_vars[index]); |
709 |
201 |
if (Trace.isOn("cegqi-arith-debug")) |
710 |
|
{ |
711 |
|
Trace("cegqi-arith-debug") << "Normalize substitution for "; |
712 |
|
Trace("cegqi-arith-debug") |
713 |
|
<< eq_lhs << " = " << sf.d_subs[index] << std::endl; |
714 |
|
} |
715 |
201 |
Assert(sf.d_vars[index].getType().isInteger()); |
716 |
|
// must ensure that divisibility constraints are met |
717 |
|
// solve updated rewritten equality for vars[index], if coefficient is one, |
718 |
|
// then we are successful |
719 |
402 |
Node eq_rhs = sf.d_subs[index]; |
720 |
402 |
Node eq = eq_lhs.eqNode(eq_rhs); |
721 |
201 |
eq = Rewriter::rewrite(eq); |
722 |
201 |
Trace("cegqi-arith-debug") << "...equality is " << eq << std::endl; |
723 |
402 |
std::map<Node, Node> msum; |
724 |
201 |
if (!ArithMSum::getMonomialSumLit(eq, msum)) |
725 |
|
{ |
726 |
36 |
Trace("cegqi-arith-debug") << "...failed to get monomial sum." << std::endl; |
727 |
36 |
return false; |
728 |
|
} |
729 |
330 |
Node veq; |
730 |
165 |
if (ArithMSum::isolate(sf.d_vars[index], msum, veq, EQUAL, true) == 0) |
731 |
|
{ |
732 |
|
Trace("cegqi-arith-debug") << "...failed to isolate." << std::endl; |
733 |
|
return false; |
734 |
|
} |
735 |
330 |
Node veq_c; |
736 |
165 |
if (veq[0] != sf.d_vars[index]) |
737 |
|
{ |
738 |
102 |
Node veq_v; |
739 |
51 |
if (ArithMSum::getMonomial(veq[0], veq_c, veq_v)) |
740 |
|
{ |
741 |
51 |
Assert(veq_v == sf.d_vars[index]); |
742 |
|
} |
743 |
|
} |
744 |
165 |
sf.d_subs[index] = veq[1]; |
745 |
165 |
if (!veq_c.isNull()) |
746 |
|
{ |
747 |
51 |
NodeManager* nm = NodeManager::currentNM(); |
748 |
51 |
sf.d_subs[index] = nm->mkNode(INTS_DIVISION_TOTAL, veq[1], veq_c); |
749 |
102 |
Trace("cegqi-arith-debug") |
750 |
51 |
<< "...bound type is : " << sf.d_props[index].d_type << std::endl; |
751 |
|
// intger division rounding up if from a lower bound |
752 |
102 |
if (sf.d_props[index].d_type == CEG_TT_UPPER |
753 |
60 |
&& options::cegqiRoundUpLowerLia()) |
754 |
|
{ |
755 |
|
sf.d_subs[index] = nm->mkNode( |
756 |
|
PLUS, |
757 |
|
sf.d_subs[index], |
758 |
|
nm->mkNode( |
759 |
|
ITE, |
760 |
|
nm->mkNode( |
761 |
|
EQUAL, nm->mkNode(INTS_MODULUS_TOTAL, veq[1], veq_c), d_zero), |
762 |
|
d_zero, |
763 |
|
d_one)); |
764 |
|
} |
765 |
|
} |
766 |
330 |
Trace("cegqi-arith-debug") << "...normalize integers : " << sf.d_vars[index] |
767 |
165 |
<< " -> " << sf.d_subs[index] << std::endl; |
768 |
165 |
return true; |
769 |
|
} |
770 |
|
|
771 |
22474 |
CegTermType ArithInstantiator::solve_arith(CegInstantiator* ci, |
772 |
|
Node pv, |
773 |
|
Node atom, |
774 |
|
Node& veq_c, |
775 |
|
Node& val, |
776 |
|
Node& vts_coeff_inf, |
777 |
|
Node& vts_coeff_delta) |
778 |
|
{ |
779 |
22474 |
NodeManager* nm = NodeManager::currentNM(); |
780 |
44948 |
Trace("cegqi-arith-debug") |
781 |
22474 |
<< "isolate for " << pv << " in " << atom << std::endl; |
782 |
44948 |
std::map<Node, Node> msum; |
783 |
22474 |
if (!ArithMSum::getMonomialSumLit(atom, msum)) |
784 |
|
{ |
785 |
18594 |
Trace("cegqi-arith-debug") |
786 |
9297 |
<< "fail : could not get monomial sum" << std::endl; |
787 |
9297 |
return CEG_TT_INVALID; |
788 |
|
} |
789 |
13177 |
Trace("cegqi-arith-debug") << "got monomial sum: " << std::endl; |
790 |
13177 |
if (Trace.isOn("cegqi-arith-debug")) |
791 |
|
{ |
792 |
|
ArithMSum::debugPrintMonomialSum(msum, "cegqi-arith-debug"); |
793 |
|
} |
794 |
26354 |
TypeNode pvtn = pv.getType(); |
795 |
|
// remove vts symbols from polynomial |
796 |
26354 |
Node vts_coeff[2]; |
797 |
39531 |
for (unsigned t = 0; t < 2; t++) |
798 |
|
{ |
799 |
26354 |
if (!d_vts_sym[t].isNull()) |
800 |
|
{ |
801 |
686 |
std::map<Node, Node>::iterator itminf = msum.find(d_vts_sym[t]); |
802 |
686 |
if (itminf != msum.end()) |
803 |
|
{ |
804 |
32 |
vts_coeff[t] = itminf->second; |
805 |
32 |
if (vts_coeff[t].isNull()) |
806 |
|
{ |
807 |
|
vts_coeff[t] = nm->mkConst(Rational(1)); |
808 |
|
} |
809 |
|
// negate if coefficient on variable is positive |
810 |
32 |
std::map<Node, Node>::iterator itv = msum.find(pv); |
811 |
32 |
if (itv != msum.end()) |
812 |
|
{ |
813 |
|
// multiply by the coefficient we will isolate for |
814 |
32 |
if (itv->second.isNull()) |
815 |
|
{ |
816 |
8 |
vts_coeff[t] = ArithMSum::negate(vts_coeff[t]); |
817 |
|
} |
818 |
|
else |
819 |
|
{ |
820 |
24 |
if (!pvtn.isInteger()) |
821 |
|
{ |
822 |
|
vts_coeff[t] = nm->mkNode( |
823 |
|
MULT, |
824 |
|
nm->mkConst(Rational(-1) / itv->second.getConst<Rational>()), |
825 |
|
vts_coeff[t]); |
826 |
|
vts_coeff[t] = Rewriter::rewrite(vts_coeff[t]); |
827 |
|
} |
828 |
24 |
else if (itv->second.getConst<Rational>().sgn() == 1) |
829 |
|
{ |
830 |
|
vts_coeff[t] = ArithMSum::negate(vts_coeff[t]); |
831 |
|
} |
832 |
|
} |
833 |
|
} |
834 |
64 |
Trace("cegqi-arith-debug") |
835 |
32 |
<< "vts[" << t << "] coefficient is " << vts_coeff[t] << std::endl; |
836 |
32 |
msum.erase(d_vts_sym[t]); |
837 |
|
} |
838 |
|
} |
839 |
|
} |
840 |
|
|
841 |
13177 |
int ires = ArithMSum::isolate(pv, msum, veq_c, val, atom.getKind()); |
842 |
13177 |
if (ires == 0) |
843 |
|
{ |
844 |
1288 |
Trace("cegqi-arith-debug") << "fail : isolate" << std::endl; |
845 |
1288 |
return CEG_TT_INVALID; |
846 |
|
} |
847 |
11889 |
if (Trace.isOn("cegqi-arith-debug")) |
848 |
|
{ |
849 |
|
Trace("cegqi-arith-debug") << "Isolate : "; |
850 |
|
if (!veq_c.isNull()) |
851 |
|
{ |
852 |
|
Trace("cegqi-arith-debug") << veq_c << " * "; |
853 |
|
} |
854 |
|
Trace("cegqi-arith-debug") |
855 |
|
<< pv << " " << atom.getKind() << " " << val << std::endl; |
856 |
|
} |
857 |
|
// when not pure LIA/LRA, we must check whether the lhs contains pv |
858 |
11889 |
if (expr::hasSubterm(val, pv)) |
859 |
|
{ |
860 |
448 |
Trace("cegqi-arith-debug") << "fail : contains bad term" << std::endl; |
861 |
448 |
return CEG_TT_INVALID; |
862 |
|
} |
863 |
|
// if its type is integer but the substitution is not integer |
864 |
22882 |
if (pvtn.isInteger() |
865 |
34349 |
&& ((!veq_c.isNull() && !veq_c.getType().isInteger()) |
866 |
21837 |
|| !val.getType().isInteger())) |
867 |
|
{ |
868 |
|
// redo, split integer/non-integer parts |
869 |
26 |
bool useCoeff = false; |
870 |
52 |
Integer coeff(1); |
871 |
88 |
for (std::map<Node, Node>::iterator it = msum.begin(); it != msum.end(); |
872 |
|
++it) |
873 |
|
{ |
874 |
62 |
if (it->first.isNull() || it->first.getType().isInteger()) |
875 |
|
{ |
876 |
44 |
if (!it->second.isNull()) |
877 |
|
{ |
878 |
31 |
coeff = coeff.lcm(it->second.getConst<Rational>().getDenominator()); |
879 |
31 |
useCoeff = true; |
880 |
|
} |
881 |
|
} |
882 |
|
} |
883 |
|
// multiply everything by this coefficient |
884 |
52 |
Node rcoeff = nm->mkConst(Rational(coeff)); |
885 |
52 |
std::vector<Node> real_part; |
886 |
88 |
for (std::map<Node, Node>::iterator it = msum.begin(); it != msum.end(); |
887 |
|
++it) |
888 |
|
{ |
889 |
62 |
if (useCoeff) |
890 |
|
{ |
891 |
56 |
if (it->second.isNull()) |
892 |
|
{ |
893 |
23 |
msum[it->first] = rcoeff; |
894 |
|
} |
895 |
|
else |
896 |
|
{ |
897 |
33 |
msum[it->first] = |
898 |
66 |
Rewriter::rewrite(nm->mkNode(MULT, it->second, rcoeff)); |
899 |
|
} |
900 |
|
} |
901 |
62 |
if (!it->first.isNull() && !it->first.getType().isInteger()) |
902 |
|
{ |
903 |
36 |
real_part.push_back(msum[it->first].isNull() |
904 |
72 |
? it->first |
905 |
36 |
: nm->mkNode(MULT, msum[it->first], it->first)); |
906 |
|
} |
907 |
|
} |
908 |
|
// remove delta |
909 |
26 |
vts_coeff[1] = Node::null(); |
910 |
|
// multiply inf |
911 |
26 |
if (!vts_coeff[0].isNull()) |
912 |
|
{ |
913 |
|
vts_coeff[0] = Rewriter::rewrite(nm->mkNode(MULT, rcoeff, vts_coeff[0])); |
914 |
|
} |
915 |
26 |
Node realPart = real_part.empty() |
916 |
|
? d_zero |
917 |
36 |
: (real_part.size() == 1 ? real_part[0] |
918 |
88 |
: nm->mkNode(PLUS, real_part)); |
919 |
26 |
Assert(ci->isEligibleForInstantiation(realPart)); |
920 |
|
// re-isolate |
921 |
26 |
Trace("cegqi-arith-debug") << "Re-isolate..." << std::endl; |
922 |
26 |
veq_c = Node::null(); |
923 |
26 |
ires = ArithMSum::isolate(pv, msum, veq_c, val, atom.getKind()); |
924 |
52 |
Trace("cegqi-arith-debug") |
925 |
26 |
<< "Isolate for mixed Int/Real : " << veq_c << " * " << pv << " " |
926 |
26 |
<< atom.getKind() << " " << val << std::endl; |
927 |
52 |
Trace("cegqi-arith-debug") |
928 |
26 |
<< " real part : " << realPart << std::endl; |
929 |
26 |
if (ires != 0) |
930 |
|
{ |
931 |
|
int ires_use = |
932 |
26 |
(msum[pv].isNull() || msum[pv].getConst<Rational>().sgn() == 1) ? 1 |
933 |
26 |
: -1; |
934 |
26 |
val = Rewriter::rewrite( |
935 |
104 |
nm->mkNode(ires_use == -1 ? PLUS : MINUS, |
936 |
52 |
nm->mkNode(ires_use == -1 ? MINUS : PLUS, val, realPart), |
937 |
52 |
nm->mkNode(TO_INTEGER, realPart))); |
938 |
|
// could round up for upper bounds here |
939 |
26 |
Trace("cegqi-arith-debug") << "result : " << val << std::endl; |
940 |
26 |
Assert(val.getType().isInteger()); |
941 |
|
} |
942 |
|
else |
943 |
|
{ |
944 |
|
return CEG_TT_INVALID; |
945 |
|
} |
946 |
|
} |
947 |
11441 |
vts_coeff_inf = vts_coeff[0]; |
948 |
11441 |
vts_coeff_delta = vts_coeff[1]; |
949 |
22882 |
Trace("cegqi-arith-debug") |
950 |
22882 |
<< "Return " << veq_c << " * " << pv << " " << atom.getKind() << " " |
951 |
11441 |
<< val << ", vts = (" << vts_coeff_inf << ", " << vts_coeff_delta << ")" |
952 |
11441 |
<< std::endl; |
953 |
11441 |
Assert(ires != 0); |
954 |
11441 |
if (atom.getKind() == EQUAL) |
955 |
|
{ |
956 |
6603 |
return CEG_TT_EQUAL; |
957 |
|
} |
958 |
4838 |
return ires == 1 ? CEG_TT_UPPER : CEG_TT_LOWER; |
959 |
|
} |
960 |
|
|
961 |
5859 |
Node ArithInstantiator::getModelBasedProjectionValue(CegInstantiator* ci, |
962 |
|
Node e, |
963 |
|
Node t, |
964 |
|
bool isLower, |
965 |
|
Node c, |
966 |
|
Node me, |
967 |
|
Node mt, |
968 |
|
Node theta, |
969 |
|
Node inf_coeff, |
970 |
|
Node delta_coeff) |
971 |
|
{ |
972 |
5859 |
NodeManager* nm = NodeManager::currentNM(); |
973 |
5859 |
Node val = t; |
974 |
5859 |
Trace("cegqi-arith-bound2") << "Value : " << val << std::endl; |
975 |
5859 |
Assert(!e.getType().isInteger() || t.getType().isInteger()); |
976 |
5859 |
Assert(!e.getType().isInteger() || mt.getType().isInteger()); |
977 |
|
// add rho value |
978 |
|
// get the value of c*e |
979 |
11718 |
Node ceValue = me; |
980 |
11718 |
Node new_theta = theta; |
981 |
5859 |
if (!c.isNull()) |
982 |
|
{ |
983 |
106 |
Assert(c.getType().isInteger()); |
984 |
106 |
ceValue = nm->mkNode(MULT, ceValue, c); |
985 |
106 |
ceValue = Rewriter::rewrite(ceValue); |
986 |
106 |
if (new_theta.isNull()) |
987 |
|
{ |
988 |
68 |
new_theta = c; |
989 |
|
} |
990 |
|
else |
991 |
|
{ |
992 |
38 |
new_theta = nm->mkNode(MULT, new_theta, c); |
993 |
38 |
new_theta = Rewriter::rewrite(new_theta); |
994 |
|
} |
995 |
106 |
Trace("cegqi-arith-bound2") << "...c*e = " << ceValue << std::endl; |
996 |
106 |
Trace("cegqi-arith-bound2") << "...theta = " << new_theta << std::endl; |
997 |
|
} |
998 |
5859 |
if (!new_theta.isNull() && e.getType().isInteger()) |
999 |
|
{ |
1000 |
458 |
Node rho; |
1001 |
229 |
if (isLower) |
1002 |
|
{ |
1003 |
128 |
rho = nm->mkNode(MINUS, ceValue, mt); |
1004 |
|
} |
1005 |
|
else |
1006 |
|
{ |
1007 |
101 |
rho = nm->mkNode(MINUS, mt, ceValue); |
1008 |
|
} |
1009 |
229 |
rho = Rewriter::rewrite(rho); |
1010 |
458 |
Trace("cegqi-arith-bound2") |
1011 |
229 |
<< "...rho = " << me << " - " << mt << " = " << rho << std::endl; |
1012 |
458 |
Trace("cegqi-arith-bound2") |
1013 |
229 |
<< "..." << rho << " mod " << new_theta << " = "; |
1014 |
229 |
rho = nm->mkNode(INTS_MODULUS_TOTAL, rho, new_theta); |
1015 |
229 |
rho = Rewriter::rewrite(rho); |
1016 |
229 |
Trace("cegqi-arith-bound2") << rho << std::endl; |
1017 |
229 |
Kind rk = isLower ? PLUS : MINUS; |
1018 |
229 |
val = nm->mkNode(rk, val, rho); |
1019 |
229 |
val = Rewriter::rewrite(val); |
1020 |
229 |
Trace("cegqi-arith-bound2") << "(after rho) : " << val << std::endl; |
1021 |
|
} |
1022 |
5859 |
if (!inf_coeff.isNull()) |
1023 |
|
{ |
1024 |
|
Assert(!d_vts_sym[0].isNull()); |
1025 |
|
val = nm->mkNode(PLUS, val, nm->mkNode(MULT, inf_coeff, d_vts_sym[0])); |
1026 |
|
val = Rewriter::rewrite(val); |
1027 |
|
} |
1028 |
5859 |
if (!delta_coeff.isNull()) |
1029 |
|
{ |
1030 |
|
// create delta here if necessary |
1031 |
107 |
val = nm->mkNode( |
1032 |
214 |
PLUS, val, nm->mkNode(MULT, delta_coeff, d_vtc->getVtsDelta())); |
1033 |
107 |
val = Rewriter::rewrite(val); |
1034 |
|
} |
1035 |
11718 |
return val; |
1036 |
|
} |
1037 |
|
|
1038 |
|
} // namespace quantifiers |
1039 |
|
} // namespace theory |
1040 |
73187 |
} // namespace cvc5 |