constraint_solver.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_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
#define OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
 
#include <stddef.h>
#include <stdint.h>
 
#include <deque>
#include <functional>
#include <memory>
#include <ostream>
#include <random>
#include <string>
#include <utility>
#include <vector>
 
#include "absl/base/attributes.h"
#include "absl/base/log_severity.h"
#include "absl/container/flat_hash_map.h"
#include "absl/container/flat_hash_set.h"
#include "absl/flags/declare.h"
#include "absl/flags/flag.h"
#include "absl/log/check.h"
#include "absl/random/random.h"
#include "absl/strings/str_format.h"
#include "absl/strings/string_view.h"
#include "absl/time/time.h"
#include "absl/types/span.h"
#include "ortools/base/logging.h"
#include "ortools/base/map_util.h"
#include "ortools/base/timer.h"
#include "ortools/base/types.h"
#include "ortools/constraint_solver/search_stats.pb.h"
#include "ortools/constraint_solver/solver_parameters.pb.h"
#include "ortools/util/piecewise_linear_function.h"
#include "ortools/util/saturated_arithmetic.h"
#include "ortools/util/sorted_interval_list.h"
#include "ortools/util/tuple_set.h"
 
#if !defined(SWIG)
OR_DLL ABSL_DECLARE_FLAG(int64_t, cp_random_seed);
OR_DLL ABSL_DECLARE_FLAG(bool, cp_disable_solve);
#endif  // !defined(SWIG)
 
class File;
 
namespace operations_research {
 
class Assignment;
class AssignmentProto;
class BaseObject;
class CastConstraint;
class Constraint;
class Decision;
class DecisionBuilder;
class DecisionVisitor;
class Demon;
class DemonProfiler;
class Dimension;
class DisjunctiveConstraint;
class ImprovementSearchLimit;
class IntExpr;
class IntVar;
class IntVarAssignment;
class IntVarLocalSearchFilter;
class IntervalVar;
class IntervalVarAssignment;
class LocalSearch;
class LocalSearchFilter;
class LocalSearchFilterManager;
class LocalSearchMonitor;
class LocalSearchOperator;
class LocalSearchPhaseParameters;
class LocalSearchProfiler;
class ModelCache;
class ModelVisitor;
class ObjectiveMonitor;
class BaseObjectiveMonitor;
class OptimizeVar;
class Pack;
class ProfiledDecisionBuilder;
class PropagationBaseObject;
class PropagationMonitor;
class Queue;
class RegularLimit;
class RegularLimitParameters;
class RevBitMatrix;
class Search;
class SearchLimit;
class SearchMonitor;
class SequenceVar;
class SequenceVarAssignment;
class SolutionCollector;
class SolutionPool;
class SymmetryBreaker;
struct StateInfo;
struct Trail;
template <class T>
class SimpleRevFIFO;
template <typename F>
class LightIntFunctionElementCt;
template <typename F>
class LightIntIntFunctionElementCt;
template <typename F>
class LightIntIntIntFunctionElementCt;
 
inline int64_t CpRandomSeed() {
  return absl::GetFlag(FLAGS_cp_random_seed) == -1
             ? absl::Uniform<int64_t>(absl::BitGen(), 0, kint64max)
             : absl::GetFlag(FLAGS_cp_random_seed);
}

struct DefaultPhaseParameters {
 public:
  enum VariableSelection {
    CHOOSE_MAX_SUM_IMPACT = 0,
    CHOOSE_MAX_AVERAGE_IMPACT = 1,
    CHOOSE_MAX_VALUE_IMPACT = 2,
  };
 
  enum ValueSelection {
    SELECT_MIN_IMPACT = 0,
    SELECT_MAX_IMPACT = 1,
  };
 
  enum DisplayLevel { NONE = 0, NORMAL = 1, VERBOSE = 2 };


  VariableSelection var_selection_schema;

  ValueSelection value_selection_schema;

  int initialization_splits;

  bool run_all_heuristics;

  int heuristic_period;

  int heuristic_num_failures_limit;

  bool persistent_impact;

  int random_seed;

  DisplayLevel display_level;

  bool use_last_conflict;

  DecisionBuilder* decision_builder;
 
  DefaultPhaseParameters();
};


class Solver {
 public:
  struct IntegerCastInfo {
    IntegerCastInfo()
        : variable(nullptr), expression(nullptr), maintainer(nullptr) {}
    IntegerCastInfo(IntVar* const v, IntExpr* const e, Constraint* const c)
        : variable(v), expression(e), maintainer(c) {}
    IntVar* variable;
    IntExpr* expression;
    Constraint* maintainer;
  };

  static constexpr int kNumPriorities = 3;

  /// This enum describes the strategy used to select the next branching
  /// variable at each node during the search.
  enum IntVarStrategy {
    INT_VAR_DEFAULT,

    INT_VAR_SIMPLE,

    CHOOSE_FIRST_UNBOUND,

    /// Randomly select one of the remaining unbound variables.
    CHOOSE_RANDOM,

    CHOOSE_MIN_SIZE_LOWEST_MIN,

    CHOOSE_MIN_SIZE_HIGHEST_MIN,

    CHOOSE_MIN_SIZE_LOWEST_MAX,

    CHOOSE_MIN_SIZE_HIGHEST_MAX,

    CHOOSE_LOWEST_MIN,

    CHOOSE_HIGHEST_MAX,

    CHOOSE_MIN_SIZE,

    CHOOSE_MAX_SIZE,

    CHOOSE_MAX_REGRET_ON_MIN,

    CHOOSE_PATH,
  };
  // TODO(user): add HIGHEST_MIN and LOWEST_MAX.

  enum IntValueStrategy {
    INT_VALUE_DEFAULT,

    INT_VALUE_SIMPLE,

    ASSIGN_MIN_VALUE,

    ASSIGN_MAX_VALUE,

    ASSIGN_RANDOM_VALUE,

    ASSIGN_CENTER_VALUE,

    SPLIT_LOWER_HALF,

    SPLIT_UPPER_HALF,
  };

  enum EvaluatorStrategy {

    CHOOSE_STATIC_GLOBAL_BEST,

    CHOOSE_DYNAMIC_GLOBAL_BEST,
  };

  enum SequenceStrategy {
    SEQUENCE_DEFAULT,
    SEQUENCE_SIMPLE,
    CHOOSE_MIN_SLACK_RANK_FORWARD,
    CHOOSE_RANDOM_RANK_FORWARD,
  };

  enum IntervalStrategy {

    INTERVAL_DEFAULT,
    /// The simple is INTERVAL_SET_TIMES_FORWARD.
    INTERVAL_SIMPLE,
    INTERVAL_SET_TIMES_FORWARD,

    INTERVAL_SET_TIMES_BACKWARD
  };

  enum LocalSearchOperators {

    TWOOPT,

    /// Relocate: OROPT and RELOCATE.
    /// Operator which moves a sub-chain of a path to another position; the
    /// specified chain length is the fixed length of the chains being moved.
    /// When this length is 1, the operator simply moves a node to another
    /// position.
    /// Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5, for a chain
    /// length of 2 (where (1, 5) are first and last nodes of the path and can
    /// therefore not be moved):
    ///   1 ->  4 -> [2 -> 3] -> 5
    ///   1 -> [3 -> 4] -> 2  -> 5
    ///
    /// Using Relocate with chain lengths of 1, 2 and 3 together is equivalent
    /// to the OrOpt operator on a path. The OrOpt operator is a limited
    ///  version of 3Opt (breaks 3 arcs on a path).
    OROPT,

    RELOCATE,

    EXCHANGE,

    CROSS,

    MAKEACTIVE,

    MAKEINACTIVE,

    MAKECHAININACTIVE,

    SWAPACTIVE,

    SWAPACTIVECHAIN,

    EXTENDEDSWAPACTIVE,

    PATHLNS,

    FULLPATHLNS,

    UNACTIVELNS,

    INCREMENT,

    DECREMENT,

    SIMPLELNS
  };

  enum EvaluatorLocalSearchOperators {
    LK,


    TSPOPT,

    TSPLNS
  };

  enum LocalSearchFilterBound {
    GE,
    LE,
    EQ
  };

  enum DemonPriority {
    DELAYED_PRIORITY = 0,

    VAR_PRIORITY = 1,

    NORMAL_PRIORITY = 2,
  };

  /// temporal relation between the two intervals t1 and t2.
  enum BinaryIntervalRelation {
    ENDS_AFTER_END,

    ENDS_AFTER_START,

    ENDS_AT_END,


    ENDS_AT_START,

    /// t1 starts after t2 end, i.e. Start(t1) >= End(t2) + delay.
    STARTS_AFTER_END,

    STARTS_AFTER_START,

    STARTS_AT_END,

    STARTS_AT_START,

    STAYS_IN_SYNC
  };

  enum UnaryIntervalRelation {
    ENDS_AFTER,

    ENDS_AT,

    ENDS_BEFORE,


    STARTS_AFTER,

    /// t starts at d, i.e. Start(t) == d.
    STARTS_AT,

    STARTS_BEFORE,

    CROSS_DATE,

    AVOID_DATE
  };

  enum DecisionModification {
    NO_CHANGE,


    KEEP_LEFT,

    KEEP_RIGHT,

    KILL_BOTH,

    SWITCH_BRANCHES
  };

  enum MarkerType { SENTINEL, SIMPLE_MARKER, CHOICE_POINT, REVERSIBLE_ACTION };

  enum SolverState {
    OUTSIDE_SEARCH,
    IN_ROOT_NODE,
    IN_SEARCH,

    AT_SOLUTION,
    NO_MORE_SOLUTIONS,
    PROBLEM_INFEASIBLE
  };

  enum OptimizationDirection { NOT_SET, MAXIMIZATION, MINIMIZATION };
 
#ifndef SWIG
  enum class MonitorEvent : int {
    kEnterSearch = 0,
    kRestartSearch,
    kExitSearch,
    kBeginNextDecision,
    kEndNextDecision,
    kApplyDecision,
    kRefuteDecision,
    kAfterDecision,
    kBeginFail,
    kEndFail,
    kBeginInitialPropagation,
    kEndInitialPropagation,
    kAcceptSolution,
    kAtSolution,
    kNoMoreSolutions,
    kLocalOptimum,
    kAcceptDelta,
    kAcceptNeighbor,
    kAcceptUncheckedNeighbor,
    kIsUncheckedSolutionLimitReached,
    kPeriodicCheck,
    kProgressPercent,
    kAccept,
    // Dummy event whose underlying int is the number of MonitorEvent enums.
    kLast,
  };
#endif  // SWIG

  typedef std::function<int64_t(int64_t)> IndexEvaluator1;
  typedef std::function<int64_t(int64_t, int64_t)> IndexEvaluator2;
  typedef std::function<int64_t(int64_t, int64_t, int64_t)> IndexEvaluator3;
 
  typedef std::function<bool(int64_t)> IndexFilter1;
 
  typedef std::function<IntVar*(int64_t)> Int64ToIntVar;
 
  typedef std::function<int64_t(Solver* solver,
                                const std::vector<IntVar*>& vars,
                                int64_t first_unbound, int64_t last_unbound)>
      VariableIndexSelector;
 
  typedef std::function<int64_t(const IntVar* v, int64_t id)>
      VariableValueSelector;
  typedef std::function<bool(int64_t, int64_t, int64_t)>
      VariableValueComparator;
  typedef std::function<DecisionModification()> BranchSelector;
  // TODO(user): wrap in swig.
  typedef std::function<void(Solver*)> Action;
  typedef std::function<void()> Closure;

  explicit Solver(const std::string& name);
  Solver(const std::string& name, const ConstraintSolverParameters& parameters);
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  Solver(const Solver&) = delete;
  Solver& operator=(const Solver&) = delete;
#endif
 
  ~Solver();

  ConstraintSolverParameters parameters() const { return parameters_; }
  // Read-only.
  const ConstraintSolverParameters& const_parameters() const {
    return parameters_;
  }
  // TODO(user): Move to constraint_solver_parameters.h.
  static ConstraintSolverParameters DefaultSolverParameters();


  template <class T>
  void SaveValue(T* o) {
    InternalSaveValue(o);
  }

  /// BaseObject: for all subclasses predefined in the library, the
  /// corresponding factory methods (e.g., MakeIntVar(...),
  /// MakeAllDifferent(...) already take care of the registration.
  template <typename T>
  T* RevAlloc(T* object) {
    return reinterpret_cast<T*>(SafeRevAlloc(object));
  }

  template <typename T>
  T* RevAllocArray(T* object) {
    return reinterpret_cast<T*>(SafeRevAllocArray(object));
  }

  /// Adds the constraint 'c' to the model.
  ///
  /// After calling this method, and until there is a backtrack that undoes the
  /// addition, any assignment of variables to values must satisfy the given
  /// constraint in order to be considered feasible. There are two fairly
  /// different use cases:
  ///
  /// - the most common use case is modeling: the given constraint is really
  /// part of the problem that the user is trying to solve. In this use case,
  /// AddConstraint is called outside of search (i.e., with <tt>state() ==
  /// OUTSIDE_SEARCH</tt>). Most users should only use AddConstraint in this
  /// way. In this case, the constraint will belong to the model forever: it
  /// cannot be removed by backtracking.
  ///
  /// - a rarer use case is that 'c' is not a real constraint of the model. It
  /// may be a constraint generated by a branching decision (a constraint whose
  /// goal is to restrict the search space), a symmetry breaking constraint (a
  /// constraint that does restrict the search space, but in a way that cannot
  /// have an impact on the quality of the solutions in the subtree), or an
  /// inferred constraint that, while having no semantic value to the model (it
  /// does not restrict the set of solutions), is worth having because we
  /// believe it may strengthen the propagation. In these cases, it happens
  /// that the constraint is added during the search (i.e., with state() ==
  /// IN_SEARCH or state() == IN_ROOT_NODE). When a constraint is
  /// added during a search, it applies only to the subtree of the search tree
  /// rooted at the current node, and will be automatically removed by
  /// backtracking.
  ///
  /// This method does not take ownership of the constraint. If the constraint
  /// has been created by any factory method (Solver::MakeXXX), it will
  /// automatically be deleted. However, power users who implement their own
  /// constraints should do: solver.AddConstraint(solver.RevAlloc(new
  /// MyConstraint(...));
  void AddConstraint(Constraint* c);
  void AddCastConstraint(CastConstraint* constraint, IntVar* target_var,
                         IntExpr* expr);

  bool Solve(DecisionBuilder* db, const std::vector<SearchMonitor*>& monitors);
  bool Solve(DecisionBuilder* db);
  bool Solve(DecisionBuilder* db, SearchMonitor* m1);
  bool Solve(DecisionBuilder* db, SearchMonitor* m1, SearchMonitor* m2);
  bool Solve(DecisionBuilder* db, SearchMonitor* m1, SearchMonitor* m2,
             SearchMonitor* m3);
  bool Solve(DecisionBuilder* db, SearchMonitor* m1, SearchMonitor* m2,
             SearchMonitor* m3, SearchMonitor* m4);

 
  void NewSearch(DecisionBuilder* db,
                 const std::vector<SearchMonitor*>& monitors);
  void NewSearch(DecisionBuilder* db);
  void NewSearch(DecisionBuilder* db, SearchMonitor* m1);
  void NewSearch(DecisionBuilder* db, SearchMonitor* m1, SearchMonitor* m2);
  void NewSearch(DecisionBuilder* db, SearchMonitor* m1, SearchMonitor* m2,
                 SearchMonitor* m3);
  void NewSearch(DecisionBuilder* db, SearchMonitor* m1, SearchMonitor* m2,
                 SearchMonitor* m3, SearchMonitor* m4);
 
  bool NextSolution();
  void RestartSearch();
  void EndSearch();

  bool SolveAndCommit(DecisionBuilder* db,
                      const std::vector<SearchMonitor*>& monitors);
  bool SolveAndCommit(DecisionBuilder* db);
  bool SolveAndCommit(DecisionBuilder* db, SearchMonitor* m1);
  bool SolveAndCommit(DecisionBuilder* db, SearchMonitor* m1,
                      SearchMonitor* m2);
  bool SolveAndCommit(DecisionBuilder* db, SearchMonitor* m1, SearchMonitor* m2,
                      SearchMonitor* m3);

  bool CheckAssignment(Assignment* solution);

  bool CheckConstraint(Constraint* ct);

  SolverState state() const { return state_; }

  void Fail();
 
#if !defined(SWIG)
  void AddBacktrackAction(Action a, bool fast);
#endif  

  std::string DebugString() const;

  static int64_t MemoryUsage();

  absl::Time Now() const;

  int64_t wall_time() const;

  int64_t branches() const { return branches_; }

  int64_t solutions() const;

  int64_t unchecked_solutions() const;

  int64_t demon_runs(DemonPriority p) const { return demon_runs_[p]; }

  int64_t failures() const { return fails_; }

  int64_t neighbors() const { return neighbors_; }

  void ClearNeighbors() { neighbors_ = 0; }
  void IncrementNeighbors() { ++neighbors_; }

  int64_t filtered_neighbors() const { return filtered_neighbors_; }

  int64_t accepted_neighbors() const { return accepted_neighbors_; }

  uint64_t stamp() const;

  uint64_t fail_stamp() const;

  void set_context(absl::string_view context) { context_ = context; }

  const std::string& context() const { return context_; }

  OptimizationDirection optimization_direction() const {
    return optimization_direction_;
  }
  void set_optimization_direction(OptimizationDirection direction) {
    optimization_direction_ = direction;
  }
 
  // An internal method called by Guided Local Search to share current
  // penalties with the solver.
  void SetGuidedLocalSearchPenaltyCallback(
      std::function<int64_t(int64_t, int64_t, int64_t)> penalty_callback) {
    penalty_callback_ = std::move(penalty_callback);
  }
  // Returns the current (Guided Local Search)penalty of the given arc tuple.
  int64_t GetGuidedLocalSearchPenalty(int64_t i, int64_t j, int64_t k) const {
    return (penalty_callback_ == nullptr) ? 0 : penalty_callback_(i, j, k);
  }
 
  // All factories (MakeXXX methods) encapsulate creation of objects
  // through RevAlloc(). Hence, the Solver used for allocating the
  // returned object will retain ownership of the allocated memory.
  // Destructors are called upon backtrack, or when the Solver is
  // itself destructed.
 
  // ----- Int Variables and Constants -----

  IntVar* MakeIntVar(int64_t min, int64_t max, const std::string& name);

  IntVar* MakeIntVar(const std::vector<int64_t>& values,
                     const std::string& name);


  IntVar* MakeIntVar(const std::vector<int>& values, const std::string& name);

  /// MakeIntVar will create the best range based int var for the bounds given.
  IntVar* MakeIntVar(int64_t min, int64_t max);

  IntVar* MakeIntVar(const std::vector<int64_t>& values);

  IntVar* MakeIntVar(const std::vector<int>& values);

  IntVar* MakeBoolVar(const std::string& name);

  IntVar* MakeBoolVar();

  IntVar* MakeIntConst(int64_t val, const std::string& name);

  IntVar* MakeIntConst(int64_t val);

  void MakeIntVarArray(int var_count, int64_t vmin, int64_t vmax,
                       const std::string& name, std::vector<IntVar*>* vars);
  void MakeIntVarArray(int var_count, int64_t vmin, int64_t vmax,
                       std::vector<IntVar*>* vars);
  IntVar** MakeIntVarArray(int var_count, int64_t vmin, int64_t vmax,
                           const std::string& name);

