linear_solver.h

Go to the documentation of this file.

// Copyright 2010-2024 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
 
#ifndef OR_TOOLS_LINEAR_SOLVER_LINEAR_SOLVER_H_
#define OR_TOOLS_LINEAR_SOLVER_LINEAR_SOLVER_H_
 
#include <atomic>
#include <cstdint>
#include <functional>
#include <limits>
#include <map>
#include <memory>
#include <optional>
#include <ostream>
#include <string>
#include <utility>
#include <vector>
 
#include "absl/base/attributes.h"
#include "absl/base/port.h"
#include "absl/base/thread_annotations.h"
#include "absl/container/flat_hash_map.h"
#include "absl/flags/declare.h"
#include "absl/log/check.h"
#include "absl/status/status.h"
#include "absl/strings/str_format.h"
#include "absl/strings/string_view.h"
#include "absl/time/clock.h"
#include "absl/time/time.h"
#include "absl/types/optional.h"
#include "ortools/base/logging.h"
#include "ortools/linear_solver/linear_expr.h"
#include "ortools/linear_solver/linear_solver.pb.h"
#include "ortools/linear_solver/linear_solver_callback.h"
#include "ortools/port/proto_utils.h"
#include "ortools/util/lazy_mutable_copy.h"
 
ABSL_DECLARE_FLAG(bool, linear_solver_enable_verbose_output);
ABSL_DECLARE_FLAG(bool, log_verification_errors);
ABSL_DECLARE_FLAG(bool, verify_solution);
 
namespace operations_research {
 
constexpr double kDefaultPrimalTolerance = 1e-07;
 
class MPConstraint;
class MPObjective;
class MPSolverInterface;
class MPSolverParameters;
class MPVariable;
 
// There is a homonymous version taking a MPSolver::OptimizationProblemType.
bool SolverTypeIsMip(MPModelRequest::SolverType solver_type);
 
class MPSolver {
 public:
  enum OptimizationProblemType {
    // Linear programming problems.
    // ----------------------------
    CLP_LINEAR_PROGRAMMING = 0,
    GLPK_LINEAR_PROGRAMMING = 1,
    GLOP_LINEAR_PROGRAMMING = 2,  // Recommended default value. Made in Google.
    // In-house linear programming solver based on the primal-dual hybrid
    // gradient method. Sometimes faster than Glop for medium-size problems and
    // scales to much larger problems than Glop.
    PDLP_LINEAR_PROGRAMMING = 8,
    HIGHS_LINEAR_PROGRAMMING = 15,
 
    // Integer programming problems.
    // -----------------------------
    // Recommended default value for MIP problems.
    SCIP_MIXED_INTEGER_PROGRAMMING = 3,
    GLPK_MIXED_INTEGER_PROGRAMMING = 4,
    CBC_MIXED_INTEGER_PROGRAMMING = 5,
    HIGHS_MIXED_INTEGER_PROGRAMMING = 16,
 
    // Boolean optimization problem (requires only integer variables and works
    // best with only Boolean variables).
    BOP_INTEGER_PROGRAMMING = 12,
 
    // SAT based solver (requires only integer and Boolean variables).
    // If you pass it mixed integer problems, it will scale coefficients to
    // integer values, and solver continuous variables as integral variables.
    //
    // Recommended default value for pure integral problems problems.
    SAT_INTEGER_PROGRAMMING = 14,
 
    // Dedicated knapsack solvers.
    KNAPSACK_MIXED_INTEGER_PROGRAMMING = 13,
 
    // Commercial software (need license).
    GUROBI_LINEAR_PROGRAMMING = 6,
    GUROBI_MIXED_INTEGER_PROGRAMMING = 7,
    CPLEX_LINEAR_PROGRAMMING = 10,
    CPLEX_MIXED_INTEGER_PROGRAMMING = 11,
    XPRESS_LINEAR_PROGRAMMING = 101,
    XPRESS_MIXED_INTEGER_PROGRAMMING = 102,
    COPT_LINEAR_PROGRAMMING = 103,
    COPT_MIXED_INTEGER_PROGRAMMING = 104,
  };
 
  MPSolver(const std::string& name, OptimizationProblemType problem_type);
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  MPSolver(const MPSolver&) = delete;
  MPSolver& operator=(const MPSolver&) = delete;
#endif
 
  virtual ~MPSolver();
 
  static MPSolver* CreateSolver(const std::string& solver_id);
 
  static bool SupportsProblemType(OptimizationProblemType problem_type);
 
  static bool ParseSolverType(absl::string_view solver_id,
                              OptimizationProblemType* type);
 
  static OptimizationProblemType ParseSolverTypeOrDie(
      const std::string& solver_id);
 
  bool IsMIP() const;
 
  const std::string& Name() const {
    return name_;  // Set at construction.
  }
 
  virtual OptimizationProblemType ProblemType() const {
    return problem_type_;  // Set at construction.
  }
 
  void Clear();
 
  int NumVariables() const { return variables_.size(); }
 
  const std::vector<MPVariable*>& variables() const { return variables_; }
 
  MPVariable* variable(int index) const { return variables_[index]; }
 
  MPVariable* LookupVariableOrNull(const std::string& var_name) const;
 
