cp_model.h

Go to the documentation of this file.

// Copyright 2010-2025 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_SAT_CP_MODEL_H_
#define OR_TOOLS_SAT_CP_MODEL_H_
 
#include <cstdint>
#include <initializer_list>
#include <iosfwd>
#include <limits>
#include <ostream>
#include <string>
#include <utility>
#include <vector>
 
#include "absl/container/flat_hash_map.h"
#include "absl/strings/string_view.h"
#include "absl/types/span.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"  // IWYU pragma: export.
#include "ortools/sat/cp_model_utils.h"
#include "ortools/sat/model.h"  // IWYU pragma: export.
#include "ortools/sat/sat_parameters.pb.h"
#include "ortools/util/sorted_interval_list.h"
 
namespace operations_research {
namespace sat {
 
class CpModelBuilder;
class IntVar;
class LinearExpr;

class BoolVar {
 public:
  BoolVar() = default;

  BoolVar WithName(absl::string_view name);

  std::string Name() const;

  BoolVar Not() const { return BoolVar(NegatedRef(index_), builder_); }
 
  bool operator==(const BoolVar& other) const {
    return other.builder_ == builder_ && other.index_ == index_;
  }
 
  bool operator!=(const BoolVar& other) const {
    return other.builder_ != builder_ || other.index_ != index_;
  }
 
  BoolVar operator~() const { return Not(); }
 
  std::string DebugString() const;

  int index() const { return index_; }
 
 private:
  friend class CircuitConstraint;
  friend class Constraint;
  friend class CpModelBuilder;
  friend class DoubleLinearExpr;
  friend class IntVar;
  friend class IntervalVar;
  friend class MultipleCircuitConstraint;
  friend class LinearExpr;
  friend class ReservoirConstraint;
  friend bool SolutionBooleanValue(const CpSolverResponse& r, BoolVar x);
 
  BoolVar(int index, CpModelBuilder* builder);
 
  CpModelBuilder* builder_ = nullptr;
  int index_ = std::numeric_limits<int32_t>::min();
};
 
std::ostream& operator<<(std::ostream& os, const BoolVar& var);

BoolVar Not(BoolVar x);

class IntVar {
 public:
  IntVar() = default;

  explicit IntVar(const BoolVar& var);

  BoolVar ToBoolVar() const;

  IntVar WithName(absl::string_view name);

  std::string Name() const;
 
  bool operator==(const IntVar& other) const {
    return other.builder_ == builder_ && other.index_ == index_;
  }
 
  bool operator!=(const IntVar& other) const {
    return other.builder_ != builder_ || other.index_ != index_;
  }
 
  // Returns the domain of the variable.
  // Note that we keep the fully qualified return type as compilation fails with
  // gcc otherwise.
  ::operations_research::Domain Domain() const;
 
  std::string DebugString() const;

  int index() const { return index_; }
 
 private:
  friend class BoolVar;
  friend class CpModelBuilder;
  friend class CumulativeConstraint;
  friend class DoubleLinearExpr;
  friend class LinearExpr;
  friend class IntervalVar;
  friend class ReservoirConstraint;
  friend int64_t SolutionIntegerValue(const CpSolverResponse& r,
                                      const LinearExpr& expr);
 
  IntVar(int index, CpModelBuilder* builder);
 
  CpModelBuilder* builder_ = nullptr;
  int index_ = std::numeric_limits<int32_t>::min();
};
 
std::ostream& operator<<(std::ostream& os, const IntVar& var);

class LinearExpr {
 public:
  /// Creates an empty linear expression with value zero.
  LinearExpr() = default;
 
  // NOLINTBEGIN(google-explicit-constructor)

  LinearExpr(BoolVar var);

  LinearExpr(IntVar var);

  LinearExpr(int64_t constant);
 
  // NOLINTEND(google-explicit-constructor)

  static LinearExpr Sum(absl::Span<const IntVar> vars);