  void MakeBoolVarArray(int var_count, const std::string& name,
                        std::vector<IntVar*>* vars);
  void MakeBoolVarArray(int var_count, std::vector<IntVar*>* vars);
  IntVar** MakeBoolVarArray(int var_count, const std::string& name);
 
  // ----- Integer Expressions -----

  IntExpr* MakeSum(IntExpr* left, IntExpr* right);
  IntExpr* MakeSum(IntExpr* expr, int64_t value);
  IntExpr* MakeSum(const std::vector<IntVar*>& vars);

  IntExpr* MakeScalProd(const std::vector<IntVar*>& vars,
                        const std::vector<int64_t>& coefs);
  IntExpr* MakeScalProd(const std::vector<IntVar*>& vars,
                        const std::vector<int>& coefs);

  IntExpr* MakeDifference(IntExpr* left, IntExpr* right);
  IntExpr* MakeDifference(int64_t value, IntExpr* expr);
  IntExpr* MakeOpposite(IntExpr* expr);

  IntExpr* MakeProd(IntExpr* left, IntExpr* right);
  IntExpr* MakeProd(IntExpr* expr, int64_t value);

  IntExpr* MakeDiv(IntExpr* expr, int64_t value);
  IntExpr* MakeDiv(IntExpr* numerator, IntExpr* denominator);

  IntExpr* MakeAbs(IntExpr* expr);
  IntExpr* MakeSquare(IntExpr* expr);
  IntExpr* MakePower(IntExpr* expr, int64_t n);

  IntExpr* MakeElement(const std::vector<int64_t>& values, IntVar* index);
  IntExpr* MakeElement(const std::vector<int>& values, IntVar* index);

  IntExpr* MakeElement(IndexEvaluator1 values, IntVar* index);
  IntExpr* MakeMonotonicElement(IndexEvaluator1 values, bool increasing,
                                IntVar* index);
  IntExpr* MakeElement(IndexEvaluator2 values, IntVar* index1, IntVar* index2);

  IntExpr* MakeElement(const std::vector<IntVar*>& vars, IntVar* index);
 
#if !defined(SWIG)
  IntExpr* MakeElement(Int64ToIntVar vars, int64_t range_start,
                       int64_t range_end, IntVar* argument);
#endif  // SWIG


  template <typename F>
  Constraint* MakeLightElement(F values, IntVar* const var, IntVar* const index,
                               std::function<bool()> deep_serialize = nullptr) {
    return RevAlloc(new LightIntFunctionElementCt<F>(
        this, var, index, std::move(values), std::move(deep_serialize)));
  }

  template <typename F>
  Constraint* MakeLightElement(F values, IntVar* const var,
                               IntVar* const index1, IntVar* const index2,
                               std::function<bool()> deep_serialize = nullptr) {
    return RevAlloc(new LightIntIntFunctionElementCt<F>(
        this, var, index1, index2, std::move(values),
        std::move(deep_serialize)));
  }

  template <typename F>
  Constraint* MakeLightElement(F values, IntVar* const var,
                               IntVar* const index1, IntVar* const index2,
                               IntVar* const index3) {
    return RevAlloc(new LightIntIntIntFunctionElementCt<F>(
        this, var, index1, index2, index3, std::move(values)));
  }

  IntExpr* MakeIndexExpression(const std::vector<IntVar*>& vars, int64_t value);

  Constraint* MakeIfThenElseCt(IntVar* condition, IntExpr* then_expr,
                               IntExpr* else_expr, IntVar* target_var);

  IntExpr* MakeMin(const std::vector<IntVar*>& vars);
  IntExpr* MakeMin(IntExpr* left, IntExpr* right);
  IntExpr* MakeMin(IntExpr* expr, int64_t value);

  IntExpr* MakeMin(IntExpr* expr, int value);

  IntExpr* MakeMax(const std::vector<IntVar*>& vars);
  IntExpr* MakeMax(IntExpr* left, IntExpr* right);
  IntExpr* MakeMax(IntExpr* expr, int64_t value);
  IntExpr* MakeMax(IntExpr* expr, int value);


  IntExpr* MakeConvexPiecewiseExpr(IntExpr* expr, int64_t early_cost,
                                   int64_t early_date, int64_t late_date,
                                   int64_t late_cost);

  IntExpr* MakeSemiContinuousExpr(IntExpr* expr, int64_t fixed_charge,
                                  int64_t step);

  // TODO(user): Investigate if we can merge all three piecewise linear
#ifndef SWIG
  IntExpr* MakePiecewiseLinearExpr(IntExpr* expr,
                                   const PiecewiseLinearFunction& f);
#endif

  IntExpr* MakeModulo(IntExpr* x, int64_t mod);

  IntExpr* MakeModulo(IntExpr* x, IntExpr* mod);

  IntExpr* MakeConditionalExpression(IntVar* condition, IntExpr* expr,
                                     int64_t unperformed_value);

  Constraint* MakeTrueConstraint();
  Constraint* MakeFalseConstraint();
  Constraint* MakeFalseConstraint(const std::string& explanation);

  Constraint* MakeIsEqualCstCt(IntExpr* var, int64_t value, IntVar* boolvar);
  IntVar* MakeIsEqualCstVar(IntExpr* var, int64_t value);
  Constraint* MakeIsEqualCt(IntExpr* v1, IntExpr* v2, IntVar* b);
  IntVar* MakeIsEqualVar(IntExpr* v1, IntExpr* v2);
  Constraint* MakeEquality(IntExpr* left, IntExpr* right);
  Constraint* MakeEquality(IntExpr* expr, int64_t value);
  Constraint* MakeEquality(IntExpr* expr, int value);

  Constraint* MakeIsDifferentCstCt(IntExpr* var, int64_t value,
                                   IntVar* boolvar);
  IntVar* MakeIsDifferentCstVar(IntExpr* var, int64_t value);
  IntVar* MakeIsDifferentVar(IntExpr* v1, IntExpr* v2);
  Constraint* MakeIsDifferentCt(IntExpr* v1, IntExpr* v2, IntVar* b);
  Constraint* MakeNonEquality(IntExpr* left, IntExpr* right);
  Constraint* MakeNonEquality(IntExpr* expr, int64_t value);
  Constraint* MakeNonEquality(IntExpr* expr, int value);

  Constraint* MakeIsLessOrEqualCstCt(IntExpr* var, int64_t value,
                                     IntVar* boolvar);
  IntVar* MakeIsLessOrEqualCstVar(IntExpr* var, int64_t value);
  IntVar* MakeIsLessOrEqualVar(IntExpr* left, IntExpr* right);
  Constraint* MakeIsLessOrEqualCt(IntExpr* left, IntExpr* right, IntVar* b);
  Constraint* MakeLessOrEqual(IntExpr* left, IntExpr* right);
  Constraint* MakeLessOrEqual(IntExpr* expr, int64_t value);
  Constraint* MakeLessOrEqual(IntExpr* expr, int value);

  Constraint* MakeIsGreaterOrEqualCstCt(IntExpr* var, int64_t value,
                                        IntVar* boolvar);
  IntVar* MakeIsGreaterOrEqualCstVar(IntExpr* var, int64_t value);
  IntVar* MakeIsGreaterOrEqualVar(IntExpr* left, IntExpr* right);
  Constraint* MakeIsGreaterOrEqualCt(IntExpr* left, IntExpr* right, IntVar* b);
  Constraint* MakeGreaterOrEqual(IntExpr* left, IntExpr* right);
  Constraint* MakeGreaterOrEqual(IntExpr* expr, int64_t value);
  Constraint* MakeGreaterOrEqual(IntExpr* expr, int value);

  Constraint* MakeIsGreaterCstCt(IntExpr* v, int64_t c, IntVar* b);
  IntVar* MakeIsGreaterCstVar(IntExpr* var, int64_t value);
  IntVar* MakeIsGreaterVar(IntExpr* left, IntExpr* right);
  Constraint* MakeIsGreaterCt(IntExpr* left, IntExpr* right, IntVar* b);
  Constraint* MakeGreater(IntExpr* left, IntExpr* right);
  Constraint* MakeGreater(IntExpr* expr, int64_t value);
  Constraint* MakeGreater(IntExpr* expr, int value);

  Constraint* MakeIsLessCstCt(IntExpr* v, int64_t c, IntVar* b);
  IntVar* MakeIsLessCstVar(IntExpr* var, int64_t value);
  IntVar* MakeIsLessVar(IntExpr* left, IntExpr* right);
  Constraint* MakeIsLessCt(IntExpr* left, IntExpr* right, IntVar* b);
  Constraint* MakeLess(IntExpr* left, IntExpr* right);
  Constraint* MakeLess(IntExpr* expr, int64_t value);
  Constraint* MakeLess(IntExpr* expr, int value);

  Constraint* MakeSumLessOrEqual(const std::vector<IntVar*>& vars, int64_t cst);
  Constraint* MakeSumGreaterOrEqual(const std::vector<IntVar*>& vars,
                                    int64_t cst);
  Constraint* MakeSumEquality(const std::vector<IntVar*>& vars, int64_t cst);
  Constraint* MakeSumEquality(const std::vector<IntVar*>& vars, IntVar* var);
  Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
                                   const std::vector<int64_t>& coefficients,
                                   int64_t cst);
  Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
                                   const std::vector<int>& coefficients,
                                   int64_t cst);
  Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
                                   const std::vector<int64_t>& coefficients,
                                   IntVar* target);
  Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
                                   const std::vector<int>& coefficients,
                                   IntVar* target);
  Constraint* MakeScalProdGreaterOrEqual(const std::vector<IntVar*>& vars,
                                         const std::vector<int64_t>& coeffs,
                                         int64_t cst);
  Constraint* MakeScalProdGreaterOrEqual(const std::vector<IntVar*>& vars,
                                         const std::vector<int>& coeffs,
                                         int64_t cst);
  Constraint* MakeScalProdLessOrEqual(const std::vector<IntVar*>& vars,
                                      const std::vector<int64_t>& coefficients,
                                      int64_t cst);
  Constraint* MakeScalProdLessOrEqual(const std::vector<IntVar*>& vars,
                                      const std::vector<int>& coefficients,
                                      int64_t cst);
 
  Constraint* MakeMinEquality(const std::vector<IntVar*>& vars,
                              IntVar* min_var);
  Constraint* MakeMaxEquality(const std::vector<IntVar*>& vars,
                              IntVar* max_var);
 
  Constraint* MakeElementEquality(const std::vector<int64_t>& vals,
                                  IntVar* index, IntVar* target);
  Constraint* MakeElementEquality(const std::vector<int>& vals, IntVar* index,
                                  IntVar* target);
  Constraint* MakeElementEquality(const std::vector<IntVar*>& vars,
                                  IntVar* index, IntVar* target);
  Constraint* MakeElementEquality(const std::vector<IntVar*>& vars,
                                  IntVar* index, int64_t target);
  Constraint* MakeAbsEquality(IntVar* var, IntVar* abs_var);
  Constraint* MakeIndexOfConstraint(const std::vector<IntVar*>& vars,
                                    IntVar* index, int64_t target);

  Demon* MakeConstraintInitialPropagateCallback(Constraint* ct);
  Demon* MakeDelayedConstraintInitialPropagateCallback(Constraint* ct);
#if !defined(SWIG)
  Demon* MakeActionDemon(Action action);
#endif  
  Demon* MakeClosureDemon(Closure closure);
 
  // ----- Between and related constraints -----

  Constraint* MakeBetweenCt(IntExpr* expr, int64_t l, int64_t u);

  Constraint* MakeNotBetweenCt(IntExpr* expr, int64_t l, int64_t u);

  Constraint* MakeIsBetweenCt(IntExpr* expr, int64_t l, int64_t u, IntVar* b);
  IntVar* MakeIsBetweenVar(IntExpr* v, int64_t l, int64_t u);
 
  // ----- Member and related constraints -----

  Constraint* MakeMemberCt(IntExpr* expr, const std::vector<int64_t>& values);
  Constraint* MakeMemberCt(IntExpr* expr, const std::vector<int>& values);

  Constraint* MakeNotMemberCt(IntExpr* expr,
                              const std::vector<int64_t>& values);
  Constraint* MakeNotMemberCt(IntExpr* expr, const std::vector<int>& values);

  Constraint* MakeNotMemberCt(IntExpr* expr, std::vector<int64_t> starts,
                              std::vector<int64_t> ends);
  Constraint* MakeNotMemberCt(IntExpr* expr, std::vector<int> starts,
                              std::vector<int> ends);
#if !defined(SWIG)
  Constraint* MakeNotMemberCt(IntExpr* expr,
                              SortedDisjointIntervalList intervals);
#endif  // !defined(SWIG)

  Constraint* MakeIsMemberCt(IntExpr* expr, const std::vector<int64_t>& values,
                             IntVar* boolvar);
  Constraint* MakeIsMemberCt(IntExpr* expr, const std::vector<int>& values,
                             IntVar* boolvar);
  IntVar* MakeIsMemberVar(IntExpr* expr, const std::vector<int64_t>& values);
  IntVar* MakeIsMemberVar(IntExpr* expr, const std::vector<int>& values);

  Constraint* MakeAtMost(std::vector<IntVar*> vars, int64_t value,
                         int64_t max_count);
  Constraint* MakeCount(const std::vector<IntVar*>& vars, int64_t value,
                        int64_t max_count);
  Constraint* MakeCount(const std::vector<IntVar*>& vars, int64_t value,
                        IntVar* max_count);

  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
                             const std::vector<int64_t>& values,
                             const std::vector<IntVar*>& cards);
  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
                             const std::vector<int>& values,
                             const std::vector<IntVar*>& cards);
  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
                             const std::vector<IntVar*>& cards);
  Constraint* MakeDistribute(const std::vector<IntVar*>& vars, int64_t card_min,
                             int64_t card_max, int64_t card_size);
  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
                             const std::vector<int64_t>& card_min,
                             const std::vector<int64_t>& card_max);
  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
                             const std::vector<int>& card_min,
                             const std::vector<int>& card_max);
  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
                             const std::vector<int64_t>& values,
                             const std::vector<int64_t>& card_min,
                             const std::vector<int64_t>& card_max);
  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
                             const std::vector<int>& values,
                             const std::vector<int>& card_min,
                             const std::vector<int>& card_max);

  Constraint* MakeDeviation(const std::vector<IntVar*>& vars,
                            IntVar* deviation_var, int64_t total_sum);

  Constraint* MakeAllDifferent(const std::vector<IntVar*>& vars);

  Constraint* MakeAllDifferent(const std::vector<IntVar*>& vars,
                               bool stronger_propagation);

  Constraint* MakeAllDifferentExcept(const std::vector<IntVar*>& vars,
                                     int64_t escape_value);
  // TODO(user): Do we need a version with an array of escape values.

  Constraint* MakeSortingConstraint(const std::vector<IntVar*>& vars,
                                    const std::vector<IntVar*>& sorted);
  // TODO(user): Add void MakeSortedArray(
  //                             const std::vector<IntVar*>& vars,
  //                             std::vector<IntVar*>* const sorted);

  Constraint* MakeLexicalLess(const std::vector<IntVar*>& left,
                              const std::vector<IntVar*>& right);

  Constraint* MakeLexicalLessOrEqual(const std::vector<IntVar*>& left,
                                     const std::vector<IntVar*>& right);

  Constraint* MakeLexicalLessOrEqualWithOffsets(std::vector<IntVar*> left,
                                                std::vector<IntVar*> right,
                                                std::vector<int64_t> offsets);
 
  // Semi-reified version of the above: boolvar -> LexLE(left, right, offsets).
  Constraint* MakeIsLexicalLessOrEqualWithOffsetsCt(
      std::vector<IntVar*> left, std::vector<IntVar*> right,
      std::vector<int64_t> offsets, IntVar* boolvar);

  Constraint* MakeInversePermutationConstraint(
      const std::vector<IntVar*>& left, const std::vector<IntVar*>& right);

  Constraint* MakeIndexOfFirstMaxValueConstraint(
      IntVar* index, const std::vector<IntVar*>& vars);

  Constraint* MakeIndexOfFirstMinValueConstraint(
      IntVar* index, const std::vector<IntVar*>& vars);

  Constraint* MakeNullIntersect(const std::vector<IntVar*>& first_vars,
                                const std::vector<IntVar*>& second_vars);

  Constraint* MakeNullIntersectExcept(const std::vector<IntVar*>& first_vars,
                                      const std::vector<IntVar*>& second_vars,
                                      int64_t escape_value);
 
  // TODO(user): Implement MakeAllNullIntersect taking an array of
  // variable vectors.

  Constraint* MakeNoCycle(const std::vector<IntVar*>& nexts,
                          const std::vector<IntVar*>& active,
                          IndexFilter1 sink_handler = nullptr);
  Constraint* MakeNoCycle(const std::vector<IntVar*>& nexts,
                          const std::vector<IntVar*>& active,
                          IndexFilter1 sink_handler, bool assume_paths);

  Constraint* MakeCircuit(const std::vector<IntVar*>& nexts);

  Constraint* MakeSubCircuit(const std::vector<IntVar*>& nexts);

  Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
                            const std::vector<IntVar*>& active,
                            const std::vector<IntVar*>& cumuls,
                            const std::vector<IntVar*>& transits);
  // TODO(user): Merge with other path-cumuls constraints.
  Constraint* MakeDelayedPathCumul(const std::vector<IntVar*>& nexts,
                                   const std::vector<IntVar*>& active,
                                   const std::vector<IntVar*>& cumuls,
                                   const std::vector<IntVar*>& transits);
  Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
                            const std::vector<IntVar*>& active,
                            const std::vector<IntVar*>& cumuls,
                            IndexEvaluator2 transit_evaluator);

  Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
                            const std::vector<IntVar*>& active,
                            const std::vector<IntVar*>& cumuls,
                            const std::vector<IntVar*>& slacks,
                            IndexEvaluator2 transit_evaluator);
  // TODO(user): Only does checking on WhenBound events on next variables.
  Constraint* MakePathConnected(std::vector<IntVar*> nexts,
                                std::vector<int64_t> sources,
                                std::vector<int64_t> sinks,
                                std::vector<IntVar*> status);
#ifndef SWIG
  // TODO(user): This constraint does not make holes in variable domains;
  Constraint* MakePathPrecedenceConstraint(
      std::vector<IntVar*> nexts,
      const std::vector<std::pair<int, int>>& precedences);
  Constraint* MakePathPrecedenceConstraint(
      std::vector<IntVar*> nexts,
      const std::vector<std::pair<int, int>>& precedences,
      absl::Span<const int> lifo_path_starts,
      absl::Span<const int> fifo_path_starts);
  Constraint* MakePathTransitPrecedenceConstraint(
      std::vector<IntVar*> nexts, std::vector<IntVar*> transits,
      const std::vector<std::pair<int, int>>& precedences);
  struct PathEnergyCostConstraintSpecification {
    struct EnergyCost {
      int64_t threshold;
      int64_t cost_per_unit_below_threshold;
      int64_t cost_per_unit_above_threshold;
      bool IsNull() const {
        return (cost_per_unit_below_threshold == 0 || threshold == 0) &&
               (cost_per_unit_above_threshold == 0 || threshold == kint64max);
      }
    };
    std::vector<IntVar*> nexts;
    std::vector<IntVar*> paths;
    std::vector<IntVar*> forces;
    std::vector<IntVar*> distances;
    std::vector<EnergyCost> path_energy_costs;
    std::vector<bool> path_used_when_empty;
    std::vector<int64_t> path_starts;
    std::vector<int64_t> path_ends;
    std::vector<IntVar*> costs;
  };
  Constraint* MakePathEnergyCostConstraint(
      PathEnergyCostConstraintSpecification specification);