  MPVariable* MakeVar(double lb, double ub, bool integer,
                      const std::string& name);
 
  MPVariable* MakeNumVar(double lb, double ub, const std::string& name);
 
  MPVariable* MakeIntVar(double lb, double ub, const std::string& name);
 
  MPVariable* MakeBoolVar(const std::string& name);
 
  void MakeVarArray(int nb, double lb, double ub, bool integer,
                    const std::string& name_prefix,
                    std::vector<MPVariable*>* vars);
 
  void MakeNumVarArray(int nb, double lb, double ub, const std::string& name,
                       std::vector<MPVariable*>* vars);
 
  void MakeIntVarArray(int nb, double lb, double ub, const std::string& name,
                       std::vector<MPVariable*>* vars);
 
  void MakeBoolVarArray(int nb, const std::string& name,
                        std::vector<MPVariable*>* vars);
 
  int NumConstraints() const { return constraints_.size(); }
 
  const std::vector<MPConstraint*>& constraints() const { return constraints_; }
 
  MPConstraint* constraint(int index) const { return constraints_[index]; }
 
  MPConstraint* LookupConstraintOrNull(
      const std::string& constraint_name) const;
 
  MPConstraint* MakeRowConstraint(double lb, double ub);
 
  MPConstraint* MakeRowConstraint();
 
  MPConstraint* MakeRowConstraint(double lb, double ub,
                                  const std::string& name);
 
  MPConstraint* MakeRowConstraint(const std::string& name);
 
  MPConstraint* MakeRowConstraint(const LinearRange& range);
 
  MPConstraint* MakeRowConstraint(const LinearRange& range,
                                  const std::string& name);
 
  const MPObjective& Objective() const { return *objective_; }
 
  MPObjective* MutableObjective() { return objective_.get(); }
 
  enum ResultStatus {
    OPTIMAL,
    FEASIBLE,
    INFEASIBLE,
    UNBOUNDED,
    ABNORMAL,
    MODEL_INVALID,
    NOT_SOLVED = 6
  };
 
  ResultStatus Solve();
 
  ResultStatus Solve(const MPSolverParameters& param);
 
  void Write(const std::string& file_name);
 
  std::vector<double> ComputeConstraintActivities() const;
 
  bool VerifySolution(double tolerance, bool log_errors) const;
 
  void Reset();
 
  bool InterruptSolve();
 
  MPSolverResponseStatus LoadModelFromProto(const MPModelProto& input_model,
                                            std::string* error_message,
                                            bool clear_names = true);
  MPSolverResponseStatus LoadModelFromProtoWithUniqueNamesOrDie(
      const MPModelProto& input_model, std::string* error_message);
 
  void FillSolutionResponseProto(MPSolutionResponse* response) const;
 
  ABSL_DEPRECATED("Prefer SolveMPModel() from solve_mp_model.h.")
  static void SolveWithProto(const MPModelRequest& model_request,
                             MPSolutionResponse* response,
                             std::atomic<bool>* interrupt = nullptr);
 
  ABSL_DEPRECATED("Prefer SolveMPModel() from solve_mp_model.h.")
  static void SolveLazyMutableRequest(LazyMutableCopy<MPModelRequest> request,
                                      MPSolutionResponse* response,
                                      std::atomic<bool>* interrupt = nullptr);
 
  ABSL_DEPRECATED(
      "Prefer SolverTypeSupportsInterruption() from solve_mp_model.h.")
  static bool SolverTypeSupportsInterruption(
      const MPModelRequest::SolverType solver) {
    // Interruption requires that MPSolver::InterruptSolve is supported for the
    // underlying solver. Interrupting requests using SCIP is also not supported
    // as of 2021/08/23, since InterruptSolve is not thread safe for SCIP.
    return solver == MPModelRequest::GLOP_LINEAR_PROGRAMMING ||
           solver == MPModelRequest::GUROBI_LINEAR_PROGRAMMING ||
           solver == MPModelRequest::GUROBI_MIXED_INTEGER_PROGRAMMING ||
           solver == MPModelRequest::SAT_INTEGER_PROGRAMMING ||
           solver == MPModelRequest::PDLP_LINEAR_PROGRAMMING;
  }
 
  void ExportModelToProto(MPModelProto* output_model) const;
 
  absl::Status LoadSolutionFromProto(
      const MPSolutionResponse& response,
      double tolerance = std::numeric_limits<double>::infinity());
 
  absl::Status ClampSolutionWithinBounds();
 
  bool ExportModelAsLpFormat(bool obfuscate, std::string* model_str) const;
  bool ExportModelAsMpsFormat(bool fixed_format, bool obfuscate,
                              std::string* model_str) const;
 
  absl::Status SetNumThreads(int num_threads);
 
  int GetNumThreads() const { return num_threads_; }
 
  bool SetSolverSpecificParametersAsString(const std::string& parameters);
  std::string GetSolverSpecificParametersAsString() const {
    return solver_specific_parameter_string_;
  }
 
  void SetHint(std::vector<std::pair<const MPVariable*, double> > hint);
 
  // Gives some brief (a few lines, at most) human-readable information about
  // the given request, suitable for debug logging.
  ABSL_DEPRECATED("Prefer MPModelRequestLoggingInfo() from solve_mp_model.h.")
  static std::string GetMPModelRequestLoggingInfo(
      const MPModelRequest& request);
 
