1 |
|
/****************************************************************************** |
2 |
|
* Top contributors (to current version): |
3 |
|
* Gereon Kremer, Andrew Reynolds, 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 |
|
* Implementation of new non-linear solver. |
14 |
|
*/ |
15 |
|
|
16 |
|
#include "theory/arith/nl/cad_solver.h" |
17 |
|
|
18 |
|
#include "expr/skolem_manager.h" |
19 |
|
#include "smt/env.h" |
20 |
|
#include "theory/arith/inference_manager.h" |
21 |
|
#include "theory/arith/nl/cad/cdcac.h" |
22 |
|
#include "theory/arith/nl/nl_model.h" |
23 |
|
#include "theory/arith/nl/poly_conversion.h" |
24 |
|
#include "theory/inference_id.h" |
25 |
|
|
26 |
|
namespace cvc5 { |
27 |
|
namespace theory { |
28 |
|
namespace arith { |
29 |
|
namespace nl { |
30 |
|
|
31 |
9696 |
CadSolver::CadSolver(Env& env, InferenceManager& im, NlModel& model) |
32 |
|
: |
33 |
|
EnvObj(env), |
34 |
|
#ifdef CVC5_POLY_IMP |
35 |
|
d_CAC(env), |
36 |
|
#endif |
37 |
|
d_foundSatisfiability(false), |
38 |
|
d_im(im), |
39 |
9696 |
d_model(model) |
40 |
|
{ |
41 |
9696 |
NodeManager* nm = NodeManager::currentNM(); |
42 |
9696 |
SkolemManager* sm = nm->getSkolemManager(); |
43 |
9696 |
d_ranVariable = sm->mkDummySkolem("__z", nm->realType(), ""); |
44 |
|
#ifdef CVC5_POLY_IMP |
45 |
9696 |
if (env.isTheoryProofProducing()) |
46 |
|
{ |
47 |
4681 |
ProofChecker* pc = env.getProofNodeManager()->getChecker(); |
48 |
|
// add checkers |
49 |
4681 |
d_proofChecker.registerTo(pc); |
50 |
|
} |
51 |
|
#endif |
52 |
9696 |
} |
53 |
|
|
54 |
9693 |
CadSolver::~CadSolver() {} |
55 |
|
|
56 |
102 |
void CadSolver::initLastCall(const std::vector<Node>& assertions) |
57 |
|
{ |
58 |
|
#ifdef CVC5_POLY_IMP |
59 |
102 |
if (Trace.isOn("nl-cad")) |
60 |
|
{ |
61 |
|
Trace("nl-cad") << "CadSolver::initLastCall" << std::endl; |
62 |
|
Trace("nl-cad") << "* Assertions: " << std::endl; |
63 |
|
for (const Node& a : assertions) |
64 |
|
{ |
65 |
|
Trace("nl-cad") << " " << a << std::endl; |
66 |
|
} |
67 |
|
} |
68 |
|
// store or process assertions |
69 |
102 |
d_CAC.reset(); |
70 |
2673 |
for (const Node& a : assertions) |
71 |
|
{ |
72 |
2571 |
d_CAC.getConstraints().addConstraint(a); |
73 |
|
} |
74 |
102 |
d_CAC.computeVariableOrdering(); |
75 |
102 |
d_CAC.retrieveInitialAssignment(d_model, d_ranVariable); |
76 |
|
#else |
77 |
|
warning() << "Tried to use CadSolver but libpoly is not available. Compile " |
78 |
|
"with --poly." |
79 |
|
<< std::endl; |
80 |
|
#endif |
81 |
102 |
} |
82 |
|
|
83 |
102 |
void CadSolver::checkFull() |
84 |
|
{ |
85 |
|
#ifdef CVC5_POLY_IMP |
86 |
102 |
if (d_CAC.getConstraints().getConstraints().empty()) { |
87 |
|
Trace("nl-cad") << "No constraints. Return." << std::endl; |
88 |
|
return; |
89 |
|
} |
90 |
102 |
d_CAC.startNewProof(); |
91 |
204 |
auto covering = d_CAC.getUnsatCover(); |
92 |
102 |
if (covering.empty()) |
93 |
|
{ |
94 |
43 |
d_foundSatisfiability = true; |
95 |
43 |
Trace("nl-cad") << "SAT: " << d_CAC.getModel() << std::endl; |
96 |
|
} |
97 |
|
else |
98 |
|
{ |
99 |
59 |
d_foundSatisfiability = false; |
100 |
118 |
auto mis = collectConstraints(covering); |
101 |
59 |
Trace("nl-cad") << "Collected MIS: " << mis << std::endl; |
102 |
59 |
Assert(!mis.empty()) << "Infeasible subset can not be empty"; |
103 |
59 |
Trace("nl-cad") << "UNSAT with MIS: " << mis << std::endl; |
104 |
118 |
Node lem = NodeManager::currentNM()->mkAnd(mis).negate(); |
105 |
59 |
ProofGenerator* proof = d_CAC.closeProof(mis); |
106 |
59 |
d_im.addPendingLemma(lem, InferenceId::ARITH_NL_CAD_CONFLICT, proof); |
107 |
|
} |
108 |
|
#else |
109 |
|
warning() << "Tried to use CadSolver but libpoly is not available. Compile " |
110 |
|
"with --poly." |
111 |
|
<< std::endl; |
112 |
|
#endif |
113 |
|
} |
114 |
|
|
115 |
|
void CadSolver::checkPartial() |
116 |
|
{ |
117 |
|
#ifdef CVC5_POLY_IMP |
118 |
|
if (d_CAC.getConstraints().getConstraints().empty()) { |
119 |
|
Trace("nl-cad") << "No constraints. Return." << std::endl; |
120 |
|
return; |
121 |
|
} |
122 |
|
auto covering = d_CAC.getUnsatCover(true); |
123 |
|
if (covering.empty()) |
124 |
|
{ |
125 |
|
d_foundSatisfiability = true; |
126 |
|
Trace("nl-cad") << "SAT: " << d_CAC.getModel() << std::endl; |
127 |
|
} |
128 |
|
else |
129 |
|
{ |
130 |
|
auto* nm = NodeManager::currentNM(); |
131 |
|
Node first_var = |
132 |
|
d_CAC.getConstraints().varMapper()(d_CAC.getVariableOrdering()[0]); |
133 |
|
for (const auto& interval : covering) |
134 |
|
{ |
135 |
|
Node premise; |
136 |
|
Assert(!interval.d_origins.empty()); |
137 |
|
if (interval.d_origins.size() == 1) |
138 |
|
{ |
139 |
|
premise = interval.d_origins[0]; |
140 |
|
} |
141 |
|
else |
142 |
|
{ |
143 |
|
premise = nm->mkNode(Kind::AND, interval.d_origins); |
144 |
|
} |
145 |
|
Node conclusion = |
146 |
|
excluding_interval_to_lemma(first_var, interval.d_interval, false); |
147 |
|
if (!conclusion.isNull()) |
148 |
|
{ |
149 |
|
Node lemma = nm->mkNode(Kind::IMPLIES, premise, conclusion); |
150 |
|
Trace("nl-cad") << "Excluding " << first_var << " -> " |
151 |
|
<< interval.d_interval << " using " << lemma |
152 |
|
<< std::endl; |
153 |
|
d_im.addPendingLemma(lemma, |
154 |
|
InferenceId::ARITH_NL_CAD_EXCLUDED_INTERVAL); |
155 |
|
} |
156 |
|
} |
157 |
|
} |
158 |
|
#else |
159 |
|
warning() << "Tried to use CadSolver but libpoly is not available. Compile " |
160 |
|
"with --poly." |
161 |
|
<< std::endl; |
162 |
|
#endif |
163 |
|
} |
164 |
|
|
165 |
25 |
bool CadSolver::constructModelIfAvailable(std::vector<Node>& assertions) |
166 |
|
{ |
167 |
|
#ifdef CVC5_POLY_IMP |
168 |
25 |
if (!d_foundSatisfiability) |
169 |
|
{ |
170 |
|
return false; |
171 |
|
} |
172 |
25 |
bool foundNonVariable = false; |
173 |
83 |
for (const auto& v : d_CAC.getVariableOrdering()) |
174 |
|
{ |
175 |
116 |
Node variable = d_CAC.getConstraints().varMapper()(v); |
176 |
58 |
if (!variable.isVar()) |
177 |
|
{ |
178 |
|
Trace("nl-cad") << "Not a variable: " << variable << std::endl; |
179 |
|
foundNonVariable = true; |
180 |
|
} |
181 |
116 |
Node value = value_to_node(d_CAC.getModel().get(v), d_ranVariable); |
182 |
58 |
if (value.isConst()) |
183 |
|
{ |
184 |
49 |
d_model.addSubstitution(variable, value); |
185 |
|
} |
186 |
|
else |
187 |
|
{ |
188 |
9 |
d_model.addWitness(variable, value); |
189 |
|
} |
190 |
58 |
Trace("nl-cad") << "-> " << v << " = " << value << std::endl; |
191 |
|
} |
192 |
25 |
if (foundNonVariable) |
193 |
|
{ |
194 |
|
Trace("nl-cad") |
195 |
|
<< "Some variable was an extended term, don't clear list of assertions." |
196 |
|
<< std::endl; |
197 |
|
return false; |
198 |
|
} |
199 |
50 |
Trace("nl-cad") << "Constructed a full assignment, clear list of assertions." |
200 |
25 |
<< std::endl; |
201 |
25 |
assertions.clear(); |
202 |
25 |
return true; |
203 |
|
#else |
204 |
|
warning() << "Tried to use CadSolver but libpoly is not available. Compile " |
205 |
|
"with --poly." |
206 |
|
<< std::endl; |
207 |
|
return false; |
208 |
|
#endif |
209 |
|
} |
210 |
|
|
211 |
|
} // namespace nl |
212 |
|
} // namespace arith |
213 |
|
} // namespace theory |
214 |
31137 |
} // namespace cvc5 |