#endif  // !SWIG
  Constraint* MakeMapDomain(IntVar* var, const std::vector<IntVar*>& actives);

  /// variables involved in the relation and the graph is given by a
  /// integer tuple set.
  Constraint* MakeAllowedAssignments(const std::vector<IntVar*>& vars,
                                     const IntTupleSet& tuples);

  /// This constraint create a finite automaton that will check the
  /// sequence of variables vars. It uses a transition table called
  /// 'transition_table'. Each transition is a triple
  ///    (current_state, variable_value, new_state).
  /// The initial state is given, and the set of accepted states is decribed
  /// by 'final_states'. These states are hidden inside the constraint.
  /// Only the transitions (i.e. the variables) are visible.
  Constraint* MakeTransitionConstraint(
      const std::vector<IntVar*>& vars, const IntTupleSet& transition_table,
      int64_t initial_state, const std::vector<int64_t>& final_states);


  Constraint* MakeTransitionConstraint(const std::vector<IntVar*>& vars,
                                       const IntTupleSet& transition_table,
                                       int64_t initial_state,
                                       const std::vector<int>& final_states);
 
#if defined(SWIGPYTHON)
  Constraint* MakeAllowedAssignments(
      const std::vector<IntVar*>& vars,
      const std::vector<std::vector<int64_t> /*keep for swig*/>& raw_tuples) {
    IntTupleSet tuples(vars.size());
    tuples.InsertAll(raw_tuples);
    return MakeAllowedAssignments(vars, tuples);
  }
 
  Constraint* MakeTransitionConstraint(
      const std::vector<IntVar*>& vars,
      const std::vector<std::vector<int64_t> /*keep for swig*/>&
          raw_transitions,
      int64_t initial_state, const std::vector<int>& final_states) {
    IntTupleSet transitions(3);
    transitions.InsertAll(raw_transitions);
    return MakeTransitionConstraint(vars, transitions, initial_state,
                                    final_states);
  }
#endif

  Constraint* MakeNonOverlappingBoxesConstraint(
      const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
      const std::vector<IntVar*>& x_size, const std::vector<IntVar*>& y_size);
  Constraint* MakeNonOverlappingBoxesConstraint(
      const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
      absl::Span<const int64_t> x_size, absl::Span<const int64_t> y_size);
  Constraint* MakeNonOverlappingBoxesConstraint(
      const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
      absl::Span<const int> x_size, absl::Span<const int> y_size);

  Constraint* MakeNonOverlappingNonStrictBoxesConstraint(
      const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
      const std::vector<IntVar*>& x_size, const std::vector<IntVar*>& y_size);
  Constraint* MakeNonOverlappingNonStrictBoxesConstraint(
      const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
      absl::Span<const int64_t> x_size, absl::Span<const int64_t> y_size);
  Constraint* MakeNonOverlappingNonStrictBoxesConstraint(
      const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
      absl::Span<const int> x_size, absl::Span<const int> y_size);

  Pack* MakePack(const std::vector<IntVar*>& vars, int number_of_bins);

  IntervalVar* MakeFixedDurationIntervalVar(int64_t start_min,
                                            int64_t start_max, int64_t duration,
                                            bool optional,
                                            const std::string& name);

  void MakeFixedDurationIntervalVarArray(int count, int64_t start_min,
                                         int64_t start_max, int64_t duration,
                                         bool optional, absl::string_view name,
                                         std::vector<IntervalVar*>* array);

  IntervalVar* MakeFixedDurationIntervalVar(IntVar* start_variable,
                                            int64_t duration,
                                            const std::string& name);

  IntervalVar* MakeFixedDurationIntervalVar(IntVar* start_variable,
                                            int64_t duration,
                                            IntVar* performed_variable,
                                            const std::string& name);

  void MakeFixedDurationIntervalVarArray(
      const std::vector<IntVar*>& start_variables, int64_t duration,
      absl::string_view name, std::vector<IntervalVar*>* array);

  void MakeFixedDurationIntervalVarArray(
      const std::vector<IntVar*>& start_variables,
      absl::Span<const int64_t> durations, absl::string_view name,
      std::vector<IntervalVar*>* array);
  void MakeFixedDurationIntervalVarArray(
      const std::vector<IntVar*>& start_variables,
      absl::Span<const int> durations, absl::string_view name,
      std::vector<IntervalVar*>* array);

  void MakeFixedDurationIntervalVarArray(
      const std::vector<IntVar*>& start_variables,
      absl::Span<const int64_t> durations,
      const std::vector<IntVar*>& performed_variables, absl::string_view name,
      std::vector<IntervalVar*>* array);

  void MakeFixedDurationIntervalVarArray(
      const std::vector<IntVar*>& start_variables,
      absl::Span<const int> durations,
      const std::vector<IntVar*>& performed_variables, absl::string_view name,
      std::vector<IntervalVar*>* array);

  IntervalVar* MakeFixedInterval(int64_t start, int64_t duration,
                                 const std::string& name);

  IntervalVar* MakeIntervalVar(int64_t start_min, int64_t start_max,
                               int64_t duration_min, int64_t duration_max,
                               int64_t end_min, int64_t end_max, bool optional,
                               const std::string& name);

  void MakeIntervalVarArray(int count, int64_t start_min, int64_t start_max,
                            int64_t duration_min, int64_t duration_max,
                            int64_t end_min, int64_t end_max, bool optional,
                            absl::string_view name,
                            std::vector<IntervalVar*>* array);

  IntervalVar* MakeMirrorInterval(IntervalVar* interval_var);

  IntervalVar* MakeFixedDurationStartSyncedOnStartIntervalVar(
      IntervalVar* interval_var, int64_t duration, int64_t offset);

  IntervalVar* MakeFixedDurationStartSyncedOnEndIntervalVar(
      IntervalVar* interval_var, int64_t duration, int64_t offset);

  IntervalVar* MakeFixedDurationEndSyncedOnStartIntervalVar(
      IntervalVar* interval_var, int64_t duration, int64_t offset);

  IntervalVar* MakeFixedDurationEndSyncedOnEndIntervalVar(
      IntervalVar* interval_var, int64_t duration, int64_t offset);

  IntervalVar* MakeIntervalRelaxedMin(IntervalVar* interval_var);

  IntervalVar* MakeIntervalRelaxedMax(IntervalVar* interval_var);

  Constraint* MakeIntervalVarRelation(IntervalVar* t, UnaryIntervalRelation r,
                                      int64_t d);

  Constraint* MakeIntervalVarRelation(IntervalVar* t1, BinaryIntervalRelation r,
                                      IntervalVar* t2);

  Constraint* MakeIntervalVarRelationWithDelay(IntervalVar* t1,
                                               BinaryIntervalRelation r,
                                               IntervalVar* t2, int64_t delay);

  Constraint* MakeTemporalDisjunction(IntervalVar* t1, IntervalVar* t2,
                                      IntVar* alt);

  Constraint* MakeTemporalDisjunction(IntervalVar* t1, IntervalVar* t2);

  DisjunctiveConstraint* MakeDisjunctiveConstraint(
      const std::vector<IntervalVar*>& intervals, const std::string& name);

  DisjunctiveConstraint* MakeStrictDisjunctiveConstraint(
      const std::vector<IntervalVar*>& intervals, const std::string& name);

  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
                             const std::vector<int64_t>& demands,
                             int64_t capacity, const std::string& name);

  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
                             const std::vector<int>& demands, int64_t capacity,
                             const std::string& name);

  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
                             const std::vector<int64_t>& demands,
                             IntVar* capacity, absl::string_view name);

  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
                             const std::vector<int>& demands, IntVar* capacity,
                             const std::string& name);

  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
                             const std::vector<IntVar*>& demands,
                             int64_t capacity, const std::string& name);

  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
                             const std::vector<IntVar*>& demands,
                             IntVar* capacity, const std::string& name);

  Constraint* MakeCover(const std::vector<IntervalVar*>& vars,
                        IntervalVar* target_var);

  Constraint* MakeEquality(IntervalVar* var1, IntervalVar* var2);

  Assignment* MakeAssignment();

  Assignment* MakeAssignment(const Assignment* a);

  SolutionCollector* MakeFirstSolutionCollector(const Assignment* assignment);
  SolutionCollector* MakeFirstSolutionCollector();

  SolutionCollector* MakeLastSolutionCollector(const Assignment* assignment);
  SolutionCollector* MakeLastSolutionCollector();

  SolutionCollector* MakeBestValueSolutionCollector(
      const Assignment* assignment, bool maximize);
  SolutionCollector* MakeBestLexicographicValueSolutionCollector(
      const Assignment* assignment, std::vector<bool> maximize);
  SolutionCollector* MakeBestValueSolutionCollector(bool maximize);
  SolutionCollector* MakeBestLexicographicValueSolutionCollector(
      std::vector<bool> maximize);

  SolutionCollector* MakeNBestValueSolutionCollector(
      const Assignment* assignment, int solution_count, bool maximize);
  SolutionCollector* MakeNBestValueSolutionCollector(int solution_count,
                                                     bool maximize);
  SolutionCollector* MakeNBestLexicographicValueSolutionCollector(
      const Assignment* assignment, int solution_count,
      std::vector<bool> maximize);
  SolutionCollector* MakeNBestLexicographicValueSolutionCollector(
      int solution_count, std::vector<bool> maximize);

  SolutionCollector* MakeAllSolutionCollector(const Assignment* assignment);
  SolutionCollector* MakeAllSolutionCollector();

  OptimizeVar* MakeMinimize(IntVar* v, int64_t step);

  OptimizeVar* MakeMaximize(IntVar* v, int64_t step);

  OptimizeVar* MakeOptimize(bool maximize, IntVar* v, int64_t step);

  OptimizeVar* MakeWeightedMinimize(const std::vector<IntVar*>& sub_objectives,
                                    const std::vector<int64_t>& weights,
                                    int64_t step);

  OptimizeVar* MakeWeightedMinimize(const std::vector<IntVar*>& sub_objectives,
                                    const std::vector<int>& weights,
                                    int64_t step);

  OptimizeVar* MakeWeightedMaximize(const std::vector<IntVar*>& sub_objectives,
                                    const std::vector<int64_t>& weights,
                                    int64_t step);

  OptimizeVar* MakeWeightedMaximize(const std::vector<IntVar*>& sub_objectives,
                                    const std::vector<int>& weights,
                                    int64_t step);

  OptimizeVar* MakeWeightedOptimize(bool maximize,
                                    const std::vector<IntVar*>& sub_objectives,
                                    const std::vector<int64_t>& weights,
                                    int64_t step);

  OptimizeVar* MakeWeightedOptimize(bool maximize,
                                    const std::vector<IntVar*>& sub_objectives,
                                    const std::vector<int>& weights,
                                    int64_t step);

  OptimizeVar* MakeLexicographicOptimize(std::vector<bool> maximize,
                                         std::vector<IntVar*> variables,
                                         std::vector<int64_t> steps);


 
  ObjectiveMonitor* MakeTabuSearch(bool maximize, IntVar* objective,
                                   int64_t step,
                                   const std::vector<IntVar*>& vars,
                                   int64_t keep_tenure, int64_t forbid_tenure,
                                   double tabu_factor);
 
  ObjectiveMonitor* MakeLexicographicTabuSearch(
      const std::vector<bool>& maximize, std::vector<IntVar*> objectives,
      std::vector<int64_t> steps, const std::vector<IntVar*>& vars,
      int64_t keep_tenure, int64_t forbid_tenure, double tabu_factor);

  ObjectiveMonitor* MakeGenericTabuSearch(bool maximize, IntVar* v,
                                          int64_t step,
                                          const std::vector<IntVar*>& tabu_vars,
                                          int64_t forbid_tenure);

  // TODO(user): document behavior
  ObjectiveMonitor* MakeSimulatedAnnealing(bool maximize, IntVar* v,
                                           int64_t step,
                                           int64_t initial_temperature);
  ObjectiveMonitor* MakeLexicographicSimulatedAnnealing(
      const std::vector<bool>& maximize, std::vector<IntVar*> vars,
      std::vector<int64_t> steps, std::vector<int64_t> initial_temperatures);

#ifndef SWIG
  ObjectiveMonitor* MakeGuidedLocalSearch(
      bool maximize, IntVar* objective, IndexEvaluator2 objective_function,
      int64_t step, const std::vector<IntVar*>& vars, double penalty_factor,
      std::function<std::vector<std::pair<int64_t, int64_t>>(int64_t, int64_t)>
          get_equivalent_pairs = nullptr,
      bool reset_penalties_on_new_best_solution = false);
  ObjectiveMonitor* MakeGuidedLocalSearch(
      bool maximize, IntVar* objective, IndexEvaluator3 objective_function,
      int64_t step, const std::vector<IntVar*>& vars,
      const std::vector<IntVar*>& secondary_vars, double penalty_factor,
      std::function<std::vector<std::pair<int64_t, int64_t>>(int64_t, int64_t)>
          get_equivalent_pairs = nullptr,
      bool reset_penalties_on_new_best_solution = false);
#endif
 
  // Creates a composite objective monitor which alternates between objective
  // monitors every time the search reaches a local optimum local optimium
  // reached. This will stop if all monitors return false when LocalOptimium is
  // called.
  BaseObjectiveMonitor* MakeRoundRobinCompoundObjectiveMonitor(
      std::vector<BaseObjectiveMonitor*> monitors,
      int num_max_local_optima_before_metaheuristic_switch);

  SearchMonitor* MakeLubyRestart(int scale_factor);

  SearchMonitor* MakeConstantRestart(int frequency);

  ABSL_MUST_USE_RESULT RegularLimit* MakeTimeLimit(absl::Duration time);
#if !defined(SWIG)
  ABSL_DEPRECATED("Use the version taking absl::Duration() as argument")
#endif  // !defined(SWIG)
  ABSL_MUST_USE_RESULT RegularLimit* MakeTimeLimit(int64_t time_in_ms) {
    return MakeTimeLimit(time_in_ms == kint64max
                             ? absl::InfiniteDuration()
                             : absl::Milliseconds(time_in_ms));
  }

  ABSL_MUST_USE_RESULT RegularLimit* MakeBranchesLimit(int64_t branches);

  ABSL_MUST_USE_RESULT RegularLimit* MakeFailuresLimit(int64_t failures);

  ABSL_MUST_USE_RESULT RegularLimit* MakeSolutionsLimit(int64_t solutions);

  // timer by estimating the number of remaining calls, and 'cumulative' means
  // that the limit applies cumulatively, instead of search-by-search.
  ABSL_MUST_USE_RESULT RegularLimit* MakeLimit(absl::Duration time,
                                               int64_t branches,
                                               int64_t failures,
                                               int64_t solutions,
                                               bool smart_time_check = false,
                                               bool cumulative = false);
  ABSL_MUST_USE_RESULT RegularLimit* MakeLimit(
      const RegularLimitParameters& proto);
 
#if !defined(SWIG)
  ABSL_DEPRECATED("Use other MakeLimit() versions")
#endif  // !defined(SWIG)
  ABSL_MUST_USE_RESULT RegularLimit* MakeLimit(int64_t time, int64_t branches,
                                               int64_t failures,
                                               int64_t solutions,
                                               bool smart_time_check = false,
                                               bool cumulative = false);

  RegularLimitParameters MakeDefaultRegularLimitParameters() const;

  /// argument limits.
  ABSL_MUST_USE_RESULT SearchLimit* MakeLimit(SearchLimit* limit_1,
                                              SearchLimit* limit_2);


  ABSL_MUST_USE_RESULT ImprovementSearchLimit* MakeImprovementLimit(
      IntVar* objective_var, bool maximize, double objective_scaling_factor,
      double objective_offset, double improvement_rate_coefficient,
      int improvement_rate_solutions_distance);
  ABSL_MUST_USE_RESULT ImprovementSearchLimit*
  MakeLexicographicImprovementLimit(
      std::vector<IntVar*> objective_vars, std::vector<bool> maximize,
      std::vector<double> objective_scaling_factors,
      std::vector<double> objective_offsets,
      double improvement_rate_coefficient,
      int improvement_rate_solutions_distance);

  ABSL_MUST_USE_RESULT SearchLimit* MakeCustomLimit(
      std::function<bool()> limiter);
 
  // TODO(user): DEPRECATE API of MakeSearchLog(.., IntVar* var,..).

  SearchMonitor* MakeSearchLog(int branch_period);

  SearchMonitor* MakeSearchLog(int branch_period, IntVar* var);

  SearchMonitor* MakeSearchLog(int branch_period,
                               std::function<std::string()> display_callback);

  SearchMonitor* MakeSearchLog(int branch_period, IntVar* var,
                               std::function<std::string()> display_callback);

  SearchMonitor* MakeSearchLog(int branch_period, std::vector<IntVar*> vars,
                               std::function<std::string()> display_callback);

  SearchMonitor* MakeSearchLog(int branch_period, OptimizeVar* opt_var);

  SearchMonitor* MakeSearchLog(int branch_period, OptimizeVar* opt_var,
                               std::function<std::string()> display_callback);

  struct SearchLogParameters {
    int branch_period = 1;
    OptimizeVar* objective = nullptr;
    std::vector<IntVar*> variables;
    std::vector<double> scaling_factors;
    std::vector<double> offsets;
    std::function<std::string()> display_callback;
    bool display_on_new_solutions_only = true;
  };
  SearchMonitor* MakeSearchLog(SearchLogParameters parameters);

  SearchMonitor* MakeSearchTrace(const std::string& prefix);

  SearchMonitor* MakeEnterSearchCallback(std::function<void()> callback);
  SearchMonitor* MakeExitSearchCallback(std::function<void()> callback);
  SearchMonitor* MakeAtSolutionCallback(std::function<void()> callback);

  ModelVisitor* MakePrintModelVisitor();
  ModelVisitor* MakeStatisticsModelVisitor();
#if !defined(SWIG)
  ModelVisitor* MakeVariableDegreeVisitor(
      absl::flat_hash_map<const IntVar*, int>* map);