  static LinearExpr Sum(absl::Span<const BoolVar> vars);

  static LinearExpr WeightedSum(absl::Span<const IntVar> vars,
                                absl::Span<const int64_t> coeffs);

  static LinearExpr WeightedSum(absl::Span<const BoolVar> vars,
                                absl::Span<const int64_t> coeffs);

  static LinearExpr Term(IntVar var, int64_t coefficient);

  static LinearExpr Term(BoolVar var, int64_t coefficient);

  static LinearExpr FromProto(const LinearExpressionProto& proto);
 
  // Operators.
  LinearExpr& operator+=(const LinearExpr& other);
  LinearExpr& operator-=(const LinearExpr& other);
  LinearExpr& operator*=(int64_t factor);

  const std::vector<int>& variables() const { return variables_; }

  const std::vector<int64_t>& coefficients() const { return coefficients_; }

  bool IsConstant() const { return variables_.empty(); }

  int64_t constant() const { return constant_; }

  std::string DebugString(const CpModelProto* proto = nullptr) const;
 
 private:
  std::vector<int> variables_;
  std::vector<int64_t> coefficients_;
  int64_t constant_ = 0;
};
 
std::ostream& operator<<(std::ostream& os, const LinearExpr& e);

class DoubleLinearExpr {
 public:
  DoubleLinearExpr();

  explicit DoubleLinearExpr(BoolVar var);

  explicit DoubleLinearExpr(IntVar var);

  explicit DoubleLinearExpr(double constant);

  DoubleLinearExpr& operator+=(double value);

  DoubleLinearExpr& operator+=(IntVar var);
  DoubleLinearExpr& operator+=(BoolVar var);

  DoubleLinearExpr& operator+=(const DoubleLinearExpr& expr);

  DoubleLinearExpr& AddTerm(IntVar var, double coeff);
  DoubleLinearExpr& AddTerm(BoolVar var, double coeff);

  DoubleLinearExpr& AddExpression(const LinearExpr& exprs, double coeff = 1.0);

  DoubleLinearExpr& operator-=(double value);

  DoubleLinearExpr& operator-=(IntVar var);

  DoubleLinearExpr& operator-=(const DoubleLinearExpr& expr);

  DoubleLinearExpr& operator*=(double coeff);

  static DoubleLinearExpr Sum(absl::Span<const IntVar> vars);

  static DoubleLinearExpr Sum(absl::Span<const BoolVar> vars);

  static DoubleLinearExpr WeightedSum(absl::Span<const IntVar> vars,
                                      absl::Span<const double> coeffs);

  static DoubleLinearExpr WeightedSum(absl::Span<const BoolVar> vars,
                                      absl::Span<const double> coeffs);

  const std::vector<int>& variables() const { return variables_; }

  const std::vector<double>& coefficients() const { return coefficients_; }
 
  // Returns true if the expression has no variable.
  bool IsConstant() const { return variables_.empty(); }

  double constant() const { return constant_; }

  std::string DebugString(const CpModelProto* proto = nullptr) const;
 
 private:
  std::vector<int> variables_;
  std::vector<double> coefficients_;
  double constant_ = 0;
};
 
std::ostream& operator<<(std::ostream& os, const DoubleLinearExpr& e);

class IntervalVar {
 public:
  /// A default constructed IntervalVar can be used to mean not defined yet.
  /// However, it shouldn't be passed to any of the functions in this file.
  /// Doing so will crash in debug mode and will result in an invalid model in
  /// opt mode.
  IntervalVar();

  IntervalVar WithName(absl::string_view name);

  std::string Name() const;

  LinearExpr StartExpr() const;

  LinearExpr SizeExpr() const;

  LinearExpr EndExpr() const;

  BoolVar PresenceBoolVar() const;

  bool operator==(const IntervalVar& other) const {
    return other.builder_ == builder_ && other.index_ == index_;
  }

  bool operator!=(const IntervalVar& other) const {
    return other.builder_ != builder_ || other.index_ != index_;
  }

