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);

1 files changed, 23 insertions, 8 deletions

diff --git a/src/theory/arith/linear_equality.h b/src/theory/arith/linear_equality.h
index 5e325d799..f6717d141 100644
--- a/src/theory/arith/linear_equality.h
+++ b/src/theory/arith/linear_equality.h
@@ -199,6 +199,7 @@ public:
 
   typedef bool (LinearEqualityModule::*UpdatePreferenceFunction)(const UpdateInfo&, const UpdateInfo&) const;
 
+  
 private:
   /**
    * Manages information about the assignment and upper and lower bounds on the
@@ -217,6 +218,8 @@ private:
   Maybe<DeltaRational> d_upperBoundDifference;
   Maybe<DeltaRational> d_lowerBoundDifference;
 
+  Rational d_one;
+  Rational d_negOne;
 public:
 
   /**
@@ -417,10 +420,20 @@ public:
   void propagateBasicFromRow(ConstraintP c);
 
   /**
+   * Let v be the variable for the constraint c.
    * Exports either the explanation of an upperbound or a lower bound
-   * of the basic variable basic, using the non-basic variables in the row.
+   * of v using the other variables in the row.
+   *
+   * If farkas != RationalVectorPSentinel, this function additionally
+   * stores the farkas coefficients of the constraints stored in into.
+   * Position 0 is the coefficient of v.
+   * Position i > 0, corresponds to the order of the other constraints.
    */
-  void propagateRow(ConstraintCPVec& into, RowIndex ridx, bool rowUp, ConstraintP c);
+  void propagateRow(ConstraintCPVec& into
+                    , RowIndex ridx
+                    , bool rowUp
+                    , ConstraintP c
+                    , RationalVectorP farkas);
 
   /**
    * Computes the value of a basic variable using the assignments
@@ -598,20 +611,22 @@ private:
 public:
   /**
    * Constructs a minimally weak conflict for the basic variable basicVar.
+   *
+   * Returns a constraint that is now in conflict.
    */
-  void minimallyWeakConflict(bool aboveUpper, ArithVar basicVar, RaiseConflict& rc) const;
+  ConstraintCP minimallyWeakConflict(bool aboveUpper, ArithVar basicVar, FarkasConflictBuilder& rc) const;
 
   /**
-   * Given a non-basic variable that is know to have a conflict on it,
+   * Given a basic variable that is know to have a conflict on it,
    * construct and return a conflict.
    * Follows section 4.2 in the CAV06 paper.
    */
-  inline void generateConflictAboveUpperBound(ArithVar conflictVar, RaiseConflict& rc) const {
-    minimallyWeakConflict(true, conflictVar, rc);
+  inline ConstraintCP generateConflictAboveUpperBound(ArithVar conflictVar, FarkasConflictBuilder& rc) const {
+    return minimallyWeakConflict(true, conflictVar, rc);
   }
 
-  inline void generateConflictBelowLowerBound(ArithVar conflictVar, RaiseConflict& rc) const {
-    minimallyWeakConflict(false, conflictVar, rc);
+  inline ConstraintCP generateConflictBelowLowerBound(ArithVar conflictVar, FarkasConflictBuilder& rc) const {
+    return minimallyWeakConflict(false, conflictVar, rc);
   }
 
   /**