#endif  // !defined(SWIG)

  SearchMonitor* MakeSymmetryManager(
      const std::vector<SymmetryBreaker*>& visitors);
  SearchMonitor* MakeSymmetryManager(SymmetryBreaker* v1);
  SearchMonitor* MakeSymmetryManager(SymmetryBreaker* v1, SymmetryBreaker* v2);
  SearchMonitor* MakeSymmetryManager(SymmetryBreaker* v1, SymmetryBreaker* v2,
                                     SymmetryBreaker* v3);
  SearchMonitor* MakeSymmetryManager(SymmetryBreaker* v1, SymmetryBreaker* v2,
                                     SymmetryBreaker* v3, SymmetryBreaker* v4);

  Decision* MakeAssignVariableValue(IntVar* var, int64_t val);
  Decision* MakeVariableLessOrEqualValue(IntVar* var, int64_t value);
  Decision* MakeVariableGreaterOrEqualValue(IntVar* var, int64_t value);
  Decision* MakeSplitVariableDomain(IntVar* var, int64_t val,
                                    bool start_with_lower_half);
  Decision* MakeAssignVariableValueOrFail(IntVar* var, int64_t value);
  Decision* MakeAssignVariableValueOrDoNothing(IntVar* var, int64_t value);
  Decision* MakeAssignVariablesValues(const std::vector<IntVar*>& vars,
                                      const std::vector<int64_t>& values);
  Decision* MakeAssignVariablesValuesOrDoNothing(
      const std::vector<IntVar*>& vars, const std::vector<int64_t>& values);
  Decision* MakeAssignVariablesValuesOrFail(const std::vector<IntVar*>& vars,
                                            const std::vector<int64_t>& values);
  Decision* MakeFailDecision();
  Decision* MakeDecision(Action apply, Action refute);

  DecisionBuilder* Compose(DecisionBuilder* db1, DecisionBuilder* db2);
  DecisionBuilder* Compose(DecisionBuilder* db1, DecisionBuilder* db2,
                           DecisionBuilder* db3);
  DecisionBuilder* Compose(DecisionBuilder* db1, DecisionBuilder* db2,
                           DecisionBuilder* db3, DecisionBuilder* db4);
  DecisionBuilder* Compose(const std::vector<DecisionBuilder*>& dbs);

  // TODO(user): The search tree can be balanced by using binary
  DecisionBuilder* Try(DecisionBuilder* db1, DecisionBuilder* db2);
  DecisionBuilder* Try(DecisionBuilder* db1, DecisionBuilder* db2,
                       DecisionBuilder* db3);
  DecisionBuilder* Try(DecisionBuilder* db1, DecisionBuilder* db2,
                       DecisionBuilder* db3, DecisionBuilder* db4);
  DecisionBuilder* Try(const std::vector<DecisionBuilder*>& dbs);

  // TODO(user): name each of them differently, and document them (and do that
  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
                             IntVarStrategy var_str, IntValueStrategy val_str);
  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
                             IndexEvaluator1 var_evaluator,
                             IntValueStrategy val_str);
 
  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
                             IntVarStrategy var_str,
                             IndexEvaluator2 value_evaluator);

  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
                             IntVarStrategy var_str,
                             VariableValueComparator var_val1_val2_comparator);
 
  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
                             IndexEvaluator1 var_evaluator,
                             IndexEvaluator2 value_evaluator);
 
  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
                             IntVarStrategy var_str,
                             IndexEvaluator2 value_evaluator,
                             IndexEvaluator1 tie_breaker);
 
  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
                             IndexEvaluator1 var_evaluator,
                             IndexEvaluator2 value_evaluator,
                             IndexEvaluator1 tie_breaker);
 
  DecisionBuilder* MakeDefaultPhase(const std::vector<IntVar*>& vars);
  DecisionBuilder* MakeDefaultPhase(const std::vector<IntVar*>& vars,
                                    const DefaultPhaseParameters& parameters);

  DecisionBuilder* MakePhase(IntVar* v0, IntVarStrategy var_str,
                             IntValueStrategy val_str);
  DecisionBuilder* MakePhase(IntVar* v0, IntVar* v1, IntVarStrategy var_str,
                             IntValueStrategy val_str);
  DecisionBuilder* MakePhase(IntVar* v0, IntVar* v1, IntVar* v2,
                             IntVarStrategy var_str, IntValueStrategy val_str);
  DecisionBuilder* MakePhase(IntVar* v0, IntVar* v1, IntVar* v2, IntVar* v3,
                             IntVarStrategy var_str, IntValueStrategy val_str);

  Decision* MakeScheduleOrPostpone(IntervalVar* var, int64_t est,
                                   int64_t* marker);

  Decision* MakeScheduleOrExpedite(IntervalVar* var, int64_t est,
                                   int64_t* marker);

  Decision* MakeRankFirstInterval(SequenceVar* sequence, int index);

  Decision* MakeRankLastInterval(SequenceVar* sequence, int index);

  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
                             IndexEvaluator2 eval, EvaluatorStrategy str);

  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
                             IndexEvaluator2 eval, IndexEvaluator1 tie_breaker,
                             EvaluatorStrategy str);

  DecisionBuilder* MakePhase(const std::vector<IntervalVar*>& intervals,
                             IntervalStrategy str);
 
  DecisionBuilder* MakePhase(const std::vector<SequenceVar*>& sequences,
                             SequenceStrategy str);

  DecisionBuilder* MakeDecisionBuilderFromAssignment(
      Assignment* assignment, DecisionBuilder* db,
      const std::vector<IntVar*>& vars);

  DecisionBuilder* MakeConstraintAdder(Constraint* ct);

  DecisionBuilder* MakeSolveOnce(DecisionBuilder* db);
  DecisionBuilder* MakeSolveOnce(DecisionBuilder* db, SearchMonitor* monitor1);
  DecisionBuilder* MakeSolveOnce(DecisionBuilder* db, SearchMonitor* monitor1,
                                 SearchMonitor* monitor2);
  DecisionBuilder* MakeSolveOnce(DecisionBuilder* db, SearchMonitor* monitor1,
                                 SearchMonitor* monitor2,
                                 SearchMonitor* monitor3);
  DecisionBuilder* MakeSolveOnce(DecisionBuilder* db, SearchMonitor* monitor1,
                                 SearchMonitor* monitor2,
                                 SearchMonitor* monitor3,
                                 SearchMonitor* monitor4);
  DecisionBuilder* MakeSolveOnce(DecisionBuilder* db,
                                 const std::vector<SearchMonitor*>& monitors);

  DecisionBuilder* MakeNestedOptimize(DecisionBuilder* db, Assignment* solution,
                                      bool maximize, int64_t step);
  DecisionBuilder* MakeNestedOptimize(DecisionBuilder* db, Assignment* solution,
                                      bool maximize, int64_t step,
                                      SearchMonitor* monitor1);
  DecisionBuilder* MakeNestedOptimize(DecisionBuilder* db, Assignment* solution,
                                      bool maximize, int64_t step,
                                      SearchMonitor* monitor1,
                                      SearchMonitor* monitor2);
  DecisionBuilder* MakeNestedOptimize(DecisionBuilder* db, Assignment* solution,
                                      bool maximize, int64_t step,
                                      SearchMonitor* monitor1,
                                      SearchMonitor* monitor2,
                                      SearchMonitor* monitor3);
  DecisionBuilder* MakeNestedOptimize(DecisionBuilder* db, Assignment* solution,
                                      bool maximize, int64_t step,
                                      SearchMonitor* monitor1,
                                      SearchMonitor* monitor2,
                                      SearchMonitor* monitor3,
                                      SearchMonitor* monitor4);
  DecisionBuilder* MakeNestedOptimize(
      DecisionBuilder* db, Assignment* solution, bool maximize, int64_t step,
      const std::vector<SearchMonitor*>& monitors);

  DecisionBuilder* MakeRestoreAssignment(Assignment* assignment);

  DecisionBuilder* MakeStoreAssignment(Assignment* assignment);

  LocalSearchOperator* MakeOperator(
      const std::vector<IntVar*>& vars, LocalSearchOperators op,
      std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =
          nullptr,
      std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =
          nullptr);
  LocalSearchOperator* MakeOperator(
      const std::vector<IntVar*>& vars,
      const std::vector<IntVar*>& secondary_vars, LocalSearchOperators op,
      std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =
          nullptr,
      std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =
          nullptr);
  // TODO(user): Make the callback an IndexEvaluator2 when there are no
  // secondary variables.
  LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
                                    IndexEvaluator3 evaluator,
                                    EvaluatorLocalSearchOperators op);
  LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
                                    const std::vector<IntVar*>& secondary_vars,
                                    IndexEvaluator3 evaluator,
                                    EvaluatorLocalSearchOperators op);

  LocalSearchOperator* MakeRandomLnsOperator(const std::vector<IntVar*>& vars,
                                             int number_of_variables);
  LocalSearchOperator* MakeRandomLnsOperator(const std::vector<IntVar*>& vars,
                                             int number_of_variables,
                                             int32_t seed);

  LocalSearchOperator* MakeMoveTowardTargetOperator(const Assignment& target);

  LocalSearchOperator* MakeMoveTowardTargetOperator(
      const std::vector<IntVar*>& variables,
      const std::vector<int64_t>& target_values);

  LocalSearchOperator* ConcatenateOperators(
      const std::vector<LocalSearchOperator*>& ops);
  LocalSearchOperator* ConcatenateOperators(
      const std::vector<LocalSearchOperator*>& ops, bool restart);
  LocalSearchOperator* ConcatenateOperators(
      const std::vector<LocalSearchOperator*>& ops,
      std::function<int64_t(int, int)> evaluator);
  LocalSearchOperator* RandomConcatenateOperators(
      const std::vector<LocalSearchOperator*>& ops);

  LocalSearchOperator* RandomConcatenateOperators(
      const std::vector<LocalSearchOperator*>& ops, int32_t seed);

  LocalSearchOperator* MultiArmedBanditConcatenateOperators(
      const std::vector<LocalSearchOperator*>& ops, double memory_coefficient,
      double exploration_coefficient, bool maximize);

  LocalSearchOperator* MakeNeighborhoodLimit(LocalSearchOperator* op,
                                             int64_t limit);

  // TODO(user): Make a variant which runs a local search after each
  //                solution found in a DFS.
 
  DecisionBuilder* MakeLocalSearchPhase(Assignment* assignment,
                                        LocalSearchPhaseParameters* parameters);
  DecisionBuilder* MakeLocalSearchPhase(const std::vector<IntVar*>& vars,
                                        DecisionBuilder* first_solution,
                                        LocalSearchPhaseParameters* parameters);
  DecisionBuilder* MakeLocalSearchPhase(
      const std::vector<IntVar*>& vars, DecisionBuilder* first_solution,
      DecisionBuilder* first_solution_sub_decision_builder,
      LocalSearchPhaseParameters* parameters);
  DecisionBuilder* MakeLocalSearchPhase(const std::vector<SequenceVar*>& vars,
                                        DecisionBuilder* first_solution,
                                        LocalSearchPhaseParameters* parameters);

  Assignment* RunUncheckedLocalSearch(
      const Assignment* initial_solution,
      LocalSearchFilterManager* filter_manager,
      LocalSearchOperator* ls_operator,
      const std::vector<SearchMonitor*>& monitors, RegularLimit* limit,
      absl::flat_hash_set<IntVar*>* touched = nullptr);

  SolutionPool* MakeDefaultSolutionPool();

  LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
      IntVar* objective, LocalSearchOperator* ls_operator,
      DecisionBuilder* sub_decision_builder);
  LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
      IntVar* objective, LocalSearchOperator* ls_operator,
      DecisionBuilder* sub_decision_builder, RegularLimit* limit);
  LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
      IntVar* objective, LocalSearchOperator* ls_operator,
      DecisionBuilder* sub_decision_builder, RegularLimit* limit,
      LocalSearchFilterManager* filter_manager);
 
  LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
      IntVar* objective, SolutionPool* pool, LocalSearchOperator* ls_operator,
      DecisionBuilder* sub_decision_builder);
  LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
      IntVar* objective, SolutionPool* pool, LocalSearchOperator* ls_operator,
      DecisionBuilder* sub_decision_builder, RegularLimit* limit);
  LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
      IntVar* objective, SolutionPool* pool, LocalSearchOperator* ls_operator,
      DecisionBuilder* sub_decision_builder, RegularLimit* limit,
      LocalSearchFilterManager* filter_manager);

  LocalSearchFilter* MakeAcceptFilter();
  LocalSearchFilter* MakeRejectFilter();
  LocalSearchFilter* MakeVariableDomainFilter();
  IntVarLocalSearchFilter* MakeSumObjectiveFilter(
      const std::vector<IntVar*>& vars, IndexEvaluator2 values,
      Solver::LocalSearchFilterBound filter_enum);
  IntVarLocalSearchFilter* MakeSumObjectiveFilter(
      const std::vector<IntVar*>& vars,
      const std::vector<IntVar*>& secondary_vars, IndexEvaluator3 values,
      Solver::LocalSearchFilterBound filter_enum);

  void TopPeriodicCheck();
  int TopProgressPercent();

  void PushState();
  void PopState();

  int SearchDepth() const;

  int SearchLeftDepth() const;

  int SolveDepth() const;

  void SetBranchSelector(BranchSelector bs);

  DecisionBuilder* MakeApplyBranchSelector(BranchSelector bs);

  template <class T>
  void SaveAndSetValue(T* adr, T val) {
    if (*adr != val) {
      InternalSaveValue(adr);
      *adr = val;
    }
  }

  template <class T>
  void SaveAndAdd(T* adr, T val) {
    if (val != 0) {
      InternalSaveValue(adr);
      (*adr) += val;
    }
  }

  int64_t Rand64(int64_t size) {
    DCHECK_GT(size, 0);
    return absl::Uniform<int64_t>(random_, 0, size);
  }

  int32_t Rand32(int32_t size) {
    DCHECK_GT(size, 0);
    return absl::Uniform<int32_t>(random_, 0, size);
  }

  void ReSeed(int32_t seed) { random_.seed(seed); }

  void ExportProfilingOverview(const std::string& filename);

  // TODO(user): Merge demon and local search profiles.
  std::string LocalSearchProfile() const;
 
#if !defined(SWIG)
  ConstraintSolverStatistics GetConstraintSolverStatistics() const;
  LocalSearchStatistics GetLocalSearchStatistics() const;
#endif  // !defined(SWIG)

  bool CurrentlyInSolve() const;

  int constraints() const { return constraints_list_.size(); }

  /// Accepts the given model visitor.
  void Accept(ModelVisitor* visitor) const;
 
  Decision* balancing_decision() const { return balancing_decision_.get(); }

#if !defined(SWIG)
  void set_fail_intercept(std::function<void()> fail_intercept) {
    fail_intercept_ = std::move(fail_intercept);
  }
#endif  // !defined(SWIG)
  void clear_fail_intercept() { fail_intercept_ = nullptr; }
  DemonProfiler* demon_profiler() const { return demon_profiler_; }
  // TODO(user): Get rid of the following methods once fast local search is

  void SetUseFastLocalSearch(bool use_fast_local_search) {
    use_fast_local_search_ = use_fast_local_search;
  }
  bool UseFastLocalSearch() const { return use_fast_local_search_; }
  bool HasName(const PropagationBaseObject* object) const;
  Demon* RegisterDemon(Demon* demon);
  IntExpr* RegisterIntExpr(IntExpr* expr);
  IntVar* RegisterIntVar(IntVar* var);
  IntervalVar* RegisterIntervalVar(IntervalVar* var);

  Search* ActiveSearch() const;
  ModelCache* Cache() const;
  bool InstrumentsDemons() const;
  bool IsProfilingEnabled() const;
  bool IsLocalSearchProfilingEnabled() const;
  bool InstrumentsVariables() const;
  bool NameAllVariables() const;
  std::string model_name() const;
  PropagationMonitor* GetPropagationMonitor() const;
  void AddPropagationMonitor(PropagationMonitor* monitor);
  LocalSearchMonitor* GetLocalSearchMonitor() const;
  void AddLocalSearchMonitor(LocalSearchMonitor* monitor);
  void SetSearchContext(Search* search, absl::string_view search_context);
  std::string SearchContext() const;
  std::string SearchContext(const Search* search) const;
  /// Returns (or creates) an assignment representing the state of local search.
  // TODO(user): Investigate if this should be moved to Search.
  Assignment* GetOrCreateLocalSearchState();

  void ClearLocalSearchState() { local_search_state_.reset(nullptr); }

  std::vector<int64_t> tmp_vector_;
 
  friend class BaseIntExpr;
  friend class Constraint;
  friend class DemonProfiler;
  friend class FindOneNeighbor;
  friend class IntVar;
  friend class PropagationBaseObject;
  friend class Queue;
  friend class SearchMonitor;
  friend class SearchLimit;
  friend class RoutingModel;
  friend class LocalSearch;
  friend class LocalSearchProfiler;
 
#if !defined(SWIG)
  friend void InternalSaveBooleanVarValue(Solver*, IntVar*);
  template <class>
  friend class SimpleRevFIFO;
  template <class K, class V>
  friend class RevImmutableMultiMap;

  bool IsBooleanVar(IntExpr* expr, IntVar** inner_var, bool* is_negated) const;

  bool IsProduct(IntExpr* expr, IntExpr** inner_expr, int64_t* coefficient);