  enum BasisStatus {
    FREE = 0,
    AT_LOWER_BOUND,
    AT_UPPER_BOUND,
    FIXED_VALUE,
    BASIC
  };
 
  void SetStartingLpBasis(
      const std::vector<MPSolver::BasisStatus>& variable_statuses,
      const std::vector<MPSolver::BasisStatus>& constraint_statuses);
 
  static double infinity() { return std::numeric_limits<double>::infinity(); }
  double solver_infinity();
 
  bool OutputIsEnabled() const;
 
  void EnableOutput();
 
  void SuppressOutput();
 
  absl::Duration TimeLimit() const { return time_limit_; }
  void SetTimeLimit(absl::Duration time_limit) {
    DCHECK_GE(time_limit, absl::ZeroDuration());
    time_limit_ = time_limit;
  }
 
  absl::Duration DurationSinceConstruction() const {
    return absl::Now() - construction_time_;
  }
 
  int64_t iterations() const;
 
  int64_t nodes() const;
 
  std::string SolverVersion() const;
 
  void* underlying_solver();
 
  double ComputeExactConditionNumber() const;
 
  ABSL_MUST_USE_RESULT bool NextSolution();
 
  // Does not take ownership of "mp_callback".
  //
  // As of 2019-10-22, only SCIP and Gurobi support Callbacks.
  // SCIP does not support suggesting a heuristic solution in the callback.
  void SetCallback(MPCallback* mp_callback);
  bool SupportsCallbacks() const;
 
  // Global counters of variables and constraints ever created across all
  // MPSolver instances. Those are only updated after the destruction
  // (or Clear()) of each MPSolver instance.
  static int64_t global_num_variables();
  static int64_t global_num_constraints();
 
  // DEPRECATED: Use TimeLimit() and SetTimeLimit(absl::Duration) instead.
  // NOTE: These deprecated functions used the convention time_limit = 0 to mean
  // "no limit", which now corresponds to time_limit_ = InfiniteDuration().
  int64_t time_limit() const {
    return time_limit_ == absl::InfiniteDuration()
               ? 0
               : absl::ToInt64Milliseconds(time_limit_);
  }
  void set_time_limit(int64_t time_limit_milliseconds) {
    SetTimeLimit(time_limit_milliseconds == 0
                     ? absl::InfiniteDuration()
                     : absl::Milliseconds(time_limit_milliseconds));
  }
  double time_limit_in_secs() const {
    return static_cast<double>(time_limit()) / 1000.0;
  }
 
  // DEPRECATED: Use DurationSinceConstruction() instead.
  int64_t wall_time() const {
    return absl::ToInt64Milliseconds(DurationSinceConstruction());
  }
 
  friend class GLPKInterface;
  friend class CLPInterface;
  friend class CBCInterface;
  friend class SCIPInterface;
  friend class GurobiInterface;
  friend class CplexInterface;
  friend class XpressInterface;
  friend class SLMInterface;
  friend class MPSolverInterface;
  friend class GLOPInterface;
  friend class BopInterface;
  friend class SatInterface;
  friend class PdlpInterface;
  friend class HighsInterface;
  friend class KnapsackInterface;
 
  // Debugging: verify that the given MPVariable* belongs to this solver.
  bool OwnsVariable(const MPVariable* var) const;
 
 private:
  // Computes the size of the constraint with the largest number of
  // coefficients with index in [min_constraint_index,
  // max_constraint_index)
  int ComputeMaxConstraintSize(int min_constraint_index,
                               int max_constraint_index) const;
 
  // Returns true if the model has constraints with lower bound > upper bound.
  bool HasInfeasibleConstraints() const;
 
  // Returns true if the model has at least 1 integer variable.
  bool HasIntegerVariables() const;
 
  // Generates the map from variable names to their indices.
  void GenerateVariableNameIndex() const;
 
  // Generates the map from constraint names to their indices.
  void GenerateConstraintNameIndex() const;
 
  // The name of the linear programming problem.
  const std::string name_;
 
  // The type of the linear programming problem.
  const OptimizationProblemType problem_type_;
 
  // The solver interface.
  std::unique_ptr<MPSolverInterface> interface_;
 
  // The vector of variables in the problem.
  std::vector<MPVariable*> variables_;
  // A map from a variable's name to its index in variables_.
  mutable std::optional<absl::flat_hash_map<std::string, int> >
      variable_name_to_index_;
  // Whether variables have been extracted to the underlying interface.
  std::vector<bool> variable_is_extracted_;
 
  // The vector of constraints in the problem.
  std::vector<MPConstraint*> constraints_;
  // A map from a constraint's name to its index in constraints_.
  mutable std::optional<absl::flat_hash_map<std::string, int> >
      constraint_name_to_index_;
  // Whether constraints have been extracted to the underlying interface.
  std::vector<bool> constraint_is_extracted_;
 
  // The linear objective function.
  std::unique_ptr<MPObjective> objective_;
 
