Branch data     Line data    Source code

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