#endif  

  IntExpr* CastExpression(const IntVar* var) const;

  void FinishCurrentSearch();
  void RestartCurrentSearch();

  void ShouldFail() { should_fail_ = true; }
  void CheckFail() {
    if (!should_fail_) return;
    should_fail_ = false;
    Fail();
  }

  DecisionBuilder* MakeProfiledDecisionBuilderWrapper(DecisionBuilder* db);
 
 private:
  void Init();  
  void PushState(MarkerType t, const StateInfo& info);
  MarkerType PopState(StateInfo* info);
  void PushSentinel(int magic_code);
  void BacktrackToSentinel(int magic_code);
  void ProcessConstraints();
  bool BacktrackOneLevel(Decision** fail_decision);
  void JumpToSentinelWhenNested();
  void JumpToSentinel();
  void check_alloc_state();
  void FreezeQueue();
  void EnqueueVar(Demon* d);
  void EnqueueDelayedDemon(Demon* d);
  void ExecuteAll(const SimpleRevFIFO<Demon*>& demons);
  void EnqueueAll(const SimpleRevFIFO<Demon*>& demons);
  void UnfreezeQueue();
  void reset_action_on_fail();
  void set_action_on_fail(Action a);
  void set_variable_to_clean_on_fail(IntVar* v);
  void IncrementUncheckedSolutionCounter();
  bool IsUncheckedSolutionLimitReached();
 
  void InternalSaveValue(int* valptr);
  void InternalSaveValue(int64_t* valptr);
  void InternalSaveValue(uint64_t* valptr);
  void InternalSaveValue(double* valptr);
  void InternalSaveValue(bool* valptr);
  void InternalSaveValue(void** valptr);
  void InternalSaveValue(int64_t** valptr) {
    InternalSaveValue(reinterpret_cast<void**>(valptr));
  }
 
  BaseObject* SafeRevAlloc(BaseObject* ptr);
 
  int* SafeRevAllocArray(int* ptr);
  int64_t* SafeRevAllocArray(int64_t* ptr);
  uint64_t* SafeRevAllocArray(uint64_t* ptr);
  double* SafeRevAllocArray(double* ptr);
  BaseObject** SafeRevAllocArray(BaseObject** ptr);
  IntVar** SafeRevAllocArray(IntVar** ptr);
  IntExpr** SafeRevAllocArray(IntExpr** ptr);
  Constraint** SafeRevAllocArray(Constraint** ptr);
  void* UnsafeRevAllocAux(void* ptr);
  template <class T>
  T* UnsafeRevAlloc(T* ptr) {
    return reinterpret_cast<T*>(
        UnsafeRevAllocAux(reinterpret_cast<void*>(ptr)));
  }
  void** UnsafeRevAllocArrayAux(void** ptr);
  template <class T>
  T** UnsafeRevAllocArray(T** ptr) {
    return reinterpret_cast<T**>(
        UnsafeRevAllocArrayAux(reinterpret_cast<void**>(ptr)));
  }
 
  void InitCachedIntConstants();
  void InitCachedConstraint();

  Search* TopLevelSearch() const { return searches_.at(1); }
  Search* ParentSearch() const {
    const size_t search_size = searches_.size();
    DCHECK_GT(search_size, 1);
    return searches_[search_size - 2];
  }
 
  template <bool is_profile_active>
  Assignment* RunUncheckedLocalSearchInternal(
      const Assignment* initial_solution,
      LocalSearchFilterManager* filter_manager,
      LocalSearchOperator* ls_operator,
      const std::vector<SearchMonitor*>& monitors, RegularLimit* limit,
      absl::flat_hash_set<IntVar*>* touched);

  std::string GetName(const PropagationBaseObject* object);
  void SetName(const PropagationBaseObject* object, absl::string_view name);

  int GetNewIntVarIndex() { return num_int_vars_++; }

  bool IsADifference(IntExpr* expr, IntExpr** left, IntExpr** right);
 
  const std::string name_;
  const ConstraintSolverParameters parameters_;
  absl::flat_hash_map<const PropagationBaseObject*, std::string>
      propagation_object_names_;
  absl::flat_hash_map<const PropagationBaseObject*, IntegerCastInfo>
      cast_information_;
  absl::flat_hash_set<const Constraint*> cast_constraints_;
  const std::string empty_name_;
  std::unique_ptr<Queue> queue_;
  std::unique_ptr<Trail> trail_;
  std::vector<Constraint*> constraints_list_;
  std::vector<Constraint*> additional_constraints_list_;
  std::vector<int> additional_constraints_parent_list_;
  SolverState state_;
  int64_t branches_;
  int64_t fails_;
  int64_t decisions_;
  int64_t demon_runs_[kNumPriorities];
  int64_t neighbors_;
  int64_t filtered_neighbors_;
  int64_t accepted_neighbors_;
  std::string context_;
  OptimizationDirection optimization_direction_;
  std::unique_ptr<ClockTimer> timer_;
  std::vector<Search*> searches_;
  std::mt19937 random_;
  uint64_t fail_stamp_;
  std::unique_ptr<Decision> balancing_decision_;
  std::function<void()> fail_intercept_;
  DemonProfiler* const demon_profiler_;
  bool use_fast_local_search_;
  LocalSearchProfiler* const local_search_profiler_;
  std::unique_ptr<Assignment> local_search_state_;

  enum { MIN_CACHED_INT_CONST = -8, MAX_CACHED_INT_CONST = 8 };
  IntVar* cached_constants_[MAX_CACHED_INT_CONST + 1 - MIN_CACHED_INT_CONST];

  Constraint* true_constraint_;
  Constraint* false_constraint_;
 
  std::unique_ptr<Decision> fail_decision_;
  int constraint_index_;
  int additional_constraint_index_;
  int num_int_vars_;
 
  std::unique_ptr<ModelCache> model_cache_;
  std::unique_ptr<PropagationMonitor> propagation_monitor_;
  PropagationMonitor* print_trace_;
  std::unique_ptr<LocalSearchMonitor> local_search_monitor_;
  int anonymous_variable_index_;
  bool should_fail_;
 
  std::function<int64_t(int64_t, int64_t, int64_t)> penalty_callback_;
};
 
std::ostream& operator<<(std::ostream& out, const Solver* const s);  

inline int64_t Zero() { return 0; }

inline int64_t One() { return 1; }

class BaseObject {
 public:
  BaseObject() {}
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  BaseObject(const BaseObject&) = delete;
  BaseObject& operator=(const BaseObject&) = delete;
#endif
  virtual ~BaseObject() {}
  virtual std::string DebugString() const { return "BaseObject"; }
};
 
std::ostream& operator<<(std::ostream& out, const BaseObject* o);  

class PropagationBaseObject : public BaseObject {
 public:
  explicit PropagationBaseObject(Solver* const s) : solver_(s) {}
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  PropagationBaseObject(const PropagationBaseObject&) = delete;
  PropagationBaseObject& operator=(const PropagationBaseObject&) = delete;
#endif
  ~PropagationBaseObject() override {};
 
  std::string DebugString() const override {
    if (name().empty()) {
      return "PropagationBaseObject";
    } else {
      return absl::StrFormat("PropagationBaseObject: %s", name());
    }
  }
  Solver* solver() const { return solver_; }

  void FreezeQueue() { solver_->FreezeQueue(); }


  void UnfreezeQueue() { solver_->UnfreezeQueue(); }

  void EnqueueDelayedDemon(Demon* const d) { solver_->EnqueueDelayedDemon(d); }
  void EnqueueVar(Demon* const d) { solver_->EnqueueVar(d); }
  void ExecuteAll(const SimpleRevFIFO<Demon*>& demons);
  void EnqueueAll(const SimpleRevFIFO<Demon*>& demons);
 
#if !defined(SWIG)
  // This method sets a callback that will be called if a failure
  // happens during the propagation of the queue.
  void set_action_on_fail(Solver::Action a) {
    solver_->set_action_on_fail(std::move(a));
  }
#endif  // !defined(SWIG)

  void reset_action_on_fail() { solver_->reset_action_on_fail(); }

  void set_variable_to_clean_on_fail(IntVar* v) {
    solver_->set_variable_to_clean_on_fail(v);
  }

  virtual std::string name() const;
  void set_name(absl::string_view name);
  bool HasName() const;
  virtual std::string BaseName() const;
 
 private:
  Solver* const solver_;
};

class Decision : public BaseObject {
 public:
  Decision() {}
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  Decision(const Decision&) = delete;
  Decision& operator=(const Decision&) = delete;
#endif
  ~Decision() override {}

  virtual void Apply(Solver* s) = 0;

  virtual void Refute(Solver* s) = 0;
 
  std::string DebugString() const override { return "Decision"; }
  virtual void Accept(DecisionVisitor* visitor) const;
};

class DecisionVisitor : public BaseObject {
 public:
  DecisionVisitor() {}
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  DecisionVisitor(const DecisionVisitor&) = delete;
  DecisionVisitor& operator=(const DecisionVisitor&) = delete;
#endif
  ~DecisionVisitor() override {}
  virtual void VisitSetVariableValue(IntVar* var, int64_t value);
  virtual void VisitSplitVariableDomain(IntVar* var, int64_t value,
                                        bool start_with_lower_half);
  virtual void VisitScheduleOrPostpone(IntervalVar* var, int64_t est);
  virtual void VisitScheduleOrExpedite(IntervalVar* var, int64_t est);
  virtual void VisitRankFirstInterval(SequenceVar* sequence, int index);
  virtual void VisitRankLastInterval(SequenceVar* sequence, int index);
  virtual void VisitUnknownDecision();
};

class DecisionBuilder : public BaseObject {
 public:
  DecisionBuilder() {}
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  DecisionBuilder(const DecisionBuilder&) = delete;
  DecisionBuilder& operator=(const DecisionBuilder&) = delete;
#endif
  ~DecisionBuilder() override {}
  /// This is the main method of the decision builder class. It must
  /// return a decision (an instance of the class Decision). If it
  /// returns nullptr, this means that the decision builder has finished
  /// its work.
  virtual Decision* Next(Solver* s) = 0;
  std::string DebugString() const override;
#if !defined(SWIG)
  virtual void AppendMonitors(Solver* solver,
                              std::vector<SearchMonitor*>* extras);
  virtual void Accept(ModelVisitor* visitor) const;
#endif
  void set_name(absl::string_view name) { name_ = name; }
  std::string GetName() const;
 
 private:
  std::string name_;
};
 
#if !defined(SWIG)
class ProfiledDecisionBuilder : public DecisionBuilder {
 public:
  explicit ProfiledDecisionBuilder(DecisionBuilder* db);
  ~ProfiledDecisionBuilder() override {}
  const std::string& name() const { return name_; }
  double seconds() const { return seconds_; }
  Decision* Next(Solver* solver) override;
  std::string DebugString() const override;
  void AppendMonitors(Solver* solver,
                      std::vector<SearchMonitor*>* extras) override;
  void Accept(ModelVisitor* visitor) const override;
 
 private:
  DecisionBuilder* const db_;
  const std::string name_;
  SimpleCycleTimer timer_;
  double seconds_;
};
#endif


///   of the variables. The main concept is that demons are listeners that are
///   attached to the variables and listen to their modifications.
/// There are two methods:
///  - Run() is the actual method called when the demon is processed.
///  - priority() returns its priority. Standard priorities are slow, normal
///    or fast. "immediate" is reserved for variables and is treated separately.
class Demon : public BaseObject {
 public:
  Demon() : stamp_(uint64_t{0}) {}
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  Demon(const Demon&) = delete;
  Demon& operator=(const Demon&) = delete;
#endif
  ~Demon() override {}

  virtual void Run(Solver* s) = 0;

  virtual Solver::DemonPriority priority() const;
 
  std::string DebugString() const override;

  void inhibit(Solver* s);

  /// This method un-inhibits the demon that was previously inhibited.
  void desinhibit(Solver* s);
 
 private:
  friend class Queue;
  void set_stamp(int64_t stamp) { stamp_ = stamp; }
  uint64_t stamp() const { return stamp_; }
  uint64_t stamp_;
};

class OR_DLL ModelVisitor : public BaseObject {
 public:
  static const char kAbs[];
  static const char kAbsEqual[];
  static const char kAllDifferent[];
  static const char kAllowedAssignments[];
  static const char kAtMost[];
  static const char kIndexOf[];
  static const char kBetween[];
  static const char kConditionalExpr[];
  static const char kCircuit[];
  static const char kConvexPiecewise[];
  static const char kCountEqual[];
  static const char kCover[];
  static const char kCumulative[];
  static const char kDeviation[];
  static const char kDifference[];
  static const char kDisjunctive[];
  static const char kDistribute[];
  static const char kDivide[];
  static const char kDurationExpr[];
  static const char kElement[];
  static const char kLightElementEqual[];
  static const char kElementEqual[];
  static const char kEndExpr[];
  static const char kEquality[];
  static const char kFalseConstraint[];
  static const char kGlobalCardinality[];
  static const char kGreater[];
  static const char kGreaterOrEqual[];
  static const char kIntegerVariable[];
  static const char kIntervalBinaryRelation[];
  static const char kIntervalDisjunction[];
  static const char kIntervalUnaryRelation[];
  static const char kIntervalVariable[];
  static const char kInversePermutation[];
  static const char kIsBetween[];
  static const char kIsDifferent[];
  static const char kIsEqual[];
  static const char kIsGreater[];
  static const char kIsGreaterOrEqual[];
  static const char kIsLess[];
  static const char kIsLessOrEqual[];
  static const char kIsMember[];
  static const char kLess[];
  static const char kLessOrEqual[];
  static const char kLexLess[];
  static const char kLinkExprVar[];
  static const char kMapDomain[];
  static const char kMax[];
  static const char kMaxEqual[];
  static const char kMember[];
  static const char kMin[];
  static const char kMinEqual[];
  static const char kModulo[];
  static const char kNoCycle[];
  static const char kNonEqual[];
  static const char kNotBetween[];
  static const char kNotMember[];
  static const char kNullIntersect[];
  static const char kOpposite[];
  static const char kPack[];
  static const char kPathCumul[];
  static const char kDelayedPathCumul[];
  static const char kPerformedExpr[];
  static const char kPower[];
  static const char kProduct[];
  static const char kScalProd[];
  static const char kScalProdEqual[];
  static const char kScalProdGreaterOrEqual[];
  static const char kScalProdLessOrEqual[];
  static const char kSemiContinuous[];
  static const char kSequenceVariable[];
  static const char kSortingConstraint[];
  static const char kSquare[];
  static const char kStartExpr[];
  static const char kSum[];
  static const char kSumEqual[];
  static const char kSumGreaterOrEqual[];
  static const char kSumLessOrEqual[];
  static const char kTrace[];
  static const char kTransition[];
  static const char kTrueConstraint[];
  static const char kVarBoundWatcher[];
  static const char kVarValueWatcher[];

  static const char kCountAssignedItemsExtension[];
  static const char kCountUsedBinsExtension[];
  static const char kInt64ToBoolExtension[];
  static const char kInt64ToInt64Extension[];
  static const char kObjectiveExtension[];
  static const char kSearchLimitExtension[];
  static const char kUsageEqualVariableExtension[];
 
  static const char kUsageLessConstantExtension[];
  static const char kVariableGroupExtension[];
  static const char kVariableUsageLessConstantExtension[];
  static const char kWeightedSumOfAssignedEqualVariableExtension[];

  static const char kActiveArgument[];
  static const char kAssumePathsArgument[];
  static const char kBranchesLimitArgument[];
  static const char kCapacityArgument[];
  static const char kCardsArgument[];
  static const char kCoefficientsArgument[];
  static const char kCountArgument[];
  static const char kCumulativeArgument[];
  static const char kCumulsArgument[];
  static const char kDemandsArgument[];
  static const char kDurationMaxArgument[];
  static const char kDurationMinArgument[];
  static const char kEarlyCostArgument[];
  static const char kEarlyDateArgument[];
  static const char kEndMaxArgument[];
  static const char kEndMinArgument[];
  static const char kEndsArgument[];
  static const char kExpressionArgument[];
  static const char kFailuresLimitArgument[];
  static const char kFinalStatesArgument[];
  static const char kFixedChargeArgument[];
  static const char kIndex2Argument[];
  static const char kIndex3Argument[];
  static const char kIndexArgument[];
  static const char kInitialState[];
  static const char kIntervalArgument[];
  static const char kIntervalsArgument[];
  static const char kLateCostArgument[];
  static const char kLateDateArgument[];
  static const char kLeftArgument[];
  static const char kMaxArgument[];
  static const char kMaximizeArgument[];
  static const char kMinArgument[];
  static const char kModuloArgument[];
  static const char kNextsArgument[];
  static const char kOptionalArgument[];
  static const char kPartialArgument[];
  static const char kPositionXArgument[];
  static const char kPositionYArgument[];
  static const char kRangeArgument[];
  static const char kRelationArgument[];
  static const char kRightArgument[];
  static const char kSequenceArgument[];
  static const char kSequencesArgument[];
  static const char kSizeArgument[];
  static const char kSizeXArgument[];
  static const char kSizeYArgument[];
  static const char kSmartTimeCheckArgument[];
  static const char kSolutionLimitArgument[];
  static const char kStartMaxArgument[];
  static const char kStartMinArgument[];
  static const char kStartsArgument[];
  static const char kStepArgument[];
  static const char kTargetArgument[];
  static const char kTimeLimitArgument[];
  static const char kTransitsArgument[];
  static const char kTuplesArgument[];
  static const char kValueArgument[];
  static const char kValuesArgument[];
  static const char kVariableArgument[];
  static const char kVarsArgument[];
  static const char kEvaluatorArgument[];

  static const char kMirrorOperation[];
  static const char kRelaxedMaxOperation[];
  static const char kRelaxedMinOperation[];
  static const char kSumOperation[];
  static const char kDifferenceOperation[];
  static const char kProductOperation[];
  static const char kStartSyncOnStartOperation[];
  static const char kStartSyncOnEndOperation[];
  static const char kTraceOperation[];
 
  ~ModelVisitor() override;


  virtual void BeginVisitModel(const std::string& type_name);
  virtual void EndVisitModel(const std::string& type_name);
  virtual void BeginVisitConstraint(const std::string& type_name,
                                    const Constraint* constraint);
  virtual void EndVisitConstraint(const std::string& type_name,
                                  const Constraint* constraint);
  virtual void BeginVisitExtension(const std::string& type);
  virtual void EndVisitExtension(const std::string& type);
  virtual void BeginVisitIntegerExpression(const std::string& type_name,
                                           const IntExpr* expr);
  virtual void EndVisitIntegerExpression(const std::string& type_name,
                                         const IntExpr* expr);
  virtual void VisitIntegerVariable(const IntVar* variable, IntExpr* delegate);
  virtual void VisitIntegerVariable(const IntVar* variable,
                                    const std::string& operation, int64_t value,
                                    IntVar* delegate);
  virtual void VisitIntervalVariable(const IntervalVar* variable,
                                     const std::string& operation,
                                     int64_t value, IntervalVar* delegate);
  virtual void VisitSequenceVariable(const SequenceVar* variable);

  virtual void VisitIntegerArgument(const std::string& arg_name, int64_t value);
  virtual void VisitIntegerArrayArgument(const std::string& arg_name,
                                         const std::vector<int64_t>& values);
  virtual void VisitIntegerMatrixArgument(const std::string& arg_name,
                                          const IntTupleSet& tuples);

  virtual void VisitIntegerExpressionArgument(const std::string& arg_name,
                                              IntExpr* argument);
 
  virtual void VisitIntegerVariableArrayArgument(
      const std::string& arg_name, const std::vector<IntVar*>& arguments);

  virtual void VisitIntervalArgument(const std::string& arg_name,
                                     IntervalVar* argument);
 
  virtual void VisitIntervalArrayArgument(
      const std::string& arg_name, const std::vector<IntervalVar*>& arguments);
  virtual void VisitSequenceArgument(const std::string& arg_name,
                                     SequenceVar* argument);
 
  virtual void VisitSequenceArrayArgument(
      const std::string& arg_name, const std::vector<SequenceVar*>& arguments);
#if !defined(SWIG)
  virtual void VisitIntegerVariableEvaluatorArgument(
      const std::string& arg_name, const Solver::Int64ToIntVar& arguments);

  void VisitInt64ToBoolExtension(Solver::IndexFilter1 filter, int64_t index_min,
                                 int64_t index_max);
  void VisitInt64ToInt64Extension(const Solver::IndexEvaluator1& eval,
                                  int64_t index_min, int64_t index_max);
  void VisitInt64ToInt64AsArray(const Solver::IndexEvaluator1& eval,
                                const std::string& arg_name, int64_t index_max);
#endif  // #if !defined(SWIG)
};

class Constraint : public PropagationBaseObject {
 public:
  explicit Constraint(Solver* const solver) : PropagationBaseObject(solver) {}
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  Constraint(const Constraint&) = delete;
  Constraint& operator=(const Constraint&) = delete;
#endif
  ~Constraint() override {}

  virtual void Post() = 0;

  virtual void InitialPropagate() = 0;
  std::string DebugString() const override;

  void PostAndPropagate();

  virtual void Accept(ModelVisitor* visitor) const;

  bool IsCastConstraint() const;

  virtual IntVar* Var();
};

class CastConstraint : public Constraint {
 public:
  CastConstraint(Solver* const solver, IntVar* const target_var)
      : Constraint(solver), target_var_(target_var) {
    CHECK(target_var != nullptr);
  }
  ~CastConstraint() override {}
 
  IntVar* target_var() const { return target_var_; }
 
 protected:
  IntVar* const target_var_;
};

class SearchMonitor : public BaseObject {
 public:
  static constexpr int kNoProgress = -1;
 
  explicit SearchMonitor(Solver* const s) : solver_(s) {}
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  SearchMonitor(const SearchMonitor&) = delete;
  SearchMonitor& operator=(const SearchMonitor&) = delete;
#endif
  ~SearchMonitor() override {}
  virtual void EnterSearch();

  virtual void RestartSearch();

  virtual void ExitSearch();

  virtual void BeginNextDecision(DecisionBuilder* b);

  virtual void EndNextDecision(DecisionBuilder* b, Decision* d);

  virtual void ApplyDecision(Decision* d);

  virtual void RefuteDecision(Decision* d);