  // Initial values for all or some of the problem variables that can be
  // exploited as a starting hint by a solver.
  //
  // Note(user): as of 05/05/2015, we can't use >> because of some SWIG errors.
  //
  // TODO(user): replace by two vectors, a std::vector<bool> to indicate if a
  // hint is provided and a std::vector<double> for the hint value.
  std::vector<std::pair<const MPVariable*, double> > solution_hint_;
 
  absl::Duration time_limit_ = absl::InfiniteDuration();  // Default = No limit.
 
  const absl::Time construction_time_;
 
  // Permanent storage for the number of threads.
  int num_threads_ = 1;
 
  // Permanent storage for SetSolverSpecificParametersAsString().
  std::string solver_specific_parameter_string_;
 
  static absl::Mutex global_count_mutex_;
#ifndef SWIG
  static int64_t global_num_variables_ ABSL_GUARDED_BY(global_count_mutex_);
  static int64_t global_num_constraints_ ABSL_GUARDED_BY(global_count_mutex_);
#endif
 
  enum ModelProtoNamesPolicy {
    DEFAULT_CLEAR_NAMES = 0,
    INVALID_MODEL_ON_DUPLICATE_NONEMPTY_NAMES = 1,
    DIE_ON_DUPLICATE_NONEMPTY_NAMES = 2,
  };
  MPSolverResponseStatus LoadModelFromProtoInternal(
      const MPModelProto& input_model, ModelProtoNamesPolicy name_policy,
      bool check_model_validity, std::string* error_message);
};
 
inline bool SolverTypeIsMip(MPSolver::OptimizationProblemType solver_type) {
  return SolverTypeIsMip(static_cast<MPModelRequest::SolverType>(solver_type));
}
 
absl::string_view ToString(
    MPSolver::OptimizationProblemType optimization_problem_type);
 
inline std::ostream& operator<<(
    std::ostream& os,
    MPSolver::OptimizationProblemType optimization_problem_type) {
  return os << ToString(optimization_problem_type);
}
 
inline std::ostream& operator<<(std::ostream& os,
                                MPSolver::ResultStatus status) {
  return os << ProtoEnumToString<MPSolverResponseStatus>(
             static_cast<MPSolverResponseStatus>(status));
}
 
bool AbslParseFlag(absl::string_view text,
                   MPSolver::OptimizationProblemType* solver_type,
                   std::string* error);
 
inline std::string AbslUnparseFlag(
    MPSolver::OptimizationProblemType solver_type) {
  return std::string(ToString(solver_type));
}
 
class MPObjective {
 public:
#ifndef SWIG
  // This type is neither copyable nor movable.
  MPObjective(const MPObjective&) = delete;
  MPObjective& operator=(const MPObjective&) = delete;
#endif
 
  void Clear();
 
  void SetCoefficient(const MPVariable* var, double coeff);
 
  double GetCoefficient(const MPVariable* var) const;
 
  const absl::flat_hash_map<const MPVariable*, double>& terms() const {
    return coefficients_;
  }
 
  void SetOffset(double value);
 
  double offset() const { return offset_; }
 
  void OptimizeLinearExpr(const LinearExpr& linear_expr, bool is_maximization);
 
  void MaximizeLinearExpr(const LinearExpr& linear_expr) {
    OptimizeLinearExpr(linear_expr, true);
  }
  void MinimizeLinearExpr(const LinearExpr& linear_expr) {
    OptimizeLinearExpr(linear_expr, false);
  }
 
  void AddLinearExpr(const LinearExpr& linear_expr);
 
  void SetOptimizationDirection(bool maximize);
 
  void SetMinimization() { SetOptimizationDirection(false); }
 
  void SetMaximization() { SetOptimizationDirection(true); }
 
  bool maximization() const;
 
  bool minimization() const;
 
  double Value() const;
 
  double BestBound() const;
 
 private:
  friend class MPSolver;
  friend class MPSolverInterface;
  friend class CBCInterface;
  friend class CLPInterface;
  friend class GLPKInterface;
  friend class SCIPInterface;
  friend class SLMInterface;
  friend class GurobiInterface;
  friend class CplexInterface;
  friend class XpressInterface;
  friend class GLOPInterface;
  friend class BopInterface;
  friend class SatInterface;
  friend class PdlpInterface;
  friend class HighsInterface;
  friend class KnapsackInterface;
 
  // Constructor. An objective points to a single MPSolverInterface
  // that is specified in the constructor. An objective cannot belong
  // to several models.
  // At construction, an MPObjective has no terms (which is equivalent
  // on having a coefficient of 0 for all variables), and an offset of 0.
  explicit MPObjective(MPSolverInterface* const interface_in)
      : interface_(interface_in), coefficients_(1), offset_(0.0) {}
 
  MPSolverInterface* const interface_;
 
  // Mapping var -> coefficient.
  absl::flat_hash_map<const MPVariable*, double> coefficients_;
  // Constant term.
  double offset_;
};
 
class MPVariable {
 public:
#ifndef SWIG
  // This type is neither copyable nor movable.
  MPVariable(const MPVariable&) = delete;
  MPVariable& operator=(const MPVariable&) = delete;
#endif
 
  const std::string& name() const { return name_; }
 
  void SetInteger(bool integer);
 
  bool integer() const { return integer_; }
 
  double solution_value() const;
 
  int index() const { return index_; }
 
