Branch data     Line data    Source code

       1                 :            : /******************************************************************************
       2                 :            :  * Top contributors (to current version):
       3                 :            :  *   Gereon Kremer, Andrew Reynolds, Aina Niemetz
       4                 :            :  *
       5                 :            :  * This file is part of the cvc5 project.
       6                 :            :  *
       7                 :            :  * Copyright (c) 2009-2025 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                 :            :  * Implements the CDCAC approach as described in
      14                 :            :  * https://arxiv.org/pdf/2003.05633.pdf.
      15                 :            :  */
      16                 :            : 
      17                 :            : #include "cvc5_private.h"
      18                 :            : 
      19                 :            : #ifndef CVC5__THEORY__ARITH__NL__COVERINGS__CDCAC_H
      20                 :            : #define CVC5__THEORY__ARITH__NL__COVERINGS__CDCAC_H
      21                 :            : 
      22                 :            : #ifdef CVC5_POLY_IMP
      23                 :            : 
      24                 :            : #include <poly/polyxx.h>
      25                 :            : 
      26                 :            : #include <vector>
      27                 :            : 
      28                 :            : #include "smt/env.h"
      29                 :            : #include "smt/env_obj.h"
      30                 :            : #include "theory/arith/nl/coverings/cdcac_utils.h"
      31                 :            : #include "theory/arith/nl/coverings/constraints.h"
      32                 :            : #include "theory/arith/nl/coverings/lazard_evaluation.h"
      33                 :            : #include "theory/arith/nl/coverings/proof_generator.h"
      34                 :            : #include "theory/arith/nl/coverings/variable_ordering.h"
      35                 :            : 
      36                 :            : namespace cvc5::internal {
      37                 :            : namespace theory {
      38                 :            : namespace arith {
      39                 :            : namespace nl {
      40                 :            : 
      41                 :            : class NlModel;
      42                 :            : 
      43                 :            : namespace coverings {
      44                 :            : 
      45                 :            : /**
      46                 :            :  * This class implements Cylindrical Algebraic Coverings as presented in
      47                 :            :  * https://arxiv.org/pdf/2003.05633.pdf
      48                 :            :  */
      49                 :            : class CDCAC : protected EnvObj
      50                 :            : {
      51                 :            :  public:
      52                 :            :   /** Initialize this method with the given variable ordering. */
      53                 :            :   CDCAC(Env& env, const std::vector<poly::Variable>& ordering = {});
      54                 :            : 
      55                 :            :   /** Reset this instance. */
      56                 :            :   void reset();
      57                 :            : 
      58                 :            :   /** Collect variables from the constraints and compute a variable ordering. */
      59                 :            :   void computeVariableOrdering();
      60                 :            : 
      61                 :            :   /**
      62                 :            :    * Extract an initial assignment from the given model.
      63                 :            :    * This initial assignment is used to guide sampling if possible.
      64                 :            :    * The ran_variable should be the variable used to encode real algebraic
      65                 :            :    * numbers in the model and is simply passed on to node_to_value.
      66                 :            :    */
      67                 :            :   void retrieveInitialAssignment(NlModel& model, const Node& ran_variable);
      68                 :            : 
      69                 :            :   /**
      70                 :            :    * Returns the constraints as a non-const reference. Can be used to add new
      71                 :            :    * constraints.
      72                 :            :    */
      73                 :            :   Constraints& getConstraints();
      74                 :            :   /** Returns the constraints as a const reference. */
      75                 :            :   const Constraints& getConstraints() const;
      76                 :            : 
      77                 :            :   /**
      78                 :            :    * Returns the current assignment. This is a satisfying model if
      79                 :            :    * get_unsat_cover() returned an empty vector.
      80                 :            :    */
      81                 :            :   const poly::Assignment& getModel() const;
      82                 :            : 
      83                 :            :   /** Returns the current variable ordering. */
      84                 :            :   const std::vector<poly::Variable>& getVariableOrdering() const;
      85                 :            : 
      86                 :            :   /**
      87                 :            :    * Collect all unsatisfiable intervals for the given variable.
      88                 :            :    * Combines unsatisfiable regions from d_constraints evaluated over
      89                 :            :    * d_assignment. Implements Algorithm 2.
      90                 :            :    */
      91                 :            :   std::vector<CACInterval> getUnsatIntervals(std::size_t cur_variable);
      92                 :            : 
      93                 :            :   /**
      94                 :            :    * Sample outside of the set of intervals.
      95                 :            :    * Uses a given initial value from mInitialAssignment if possible.
      96                 :            :    * Returns whether a sample was found (true) or the infeasible intervals cover
      97                 :            :    * the whole real line (false).
      98                 :            :    */
      99                 :            :   bool sampleOutsideWithInitial(const std::vector<CACInterval>& infeasible,
     100                 :            :                                 poly::Value& sample,
     101                 :            :                                 std::size_t cur_variable);
     102                 :            : 
     103                 :            :   /**
     104                 :            :    * Collects the coefficients required for projection from the given
     105                 :            :    * polynomial. Implements Algorithm 6, depending on the command line
     106                 :            :    * arguments. Either directly implements Algorithm 6, or improved variants
     107                 :            :    * based on Lazard's projection.
     108                 :            :    */
     109                 :            :   PolyVector requiredCoefficients(const poly::Polynomial& p);
     110                 :            : 
     111                 :            :   /**
     112                 :            :    * Constructs a characterization of the given covering.
     113                 :            :    * A characterization contains polynomials whose roots bound the region around
     114                 :            :    * the current assignment. Implements Algorithm 4.
     115                 :            :    */
     116                 :            :   PolyVector constructCharacterization(std::vector<CACInterval>& intervals);
     117                 :            : 
     118                 :            :   /**
     119                 :            :    * Constructs an infeasible interval from a characterization.
     120                 :            :    * Implements Algorithm 5.
     121                 :            :    */
     122                 :            :   CACInterval intervalFromCharacterization(const PolyVector& characterization,
     123                 :            :                                            std::size_t cur_variable,
     124                 :            :                                            const poly::Value& sample);
     125                 :            : 
     126                 :            :   /**
     127                 :            :    * Internal implementation of getUnsatCover().
     128                 :            :    * @param curVariable The id of the variable (within d_variableOrdering) to
     129                 :            :    * be considered. This argument is used to manage the recursion internally and
     130                 :            :    * should always be zero if called externally.
     131                 :            :    * @param returnFirstInterval If true, the function returns after the first
     132                 :            :    * interval obtained from a recursive call. The result is not (necessarily) an
     133                 :            :    * unsat cover, but merely a list of infeasible intervals.
     134                 :            :    */
     135                 :            :   std::vector<CACInterval> getUnsatCoverImpl(std::size_t curVariable = 0,
     136                 :            :                                              bool returnFirstInterval = false);
     137                 :            : 
     138                 :            :   /**
     139                 :            :    * Main method that checks for the satisfiability of the constraints.
     140                 :            :    * Recursively explores possible assignments and excludes regions based on the
     141                 :            :    * coverings. Returns either a covering for the lowest dimension or an empty
     142                 :            :    * vector. If the covering is empty, the result is SAT and an assignment can
     143                 :            :    * be obtained from d_assignment. If the covering is not empty, the result is
     144                 :            :    * UNSAT and an infeasible subset can be extracted from the returned covering.
     145                 :            :    * Implements Algorithm 2.
     146                 :            :    * This method itself only takes care of the outermost proof scope and calls
     147                 :            :    * out to getUnsatCoverImpl() with curVariable set to zero.
     148                 :            :    * @param returnFirstInterval If true, the function returns after the first
     149                 :            :    * interval obtained from a recursive call. The result is not (necessarily) an
     150                 :            :    * unsat cover, but merely a list of infeasible intervals.
     151                 :            :    */
     152                 :            :   std::vector<CACInterval> getUnsatCover(bool returnFirstInterval = false);
     153                 :            : 
     154                 :            :   void startNewProof();
     155                 :            :   /**
     156                 :            :    * Finish the generated proof (if proofs are enabled) with a scope over the
     157                 :            :    * given assertions.
     158                 :            :    */
     159                 :            :   ProofGenerator* closeProof(const std::vector<Node>& assertions);
     160                 :            : 
     161                 :            :   /** Get the proof generator */
     162                 :          1 :   CoveringsProofGenerator* getProof() { return d_proof.get(); }
     163                 :            : 
     164                 :            :  private:
     165                 :            :   /** Check whether proofs are enabled */
     166                 :      19755 :   bool isProofEnabled() const { return d_proof != nullptr; }
     167                 :            : 
     168                 :            :   /**
     169                 :            :    * Check whether the current sample satisfies the integrality condition of the
     170                 :            :    * current variable. Returns true if the variable is not integral or the
     171                 :            :    * sample is integral.
     172                 :            :    */
     173                 :            :   bool checkIntegrality(std::size_t cur_variable, const poly::Value& value);
     174                 :            :   /**
     175                 :            :    * Constructs an interval that excludes the non-integral region around the
     176                 :            :    * current sample. Assumes !check_integrality(cur_variable, value).
     177                 :            :    */
     178                 :            :   CACInterval buildIntegralityInterval(std::size_t cur_variable,
     179                 :            :                                        const poly::Value& value);
     180                 :            : 
     181                 :            :   /**
     182                 :            :    * Check whether the polynomial has a real root above the given value (when
     183                 :            :    * evaluated over the current assignment).
     184                 :            :    */
     185                 :            :   bool hasRootAbove(const poly::Polynomial& p, const poly::Value& val) const;
     186                 :            :   /**
     187                 :            :    * Check whether the polynomial has a real root below the given value (when
     188                 :            :    * evaluated over the current assignment).
     189                 :            :    */
     190                 :            :   bool hasRootBelow(const poly::Polynomial& p, const poly::Value& val) const;
     191                 :            : 
     192                 :            :   /**
     193                 :            :    * Sort intervals according to section 4.4.1. and removes fully redundant
     194                 :            :    * intervals as in 4.5. 1. by calling out to cleanIntervals.
     195                 :            :    * Additionally makes sure to prune proofs for removed intervals.
     196                 :            :    */
     197                 :            :   void pruneRedundantIntervals(std::vector<CACInterval>& intervals);
     198                 :            : 
     199                 :            :   /**
     200                 :            :    * Prepare the lazard evaluation object with the current assignment, if the
     201                 :            :    * lazard lifting is enabled. Otherwise, this function does nothing.
     202                 :            :    */
     203                 :            :   void prepareRootIsolation(LazardEvaluation& le, size_t cur_variable) const;
     204                 :            : 
     205                 :            :   /**
     206                 :            :    * Isolates the real roots of the polynomial `p`. If the lazard lifting is
     207                 :            :    * enabled, this function uses `le.isolateRealRoots()`, otherwise uses the
     208                 :            :    * regular `poly::isolate_real_roots()`.
     209                 :            :    */
     210                 :            :   std::vector<poly::Value> isolateRealRoots(LazardEvaluation& le,
     211                 :            :                                             const poly::Polynomial& p) const;
     212                 :            : 
     213                 :            :   /**
     214                 :            :    * The current assignment. When the method terminates with SAT, it contains a
     215                 :            :    * model for the input constraints.
     216                 :            :    */
     217                 :            :   poly::Assignment d_assignment;
     218                 :            : 
     219                 :            :   /** The set of input constraints to be checked for consistency. */
     220                 :            :   Constraints d_constraints;
     221                 :            : 
     222                 :            :   /** The computed variable ordering used for this method. */
     223                 :            :   std::vector<poly::Variable> d_variableOrdering;
     224                 :            : 
     225                 :            :   /** The object computing the variable ordering. */
     226                 :            :   VariableOrdering d_varOrder;
     227                 :            : 
     228                 :            :   /** The linear assignment used as an initial guess. */
     229                 :            :   std::vector<poly::Value> d_initialAssignment;
     230                 :            : 
     231                 :            :   /** The proof generator */
     232                 :            :   std::unique_ptr<CoveringsProofGenerator> d_proof;
     233                 :            : 
     234                 :            :   /** The next interval id */
     235                 :            :   size_t d_nextIntervalId = 1;
     236                 :            : };
     237                 :            : 
     238                 :            : }  // namespace coverings
     239                 :            : }  // namespace nl
     240                 :            : }  // namespace arith
     241                 :            : }  // namespace theory
     242                 :            : }  // namespace cvc5::internal
     243                 :            : 
     244                 :            : #endif
     245                 :            : 
     246                 :            : #endif