  virtual void AfterDecision(Decision* d, bool apply);


  virtual void BeginFail();

  virtual void EndFail();

  /// Before the initial propagation.
  virtual void BeginInitialPropagation();

  virtual void EndInitialPropagation();

  virtual bool AcceptSolution();


  /// is false, then search will stop there.
  virtual bool AtSolution();

  virtual void NoMoreSolutions();

  virtual bool LocalOptimum();

  virtual bool AcceptDelta(Assignment* delta, Assignment* deltadelta);

  virtual void AcceptNeighbor();

  virtual void AcceptUncheckedNeighbor();

  virtual bool IsUncheckedSolutionLimitReached() { return false; }

  virtual void PeriodicCheck();

  virtual int ProgressPercent() { return kNoProgress; }

  virtual void Accept(ModelVisitor* visitor) const;

  virtual void Install();
 
  Solver* solver() const { return solver_; }
 
 protected:
  void ListenToEvent(Solver::MonitorEvent event);
 
 private:
  Solver* const solver_;
};

template <class T>
class Rev {
 public:
  explicit Rev(const T& val) : stamp_(0), value_(val) {}
 
  const T& Value() const { return value_; }
 
  void SetValue(Solver* const s, const T& val) {
    if (val != value_) {
      if (stamp_ < s->stamp()) {
        s->SaveValue(&value_);
        stamp_ = s->stamp();
      }
      value_ = val;
    }
  }
 
 private:
  uint64_t stamp_;
  T value_;
};

template <class T>
class NumericalRev : public Rev<T> {
 public:
  explicit NumericalRev(const T& val) : Rev<T>(val) {}
 
  void Add(Solver* const s, const T& to_add) {
    this->SetValue(s, this->Value() + to_add);
  }
 
  void Incr(Solver* const s) { Add(s, 1); }
 
  void Decr(Solver* const s) { Add(s, -1); }
};

template <class T>
class RevArray {
 public:
  RevArray(int size, const T& val)
      : stamps_(new uint64_t[size]), values_(new T[size]), size_(size) {
    for (int i = 0; i < size; ++i) {
      stamps_[i] = 0;
      values_[i] = val;
    }
  }
 
  ~RevArray() {}
 
  int64_t size() const { return size_; }
 
  const T& Value(int index) const { return values_[index]; }
 
#if !defined(SWIG)
  const T& operator[](int index) const { return values_[index]; }
#endif
 
  void SetValue(Solver* const s, int index, const T& val) {
    DCHECK_LT(index, size_);
    if (val != values_[index]) {
      if (stamps_[index] < s->stamp()) {
        s->SaveValue(&values_[index]);
        stamps_[index] = s->stamp();
      }
      values_[index] = val;
    }
  }
 
 private:
  std::unique_ptr<uint64_t[]> stamps_;
  std::unique_ptr<T[]> values_;
  const int size_;
};

template <class T>
class NumericalRevArray : public RevArray<T> {
 public:
  NumericalRevArray(int size, const T& val) : RevArray<T>(size, val) {}
 
  void Add(Solver* const s, int index, const T& to_add) {
    this->SetValue(s, index, this->Value(index) + to_add);
  }
 
  void Incr(Solver* const s, int index) { Add(s, index, 1); }
 
  void Decr(Solver* const s, int index) { Add(s, index, -1); }
};

///   - listening to events modifying its bounds
///   - casting it into a variable (instance of IntVar)
class IntExpr : public PropagationBaseObject {
 public:
  explicit IntExpr(Solver* const s) : PropagationBaseObject(s) {}
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  IntExpr(const IntExpr&) = delete;
  IntExpr& operator=(const IntExpr&) = delete;
#endif
  ~IntExpr() override {}
 
  virtual int64_t Min() const = 0;
  virtual void SetMin(int64_t m) = 0;
  virtual int64_t Max() const = 0;
  virtual void SetMax(int64_t m) = 0;

  virtual void Range(int64_t* l, int64_t* u) {
    *l = Min();
    *u = Max();
  }
  virtual void SetRange(int64_t l, int64_t u) {
    SetMin(l);
    SetMax(u);
  }


  virtual void SetValue(int64_t v) { SetRange(v, v); }

  virtual bool Bound() const { return (Min() == Max()); }


  virtual bool IsVar() const { return false; }

  /// Creates a variable from the expression.
  virtual IntVar* Var() = 0;

  /// resulting var. If the expression is already a variable, then it
  /// will set the name of the expression, possibly overwriting it.
  /// This is just a shortcut to Var() followed by set_name().
  IntVar* VarWithName(const std::string& name);

  virtual void WhenRange(Demon* d) = 0;
  void WhenRange(Solver::Closure closure) {
    WhenRange(solver()->MakeClosureDemon(std::move(closure)));
  }
 
#if !defined(SWIG)
  void WhenRange(Solver::Action action) {
    WhenRange(solver()->MakeActionDemon(std::move(action)));
  }
#endif  // SWIG

  virtual void Accept(ModelVisitor* visitor) const;
};



/// IntVar* current_var;
/// std::unique_ptr<IntVarIterator> it(current_var->MakeHoleIterator(false));
/// for (const int64_t hole : InitAndGetValues(it)) {
///   /// use the hole
/// }
 
class IntVarIterator : public BaseObject {
 public:
  ~IntVarIterator() override {}

  virtual void Init() = 0;

  virtual bool Ok() const = 0;

  virtual int64_t Value() const = 0;

  virtual void Next() = 0;

  std::string DebugString() const override { return "IntVar::Iterator"; }
};
 
#ifndef SWIG
/// same iterator instance isn't being iterated on in multiple places
/// simultaneously.
class InitAndGetValues {
 public:
  explicit InitAndGetValues(IntVarIterator* it)
      : it_(it), begin_was_called_(false) {
    it_->Init();
  }
  struct Iterator;
 
  Iterator begin() {
    if (DEBUG_MODE) {
      DCHECK(!begin_was_called_);
      begin_was_called_ = true;
    }
    return Iterator::Begin(it_);
  }
  Iterator end() { return Iterator::End(it_); }
 
  struct Iterator {
    static Iterator Begin(IntVarIterator* it) {
      return Iterator(it, /*is_end=*/false);
    }
    static Iterator End(IntVarIterator* it) {
      return Iterator(it, /*is_end=*/true);
    }
 
    int64_t operator*() const {
      DCHECK(it->Ok());
      return it->Value();
    }
    Iterator& operator++() {
      DCHECK(it->Ok());
      it->Next();
      return *this;
    }
    bool operator!=(const Iterator& other) const {
      DCHECK(other.it == it);
      DCHECK(other.is_end);
      return it->Ok();
    }
 
   private:
    Iterator(IntVarIterator* it, bool is_end) : it(it), is_end(is_end) {}
 
    IntVarIterator* const it;
    const bool is_end;
  };
 
 private:
  IntVarIterator* const it_;
  bool begin_was_called_;
};
#endif  // SWIG

class IntVar : public IntExpr {
 public:
  explicit IntVar(Solver* s);
  IntVar(Solver* s, const std::string& name);
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  IntVar(const IntVar&) = delete;
  IntVar& operator=(const IntVar&) = delete;
#endif
 
  ~IntVar() override {};
 
  bool IsVar() const override { return true; }
  IntVar* Var() override { return this; }


  virtual int64_t Value() const = 0;

  /// This method removes the value 'v' from the domain of the variable.
  virtual void RemoveValue(int64_t v) = 0;


  /// This method removes the interval 'l' .. 'u' from the domain of
  /// the variable. It assumes that 'l' <= 'u'.
  virtual void RemoveInterval(int64_t l, int64_t u) = 0;

  /// This method remove the values from the domain of the variable.
  virtual void RemoveValues(const std::vector<int64_t>& values);

  virtual void SetValues(const std::vector<int64_t>& values);

  virtual void WhenBound(Demon* d) = 0;

  /// This method attaches a closure that will be awakened when the
  /// variable is bound.
  void WhenBound(Solver::Closure closure) {
    WhenBound(solver()->MakeClosureDemon(std::move(closure)));
  }
 
#if !defined(SWIG)
  void WhenBound(Solver::Action action) {
    WhenBound(solver()->MakeActionDemon(std::move(action)));
  }
#endif  // SWIG

  virtual void WhenDomain(Demon* d) = 0;

  void WhenDomain(Solver::Closure closure) {
    WhenDomain(solver()->MakeClosureDemon(std::move(closure)));
  }
#if !defined(SWIG)
  void WhenDomain(Solver::Action action) {
    WhenDomain(solver()->MakeActionDemon(std::move(action)));
  }
#endif  // SWIG

  virtual uint64_t Size() const = 0;

  virtual bool Contains(int64_t v) const = 0;

  virtual IntVarIterator* MakeHoleIterator(bool reversible) const = 0;

  virtual IntVarIterator* MakeDomainIterator(bool reversible) const = 0;

  virtual int64_t OldMin() const = 0;

  virtual int64_t OldMax() const = 0;
 
  virtual int VarType() const;

  void Accept(ModelVisitor* visitor) const override;

  virtual IntVar* IsEqual(int64_t constant) = 0;
  virtual IntVar* IsDifferent(int64_t constant) = 0;
  virtual IntVar* IsGreaterOrEqual(int64_t constant) = 0;
  virtual IntVar* IsLessOrEqual(int64_t constant) = 0;

  int index() const { return index_; }
 
 private:
  const int index_;
};

class SolutionCollector : public SearchMonitor {
 public:
  SolutionCollector(Solver* solver, const Assignment* assignment);
  explicit SolutionCollector(Solver* solver);
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  SolutionCollector(const SolutionCollector&) = delete;
  SolutionCollector& operator=(const SolutionCollector&) = delete;
#endif
 
  ~SolutionCollector() override;
  void Install() override;
  std::string DebugString() const override { return "SolutionCollector"; }

  void Add(IntVar* var);
  void Add(const std::vector<IntVar*>& vars);
  void Add(IntervalVar* var);
  void Add(const std::vector<IntervalVar*>& vars);
  void Add(SequenceVar* var);
  void Add(const std::vector<SequenceVar*>& vars);
  void AddObjective(IntVar* objective);
  void AddObjectives(const std::vector<IntVar*>& objectives);

  void EnterSearch() override;

  int solution_count() const;

  bool has_solution() const;

  Assignment* solution(int n) const;

  Assignment* last_solution_or_null() const;

  int64_t wall_time(int n) const;

  int64_t branches(int n) const;

  int64_t failures(int n) const;

  int64_t objective_value(int n) const;

  int64_t ObjectiveValueFromIndex(int n, int index) const;

  int64_t Value(int n, IntVar* var) const;

  int64_t StartValue(int n, IntervalVar* var) const;

  int64_t EndValue(int n, IntervalVar* var) const;

  int64_t DurationValue(int n, IntervalVar* var) const;

  int64_t PerformedValue(int n, IntervalVar* var) const;

  const std::vector<int>& ForwardSequence(int n, SequenceVar* var) const;
  const std::vector<int>& BackwardSequence(int n, SequenceVar* var) const;
  const std::vector<int>& Unperformed(int n, SequenceVar* var) const;
 
 protected:
  struct SolutionData {
    Assignment* solution;
    int64_t time;
    int64_t branches;
    int64_t failures;
    int64_t ObjectiveValue() const;
    int64_t ObjectiveValueFromIndex(int index) const;
    bool operator<(const SolutionData& other) const;
  };

  void PushSolution();
  void Push(const SolutionData& data) { solution_data_.push_back(data); }
  void PopSolution();
  SolutionData BuildSolutionDataForCurrentState();
  void FreeSolution(Assignment* solution);
  void check_index(int n) const;
 
  std::unique_ptr<Assignment> prototype_;
  std::vector<SolutionData> solution_data_;
  std::vector<Assignment*> recycle_solutions_;
#if !defined(SWIG)
  std::vector<std::unique_ptr<Assignment>> solution_pool_;
#endif  // SWIG
};
 
// Base objective monitor class. All metaheuristics and metaheuristic combiners
// derive from this.
class BaseObjectiveMonitor : public SearchMonitor {
 public:
  explicit BaseObjectiveMonitor(Solver* solver) : SearchMonitor(solver) {}
  ~BaseObjectiveMonitor() override {}
#ifndef SWIG
  BaseObjectiveMonitor(const BaseObjectiveMonitor&) = delete;
  BaseObjectiveMonitor& operator=(const BaseObjectiveMonitor&) = delete;
#endif  // SWIG
  virtual IntVar* ObjectiveVar(int index) const = 0;
  virtual IntVar* MinimizationVar(int index) const = 0;
  virtual int64_t Step(int index) const = 0;
  virtual bool Maximize(int index) const = 0;
  virtual int64_t BestValue(int index) const = 0;
  virtual int Size() const = 0;
  bool is_active() const { return is_active_; }
  void set_active(bool is_active) { is_active_ = is_active; }
 
 private:
  bool is_active_ = true;
};
 
// Base atomic objective monitor class. All non-composite metaheuristics derive
// from this.
class ObjectiveMonitor : public BaseObjectiveMonitor {
 public:
  ObjectiveMonitor(Solver* solver, const std::vector<bool>& maximize,
                   std::vector<IntVar*> vars, std::vector<int64_t> steps);
  ~ObjectiveMonitor() override {}
#ifndef SWIG
  ObjectiveMonitor(const ObjectiveMonitor&) = delete;
  ObjectiveMonitor& operator=(const ObjectiveMonitor&) = delete;
#endif  // SWIG
  IntVar* ObjectiveVar(int index) const override {
    return objective_vars_[index];
  }
  IntVar* MinimizationVar(int index) const override {
    return minimization_vars_[index];
  }
  int64_t Step(int index) const override { return steps_[index]; }
  bool Maximize(int index) const override {
    return ObjectiveVar(index) != MinimizationVar(index);
  }
  int64_t BestValue(int index) const override {
    return Maximize(index) ? CapOpp(BestInternalValue(index))
                           : BestInternalValue(index);
  }
  int Size() const override { return objective_vars_.size(); }
  void EnterSearch() override;
  bool AtSolution() override;
  bool AcceptDelta(Assignment* delta, Assignment* deltadelta) override;
  void Accept(ModelVisitor* visitor) const override;
 
 protected:
  const std::vector<IntVar*>& objective_vars() const { return objective_vars_; }
  const std::vector<IntVar*>& minimization_vars() const {
    return minimization_vars_;
  }
  int64_t BestInternalValue(int index) const { return best_values_[index]; }
  int64_t CurrentInternalValue(int index) const {
    return current_values_[index];
  }
  void SetCurrentInternalValue(int index, int64_t value) {
    current_values_[index] = value;
  }
  template <typename T>
  void MakeMinimizationVarsLessOrEqualWithSteps(const T& upper_bounds) {
    if (Size() == 1) {
      MinimizationVar(0)->SetMax(CapSub(upper_bounds(0), Step(0)));
    } else {
      Solver* const solver = this->solver();
      for (int i = 0; i < Size(); ++i) {
        upper_bounds_[i] = solver->MakeIntConst(upper_bounds(i));
      }
      solver->AddConstraint(solver->MakeLexicalLessOrEqualWithOffsets(
          minimization_vars_, upper_bounds_, steps_));
    }
  }
  template <typename T>
  IntVar* MakeMinimizationVarsLessOrEqualWithStepsStatus(
      const T& upper_bounds) {
    Solver* const solver = this->solver();
    IntVar* status = solver->MakeBoolVar();
    if (Size() == 1) {
      solver->AddConstraint(solver->MakeIsLessOrEqualCstCt(
          MinimizationVar(0), CapSub(upper_bounds(0), Step(0)), status));
    } else {
      for (int i = 0; i < Size(); ++i) {
        upper_bounds_[i] = solver->MakeIntConst(upper_bounds(i));
      }
      solver->AddConstraint(solver->MakeIsLexicalLessOrEqualWithOffsetsCt(
          minimization_vars_, upper_bounds_, steps_, status));
    }
    return status;
  }
  bool CurrentInternalValuesAreConstraining() const;
 
  bool found_initial_solution_;
 
 private:
  friend class Solver;
  const std::vector<IntVar*> objective_vars_;
  std::vector<IntVar*> minimization_vars_;
  std::vector<IntVar*> upper_bounds_;
  std::vector<int64_t> steps_;
  std::vector<int64_t> best_values_;
  std::vector<int64_t> current_values_;
};

class OptimizeVar : public ObjectiveMonitor {
 public:
  OptimizeVar(Solver* solver, bool maximize, IntVar* var, int64_t step);
  // Specifies a lexicographic objective. Each objective is specified in
  // decreasing order with the corresponding direction and step.
  OptimizeVar(Solver* solver, const std::vector<bool>& maximize,
              std::vector<IntVar*> vars, std::vector<int64_t> steps);
#ifndef SWIG
  ~OptimizeVar() override {}
#endif  // SIWG


  int64_t best() const { return BestValue(0); }

  IntVar* var() const { return Size() == 0 ? nullptr : ObjectiveVar(0); }

  void BeginNextDecision(DecisionBuilder* db) override;
  void RefuteDecision(Decision* d) override;
  bool AtSolution() override;
  bool AcceptSolution() override;
  virtual std::string Name() const;
  std::string DebugString() const override;
 
  void ApplyBound();
};

class SearchLimit : public SearchMonitor {
 public:
  explicit SearchLimit(Solver* const s) : SearchMonitor(s), crossed_(false) {}
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  SearchLimit(const SearchLimit&) = delete;
  SearchLimit& operator=(const SearchLimit&) = delete;
#endif
  ~SearchLimit() override;

  bool crossed() const { return crossed_; }

  bool Check() { return CheckWithOffset(absl::ZeroDuration()); }
  virtual bool CheckWithOffset(absl::Duration offset) = 0;

  virtual void Init() = 0;

  virtual void Copy(const SearchLimit* limit) = 0;

  virtual SearchLimit* MakeClone() const = 0;

  void EnterSearch() override;
  void BeginNextDecision(DecisionBuilder* b) override;
  void PeriodicCheck() override;
  void RefuteDecision(Decision* d) override;
  std::string DebugString() const override {
    return absl::StrFormat("SearchLimit(crossed = %i)", crossed_);
  }
  void Install() override;
 
 private:
  void TopPeriodicCheck();
 
  bool crossed_;
};

class RegularLimit : public SearchLimit {
 public:
  RegularLimit(Solver* s, absl::Duration time, int64_t branches,
               int64_t failures, int64_t solutions, bool smart_time_check,
               bool cumulative);
  ~RegularLimit() override;
  void Copy(const SearchLimit* limit) override;
  SearchLimit* MakeClone() const override;
  RegularLimit* MakeIdenticalClone() const;
  bool CheckWithOffset(absl::Duration offset) override;
  void Init() override;
  void ExitSearch() override;
  void UpdateLimits(absl::Duration time, int64_t branches, int64_t failures,
                    int64_t solutions);
  absl::Duration duration_limit() const { return duration_limit_; }
  int64_t wall_time() const {
    return duration_limit_ == absl::InfiniteDuration()
               ? kint64max
               : absl::ToInt64Milliseconds(duration_limit());
  }
  int64_t branches() const { return branches_; }
  int64_t failures() const { return failures_; }
  int64_t solutions() const { return solutions_; }
  bool IsUncheckedSolutionLimitReached() override;
  int ProgressPercent() override;
  std::string DebugString() const override;
  void Install() override;
 