  double lb() const { return lb_; }
 
  double ub() const { return ub_; }
 
  void SetLB(double lb) { SetBounds(lb, ub_); }
 
  void SetUB(double ub) { SetBounds(lb_, ub); }
 
  void SetBounds(double lb, double ub);
 
  double unrounded_solution_value() const;
 
  double reduced_cost() const;
 
  MPSolver::BasisStatus basis_status() const;
 
  int branching_priority() const { return branching_priority_; }
  void SetBranchingPriority(int priority);
 
 protected:
  friend class MPSolver;
  friend class MPSolverInterface;
  friend class CBCInterface;
  friend class CLPInterface;
  friend class GLPKInterface;
  friend class SCIPInterface;
  friend class SLMInterface;
  friend class GurobiInterface;
  friend class CplexInterface;
  friend class XpressInterface;
  friend class GLOPInterface;
  friend class MPVariableSolutionValueTest;
  friend class BopInterface;
  friend class SatInterface;
  friend class PdlpInterface;
  friend class HighsInterface;
  friend class KnapsackInterface;
 
  // Constructor. A variable points to a single MPSolverInterface that
  // is specified in the constructor. A variable cannot belong to
  // several models.
  MPVariable(int index, double lb, double ub, bool integer,
             const std::string& name, MPSolverInterface* const interface_in)
      : index_(index),
        lb_(lb),
        ub_(ub),
        integer_(integer),
        name_(name.empty() ? absl::StrFormat("auto_v_%09d", index) : name),
        solution_value_(0.0),
        reduced_cost_(0.0),
        interface_(interface_in) {}
 
  void set_solution_value(double value) { solution_value_ = value; }
  void set_reduced_cost(double reduced_cost) { reduced_cost_ = reduced_cost; }
 
 private:
  const int index_;
  double lb_;
  double ub_;
  bool integer_;
  const std::string name_;
  double solution_value_;
  double reduced_cost_;
  int branching_priority_ = 0;
  MPSolverInterface* const interface_;
};
 
class MPConstraint {
 public:
#ifndef SWIG
  // This type is neither copyable nor movable.
  MPConstraint(const MPConstraint&) = delete;
  MPConstraint& operator=(const MPConstraint&) = delete;
#endif
 
  const std::string& name() const { return name_; }
 
  void Clear();
 
  void SetCoefficient(const MPVariable* var, double coeff);
 
  double GetCoefficient(const MPVariable* var) const;
 
  const absl::flat_hash_map<const MPVariable*, double>& terms() const {
    return coefficients_;
  }
 
  double lb() const { return lb_; }
 
  double ub() const { return ub_; }
 
  void SetLB(double lb) { SetBounds(lb, ub_); }
 
  void SetUB(double ub) { SetBounds(lb_, ub); }
 
  void SetBounds(double lb, double ub);
 
  bool is_lazy() const { return is_lazy_; }
 
  void set_is_lazy(bool laziness) { is_lazy_ = laziness; }
 
  const MPVariable* indicator_variable() const { return indicator_variable_; }
  bool indicator_value() const { return indicator_value_; }
 
  int index() const { return index_; }
 
  double dual_value() const;
 
  MPSolver::BasisStatus basis_status() const;
 
 protected:
  friend class MPSolver;
  friend class MPSolverInterface;
  friend class CBCInterface;
  friend class CLPInterface;
  friend class GLPKInterface;
  friend class SCIPInterface;
  friend class SLMInterface;
  friend class GurobiInterface;
  friend class CplexInterface;
  friend class XpressInterface;
  friend class GLOPInterface;
  friend class BopInterface;
  friend class SatInterface;
  friend class PdlpInterface;
  friend class HighsInterface;
  friend class KnapsackInterface;
 
  // Constructor. A constraint points to a single MPSolverInterface
  // that is specified in the constructor. A constraint cannot belong
  // to several models.
  MPConstraint(int index, double lb, double ub, const std::string& name,
               MPSolverInterface* const interface_in)
      : coefficients_(1),
        index_(index),
        lb_(lb),
        ub_(ub),
        name_(name.empty() ? absl::StrFormat("auto_c_%09d", index) : name),
        is_lazy_(false),
        indicator_variable_(nullptr),
        dual_value_(0.0),
        interface_(interface_in) {}
 
  void set_dual_value(double dual_value) { dual_value_ = dual_value; }
 
 private:
  // Returns true if the constraint contains variables that have not
  // been extracted yet.
  bool ContainsNewVariables();
 
  // Mapping var -> coefficient.
  absl::flat_hash_map<const MPVariable*, double> coefficients_;
 
  const int index_;  // See index().
 
  // The lower bound for the linear constraint.
  double lb_;
 
  // The upper bound for the linear constraint.
  double ub_;
 
  // Name.
  const std::string name_;
 
  // True if the constraint is "lazy", i.e. the constraint is added to the
  // underlying Linear Programming solver only if it is violated.
  // By default this parameter is 'false'.
  bool is_lazy_;
 
  // If given, this constraint is only active if `indicator_variable_`'s value
  // is equal to `indicator_value_`.
  const MPVariable* indicator_variable_;
  bool indicator_value_;
 