  std::string DebugString() const;

  int index() const { return index_; }
 
 private:
  friend class CpModelBuilder;
  friend class CumulativeConstraint;
  friend class NoOverlap2DConstraint;
  friend std::ostream& operator<<(std::ostream& os, const IntervalVar& var);
 
  IntervalVar(int index, CpModelBuilder* builder);
 
  CpModelBuilder* builder_ = nullptr;
  int index_ = std::numeric_limits<int32_t>::min();
};
 
std::ostream& operator<<(std::ostream& os, const IntervalVar& var);
 
// -- ABSL HASHING SUPPORT -----------------------------------------------------
template <typename H>
H AbslHashValue(H h, const IntVar& i) {
  return H::combine(std::move(h), i.index());
}
 
template <typename H>
H AbslHashValue(H h, const IntervalVar& i) {
  return H::combine(std::move(h), i.index());
}


class Constraint {
 public:
  /**
   * The constraint will be enforced iff all literals listed here are true.
   *
   * If this is empty, then the constraint will always be enforced. An enforced
   * constraint must be satisfied, and an un-enforced one will simply be
   * ignored.
   *
   * This is also called half-reification. To have an equivalence between a
   * literal and a constraint (full reification), one must add both a constraint
   * (controlled by a literal l) and its negation (controlled by the negation of
   * l).
   *
   * [Important] currently, only a few constraints support enforcement:
   * - bool_or, bool_and, linear: fully supported.
   * - interval: only support a single enforcement literal.
   * - other: no support (but can be added on a per-demand basis).
   */
  Constraint OnlyEnforceIf(absl::Span<const BoolVar> literals);

  Constraint OnlyEnforceIf(BoolVar literal);

  Constraint WithName(absl::string_view name);

  absl::string_view Name() const;

  const ConstraintProto& Proto() const { return *proto_; }

  ConstraintProto* MutableProto() const { return proto_; }
 
 protected:
  friend class CpModelBuilder;
 
  explicit Constraint(ConstraintProto* proto);
 
  ConstraintProto* proto_ = nullptr;
};


class CircuitConstraint : public Constraint {
 public:
  /**
   * Add an arc to the circuit.
   *
   * @param tail the index of the tail node.
   * @param head the index of the head node.
   * @param literal it will be set to true if the arc is selected.
   */
  void AddArc(int tail, int head, BoolVar literal);
 
 private:
  friend class CpModelBuilder;
 
  using Constraint::Constraint;
};


class MultipleCircuitConstraint : public Constraint {
 public:
  /**
   * Add an arc to the circuit.
   *
   * @param tail the index of the tail node.
   * @param head the index of the head node.
   * @param literal it will be set to true if the arc is selected.
   */
  void AddArc(int tail, int head, BoolVar literal);
 
 private:
  friend class CpModelBuilder;
 
  using Constraint::Constraint;
};


class TableConstraint : public Constraint {
 public:
  /// Adds a tuple of possible values to the constraint.
  void AddTuple(absl::Span<const int64_t> tuple);
 
 private:
  friend class CpModelBuilder;
 
  using Constraint::Constraint;
};


class ReservoirConstraint : public Constraint {
 public:
  /**
   * Adds a mandatory event
   *
   * It will increase the used capacity by `level_change` at time `time`.
   * `time` must be an affine expression.
   */
  void AddEvent(LinearExpr time, int64_t level_change);

  void AddOptionalEvent(LinearExpr time, int64_t level_change,
                        BoolVar is_active);
 
 private:
  friend class CpModelBuilder;
 
  ReservoirConstraint(ConstraintProto* proto, CpModelBuilder* builder);
 
  CpModelBuilder* builder_;
};


class AutomatonConstraint : public Constraint {
 public:
  /// Adds a transitions to the automaton.
  void AddTransition(int tail, int head, int64_t transition_label);
 
 private:
  friend class CpModelBuilder;
 