  absl::Time AbsoluteSolverDeadline() const {
    return solver_time_at_limit_start_ + duration_limit_;
  }
 
  void Accept(ModelVisitor* visitor) const override;
 
 private:
  bool CheckTime(absl::Duration offset);
  absl::Duration TimeElapsed();
  static int64_t GetPercent(int64_t value, int64_t offset, int64_t total) {
    return (total > 0 && total < kint64max) ? 100 * (value - offset) / total
                                            : -1;
  }
 
  absl::Duration duration_limit_;
  absl::Time solver_time_at_limit_start_;
  absl::Duration last_time_elapsed_;
  int64_t check_count_;
  int64_t next_check_;
  bool smart_time_check_;
  int64_t branches_;
  int64_t branches_offset_;
  int64_t failures_;
  int64_t failures_offset_;
  int64_t solutions_;
  int64_t solutions_offset_;

  /// depending on context:
  /// - within a search, it's an offset to be subtracted from the current value
  /// - outside of search, it's the amount consumed in previous searches
  bool cumulative_;
};
 
// Limit based on the improvement rate of 'objective_var' or a lexicographic
// objective composed of 'objective_vars'.
// This limit proceeds in two stages:
// 1) During the phase of the search in which the objective is strictly
// improving, a threshold value is computed as the minimum improvement rate of
// the objective, based on the 'improvement_rate_coefficient' and
// 'improvement_rate_solutions_distance' parameters.
// 2) Then, if the search continues beyond this phase of strict improvement, the
// limit stops the search when the improvement rate of the objective gets below
// this threshold value.
class ImprovementSearchLimit : public SearchLimit {
 public:
  ImprovementSearchLimit(Solver* solver, IntVar* objective_var, bool maximize,
                         double objective_scaling_factor,
                         double objective_offset,
                         double improvement_rate_coefficient,
                         int improvement_rate_solutions_distance);
  ImprovementSearchLimit(Solver* solver, std::vector<IntVar*> objective_vars,
                         std::vector<bool> maximize,
                         std::vector<double> objective_scaling_factors,
                         std::vector<double> objective_offsets,
                         double improvement_rate_coefficient,
                         int improvement_rate_solutions_distance);
  ~ImprovementSearchLimit() override;
  void Copy(const SearchLimit* limit) override;
  SearchLimit* MakeClone() const override;
  bool CheckWithOffset(absl::Duration offset) override;
  bool AtSolution() override;
  void Init() override;
  void Install() override;
 
 private:
  std::vector<IntVar*> objective_vars_;
  std::vector<bool> maximize_;
  std::vector<double> objective_scaling_factors_;
  std::vector<double> objective_offsets_;
  double improvement_rate_coefficient_;
  int improvement_rate_solutions_distance_;
 
  std::vector<double> best_objectives_;
  // clang-format off
  std::vector<std::deque<std::pair<double, int64_t> > > improvements_;
  // clang-format on
  std::vector<double> thresholds_;
  bool objective_updated_;
  bool gradient_stage_;
};


class OR_DLL IntervalVar : public PropagationBaseObject {
 public:
  static const int64_t kMinValidValue;
  static const int64_t kMaxValidValue;
  IntervalVar(Solver* const solver, const std::string& name)
      : PropagationBaseObject(solver) {
    set_name(name);
  }
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  IntervalVar(const IntervalVar&) = delete;
  IntervalVar& operator=(const IntervalVar&) = delete;
#endif
  ~IntervalVar() override {}

  virtual int64_t StartMin() const = 0;
  virtual int64_t StartMax() const = 0;
  virtual void SetStartMin(int64_t m) = 0;
  virtual void SetStartMax(int64_t m) = 0;
  virtual void SetStartRange(int64_t mi, int64_t ma) = 0;
  virtual int64_t OldStartMin() const = 0;
  virtual int64_t OldStartMax() const = 0;
  virtual void WhenStartRange(Demon* d) = 0;
  void WhenStartRange(Solver::Closure closure) {
    WhenStartRange(solver()->MakeClosureDemon(std::move(closure)));
  }
#if !defined(SWIG)
  void WhenStartRange(Solver::Action action) {
    WhenStartRange(solver()->MakeActionDemon(std::move(action)));
  }
#endif  // SWIG
  virtual void WhenStartBound(Demon* d) = 0;
  void WhenStartBound(Solver::Closure closure) {
    WhenStartBound(solver()->MakeClosureDemon(std::move(closure)));
  }
#if !defined(SWIG)
  void WhenStartBound(Solver::Action action) {
    WhenStartBound(solver()->MakeActionDemon(std::move(action)));
  }
#endif  // SWIG

  virtual int64_t DurationMin() const = 0;
  virtual int64_t DurationMax() const = 0;
  virtual void SetDurationMin(int64_t m) = 0;
  virtual void SetDurationMax(int64_t m) = 0;
  virtual void SetDurationRange(int64_t mi, int64_t ma) = 0;
  virtual int64_t OldDurationMin() const = 0;
  virtual int64_t OldDurationMax() const = 0;
  virtual void WhenDurationRange(Demon* d) = 0;
  void WhenDurationRange(Solver::Closure closure) {
    WhenDurationRange(solver()->MakeClosureDemon(std::move(closure)));
  }
#if !defined(SWIG)
  void WhenDurationRange(Solver::Action action) {
    WhenDurationRange(solver()->MakeActionDemon(std::move(action)));
  }
#endif  // SWIG
  virtual void WhenDurationBound(Demon* d) = 0;
  void WhenDurationBound(Solver::Closure closure) {
    WhenDurationBound(solver()->MakeClosureDemon(std::move(closure)));
  }
#if !defined(SWIG)
  void WhenDurationBound(Solver::Action action) {
    WhenDurationBound(solver()->MakeActionDemon(std::move(action)));
  }
#endif  // SWIG

  virtual int64_t EndMin() const = 0;
  virtual int64_t EndMax() const = 0;
  virtual void SetEndMin(int64_t m) = 0;
  virtual void SetEndMax(int64_t m) = 0;
  virtual void SetEndRange(int64_t mi, int64_t ma) = 0;
  virtual int64_t OldEndMin() const = 0;
  virtual int64_t OldEndMax() const = 0;
  virtual void WhenEndRange(Demon* d) = 0;
  void WhenEndRange(Solver::Closure closure) {
    WhenEndRange(solver()->MakeClosureDemon(std::move(closure)));
  }
#if !defined(SWIG)
  void WhenEndRange(Solver::Action action) {
    WhenEndRange(solver()->MakeActionDemon(std::move(action)));
  }
#endif  // SWIG
  virtual void WhenEndBound(Demon* d) = 0;
  void WhenEndBound(Solver::Closure closure) {
    WhenEndBound(solver()->MakeClosureDemon(std::move(closure)));
  }
#if !defined(SWIG)
  void WhenEndBound(Solver::Action action) {
    WhenEndBound(solver()->MakeActionDemon(std::move(action)));
  }
#endif  // SWIG

  /// These methods query, set, and watch the performed status of the
  /// interval var.
  virtual bool MustBePerformed() const = 0;
  virtual bool MayBePerformed() const = 0;
  bool CannotBePerformed() const { return !MayBePerformed(); }
  bool IsPerformedBound() const {
    return MustBePerformed() || !MayBePerformed();
  }
  virtual void SetPerformed(bool val) = 0;
  virtual bool WasPerformedBound() const = 0;
  virtual void WhenPerformedBound(Demon* d) = 0;
  void WhenPerformedBound(Solver::Closure closure) {
    WhenPerformedBound(solver()->MakeClosureDemon(std::move(closure)));
  }
#if !defined(SWIG)
  void WhenPerformedBound(Solver::Action action) {
    WhenPerformedBound(solver()->MakeActionDemon(std::move(action)));
  }
#endif  // SWIG

  void WhenAnything(Demon* d);
  void WhenAnything(Solver::Closure closure) {
    WhenAnything(solver()->MakeClosureDemon(std::move(closure)));
  }
#if !defined(SWIG)
  /// Attaches an action awakened when anything about this interval changes.
  void WhenAnything(Solver::Action action) {
    WhenAnything(solver()->MakeActionDemon(std::move(action)));
  }
#endif  // SWIG

  virtual IntExpr* StartExpr() = 0;
  virtual IntExpr* DurationExpr() = 0;
  virtual IntExpr* EndExpr() = 0;
  virtual IntExpr* PerformedExpr() = 0;
  /// and duration of the interval var. If the interval var is
  /// unperformed, they will return the unperformed_value.
  virtual IntExpr* SafeStartExpr(int64_t unperformed_value) = 0;
  virtual IntExpr* SafeDurationExpr(int64_t unperformed_value) = 0;
  virtual IntExpr* SafeEndExpr(int64_t unperformed_value) = 0;

  virtual void Accept(ModelVisitor* visitor) const = 0;
};


/// returns the list of interval variables that can be ranked first or
/// last; and RankFirst/RankNotFirst/RankLast/RankNotLast, which can be
/// used to create the search decision.
class SequenceVar : public PropagationBaseObject {
 public:
  SequenceVar(Solver* s, const std::vector<IntervalVar*>& intervals,
              const std::vector<IntVar*>& nexts, const std::string& name);
 
  ~SequenceVar() override;
 
  std::string DebugString() const override;
 
#if !defined(SWIG)

  void DurationRange(int64_t* dmin, int64_t* dmax) const;

  void HorizonRange(int64_t* hmin, int64_t* hmax) const;

  void ActiveHorizonRange(int64_t* hmin, int64_t* hmax) const;

  void ComputeStatistics(int* ranked, int* not_ranked, int* unperformed) const;
#endif  // !defined(SWIG)

  void RankFirst(int index);

  /// Indicates that the index_th interval var will not be ranked first
  /// of all currently unranked interval vars.
  void RankNotFirst(int index);

  void RankLast(int index);

  void RankNotLast(int index);

  void ComputePossibleFirstsAndLasts(std::vector<int>* possible_firsts,
                                     std::vector<int>* possible_lasts);

  void RankSequence(const std::vector<int>& rank_first,
                    const std::vector<int>& rank_last,
                    const std::vector<int>& unperformed);

  /// contain none.
  /// 'unperformed' will contains all such interval variables.
  /// rank_first and rank_last represents different directions.
  /// rank_first[0] corresponds to the first interval of the sequence.
  /// rank_last[0] corresponds to the last interval of the sequence.
  void FillSequence(std::vector<int>* rank_first, std::vector<int>* rank_last,
                    std::vector<int>* unperformed) const;

  IntervalVar* Interval(int index) const;

  IntVar* Next(int index) const;

  int64_t size() const { return intervals_.size(); }

  virtual void Accept(ModelVisitor* visitor) const;
 
 private:
  int ComputeForwardFrontier();
  int ComputeBackwardFrontier();
  void UpdatePrevious() const;
 
  const std::vector<IntervalVar*> intervals_;
  const std::vector<IntVar*> nexts_;
  mutable std::vector<int> previous_;
};
 
class AssignmentElement {
 public:
  AssignmentElement() : activated_(true) {}
 
  void Activate() { activated_ = true; }
  void Deactivate() { activated_ = false; }
  bool Activated() const { return activated_; }
 
 private:
  bool activated_;
};
 
class IntVarElement : public AssignmentElement {
 public:
  IntVarElement();
  explicit IntVarElement(IntVar* var);
  void Reset(IntVar* var);
  IntVarElement* Clone();
  void Copy(const IntVarElement& element);
  IntVar* Var() const { return var_; }
  void Store() {
    min_ = var_->Min();
    max_ = var_->Max();
  }
  void Restore() {
    if (var_ != nullptr) {
      var_->SetRange(min_, max_);
    }
  }
  void LoadFromProto(const IntVarAssignment& int_var_assignment_proto);
  void WriteToProto(IntVarAssignment* int_var_assignment_proto) const;
 
  int64_t Min() const { return min_; }
  void SetMin(int64_t m) { min_ = m; }
  int64_t Max() const { return max_; }
  void SetMax(int64_t m) { max_ = m; }
  int64_t Value() const {
    DCHECK_EQ(min_, max_);
    // Get the value from an unbound int var assignment element.
    return min_;
  }
  bool Bound() const { return (max_ == min_); }
  void SetRange(int64_t l, int64_t u) {
    min_ = l;
    max_ = u;
  }
  void SetValue(int64_t v) {
    min_ = v;
    max_ = v;
  }
  std::string DebugString() const;
 
  bool operator==(const IntVarElement& element) const;
  bool operator!=(const IntVarElement& element) const {
    return !(*this == element);
  }
 
 private:
  IntVar* var_;
  int64_t min_;
  int64_t max_;
};
 
class IntervalVarElement : public AssignmentElement {
 public:
  IntervalVarElement();
  explicit IntervalVarElement(IntervalVar* var);
  void Reset(IntervalVar* var);
  IntervalVarElement* Clone();
  void Copy(const IntervalVarElement& element);
  IntervalVar* Var() const { return var_; }
  void Store();
  void Restore();
  void LoadFromProto(
      const IntervalVarAssignment& interval_var_assignment_proto);
  void WriteToProto(IntervalVarAssignment* interval_var_assignment_proto) const;
 
  int64_t StartMin() const { return start_min_; }
  int64_t StartMax() const { return start_max_; }
  int64_t StartValue() const {
    CHECK_EQ(start_max_, start_min_);
    return start_max_;
  }
  int64_t DurationMin() const { return duration_min_; }
  int64_t DurationMax() const { return duration_max_; }
  int64_t DurationValue() const {
    CHECK_EQ(duration_max_, duration_min_);
    return duration_max_;
  }
  int64_t EndMin() const { return end_min_; }
  int64_t EndMax() const { return end_max_; }
  int64_t EndValue() const {
    CHECK_EQ(end_max_, end_min_);
    return end_max_;
  }
  int64_t PerformedMin() const { return performed_min_; }
  int64_t PerformedMax() const { return performed_max_; }
  int64_t PerformedValue() const {
    CHECK_EQ(performed_max_, performed_min_);
    return performed_max_;
  }
  void SetStartMin(int64_t m) { start_min_ = m; }
  void SetStartMax(int64_t m) { start_max_ = m; }
  void SetStartRange(int64_t mi, int64_t ma) {
    start_min_ = mi;
    start_max_ = ma;
  }
  void SetStartValue(int64_t v) {
    start_min_ = v;
    start_max_ = v;
  }
  void SetDurationMin(int64_t m) { duration_min_ = m; }
  void SetDurationMax(int64_t m) { duration_max_ = m; }
  void SetDurationRange(int64_t mi, int64_t ma) {
    duration_min_ = mi;
    duration_max_ = ma;
  }
  void SetDurationValue(int64_t v) {
    duration_min_ = v;
    duration_max_ = v;
  }
  void SetEndMin(int64_t m) { end_min_ = m; }
  void SetEndMax(int64_t m) { end_max_ = m; }
  void SetEndRange(int64_t mi, int64_t ma) {
    end_min_ = mi;
    end_max_ = ma;
  }
  void SetEndValue(int64_t v) {
    end_min_ = v;
    end_max_ = v;
  }
  void SetPerformedMin(int64_t m) { performed_min_ = m; }
  void SetPerformedMax(int64_t m) { performed_max_ = m; }
  void SetPerformedRange(int64_t mi, int64_t ma) {
    performed_min_ = mi;
    performed_max_ = ma;
  }
  void SetPerformedValue(int64_t v) {
    performed_min_ = v;
    performed_max_ = v;
  }
  bool Bound() const {
    return (start_min_ == start_max_ && duration_min_ == duration_max_ &&
            end_min_ == end_max_ && performed_min_ == performed_max_);
  }
  std::string DebugString() const;
  bool operator==(const IntervalVarElement& element) const;
  bool operator!=(const IntervalVarElement& element) const {
    return !(*this == element);
  }
 
 private:
  int64_t start_min_;
  int64_t start_max_;
  int64_t duration_min_;
  int64_t duration_max_;
  int64_t end_min_;
  int64_t end_max_;
  int64_t performed_min_;
  int64_t performed_max_;
  IntervalVar* var_;
};


///   - the forward sequence. That is the list of interval variables
///     ranked first in the sequence.  The first element of the backward
///     sequence is the first interval in the sequence variable.
///   - the backward sequence. That is the list of interval variables
///     ranked last in the sequence. The first element of the backward
///     sequence is the last interval in the sequence variable.
///   - The list of unperformed interval variables.
///  Furthermore, if all performed variables are ranked, then by
///  convention, the forward_sequence will contain all such variables
///  and the backward_sequence will be empty.
class SequenceVarElement : public AssignmentElement {
 public:
  SequenceVarElement();
  explicit SequenceVarElement(SequenceVar* var);
  void Reset(SequenceVar* var);
  SequenceVarElement* Clone();
  void Copy(const SequenceVarElement& element);
  SequenceVar* Var() const { return var_; }
  void Store();
  void Restore();
  void LoadFromProto(
      const SequenceVarAssignment& sequence_var_assignment_proto);
  void WriteToProto(SequenceVarAssignment* sequence_var_assignment_proto) const;
 
  const std::vector<int>& ForwardSequence() const;
  const std::vector<int>& BackwardSequence() const;
  const std::vector<int>& Unperformed() const;
  void SetSequence(const std::vector<int>& forward_sequence,
                   const std::vector<int>& backward_sequence,
                   const std::vector<int>& unperformed);
  void SetForwardSequence(const std::vector<int>& forward_sequence);
  void SetBackwardSequence(const std::vector<int>& backward_sequence);
  void SetUnperformed(const std::vector<int>& unperformed);
  bool Bound() const {
    return forward_sequence_.size() + unperformed_.size() == var_->size();
  }
 
  std::string DebugString() const;
 
  bool operator==(const SequenceVarElement& element) const;
  bool operator!=(const SequenceVarElement& element) const {
    return !(*this == element);
  }
 
 private:
  bool CheckClassInvariants();
 
  SequenceVar* var_;
  std::vector<int> forward_sequence_;
  std::vector<int> backward_sequence_;
  std::vector<int> unperformed_;
};
 
template <class V, class E>
class AssignmentContainer {
 public:
  AssignmentContainer() {}
  E* Add(V* var) {
    CHECK(var != nullptr);
    int index = -1;
    if (!Find(var, &index)) {
      return FastAdd(var);
    } else {
      return &elements_[index];
    }
  }
  E* FastAdd(V* var) {
    DCHECK(var != nullptr);
    elements_.emplace_back(var);
    return &elements_.back();
  }
  E* AddAtPosition(V* var, int position) {
    elements_[position].Reset(var);
    return &elements_[position];
  }
  void Clear() {
    elements_.clear();
    if (!elements_map_.empty()) {  
      elements_map_.clear();
    }
  }
  void Resize(size_t size) { elements_.resize(size); }
  bool Empty() const { return elements_.empty(); }
  void CopyIntersection(const AssignmentContainer<V, E>& container) {
    for (int i = 0; i < container.elements_.size(); ++i) {
      const E& element = container.elements_[i];
      const V* const var = element.Var();
      int index = -1;
      if (i < elements_.size() && elements_[i].Var() == var) {
        index = i;
      } else if (!Find(var, &index)) {
        continue;
      }
      DCHECK_GE(index, 0);
      E* const local_element = &elements_[index];
      local_element->Copy(element);
      if (element.Activated()) {
        local_element->Activate();
      } else {
        local_element->Deactivate();
      }
    }
  }

