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