diff options
author | Tim King <taking@cs.nyu.edu> | 2015-04-17 15:22:53 +0200 |
---|---|---|
committer | Tim King <taking@cs.nyu.edu> | 2015-04-18 13:32:28 +0200 |
commit | 174e03832db4325d79880a2048aaad5c405ff699 (patch) | |
tree | f739b2428a8a2e9262e0d0b1fc77c04b5ec707ea /src/theory/arith/simplex.h | |
parent | 4d359ce4470c44c3e7532edb6b60bcb61b51f862 (diff) |
Farkas proof coefficients.
This commit adds tracking of Farkas coefficients to proof enabled builds in the theory of linear
real arithmetic when proofs are enabled. There could be some performance changes due to subtly
different search paths being taken.
Additional bug fixes:
- Polynomial::exactDivide did not satisfy preconditions to the Monomial constructor.
To prevent future problems, Monomials should now be made via one of the mkMonomial functions.
- Fixes a bug in SumOfInfeasibilitiesSPD::greedyConflictSubsets().
There was a way to use a row twice in the construction of the conflicts.
This was violating an assumption in the Tableau when constructing the intermediate rows.
Constraints:
- To enable proofs, all conflicts and propagations are designed to go through the Constraint system
before they are converted to externally understandable conflicts and propagations in the form
of Node.
- Constraints must now be given a reason for marking them as true that corresponds to a proof.
- Constraints should now be marked as being true by one of the impliedbyX functions.
- Each impliedByX function has an ArithProofType associated with it.
- Each call to an impliedByX function stores a context dependent ConstraintRule object
to track the proof.
- After marking the node as true the caller should either try to propagate the constraint or raise
a conflict.
- There are no more special cases for marking a node as being true when its negation has a proof
vs. when the negation does not have a proof. One must now explicitly pass in a inConflict flag
to the impliedByX (and similar functions).
For example,this is now longer both:
void setAssertedToTheTheory(TNode witness);
void setAssertedToTheTheoryWithNegationTrue(TNode witness);
There is just:
void setAssertedToTheTheory(TNode witness, bool inConflict);
Diffstat (limited to 'src/theory/arith/simplex.h')
-rw-r--r-- | src/theory/arith/simplex.h | 12 |
1 files changed, 11 insertions, 1 deletions
diff --git a/src/theory/arith/simplex.h b/src/theory/arith/simplex.h index 91e6e4244..ada9b5efd 100644 --- a/src/theory/arith/simplex.h +++ b/src/theory/arith/simplex.h @@ -105,6 +105,9 @@ protected: /** This is the call back channel for Simplex to report conflicts. */ RaiseConflict d_conflictChannel; + /** This is the call back channel for Simplex to report conflicts. */ + FarkasConflictBuilder* d_conflictBuilder; + /** Used for requesting d_opt, bound and error variables for primal.*/ TempVarMalloc d_arithVarMalloc; @@ -114,6 +117,12 @@ protected: /** A local copy of 0. */ const Rational d_zero; + /** A local copy of 1. */ + const Rational d_posOne; + + /** A local copy of -1. */ + const Rational d_negOne; + ArithVar constructInfeasiblityFunction(TimerStat& timer); ArithVar constructInfeasiblityFunction(TimerStat& timer, ArithVar e); ArithVar constructInfeasiblityFunction(TimerStat& timer, const ArithVarVec& set); @@ -126,6 +135,7 @@ protected: public: SimplexDecisionProcedure(LinearEqualityModule& linEq, ErrorSet& errors, RaiseConflict conflictChannel, TempVarMalloc tvmalloc); + ~SimplexDecisionProcedure(); /** * Tries to update the assignments of variables such that all of the @@ -166,7 +176,7 @@ protected: * If a basic variable has a conflict on its row, * this produces a minimized row on the conflict channel. */ - void generateConflictForBasic(ArithVar basic, RaiseConflict& rc) const; + ConstraintCP generateConflictForBasic(ArithVar basic) const; /** Gets a fresh variable from TheoryArith. */ |