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