  void Copy(const AssignmentContainer<V, E>& container) {
    Clear();
    for (int i = 0; i < container.elements_.size(); ++i) {
      const E& element = container.elements_[i];
      FastAdd(element.Var())->Copy(element);
    }
  }
  bool Contains(const V* const var) const {
    int index;
    return Find(var, &index);
  }
  E* MutableElement(const V* const var) {
    E* const element = MutableElementOrNull(var);
    DCHECK(element != nullptr)
        << "Unknown variable " << var->DebugString() << " in solution";
    return element;
  }
  E* MutableElementOrNull(const V* const var) {
    int index = -1;
    if (Find(var, &index)) {
      return MutableElement(index);
    }
    return nullptr;
  }
  const E& Element(const V* const var) const {
    const E* const element = ElementPtrOrNull(var);
    DCHECK(element != nullptr)
        << "Unknown variable " << var->DebugString() << " in solution";
    return *element;
  }
  const E* ElementPtrOrNull(const V* const var) const {
    int index = -1;
    if (Find(var, &index)) {
      return &Element(index);
    }
    return nullptr;
  }
  const std::vector<E>& elements() const { return elements_; }
  E* MutableElement(int index) { return &elements_[index]; }
  const E& Element(int index) const { return elements_[index]; }
  int Size() const { return elements_.size(); }
  void Store() {
    for (E& element : elements_) {
      element.Store();
    }
  }
  void Restore() {
    for (E& element : elements_) {
      if (element.Activated()) {
        element.Restore();
      }
    }
  }
  bool AreAllElementsBound() const {
    for (const E& element : elements_) {
      if (!element.Bound()) return false;
    }
    return true;
  }

  bool operator==(const AssignmentContainer<V, E>& container) const {
    if (Size() != container.Size()) {
      return false;
    }
    EnsureMapIsUpToDate();

    /// Do not use the hash_map::== operator! It
    /// compares both content and how the map is hashed (e.g., number of
    /// buckets). This is not what we want.
    for (const E& element : container.elements_) {
      const int position =
          gtl::FindWithDefault(elements_map_, element.Var(), -1);
      if (position < 0 || elements_[position] != element) {
        return false;
      }
    }
    return true;
  }
  bool operator!=(const AssignmentContainer<V, E>& container) const {
    return !(*this == container);
  }
 
 private:
  void EnsureMapIsUpToDate() const {
    absl::flat_hash_map<const V*, int>* map =
        const_cast<absl::flat_hash_map<const V*, int>*>(&elements_map_);
    for (int i = map->size(); i < elements_.size(); ++i) {
      (*map)[elements_[i].Var()] = i;
    }
  }
  bool Find(const V* const var, int* index) const {
    const size_t kMaxSizeForLinearAccess = 11;
    if (Size() <= kMaxSizeForLinearAccess) {
      /// hash table.
      for (int i = 0; i < elements_.size(); ++i) {
        if (var == elements_[i].Var()) {
          *index = i;
          return true;
        }
      }
      return false;
    } else {
      EnsureMapIsUpToDate();
      DCHECK_EQ(elements_map_.size(), elements_.size());
      return gtl::FindCopy(elements_map_, var, index);
    }
  }
 
  std::vector<E> elements_;
  absl::flat_hash_map<const V*, int> elements_map_;
};

class Assignment : public PropagationBaseObject {
 public:
  typedef AssignmentContainer<IntVar, IntVarElement> IntContainer;
  typedef AssignmentContainer<IntervalVar, IntervalVarElement>
      IntervalContainer;
  typedef AssignmentContainer<SequenceVar, SequenceVarElement>
      SequenceContainer;
 
  explicit Assignment(Solver* solver);
  explicit Assignment(const Assignment* copy);
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  Assignment(const Assignment&) = delete;
  Assignment& operator=(const Assignment&) = delete;
#endif
 
  ~Assignment() override;
 
  void Clear();
  bool Empty() const {
    return int_var_container_.Empty() && interval_var_container_.Empty() &&
           sequence_var_container_.Empty();
  }
  int Size() const {
    return NumIntVars() + NumIntervalVars() + NumSequenceVars();
  }
  int NumIntVars() const { return int_var_container_.Size(); }
  int NumIntervalVars() const { return interval_var_container_.Size(); }
  int NumSequenceVars() const { return sequence_var_container_.Size(); }
  void Store();
  void Restore();

  bool Load(const std::string& filename);
#if !defined(SWIG)
  bool Load(File* file);
#endif  
  void Load(const AssignmentProto& assignment_proto);
  bool Save(const std::string& filename) const;
#if !defined(SWIG)
  bool Save(File* file) const;
#endif  // #if !defined(SWIG)
  void Save(AssignmentProto* assignment_proto) const;
 
  void AddObjective(IntVar* const v) { AddObjectives({v}); }
  void AddObjectives(const std::vector<IntVar*>& vars) {
    // Objective can only set once.
    DCHECK(!HasObjective());
    objective_elements_.reserve(vars.size());
    for (IntVar* const var : vars) {
      if (var != nullptr) {
        objective_elements_.emplace_back(var);
      }
    }
  }
  void ClearObjective() { objective_elements_.clear(); }
  int NumObjectives() const { return objective_elements_.size(); }
  IntVar* Objective() const { return ObjectiveFromIndex(0); }
  IntVar* ObjectiveFromIndex(int index) const {
    return HasObjectiveFromIndex(index) ? objective_elements_[index].Var()
                                        : nullptr;
  }
  bool HasObjective() const { return !objective_elements_.empty(); }
  bool HasObjectiveFromIndex(int index) const {
    return index < objective_elements_.size();
  }
  int64_t ObjectiveMin() const { return ObjectiveMinFromIndex(0); }
  int64_t ObjectiveMax() const { return ObjectiveMaxFromIndex(0); }
  int64_t ObjectiveValue() const { return ObjectiveValueFromIndex(0); }
  bool ObjectiveBound() const { return ObjectiveBoundFromIndex(0); }
  void SetObjectiveMin(int64_t m) { SetObjectiveMinFromIndex(0, m); }
  void SetObjectiveMax(int64_t m) { SetObjectiveMaxFromIndex(0, m); }
  void SetObjectiveValue(int64_t value) {
    SetObjectiveValueFromIndex(0, value);
  }
  void SetObjectiveRange(int64_t l, int64_t u) {
    SetObjectiveRangeFromIndex(0, l, u);
  }
  int64_t ObjectiveMinFromIndex(int index) const {
    return HasObjectiveFromIndex(index) ? objective_elements_[index].Min() : 0;
  }
  int64_t ObjectiveMaxFromIndex(int index) const {
    return HasObjectiveFromIndex(index) ? objective_elements_[index].Max() : 0;
  }
  int64_t ObjectiveValueFromIndex(int index) const {
    return HasObjectiveFromIndex(index) ? objective_elements_[index].Value()
                                        : 0;
  }
  bool ObjectiveBoundFromIndex(int index) const {
    return HasObjectiveFromIndex(index) ? objective_elements_[index].Bound()
                                        : true;
  }
  void SetObjectiveMinFromIndex(int index, int64_t m) {
    if (HasObjectiveFromIndex(index)) {
      objective_elements_[index].SetMin(m);
    }
  }
  void SetObjectiveMaxFromIndex(int index, int64_t m) {
    if (HasObjectiveFromIndex(index)) {
      objective_elements_[index].SetMax(m);
    }
  }
  void SetObjectiveValueFromIndex(int index, int64_t value) {
    if (HasObjectiveFromIndex(index)) {
      objective_elements_[index].SetValue(value);
    }
  }
  void SetObjectiveRangeFromIndex(int index, int64_t l, int64_t u) {
    if (HasObjectiveFromIndex(index)) {
      objective_elements_[index].SetRange(l, u);
    }
  }
 
  IntVarElement* Add(IntVar* var);
  void Add(const std::vector<IntVar*>& vars);
  IntVarElement* FastAdd(IntVar* var);
  int64_t Min(const IntVar* var) const;
  int64_t Max(const IntVar* var) const;
  int64_t Value(const IntVar* var) const;
  bool Bound(const IntVar* var) const;
  void SetMin(const IntVar* var, int64_t m);
  void SetMax(const IntVar* var, int64_t m);
  void SetRange(const IntVar* var, int64_t l, int64_t u);
  void SetValue(const IntVar* var, int64_t value);
 
  IntervalVarElement* Add(IntervalVar* var);
  void Add(const std::vector<IntervalVar*>& vars);
  IntervalVarElement* FastAdd(IntervalVar* var);
  int64_t StartMin(const IntervalVar* var) const;
  int64_t StartMax(const IntervalVar* var) const;
  int64_t StartValue(const IntervalVar* var) const;
  int64_t DurationMin(const IntervalVar* var) const;
  int64_t DurationMax(const IntervalVar* var) const;
  int64_t DurationValue(const IntervalVar* var) const;
  int64_t EndMin(const IntervalVar* var) const;
  int64_t EndMax(const IntervalVar* var) const;
  int64_t EndValue(const IntervalVar* var) const;
  int64_t PerformedMin(const IntervalVar* var) const;
  int64_t PerformedMax(const IntervalVar* var) const;
  int64_t PerformedValue(const IntervalVar* var) const;
  void SetStartMin(const IntervalVar* var, int64_t m);
  void SetStartMax(const IntervalVar* var, int64_t m);
  void SetStartRange(const IntervalVar* var, int64_t mi, int64_t ma);
  void SetStartValue(const IntervalVar* var, int64_t value);
  void SetDurationMin(const IntervalVar* var, int64_t m);
  void SetDurationMax(const IntervalVar* var, int64_t m);
  void SetDurationRange(const IntervalVar* var, int64_t mi, int64_t ma);
  void SetDurationValue(const IntervalVar* var, int64_t value);
  void SetEndMin(const IntervalVar* var, int64_t m);
  void SetEndMax(const IntervalVar* var, int64_t m);
  void SetEndRange(const IntervalVar* var, int64_t mi, int64_t ma);
  void SetEndValue(const IntervalVar* var, int64_t value);
  void SetPerformedMin(const IntervalVar* var, int64_t m);
  void SetPerformedMax(const IntervalVar* var, int64_t m);
  void SetPerformedRange(const IntervalVar* var, int64_t mi, int64_t ma);
  void SetPerformedValue(const IntervalVar* var, int64_t value);
 
  SequenceVarElement* Add(SequenceVar* var);
  void Add(const std::vector<SequenceVar*>& vars);

  /// Adds without checking if the variable had been previously added.
  SequenceVarElement* FastAdd(SequenceVar* var);
  const std::vector<int>& ForwardSequence(const SequenceVar* var) const;
  const std::vector<int>& BackwardSequence(const SequenceVar* var) const;
  const std::vector<int>& Unperformed(const SequenceVar* var) const;
  void SetSequence(const SequenceVar* var,
                   const std::vector<int>& forward_sequence,
                   const std::vector<int>& backward_sequence,
                   const std::vector<int>& unperformed);
  void SetForwardSequence(const SequenceVar* var,
                          const std::vector<int>& forward_sequence);
  void SetBackwardSequence(const SequenceVar* var,
                           const std::vector<int>& backward_sequence);
  void SetUnperformed(const SequenceVar* var,
                      const std::vector<int>& unperformed);
 
  void Activate(const IntVar* var);
  void Deactivate(const IntVar* var);
  bool Activated(const IntVar* var) const;
 
  void Activate(const IntervalVar* var);
  void Deactivate(const IntervalVar* var);
  bool Activated(const IntervalVar* var) const;
 
  void Activate(const SequenceVar* var);
  void Deactivate(const SequenceVar* var);
  bool Activated(const SequenceVar* var) const;
 
  void ActivateObjective() { ActivateObjectiveFromIndex(0); }
  void DeactivateObjective() { DeactivateObjectiveFromIndex(0); }
  bool ActivatedObjective() const { return ActivatedObjectiveFromIndex(0); }
  void ActivateObjectiveFromIndex(int index) {
    if (HasObjectiveFromIndex(index)) {
      objective_elements_[index].Activate();
    }
  }
  void DeactivateObjectiveFromIndex(int index) {
    if (HasObjectiveFromIndex(index)) {
      objective_elements_[index].Deactivate();
    }
  }
  bool ActivatedObjectiveFromIndex(int index) const {
    return HasObjectiveFromIndex(index) ? objective_elements_[index].Activated()
                                        : true;
  }
 
  std::string DebugString() const override;
 
  bool AreAllElementsBound() const {
    return int_var_container_.AreAllElementsBound() &&
           interval_var_container_.AreAllElementsBound() &&
           sequence_var_container_.AreAllElementsBound();
  }
 
  bool Contains(const IntVar* var) const;
  bool Contains(const IntervalVar* var) const;
  bool Contains(const SequenceVar* var) const;
  void CopyIntersection(const Assignment* assignment);
  void Copy(const Assignment* assignment);
 
  // TODO(user): Add element iterators to avoid exposing container class.
  const IntContainer& IntVarContainer() const { return int_var_container_; }
  IntContainer* MutableIntVarContainer() { return &int_var_container_; }
  const IntervalContainer& IntervalVarContainer() const {
    return interval_var_container_;
  }
  IntervalContainer* MutableIntervalVarContainer() {
    return &interval_var_container_;
  }
  const SequenceContainer& SequenceVarContainer() const {
    return sequence_var_container_;
  }
  SequenceContainer* MutableSequenceVarContainer() {
    return &sequence_var_container_;
  }
  bool operator==(const Assignment& assignment) const {
    return int_var_container_ == assignment.int_var_container_ &&
           interval_var_container_ == assignment.interval_var_container_ &&
           sequence_var_container_ == assignment.sequence_var_container_ &&
           objective_elements_ == assignment.objective_elements_;
  }
  bool operator!=(const Assignment& assignment) const {
    return !(*this == assignment);
  }
 
 private:
  IntContainer int_var_container_;
  IntervalContainer interval_var_container_;
  SequenceContainer sequence_var_container_;
  std::vector<IntVarElement> objective_elements_;
};
 
std::ostream& operator<<(std::ostream& out,
                         const Assignment& assignment);  


/// all IntVars in "target_vars", with the values of the variables set according
/// to the corresponding values of "source_vars" in "source_assignment".
/// source_vars and target_vars must have the same number of elements.
/// The source and target assignments can belong to different Solvers.
void SetAssignmentFromAssignment(Assignment* target_assignment,
                                 const std::vector<IntVar*>& target_vars,
                                 const Assignment* source_assignment,
                                 const std::vector<IntVar*>& source_vars);
 
class Pack : public Constraint {
 public:
  Pack(Solver* s, const std::vector<IntVar*>& vars, int number_of_bins);
 
  ~Pack() override;


  void AddWeightedSumLessOrEqualConstantDimension(
      const std::vector<int64_t>& weights, const std::vector<int64_t>& bounds);

  /// This dimension imposes that for all bins b, the weighted sum
  /// (weights->Run(i)) of all objects i assigned to 'b' is less or
  /// equal to 'bounds[b]'. Ownership of the callback is transferred to
  /// the pack constraint.
  void AddWeightedSumLessOrEqualConstantDimension(
      Solver::IndexEvaluator1 weights, const std::vector<int64_t>& bounds);


  /// equal to 'bounds[b]'. Ownership of the callback is transferred to
  /// the pack constraint.
  void AddWeightedSumLessOrEqualConstantDimension(
      Solver::IndexEvaluator2 weights, const std::vector<int64_t>& bounds);

  void AddWeightedSumEqualVarDimension(const std::vector<int64_t>& weights,
                                       const std::vector<IntVar*>& loads);


  void AddWeightedSumEqualVarDimension(Solver::IndexEvaluator2 weights,
                                       const std::vector<IntVar*>& loads);


  void AddSumVariableWeightsLessOrEqualConstantDimension(
      const std::vector<IntVar*>& usage, const std::vector<int64_t>& capacity);

  void AddWeightedSumOfAssignedDimension(const std::vector<int64_t>& weights,
                                         IntVar* cost_var);

  /// This dimension links 'count_var' to the actual number of bins used in the
  /// pack.
  void AddCountUsedBinDimension(IntVar* count_var);

  void AddCountAssignedItemsDimension(IntVar* count_var);
 
  void Post() override;
  void ClearAll();
  void PropagateDelayed();
  void InitialPropagate() override;
  void Propagate();
  void OneDomain(int var_index);
  std::string DebugString() const override;
  bool IsUndecided(int var_index, int bin_index) const;
  void SetImpossible(int var_index, int bin_index);
  void Assign(int var_index, int bin_index);
  bool IsAssignedStatusKnown(int var_index) const;
  bool IsPossible(int var_index, int bin_index) const;
  IntVar* AssignVar(int var_index, int bin_index) const;
  void SetAssigned(int var_index);
  void SetUnassigned(int var_index);
  void RemoveAllPossibleFromBin(int bin_index);
  void AssignAllPossibleToBin(int bin_index);
  void AssignFirstPossibleToBin(int bin_index);
  void AssignAllRemainingItems();
  void UnassignAllRemainingItems();
  void Accept(ModelVisitor* visitor) const override;
 
 private:
  bool IsInProcess() const;
  const std::vector<IntVar*> vars_;
  const int bins_;
  std::vector<Dimension*> dims_;
  std::unique_ptr<RevBitMatrix> unprocessed_;
  std::vector<std::vector<int>> forced_;
  std::vector<std::vector<int>> removed_;
  std::vector<IntVarIterator*> holes_;
  uint64_t stamp_;
  Demon* demon_;
  std::vector<std::pair<int, int>> to_set_;
  std::vector<std::pair<int, int>> to_unset_;
  bool in_process_;
};
 
class DisjunctiveConstraint : public Constraint {
 public:
  DisjunctiveConstraint(Solver* s, const std::vector<IntervalVar*>& intervals,
                        const std::string& name);
 
#ifndef SWIG
  // This type is neither copyable nor movable.
  DisjunctiveConstraint(const DisjunctiveConstraint&) = delete;
  DisjunctiveConstraint& operator=(const DisjunctiveConstraint&) = delete;
#endif
 
  ~DisjunctiveConstraint() override;

  virtual SequenceVar* MakeSequenceVar() = 0;

  void SetTransitionTime(Solver::IndexEvaluator2 transition_time);
 
  int64_t TransitionTime(int before_index, int after_index) {
    DCHECK(transition_time_);
    return transition_time_(before_index, after_index);
  }
 
#if !defined(SWIG)
  virtual const std::vector<IntVar*>& nexts() const = 0;
  virtual const std::vector<IntVar*>& actives() const = 0;
  virtual const std::vector<IntVar*>& time_cumuls() const = 0;
  virtual const std::vector<IntVar*>& time_slacks() const = 0;
#endif  // !defined(SWIG)
 
 protected:
  const std::vector<IntervalVar*> intervals_;
  Solver::IndexEvaluator2 transition_time_;
};

class SolutionPool : public BaseObject {
 public:
  SolutionPool() {}
  ~SolutionPool() override {}

  virtual void Initialize(Assignment* assignment) = 0;

  virtual void RegisterNewSolution(Assignment* assignment) = 0;

  virtual void GetNextSolution(Assignment* assignment) = 0;


  virtual bool SyncNeeded(Assignment* local_assignment) = 0;
};
}  // namespace operations_research
 
#endif  // OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_