  double dual_value_;
  MPSolverInterface* const interface_;
};
 
class MPSolverParameters {
 public:
  enum DoubleParam {
    RELATIVE_MIP_GAP = 0,
 
    PRIMAL_TOLERANCE = 1,
    DUAL_TOLERANCE = 2
  };
 
  enum IntegerParam {
    PRESOLVE = 1000,
    LP_ALGORITHM = 1001,
    INCREMENTALITY = 1002,
    SCALING = 1003
  };
 
  enum PresolveValues {
    PRESOLVE_OFF = 0,
    PRESOLVE_ON = 1
  };
 
  enum LpAlgorithmValues {
    DUAL = 10,
    PRIMAL = 11,
    BARRIER = 12
  };
 
  enum IncrementalityValues {
    INCREMENTALITY_OFF = 0,
 
    INCREMENTALITY_ON = 1
  };
 
  enum ScalingValues {
    SCALING_OFF = 0,
    SCALING_ON = 1
  };
 
  // Placeholder value to indicate that a parameter is set to
  // the default value defined in the wrapper.
  static const double kDefaultDoubleParamValue;
  static const int kDefaultIntegerParamValue;
 
  // Placeholder value to indicate that a parameter is unknown.
  static const double kUnknownDoubleParamValue;
  static const int kUnknownIntegerParamValue;
 
  // Default values for parameters. Only parameters that define the
  // properties of the solution returned need to have a default value
  // (that is the same for all solvers). You can also define a default
  // value for performance parameters when you are confident it is a
  // good choice (example: always turn presolve on).
  static const double kDefaultRelativeMipGap;
  static const double kDefaultPrimalTolerance;
  static const double kDefaultDualTolerance;
  static const PresolveValues kDefaultPresolve;
  static const IncrementalityValues kDefaultIncrementality;
 
  MPSolverParameters();
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  MPSolverParameters(const MPSolverParameters&) = delete;
  MPSolverParameters& operator=(const MPSolverParameters&) = delete;
#endif
 
  void SetDoubleParam(MPSolverParameters::DoubleParam param, double value);
 
  void SetIntegerParam(MPSolverParameters::IntegerParam param, int value);
 
  void ResetDoubleParam(MPSolverParameters::DoubleParam param);
 
  void ResetIntegerParam(MPSolverParameters::IntegerParam param);
 
  void Reset();
 
  double GetDoubleParam(MPSolverParameters::DoubleParam param) const;
 
  int GetIntegerParam(MPSolverParameters::IntegerParam param) const;
 
 private:
  // Parameter value for each parameter.
  // @see DoubleParam
  // @see IntegerParam
  double relative_mip_gap_value_;
  double primal_tolerance_value_;
  double dual_tolerance_value_;
  int presolve_value_;
  int scaling_value_;
  int lp_algorithm_value_;
  int incrementality_value_;
 
  // Boolean value indicating whether each parameter is set to the
  // solver's default value. Only parameters for which the wrapper
  // does not define a default value need such an indicator.
  bool lp_algorithm_is_default_;
};
 
// Whether the given MPSolverResponseStatus (of a solve) would yield an RPC
// error when happening on the linear solver stubby server, see
// ./linear_solver_service.proto.
// Note that RPC errors forbid to carry a response to the client, who can only
// see the RPC error itself (error code + error message).
bool MPSolverResponseStatusIsRpcError(MPSolverResponseStatus status);
 
// This class wraps the actual mathematical programming solvers. Each
// solver (GLOP, CLP, CBC, GLPK, SCIP) has its own interface class that
// derives from this abstract class. This class is never directly
// accessed by the user.
// @see glop_interface.cc
// @see cbc_interface.cc
// @see clp_interface.cc
// @see glpk_interface.cc
// @see scip_interface.cc
class MPSolverInterface {
 public:
  enum SynchronizationStatus {
    // The underlying solver (CLP, GLPK, ...) and MPSolver are not in
    // sync for the model nor for the solution.
    MUST_RELOAD,
    // The underlying solver and MPSolver are in sync for the model
    // but not for the solution: the model has changed since the
    // solution was computed last.
    MODEL_SYNCHRONIZED,
    // The underlying solver and MPSolver are in sync for the model and
    // the solution.
    SOLUTION_SYNCHRONIZED
  };
 
  // When the underlying solver does not provide the number of simplex
  // iterations.
  static constexpr int64_t kUnknownNumberOfIterations = -1;
  // When the underlying solver does not provide the number of
  // branch-and-bound nodes.
  static constexpr int64_t kUnknownNumberOfNodes = -1;
 
  // Constructor. The user will access the MPSolverInterface through the
  // MPSolver passed as argument.
  explicit MPSolverInterface(MPSolver* solver);
  virtual ~MPSolverInterface();
 
  // ----- Solve -----
  // Solves problem with specified parameter values. Returns true if the
  // solution is optimal.
  virtual MPSolver::ResultStatus Solve(const MPSolverParameters& param) = 0;
 