  using Constraint::Constraint;
};


class NoOverlap2DConstraint : public Constraint {
 public:
  /// Adds a rectangle (parallel to the axis) to the constraint.
  void AddRectangle(IntervalVar x_coordinate, IntervalVar y_coordinate);
 
 private:
  friend class CpModelBuilder;
 
  using Constraint::Constraint;
};


class CumulativeConstraint : public Constraint {
 public:
  /// Adds a pair (interval, demand) to the constraint.
  void AddDemand(IntervalVar interval, LinearExpr demand);
 
 private:
  friend class CpModelBuilder;
 
  CumulativeConstraint(ConstraintProto* proto, CpModelBuilder* builder);
 
  CpModelBuilder* builder_;
};


class CpModelBuilder {
 public:
  /// Sets the name of the model.
  void SetName(absl::string_view name);

  IntVar NewIntVar(const Domain& domain);

  BoolVar NewBoolVar();

  IntVar NewConstant(int64_t value);

  BoolVar TrueVar();

  BoolVar FalseVar();

  IntervalVar NewIntervalVar(const LinearExpr& start, const LinearExpr& size,
                             const LinearExpr& end);

  IntervalVar NewFixedSizeIntervalVar(const LinearExpr& start, int64_t size);

  IntervalVar NewOptionalIntervalVar(const LinearExpr& start,
                                     const LinearExpr& size,
                                     const LinearExpr& end, BoolVar presence);

  IntervalVar NewOptionalFixedSizeIntervalVar(const LinearExpr& start,
                                              int64_t size, BoolVar presence);

  void FixVariable(IntVar var, int64_t value);
  void FixVariable(BoolVar var, bool value);

  Constraint AddBoolOr(absl::Span<const BoolVar> literals);

  Constraint AddAtLeastOne(absl::Span<const BoolVar> literals);

  Constraint AddAtMostOne(absl::Span<const BoolVar> literals);

  Constraint AddExactlyOne(absl::Span<const BoolVar> literals);

  Constraint AddBoolAnd(absl::Span<const BoolVar> literals);

  Constraint AddBoolXor(absl::Span<const BoolVar> literals);

  Constraint AddImplication(BoolVar a, BoolVar b) {
    return AddBoolOr({a.Not(), b});
  }

  Constraint AddImplication(absl::Span<const BoolVar> lhs,
                            absl::Span<const BoolVar> rhs) {
    return AddBoolAnd(rhs).OnlyEnforceIf(lhs);
  }

  Constraint AddEquality(const LinearExpr& left, const LinearExpr& right);

  Constraint AddGreaterOrEqual(const LinearExpr& left, const LinearExpr& right);

  Constraint AddGreaterThan(const LinearExpr& left, const LinearExpr& right);

  Constraint AddLessOrEqual(const LinearExpr& left, const LinearExpr& right);

  Constraint AddLessThan(const LinearExpr& left, const LinearExpr& right);

  Constraint AddLinearConstraint(const LinearExpr& expr, const Domain& domain);

  Constraint AddNotEqual(const LinearExpr& left, const LinearExpr& right);

  Constraint AddAllDifferent(absl::Span<const IntVar> vars);

  Constraint AddAllDifferent(absl::Span<const LinearExpr> exprs);

  Constraint AddAllDifferent(std::initializer_list<LinearExpr> exprs);

  Constraint AddVariableElement(LinearExpr index,
                                absl::Span<const IntVar> variables,
                                LinearExpr target);

  Constraint AddElement(LinearExpr index,
                        absl::Span<const LinearExpr> expressions,
                        LinearExpr target);

  Constraint AddElement(LinearExpr index,
                        std::initializer_list<LinearExpr> expressions,
                        LinearExpr target);

  Constraint AddElement(LinearExpr index, absl::Span<const int64_t> values,
                        LinearExpr target);

  CircuitConstraint AddCircuitConstraint();

  MultipleCircuitConstraint AddMultipleCircuitConstraint();

