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                 :            :  * [[ Add one-line brief description here ]]
      11                 :            :  *
      12                 :            :  * [[ Add lengthier description here ]]
      13                 :            :  * \todo document this file
      14                 :            :  */
      15                 :            : 
      16                 :            : #include "cvc5_private.h"
      17                 :            : 
      18                 :            : #pragma once
      19                 :            : 
      20                 :            : #include <optional>
      21                 :            : #include <vector>
      22                 :            : 
      23                 :            : #include "theory/arith/delta_rational.h"
      24                 :            : #include "theory/arith/linear/arithvar.h"
      25                 :            : #include "util/dense_map.h"
      26                 :            : #include "util/rational.h"
      27                 :            : #include "util/statistics_stats.h"
      28                 :            : 
      29                 :            : namespace cvc5::internal {
      30                 :            : namespace theory {
      31                 :            : namespace arith::linear {
      32                 :            : 
      33                 :            : enum LinResult
      34                 :            : {
      35                 :            :   LinUnknown,    /* Unknown error */
      36                 :            :   LinFeasible,   /* Relaxation is feasible */
      37                 :            :   LinInfeasible, /* Relaxation is infeasible/all integer branches closed */
      38                 :            :   LinExhausted
      39                 :            : };
      40                 :            : 
      41                 :            : enum MipResult
      42                 :            : {
      43                 :            :   MipUnknown,        /* Unknown error */
      44                 :            :   MipBingo,          /* Integer feasible */
      45                 :            :   MipClosed,         /* All integer branches closed */
      46                 :            :   BranchesExhausted, /* Exhausted number of branches */
      47                 :            :   PivotsExhauasted,  /* Exhausted number of pivots */
      48                 :            :   ExecExhausted      /* Exhausted total operations */
      49                 :            : };
      50                 :            : std::ostream& operator<<(std::ostream& out, MipResult res);
      51                 :            : 
      52                 :            : class ApproximateStatistics
      53                 :            : {
      54                 :            :  public:
      55                 :            :   ApproximateStatistics(StatisticsRegistry& sr);
      56                 :            : 
      57                 :            :   IntStat d_branchMaxDepth;
      58                 :            :   IntStat d_branchesMaxOnAVar;
      59                 :            : 
      60                 :            :   TimerStat d_gaussianElimConstructTime;
      61                 :            :   IntStat d_gaussianElimConstruct;
      62                 :            :   AverageStat d_averageGuesses;
      63                 :            : };
      64                 :            : 
      65                 :            : class NodeLog;
      66                 :            : class TreeLog;
      67                 :            : class ArithVariables;
      68                 :            : class CutInfo;
      69                 :            : 
      70                 :            : class ApproximateSimplex
      71                 :            : {
      72                 :            :  public:
      73                 :            :   /** Is GLPK enabled? */
      74                 :            :   static bool enabled();
      75                 :            : 
      76                 :            :   /**
      77                 :            :    * If GLPK is enabled, creates a GPLK-based approximating solver.
      78                 :            :    */
      79                 :            :   static ApproximateSimplex* mkApproximateSimplexSolver(
      80                 :            :       const ArithVariables& vars, TreeLog& l, ApproximateStatistics& s);
      81                 :            : 
      82                 :          6 :   ApproximateSimplex() = default;
      83                 :          6 :   virtual ~ApproximateSimplex() {}
      84                 :            : 
      85                 :            :   /** A result is either sat, unsat or unknown.*/
      86                 :            :   struct Solution
      87                 :            :   {
      88                 :            :     DenseSet newBasis;
      89                 :            :     DenseMap<DeltaRational> newValues;
      90                 :         12 :     Solution() : newBasis(), newValues() {}
      91                 :            :   };
      92                 :            : 
      93                 :            :   /* maximum branches allowed on a variable */
      94                 :            :   virtual void setBranchingDepth(int bd) = 0;
      95                 :            : 
      96                 :            :   /* gets a branching variable */
      97                 :            :   virtual ArithVar getBranchVar(const NodeLog& nl) const = 0;
      98                 :            : 
      99                 :            :   /**
     100                 :            :    * Estimates a double as a Rational using continued fraction expansion that
     101                 :            :    * cuts off the estimate once the value is approximately zero.
     102                 :            :    * This is designed for removing rounding artifacts.
     103                 :            :    */
     104                 :            :   virtual std::optional<Rational> estimateWithCFE(double d) const = 0;
     105                 :            :   virtual std::optional<Rational> estimateWithCFE(double d,
     106                 :            :                                                   const Integer& D) const = 0;
     107                 :            : 
     108                 :            :   virtual void tryCut(int nid, CutInfo& cut) = 0;
     109                 :            : 
     110                 :            :   virtual std::vector<const CutInfo*> getValidCuts(const NodeLog& node) = 0;
     111                 :            : 
     112                 :            :   /* the maximum pivots allowed in a query. */
     113                 :            :   virtual void setPivotLimit(int pl) = 0;
     114                 :            : 
     115                 :            :   virtual ArithRatPairVec heuristicOptCoeffs() const = 0;
     116                 :            : 
     117                 :            :   /** Sets a maximization criteria for the approximate solver.*/
     118                 :            :   virtual void setOptCoeffs(const ArithRatPairVec& ref) = 0;
     119                 :            : 
     120                 :            :   /* maximum branches allowed on a variable */
     121                 :            :   virtual void setBranchOnVariableLimit(int bl) = 0;
     122                 :            : 
     123                 :            :   virtual LinResult solveRelaxation() = 0;
     124                 :            : 
     125                 :            :   virtual MipResult solveMIP(bool activelyLog) = 0;
     126                 :            : 
     127                 :            :   virtual Solution extractMIP() const = 0;
     128                 :            : 
     129                 :            :   virtual Solution extractRelaxation() const = 0;
     130                 :            : }; /* class ApproximateSimplex */
     131                 :            : 
     132                 :            : }  // namespace arith::linear
     133                 :            : }  // namespace theory
     134                 :            : }  // namespace cvc5::internal