Branch data     Line data    Source code

       1                 :            : /******************************************************************************
       2                 :            :  * Top contributors (to current version):
       3                 :            :  *   Tim King, Andrew V. Teylu, Andrew Reynolds
       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                 :            :  * [[ Add one-line brief description here ]]
      14                 :            :  *
      15                 :            :  * [[ Add lengthier description here ]]
      16                 :            :  * \todo document this file
      17                 :            :  */
      18                 :            : 
      19                 :            : #include "cvc5_private.h"
      20                 :            : 
      21                 :            : #pragma once
      22                 :            : 
      23                 :            : #include <optional>
      24                 :            : #include <vector>
      25                 :            : 
      26                 :            : #include "theory/arith/linear/arithvar.h"
      27                 :            : #include "theory/arith/delta_rational.h"
      28                 :            : #include "util/dense_map.h"
      29                 :            : #include "util/rational.h"
      30                 :            : #include "util/statistics_stats.h"
      31                 :            : 
      32                 :            : namespace cvc5::internal {
      33                 :            : namespace theory {
      34                 :            : namespace arith::linear {
      35                 :            : 
      36                 :            : enum LinResult {
      37                 :            :   LinUnknown,  /* Unknown error */
      38                 :            :   LinFeasible, /* Relaxation is feasible */
      39                 :            :   LinInfeasible,   /* Relaxation is infeasible/all integer branches closed */
      40                 :            :   LinExhausted
      41                 :            : };
      42                 :            : 
      43                 :            : enum MipResult {
      44                 :            :   MipUnknown,  /* Unknown error */
      45                 :            :   MipBingo,    /* Integer feasible */
      46                 :            :   MipClosed,   /* All integer branches closed */
      47                 :            :   BranchesExhausted, /* Exhausted number of branches */
      48                 :            :   PivotsExhauasted,  /* Exhausted number of pivots */
      49                 :            :   ExecExhausted      /* Exhausted total operations */
      50                 :            : };
      51                 :            : std::ostream& operator<<(std::ostream& out, MipResult res);
      52                 :            : 
      53                 :            : class ApproximateStatistics {
      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                 :            : 
      66                 :            : class NodeLog;
      67                 :            : class TreeLog;
      68                 :            : class ArithVariables;
      69                 :            : class CutInfo;
      70                 :            : 
      71                 :            : class ApproximateSimplex{
      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                 :            :     DenseSet newBasis;
      88                 :            :     DenseMap<DeltaRational> newValues;
      89                 :         12 :     Solution() : newBasis(), newValues(){}
      90                 :            :   };
      91                 :            : 
      92                 :            :   /* maximum branches allowed on a variable */
      93                 :            :   virtual void setBranchingDepth(int bd) = 0;
      94                 :            : 
      95                 :            :   /* gets a branching variable */
      96                 :            :   virtual ArithVar getBranchVar(const NodeLog& nl) const = 0;
      97                 :            : 
      98                 :            :   /**
      99                 :            :    * Estimates a double as a Rational using continued fraction expansion that
     100                 :            :    * cuts off the estimate once the value is approximately zero.
     101                 :            :    * This is designed for removing rounding artifacts.
     102                 :            :    */
     103                 :            :   virtual std::optional<Rational> estimateWithCFE(double d) const = 0;
     104                 :            :   virtual std::optional<Rational> estimateWithCFE(double d,
     105                 :            :                                                   const Integer& D) const = 0;
     106                 :            : 
     107                 :            :   virtual void tryCut(int nid, CutInfo& cut) = 0;
     108                 :            : 
     109                 :            :   virtual std::vector<const CutInfo*> getValidCuts(const NodeLog& node) = 0;
     110                 :            : 
     111                 :            :   /* the maximum pivots allowed in a query. */
     112                 :            :   virtual void setPivotLimit(int pl) = 0;
     113                 :            : 
     114                 :            :   virtual ArithRatPairVec heuristicOptCoeffs() const = 0;
     115                 :            : 
     116                 :            :   /** Sets a maximization criteria for the approximate solver.*/
     117                 :            :   virtual void setOptCoeffs(const ArithRatPairVec& ref) = 0;
     118                 :            : 
     119                 :            :   /* maximum branches allowed on a variable */
     120                 :            :   virtual void setBranchOnVariableLimit(int bl) = 0;
     121                 :            : 
     122                 :            :   virtual LinResult solveRelaxation() = 0;
     123                 :            : 
     124                 :            :   virtual MipResult solveMIP(bool activelyLog) = 0;
     125                 :            : 
     126                 :            :   virtual Solution extractMIP() const = 0;
     127                 :            : 
     128                 :            :   virtual Solution extractRelaxation() const = 0;
     129                 :            : };/* class ApproximateSimplex */
     130                 :            : 
     131                 :            : }  // namespace arith
     132                 :            : }  // namespace theory
     133                 :            : }  // namespace cvc5::internal