diff options
author | Tim King <taking@cs.nyu.edu> | 2013-01-31 16:34:12 -0500 |
---|---|---|
committer | Tim King <taking@cs.nyu.edu> | 2013-01-31 16:34:25 -0500 |
commit | 9d7f0244034f1807e28b8ded23f4d6104ecf5263 (patch) | |
tree | 9a0eedb4e08c0dad66a052a6c6b6b8879e896c55 /src/theory/arith/theory_arith.cpp | |
parent | 82058d4af2f41f9236433294cd092dd5e2a2c1b9 (diff) |
Adding a heuristic to more eagerly split bounded integer variables.
Diffstat (limited to 'src/theory/arith/theory_arith.cpp')
-rw-r--r-- | src/theory/arith/theory_arith.cpp | 128 |
1 files changed, 98 insertions, 30 deletions
diff --git a/src/theory/arith/theory_arith.cpp b/src/theory/arith/theory_arith.cpp index 39ded7991..52f234129 100644 --- a/src/theory/arith/theory_arith.cpp +++ b/src/theory/arith/theory_arith.cpp @@ -88,6 +88,7 @@ TheoryArith::TheoryArith(context::Context* c, context::UserContext* u, OutputCha d_deltaComputeCallback(this), d_basicVarModelUpdateCallBack(d_simplex), d_DELTA_ZERO(0), + d_fullCheckCounter(0), d_statistics() { } @@ -1730,6 +1731,20 @@ void TheoryArith::check(Effort effortLevel){ } Assert( d_currentPropagationList.empty()); + if(!emmittedConflictOrSplit && fullEffort(effortLevel)){ + ++d_fullCheckCounter; + } + static const int CUT_ALL_BOUNDED_PERIOD = 10; + if(!emmittedConflictOrSplit && fullEffort(effortLevel) && + d_fullCheckCounter % CUT_ALL_BOUNDED_PERIOD == 1){ + vector<Node> lemmas = cutAllBounded(); + //output the lemmas + for(vector<Node>::const_iterator i = lemmas.begin(); i != lemmas.end(); ++i){ + d_out->lemma(*i); + ++(d_statistics.d_externalBranchAndBounds); + } + emmittedConflictOrSplit = lemmas.size() > 0; + } if(!emmittedConflictOrSplit && fullEffort(effortLevel)){ emmittedConflictOrSplit = splitDisequalities(); @@ -1776,6 +1791,55 @@ void TheoryArith::check(Effort effortLevel){ Debug("arith") << "TheoryArith::check end" << std::endl; } +Node TheoryArith::branchIntegerVariable(ArithVar x) const { + const DeltaRational& d = d_partialModel.getAssignment(x); + Assert(!d.isIntegral()); + const Rational& r = d.getNoninfinitesimalPart(); + const Rational& i = d.getInfinitesimalPart(); + Trace("integers") << "integers: assignment to [[" << d_arithvarNodeMap.asNode(x) << "]] is " << r << "[" << i << "]" << endl; + + Assert(! (r.getDenominator() == 1 && i.getNumerator() == 0)); + Assert(!d.isIntegral()); + TNode var = d_arithvarNodeMap.asNode(x); + Integer floor_d = d.floor(); + + Node ub = Rewriter::rewrite(NodeManager::currentNM()->mkNode(kind::LEQ, var, mkRationalNode(floor_d))); + Node lb = ub.notNode(); + + + Node lem = NodeManager::currentNM()->mkNode(kind::OR, ub, lb); + Trace("integers") << "integers: branch & bound: " << lem << endl; + if(d_valuation.isSatLiteral(lem[0])) { + Debug("integers") << " " << lem[0] << " == " << d_valuation.getSatValue(lem[0]) << endl; + } else { + Debug("integers") << " " << lem[0] << " is not assigned a SAT literal" << endl; + } + if(d_valuation.isSatLiteral(lem[1])) { + Debug("integers") << " " << lem[1] << " == " << d_valuation.getSatValue(lem[1]) << endl; + } else { + Debug("integers") << " " << lem[1] << " is not assigned a SAT literal" << endl; + } + return lem; +} + +std::vector<Node> TheoryArith::cutAllBounded() const{ + vector<Node> lemmas; + if(options::doCutAllBounded() && getNumberOfVariables() > 0){ + for(ArithVar iter = 0; iter != getNumberOfVariables(); ++iter){ + //Do not include slack variables + const DeltaRational& d = d_partialModel.getAssignment(iter); + if(isInteger(iter) && !isSlackVariable(iter) && + d_partialModel.hasUpperBound(iter) && + d_partialModel.hasLowerBound(iter) && + !d.isIntegral()){ + Node lem = branchIntegerVariable(iter); + lemmas.push_back(lem); + } + } + } + return lemmas; +} + /** Returns true if the roundRobinBranching() issues a lemma. */ Node TheoryArith::roundRobinBranch(){ if(hasIntegerModel()){ @@ -1785,36 +1849,40 @@ Node TheoryArith::roundRobinBranch(){ Assert(isInteger(v)); Assert(!isSlackVariable(v)); - - const DeltaRational& d = d_partialModel.getAssignment(v); - const Rational& r = d.getNoninfinitesimalPart(); - const Rational& i = d.getInfinitesimalPart(); - Trace("integers") << "integers: assignment to [[" << d_arithvarNodeMap.asNode(v) << "]] is " << r << "[" << i << "]" << endl; - - Assert(! (r.getDenominator() == 1 && i.getNumerator() == 0)); - Assert(!d.isIntegral()); - - TNode var = d_arithvarNodeMap.asNode(v); - Integer floor_d = d.floor(); - Integer ceil_d = d.ceiling(); - - Node leq = Rewriter::rewrite(NodeManager::currentNM()->mkNode(kind::LEQ, var, mkRationalNode(floor_d))); - Node geq = Rewriter::rewrite(NodeManager::currentNM()->mkNode(kind::GEQ, var, mkRationalNode(ceil_d))); - - - Node lem = NodeManager::currentNM()->mkNode(kind::OR, leq, geq); - Trace("integers") << "integers: branch & bound: " << lem << endl; - if(d_valuation.isSatLiteral(lem[0])) { - Debug("integers") << " " << lem[0] << " == " << d_valuation.getSatValue(lem[0]) << endl; - } else { - Debug("integers") << " " << lem[0] << " is not assigned a SAT literal" << endl; - } - if(d_valuation.isSatLiteral(lem[1])) { - Debug("integers") << " " << lem[1] << " == " << d_valuation.getSatValue(lem[1]) << endl; - } else { - Debug("integers") << " " << lem[1] << " is not assigned a SAT literal" << endl; - } - return lem; + return branchIntegerVariable(v); + + // Assert(isInteger(v)); + // Assert(!isSlackVariable(v)); + + // const DeltaRational& d = d_partialModel.getAssignment(v); + // const Rational& r = d.getNoninfinitesimalPart(); + // const Rational& i = d.getInfinitesimalPart(); + // Trace("integers") << "integers: assignment to [[" << d_arithvarNodeMap.asNode(v) << "]] is " << r << "[" << i << "]" << endl; + + // Assert(! (r.getDenominator() == 1 && i.getNumerator() == 0)); + // Assert(!d.isIntegral()); + + // TNode var = d_arithvarNodeMap.asNode(v); + // Integer floor_d = d.floor(); + // Integer ceil_d = d.ceiling(); + + // Node leq = Rewriter::rewrite(NodeManager::currentNM()->mkNode(kind::LEQ, var, mkRationalNode(floor_d))); + // Node geq = Rewriter::rewrite(NodeManager::currentNM()->mkNode(kind::GEQ, var, mkRationalNode(ceil_d))); + + + // Node lem = NodeManager::currentNM()->mkNode(kind::OR, leq, geq); + // Trace("integers") << "integers: branch & bound: " << lem << endl; + // if(d_valuation.isSatLiteral(lem[0])) { + // Debug("integers") << " " << lem[0] << " == " << d_valuation.getSatValue(lem[0]) << endl; + // } else { + // Debug("integers") << " " << lem[0] << " is not assigned a SAT literal" << endl; + // } + // if(d_valuation.isSatLiteral(lem[1])) { + // Debug("integers") << " " << lem[1] << " == " << d_valuation.getSatValue(lem[1]) << endl; + // } else { + // Debug("integers") << " " << lem[1] << " is not assigned a SAT literal" << endl; + // } + // return lem; } } |