diff options
author | Tim King <taking@cs.nyu.edu> | 2012-04-17 16:07:22 +0000 |
---|---|---|
committer | Tim King <taking@cs.nyu.edu> | 2012-04-17 16:07:22 +0000 |
commit | ccd77233892ace44fd4852999e66534d1c2283ea (patch) | |
tree | a856cacd24508a5839fcdbe728583ff055b64e34 /src/theory/arith/linear_equality.cpp | |
parent | 9644b6e12fbd3b649daafa43c5400d272e27bfb4 (diff) |
Merges branches/arithmetic/atom-database r2979 through 3247 into trunk. Below is a highlight of the changes:
- This introduces a new normal form to arithmetic.
-- Equalities and disequalities are in solved form.
Roughly speaking this means: (= x (+ y z)) is in normal form.
(See the comments in normal_form.h for what this formally requires.)
-- The normal form for inequality atoms always uses GEQ and GT instead of GEQ and LEQ.
Integer atoms always use GEQ.
- Constraint was added to TheoryArith.
-- A constraint is a triple of (k x v) where:
--- k is the type of the constraint (either LowerBound, UpperBound, Equality or Disequality),
--- x is an ArithVar, and
--- v is a DeltaRational value.
-- Constraints are always attached to a ConstraintDatabase.
-- A Constraint has its negation in the ConstraintDatabase [at least for now].
-- Every constraint belongs to a set of constraints for each ArithVar sorted by the delta rational values.
-- This set can be iterated over and provides efficient access to other constraints for this variable.
-- A literal may be attached to a constraint.
-- Constraints with attached literals may be marked as being asserted to the theory (sat context dependent).
-- Constraints can be propagated.
-- Every constraint has a proof (sat context dependent).
-- Proofs can be explained for either conflicts or propagations (if the node was propagated). (These proofs may be different.)
-- Equalities and disequalities can be marked as being split (user context dependent)
- This removes and replaces:
-- src/theory/arith/arith_prop_manager.*
-- src/theory/arith/atom_database.*
-- src/theory/arith/ordered_set.h
- Added isZero(), isOne() and isNegativeOne() to Rational and Integer.
- Added operator+ to CDList::const_iterator.
- Added const_iterator to CDQueue.
- Changes to regression tests.
Diffstat (limited to 'src/theory/arith/linear_equality.cpp')
-rw-r--r-- | src/theory/arith/linear_equality.cpp | 47 |
1 files changed, 32 insertions, 15 deletions
diff --git a/src/theory/arith/linear_equality.cpp b/src/theory/arith/linear_equality.cpp index c84e61285..ca7cd69c4 100644 --- a/src/theory/arith/linear_equality.cpp +++ b/src/theory/arith/linear_equality.cpp @@ -26,8 +26,8 @@ namespace theory { namespace arith { /* Explicitly instatiate this function. */ -template void LinearEqualityModule::explainNonbasics<true>(ArithVar basic, NodeBuilder<>& output); -template void LinearEqualityModule::explainNonbasics<false>(ArithVar basic, NodeBuilder<>& output); +template void LinearEqualityModule::propagateNonbasics<true>(ArithVar basic, Constraint c); +template void LinearEqualityModule::propagateNonbasics<false>(ArithVar basic, Constraint c); LinearEqualityModule::Statistics::Statistics(): d_statPivots("theory::arith::pivots",0), @@ -71,7 +71,7 @@ void LinearEqualityModule::update(ArithVar x_i, const DeltaRational& v){ DeltaRational nAssignment = assignment+(diff * a_ji); d_partialModel.setAssignment(x_j, nAssignment); - d_basicVariableUpdates.callback(x_j); + d_basicVariableUpdates(x_j); } d_partialModel.setAssignment(x_i, v); @@ -119,7 +119,7 @@ void LinearEqualityModule::pivotAndUpdate(ArithVar x_i, ArithVar x_j, DeltaRatio DeltaRational nextAssignment = d_partialModel.getAssignment(x_k) + (theta * a_kj); d_partialModel.setAssignment(x_k, nextAssignment); - d_basicVariableUpdates.callback(x_k); + d_basicVariableUpdates(x_k); } } @@ -131,7 +131,7 @@ void LinearEqualityModule::pivotAndUpdate(ArithVar x_i, ArithVar x_j, DeltaRatio //(d_statistics.d_avgNumRowsNotContainingOnPivot).addEntry(difference); d_tableau.pivot(x_i, x_j); - d_basicVariableUpdates.callback(x_j); + d_basicVariableUpdates(x_j); if(Debug.isOn("tableau")){ d_tableau.printTableau(); @@ -255,12 +255,17 @@ bool LinearEqualityModule::hasBounds(ArithVar basic, bool upperBound){ } template <bool upperBound> -void LinearEqualityModule::explainNonbasics(ArithVar basic, NodeBuilder<>& output){ +void LinearEqualityModule::propagateNonbasics(ArithVar basic, Constraint c){ Assert(d_tableau.isBasic(basic)); + Assert(c->getVariable() == basic); + Assert(!c->assertedToTheTheory()); + Assert(c->canBePropagated()); + Assert(!c->hasProof()); Debug("arith::explainNonbasics") << "LinearEqualityModule::explainNonbasics(" << basic <<") start" << endl; + vector<Constraint> bounds; Tableau::RowIterator iter = d_tableau.rowIterator(basic); for(; !iter.atEnd(); ++iter){ @@ -269,30 +274,42 @@ void LinearEqualityModule::explainNonbasics(ArithVar basic, NodeBuilder<>& outpu if(nonbasic == basic) continue; const Rational& a_ij = entry.getCoefficient(); - TNode bound = TNode::null(); int sgn = a_ij.sgn(); Assert(sgn != 0); + Constraint bound = NullConstraint; if(upperBound){ if(sgn < 0){ - bound = d_partialModel.getLowerConstraint(nonbasic); + bound = d_partialModel.getLowerBoundConstraint(nonbasic); + //d_partialModel.explainLowerBound(nonbasic, output); + //bound = d_partialModel.explainLowerBound(nonbasic); }else{ Assert(sgn > 0); - bound = d_partialModel.getUpperConstraint(nonbasic); + bound = d_partialModel.getUpperBoundConstraint(nonbasic); + //d_partialModel.explainUpperBound(nonbasic, output); + //bound = d_partialModel.explainUpperBound(nonbasic); } }else{ if(sgn < 0){ - bound = d_partialModel.getUpperConstraint(nonbasic); + bound = d_partialModel.getUpperBoundConstraint(nonbasic); + //d_partialModel.explainUpperBound(nonbasic, output); + //bound = d_partialModel.explainUpperBound(nonbasic); }else{ Assert(sgn > 0); - bound = d_partialModel.getLowerConstraint(nonbasic); + bound = d_partialModel.getLowerBoundConstraint(nonbasic); + //d_partialModel.explainLowerBound(nonbasic, output); + //bound = d_partialModel.explainLowerBound(nonbasic); } } - Assert(!bound.isNull()); - Debug("arith::explainNonbasics") << "\t" << nonbasic << " " << sgn << " " << bound - << endl; - output << bound; + Assert(bound != NullConstraint); + Debug("arith::explainNonbasics") << "explainNonbasics" << bound << " for " << c << endl; + bounds.push_back(bound); + //Assert(!bound.isNull()); + // Debug("arith::explainNonbasics") << "\t" << nonbasic << " " << sgn << " " << bound + // << endl; + // output << bound; } + c->propagate(bounds); Debug("arith::explainNonbasics") << "LinearEqualityModule::explainNonbasics(" << basic << ") done" << endl; } |