  TableConstraint AddAllowedAssignments(
      absl::Span<const LinearExpr> expressions);

  TableConstraint AddAllowedAssignments(absl::Span<const IntVar> variables);

  TableConstraint AddAllowedAssignments(
      std::initializer_list<LinearExpr> expressions);

  TableConstraint AddForbiddenAssignments(
      absl::Span<const LinearExpr> expression);

  TableConstraint AddForbiddenAssignments(absl::Span<const IntVar> variables);

  TableConstraint AddForbiddenAssignments(
      std::initializer_list<LinearExpr> expressions);

  Constraint AddInverseConstraint(absl::Span<const IntVar> variables,
                                  absl::Span<const IntVar> inverse_variables);

  ReservoirConstraint AddReservoirConstraint(int64_t min_level,
                                             int64_t max_level);

  AutomatonConstraint AddAutomaton(
      absl::Span<const LinearExpr> transition_expressions, int starting_state,
      absl::Span<const int> final_states);

  AutomatonConstraint AddAutomaton(
      absl::Span<const IntVar> transition_variables, int starting_state,
      absl::Span<const int> final_states);

  AutomatonConstraint AddAutomaton(
      std::initializer_list<LinearExpr> transition_expressions,
      int starting_state, absl::Span<const int> final_states);

  Constraint AddMinEquality(const LinearExpr& target,
                            absl::Span<const IntVar> vars);

  Constraint AddMinEquality(const LinearExpr& target,
                            absl::Span<const LinearExpr> exprs);

  Constraint AddMinEquality(const LinearExpr& target,
                            std::initializer_list<LinearExpr> exprs);

  Constraint AddMaxEquality(const LinearExpr& target,
                            absl::Span<const IntVar> vars);

  Constraint AddMaxEquality(const LinearExpr& target,
                            absl::Span<const LinearExpr> exprs);

  Constraint AddMaxEquality(const LinearExpr& target,
                            std::initializer_list<LinearExpr> exprs);

  Constraint AddDivisionEquality(const LinearExpr& target,
                                 const LinearExpr& numerator,
                                 const LinearExpr& denominator);

  Constraint AddAbsEquality(const LinearExpr& target, const LinearExpr& expr);

  Constraint AddModuloEquality(const LinearExpr& target, const LinearExpr& var,
                               const LinearExpr& mod);

  Constraint AddMultiplicationEquality(const LinearExpr& target,
                                       absl::Span<const LinearExpr> exprs);

  Constraint AddMultiplicationEquality(const LinearExpr& target,
                                       absl::Span<const IntVar> vars);

  Constraint AddMultiplicationEquality(const LinearExpr& target,
                                       std::initializer_list<LinearExpr> exprs);

  Constraint AddMultiplicationEquality(const LinearExpr& target,
                                       const LinearExpr& left,
                                       const LinearExpr& right);

  Constraint AddNoOverlap(absl::Span<const IntervalVar> vars);

  NoOverlap2DConstraint AddNoOverlap2D();

  CumulativeConstraint AddCumulative(LinearExpr capacity);

  void Minimize(const LinearExpr& expr);

  void Minimize(const DoubleLinearExpr& expr);

  void Maximize(const LinearExpr& expr);

  void Maximize(const DoubleLinearExpr& expr);

  void ClearObjective();

  bool HasObjective() const;

  void AddDecisionStrategy(
      absl::Span<const IntVar> variables,
      DecisionStrategyProto::VariableSelectionStrategy var_strategy,
      DecisionStrategyProto::DomainReductionStrategy domain_strategy);

  void AddDecisionStrategy(
      absl::Span<const BoolVar> variables,
      DecisionStrategyProto::VariableSelectionStrategy var_strategy,
      DecisionStrategyProto::DomainReductionStrategy domain_strategy);

  void AddDecisionStrategy(
      absl::Span<const LinearExpr> expressions,
      DecisionStrategyProto::VariableSelectionStrategy var_strategy,
      DecisionStrategyProto::DomainReductionStrategy domain_strategy);