  // DirectlySolveProto() shall only be used if SupportsDirectlySolveProto() is
  // true.
  //
  // DirectlySolveProto() solves a MPModelRequest, bypassing the MPSolver data
  // structures entirely. Like MPSolver::SolveWithProto(), optionally takes in
  // an 'interrupt' boolean.
  virtual bool SupportsDirectlySolveProto(
      std::atomic<bool>* /*interrupt*/) const {
    return false;
  }
  virtual MPSolutionResponse DirectlySolveProto(
      LazyMutableCopy<MPModelRequest> /*request*/,
      // `interrupt` is non-const because the internal
      // solver may set it to true itself, in some cases.
      std::atomic<bool>* /*interrupt*/) {
    LOG(DFATAL) << "Default implementation should never be called.";
    return MPSolutionResponse();
  }
 
  // Writes the model using the solver internal write function.  Currently only
  // available for GurobiInterface and XpressInterface.
  virtual void Write(const std::string& filename);
 
  // ----- Model modifications and extraction -----
  // Resets extracted model.
  virtual void Reset() = 0;
 
  // Sets the optimization direction (min/max).
  virtual void SetOptimizationDirection(bool maximize) = 0;
 
  // Modifies bounds of an extracted variable.
  virtual void SetVariableBounds(int index, double lb, double ub) = 0;
 
  // Modifies integrality of an extracted variable.
  virtual void SetVariableInteger(int index, bool integer) = 0;
 
  // Modify bounds of an extracted variable.
  virtual void SetConstraintBounds(int index, double lb, double ub) = 0;
 
  // Adds a linear constraint.
  virtual void AddRowConstraint(MPConstraint* ct) = 0;
 
  // Adds an indicator constraint. Returns true if the feature is supported by
  // the underlying solver.
  virtual bool AddIndicatorConstraint(MPConstraint* const /*ct*/) {
    LOG(ERROR) << "Solver doesn't support indicator constraints.";
    return false;
  }
 
  // Add a variable.
  virtual void AddVariable(MPVariable* var) = 0;
 
  // Changes a coefficient in a constraint.
  virtual void SetCoefficient(MPConstraint* constraint,
                              const MPVariable* variable, double new_value,
                              double old_value) = 0;
 
  // Clears a constraint from all its terms.
  virtual void ClearConstraint(MPConstraint* constraint) = 0;
 
  // Changes a coefficient in the linear objective.
  virtual void SetObjectiveCoefficient(const MPVariable* variable,
                                       double coefficient) = 0;
 
  // Changes the constant term in the linear objective.
  virtual void SetObjectiveOffset(double value) = 0;
 
  // Clears the objective from all its terms.
  virtual void ClearObjective() = 0;
 
  virtual void BranchingPriorityChangedForVariable(int /*var_index*/) {}
  // ------ Query statistics on the solution and the solve ------
  // Returns the number of simplex iterations. The problem must be discrete,
  // otherwise it crashes, or returns kUnknownNumberOfIterations in NDEBUG mode.
  virtual int64_t iterations() const = 0;
  // Returns the number of branch-and-bound nodes. The problem must be discrete,
  // otherwise it crashes, or returns kUnknownNumberOfNodes in NDEBUG mode.
  virtual int64_t nodes() const = 0;
  // Returns the best objective bound. The problem must be discrete, otherwise
  // it crashes, or returns trivial bound (+/- inf) in NDEBUG mode.
  double best_objective_bound() const;
  // Returns the objective value of the best solution found so far.
  double objective_value() const;
 
  // Returns the basis status of a row.
  virtual MPSolver::BasisStatus row_status(int constraint_index) const = 0;
  // Returns the basis status of a constraint.
  virtual MPSolver::BasisStatus column_status(int variable_index) const = 0;
 
  // Checks whether the solution is synchronized with the model, i.e. whether
  // the model has changed since the solution was computed last.
  // If it isn't, it crashes in NDEBUG, and returns false otherwise.
  bool CheckSolutionIsSynchronized() const;
  // Checks whether a feasible solution exists. The behavior is similar to
  // CheckSolutionIsSynchronized() above.
  virtual bool CheckSolutionExists() const;
  // Handy shortcut to do both checks above (it is often used).
  bool CheckSolutionIsSynchronizedAndExists() const {
    return CheckSolutionIsSynchronized() && CheckSolutionExists();
  }
 
  // ----- Misc -----
  // Queries problem type. For simplicity, the distinction between
  // continuous and discrete is based on the declaration of the user
  // when the solver is created (example: GLPK_LINEAR_PROGRAMMING
  // vs. GLPK_MIXED_INTEGER_PROGRAMMING), not on the actual content of
  // the model.
  // Returns true if the problem is continuous.
  virtual bool IsContinuous() const = 0;
  // Returns true if the problem is continuous and linear.
  virtual bool IsLP() const = 0;
  // Returns true if the problem is discrete and linear.
  virtual bool IsMIP() const = 0;
 
  // Returns the index of the last variable extracted.
  int last_variable_index() const { return last_variable_index_; }
 
  bool variable_is_extracted(int var_index) const {
    return solver_->variable_is_extracted_[var_index];
  }
  void set_variable_as_extracted(int var_index, bool extracted) {
    solver_->variable_is_extracted_[var_index] = extracted;
  }
  bool constraint_is_extracted(int ct_index) const {
    return solver_->constraint_is_extracted_[ct_index];
  }
  void set_constraint_as_extracted(int ct_index, bool extracted) {
    solver_->constraint_is_extracted_[ct_index] = extracted;
  }
 