  void AddDecisionStrategy(
      std::initializer_list<LinearExpr> expressions,
      DecisionStrategyProto::VariableSelectionStrategy var_strategy,
      DecisionStrategyProto::DomainReductionStrategy domain_strategy);

  void AddHint(IntVar var, int64_t value);

  void AddHint(BoolVar var, bool value);

  void ClearHints();

  void AddAssumption(BoolVar lit);

  void AddAssumptions(absl::Span<const BoolVar> literals);

  void ClearAssumptions();
 
  const CpModelProto& Build() const { return cp_model_; }
  const CpModelProto& Proto() const { return cp_model_; }
  CpModelProto* MutableProto() { return &cp_model_; }

  bool ExportToFile(absl::string_view filename) const;

  CpModelBuilder Clone() const;

  BoolVar GetBoolVarFromProtoIndex(int index);

  IntVar GetIntVarFromProtoIndex(int index);

  IntervalVar GetIntervalVarFromProtoIndex(int index);
 
 private:
  friend class CumulativeConstraint;
  friend class ReservoirConstraint;
  friend class IntervalVar;
  friend class IntVar;
 
  // Used for cloning a model.
  void ResetAndImport(const CpModelProto& model_proto);
 
  // Fills the 'expr_proto' with the linear expression represented by 'expr'.
  LinearExpressionProto LinearExprToProto(const LinearExpr& expr,
                                          bool negate = false);
 
  // Returns a (cached) integer variable index with a constant value.
  int IndexFromConstant(int64_t value);
 
  // Returns a valid integer index from a BoolVar index.
  // If the input index is a positive, it returns this index.
  // If the input index is negative, it creates a cached IntVar equal to
  // 1 - BoolVar(PositiveRef(index)), and returns the index of this new
  // variable.
  int GetOrCreateIntegerIndex(int index);
 
  void FillLinearTerms(const LinearExpr& left, const LinearExpr& right,
                       LinearConstraintProto* proto);
 
  CpModelProto cp_model_;
  absl::flat_hash_map<int64_t, int> constant_to_index_map_;
  absl::flat_hash_map<int, int> bool_to_integer_index_map_;
};

int64_t SolutionIntegerValue(const CpSolverResponse& r, const LinearExpr& expr);

bool SolutionBooleanValue(const CpSolverResponse& r, BoolVar x);
 
// Returns a more readable and compact DebugString() than
// proto.variables(index).DebugString(). This is used by IntVar::DebugString()
// but also allow to get the same string from a const proto.
std::string VarDebugString(const CpModelProto& proto, int index);
 
// ============================================================================
// Minimal support for "natural" API to create LinearExpr.
//
// Note(user): This might be optimized further by optimizing LinearExpr for
// holding one term, or introducing an LinearTerm class, but these should mainly
// be used to construct small expressions. Revisit if we run into performance
// issues. Note that if perf become a bottleneck for a client, then probably
// directly writing the proto will be even faster.
// ============================================================================
 
inline LinearExpr operator-(LinearExpr expr) { return expr *= -1; }
 
inline LinearExpr operator+(const LinearExpr& lhs, const LinearExpr& rhs) {
  LinearExpr temp(lhs);
  temp += rhs;
  return temp;
}
inline LinearExpr operator+(LinearExpr&& lhs, const LinearExpr& rhs) {
  lhs += rhs;
  return std::move(lhs);
}
inline LinearExpr operator+(const LinearExpr& lhs, LinearExpr&& rhs) {
  rhs += lhs;
  return std::move(rhs);
}
inline LinearExpr operator+(LinearExpr&& lhs, LinearExpr&& rhs) {
  if (lhs.variables().size() < rhs.variables().size()) {
    rhs += std::move(lhs);
    return std::move(rhs);
  } else {
    lhs += std::move(rhs);
    return std::move(lhs);
  }
}
 
inline LinearExpr operator-(const LinearExpr& lhs, const LinearExpr& rhs) {
  LinearExpr temp(lhs);
  temp -= rhs;
  return temp;
}
inline LinearExpr operator-(LinearExpr&& lhs, const LinearExpr& rhs) {
  lhs -= rhs;
  return std::move(lhs);
}
inline LinearExpr operator-(const LinearExpr& lhs, LinearExpr&& rhs) {
  rhs *= -1;
  rhs += lhs;
  return std::move(rhs);
}
inline LinearExpr operator-(LinearExpr&& lhs, LinearExpr&& rhs) {
  lhs -= std::move(rhs);
  return std::move(lhs);
}
 
inline LinearExpr operator*(LinearExpr expr, int64_t factor) {
  expr *= factor;
  return expr;
}
inline LinearExpr operator*(int64_t factor, LinearExpr expr) {
  expr *= factor;
  return expr;
}
 
// For DoubleLinearExpr.
 
inline DoubleLinearExpr operator-(DoubleLinearExpr expr) {
  expr *= -1;
  return expr;
}
 
inline DoubleLinearExpr operator+(const DoubleLinearExpr& lhs,
                                  const DoubleLinearExpr& rhs) {
  DoubleLinearExpr temp(lhs);
  temp += rhs;
  return temp;
}
inline DoubleLinearExpr operator+(DoubleLinearExpr&& lhs,
                                  const DoubleLinearExpr& rhs) {
  lhs += rhs;
  return std::move(lhs);
}
inline DoubleLinearExpr operator+(const DoubleLinearExpr& lhs,
                                  DoubleLinearExpr&& rhs) {
  rhs += lhs;
  return std::move(rhs);
}
inline DoubleLinearExpr operator+(DoubleLinearExpr&& lhs,
                                  DoubleLinearExpr&& rhs) {
  if (lhs.variables().size() < rhs.variables().size()) {
    rhs += std::move(lhs);
    return std::move(rhs);
  } else {
    lhs += std::move(rhs);
    return std::move(lhs);
  }
}
 
inline DoubleLinearExpr operator+(DoubleLinearExpr expr, double rhs) {
  expr += rhs;
  return expr;
}
inline DoubleLinearExpr operator+(double lhs, DoubleLinearExpr expr) {
  expr += lhs;
  return expr;
}
 
inline DoubleLinearExpr operator-(const DoubleLinearExpr& lhs,
                                  const DoubleLinearExpr& rhs) {
  DoubleLinearExpr temp(lhs);
  temp -= rhs;
  return temp;
}
inline DoubleLinearExpr operator-(DoubleLinearExpr&& lhs,
                                  const DoubleLinearExpr& rhs) {
  lhs -= rhs;
  return std::move(lhs);
}
inline DoubleLinearExpr operator-(const DoubleLinearExpr& lhs,
                                  DoubleLinearExpr&& rhs) {
  rhs *= -1;
  rhs += lhs;
  return std::move(rhs);
}
inline DoubleLinearExpr operator-(DoubleLinearExpr&& lhs,
                                  DoubleLinearExpr&& rhs) {
  lhs -= std::move(rhs);
  return std::move(lhs);
}
 
inline DoubleLinearExpr operator-(DoubleLinearExpr epxr, double rhs) {
  epxr -= rhs;
  return epxr;
}
inline DoubleLinearExpr operator-(double lhs, DoubleLinearExpr expr) {
  expr *= -1;
  expr += lhs;
  return expr;
}
 
inline DoubleLinearExpr operator*(DoubleLinearExpr expr, double factor) {
  expr *= factor;
  return expr;
}
 
inline DoubleLinearExpr operator*(double factor, DoubleLinearExpr expr) {
  expr *= factor;
  return expr;
}
 
}  // namespace sat
}  // namespace operations_research
 
#endif  // OR_TOOLS_SAT_CP_MODEL_H_