  // Returns the boolean indicating the verbosity of the solver output.
  bool quiet() const { return quiet_; }
  // Sets the boolean indicating the verbosity of the solver output.
  void set_quiet(bool quiet_value) { quiet_ = quiet_value; }
 
  // Returns the result status of the last solve.
  MPSolver::ResultStatus result_status() const {
    CheckSolutionIsSynchronized();
    return result_status_;
  }
 
  // Returns a string describing the underlying solver and its version.
  virtual std::string SolverVersion() const = 0;
 
  // Returns the underlying solver.
  virtual void* underlying_solver() = 0;
 
  // Computes exact condition number. Only available for continuous
  // problems and only implemented in GLPK.
  virtual double ComputeExactConditionNumber() const;
 
  // See MPSolver::SetStartingLpBasis().
  virtual void SetStartingLpBasis(
      const std::vector<MPSolver::BasisStatus>& /*variable_statuses*/,
      const std::vector<MPSolver::BasisStatus>& /*constraint_statuses*/) {
    LOG(FATAL) << "Not supported by this solver.";
  }
 
  virtual double infinity() { return std::numeric_limits<double>::infinity(); }
 
  virtual bool InterruptSolve() { return false; }
 
  // See MPSolver::NextSolution() for contract.
  virtual bool NextSolution() { return false; }
 
  // See MPSolver::SetCallback() for details.
  virtual void SetCallback(MPCallback* /*mp_callback*/) {
    LOG(FATAL) << "Callbacks not supported for this solver.";
  }
 
  virtual bool SupportsCallbacks() const { return false; }
 
  friend class MPSolver;
 
  // To access the maximize_ bool and the MPSolver.
  friend class MPConstraint;
  friend class MPObjective;
 
 protected:
  MPSolver* const solver_;
  // Indicates whether the model and the solution are synchronized.
  SynchronizationStatus sync_status_;
  // Indicates whether the solve has reached optimality,
  // infeasibility, a limit, etc.
  MPSolver::ResultStatus result_status_;
  // Optimization direction.
  bool maximize_;
 
  // Index in MPSolver::variables_ of last constraint extracted.
  int last_constraint_index_;
  // Index in MPSolver::constraints_ of last variable extracted.
  int last_variable_index_;
 
  // The value of the objective function.
  double objective_value_;
 
  // The value of the best objective bound. Used only for MIP solvers.
  double best_objective_bound_;
 
  // Boolean indicator for the verbosity of the solver output.
  bool quiet_;
 
  // Index of dummy variable created for empty constraints or the
  // objective offset.
  static const int kDummyVariableIndex;
 
  // Extracts model stored in MPSolver.
  void ExtractModel();
  // Extracts the variables that have not been extracted yet.
  virtual void ExtractNewVariables() = 0;
  // Extracts the constraints that have not been extracted yet.
  virtual void ExtractNewConstraints() = 0;
  // Extracts the objective.
  virtual void ExtractObjective() = 0;
  // Resets the extraction information.
  void ResetExtractionInformation();
  // Change synchronization status from SOLUTION_SYNCHRONIZED to
  // MODEL_SYNCHRONIZED. To be used for model changes.
  void InvalidateSolutionSynchronization();
 
  // Sets parameters common to LP and MIP in the underlying solver.
  void SetCommonParameters(const MPSolverParameters& param);
  // Sets MIP specific parameters in the underlying solver.
  void SetMIPParameters(const MPSolverParameters& param);
  // Sets all parameters in the underlying solver.
  virtual void SetParameters(const MPSolverParameters& param) = 0;
  // Sets an unsupported double parameter.
  void SetUnsupportedDoubleParam(MPSolverParameters::DoubleParam param);
  // Sets an unsupported integer parameter.
  virtual void SetUnsupportedIntegerParam(
      MPSolverParameters::IntegerParam param);
  // Sets a supported double parameter to an unsupported value.
  void SetDoubleParamToUnsupportedValue(MPSolverParameters::DoubleParam param,
                                        double value);
  // Sets a supported integer parameter to an unsupported value.
  virtual void SetIntegerParamToUnsupportedValue(
      MPSolverParameters::IntegerParam param, int value);
  // Sets each parameter in the underlying solver.
  virtual void SetRelativeMipGap(double value) = 0;
  virtual void SetPrimalTolerance(double value) = 0;
  virtual void SetDualTolerance(double value) = 0;
  virtual void SetPresolveMode(int value) = 0;
 
  // Sets the number of threads to be used by the solver.
  virtual absl::Status SetNumThreads(int num_threads);
 
  // Pass solver specific parameters in text format. The format is
  // solver-specific and is the same as the corresponding solver configuration
  // file format. Returns true if the operation was successful.
  //
  // Default implementation returns true if the input is empty. It returns false
  // and logs a WARNING if the input is not empty.
  virtual bool SetSolverSpecificParametersAsString(
      const std::string& parameters);
 
  // Sets the scaling mode.
  virtual void SetScalingMode(int value) = 0;
  virtual void SetLpAlgorithm(int value) = 0;
};
 
}  // namespace operations_research
 
#endif  // OR_TOOLS_LINEAR_SOLVER_LINEAR_SOLVER_H_