1 // Copyright 2010-2021 Google LLC 2 // Licensed under the Apache License, Version 2.0 (the "License"); 3 // you may not use this file except in compliance with the License. 4 // You may obtain a copy of the License at 5 // 6 // http://www.apache.org/licenses/LICENSE-2.0 7 // 8 // Unless required by applicable law or agreed to in writing, software 9 // distributed under the License is distributed on an "AS IS" BASIS, 10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11 // See the License for the specific language governing permissions and 12 // limitations under the License. 13 14 #ifndef OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_FILTERS_H_ 15 #define OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_FILTERS_H_ 16 17 #include <utility> 18 #include <vector> 19 20 #include "ortools/base/integral_types.h" 21 #include "ortools/constraint_solver/constraint_solver.h" 22 #include "ortools/constraint_solver/constraint_solveri.h" 23 #include "ortools/constraint_solver/routing.h" 24 #include "ortools/constraint_solver/routing_lp_scheduling.h" 25 #include "ortools/constraint_solver/routing_parameters.pb.h" 26 #include "ortools/util/bitset.h" 27 28 namespace operations_research { 29 30 /// Returns a filter ensuring that max active vehicles constraints are enforced. 31 IntVarLocalSearchFilter* MakeMaxActiveVehiclesFilter( 32 const RoutingModel& routing_model); 33 34 /// Returns a filter ensuring that node disjunction constraints are enforced. 35 IntVarLocalSearchFilter* MakeNodeDisjunctionFilter( 36 const RoutingModel& routing_model, bool filter_cost); 37 38 /// Returns a filter computing vehicle amortized costs. 39 IntVarLocalSearchFilter* MakeVehicleAmortizedCostFilter( 40 const RoutingModel& routing_model); 41 42 /// Returns a filter ensuring type regulation constraints are enforced. 43 IntVarLocalSearchFilter* MakeTypeRegulationsFilter( 44 const RoutingModel& routing_model); 45 46 /// Returns a filter enforcing pickup and delivery constraints for the given 47 /// pair of nodes and given policies. 48 IntVarLocalSearchFilter* MakePickupDeliveryFilter( 49 const RoutingModel& routing_model, const RoutingModel::IndexPairs& pairs, 50 const std::vector<RoutingModel::PickupAndDeliveryPolicy>& vehicle_policies); 51 52 /// Returns a filter checking that vehicle variable domains are respected. 53 IntVarLocalSearchFilter* MakeVehicleVarFilter( 54 const RoutingModel& routing_model); 55 56 /// Returns a filter handling dimension costs and constraints. 57 IntVarLocalSearchFilter* MakePathCumulFilter( 58 const RoutingDimension& dimension, 59 const RoutingSearchParameters& parameters, 60 bool propagate_own_objective_value, bool filter_objective_cost, 61 bool can_use_lp = true); 62 63 /// Returns a filter handling dimension cumul bounds. 64 IntVarLocalSearchFilter* MakeCumulBoundsPropagatorFilter( 65 const RoutingDimension& dimension); 66 67 /// Returns a filter checking global linear constraints and costs. 68 IntVarLocalSearchFilter* MakeGlobalLPCumulFilter( 69 GlobalDimensionCumulOptimizer* optimizer, 70 GlobalDimensionCumulOptimizer* mp_optimizer, bool filter_objective_cost); 71 72 /// Returns a filter checking the feasibility and cost of the resource 73 /// assignment. 74 LocalSearchFilter* MakeResourceAssignmentFilter( 75 LocalDimensionCumulOptimizer* optimizer, 76 LocalDimensionCumulOptimizer* mp_optimizer, 77 bool propagate_own_objective_value, bool filter_objective_cost); 78 79 /// Returns a filter checking the current solution using CP propagation. 80 IntVarLocalSearchFilter* MakeCPFeasibilityFilter(RoutingModel* routing_model); 81 82 /// Appends dimension-based filters to the given list of filters using a path 83 /// state. 84 void AppendLightWeightDimensionFilters( 85 const PathState* path_state, 86 const std::vector<RoutingDimension*>& dimensions, 87 std::vector<LocalSearchFilterManager::FilterEvent>* filters); 88 89 void AppendDimensionCumulFilters( 90 const std::vector<RoutingDimension*>& dimensions, 91 const RoutingSearchParameters& parameters, bool filter_objective_cost, 92 bool filter_light_weight_unary_dimensions, 93 std::vector<LocalSearchFilterManager::FilterEvent>* filters); 94 95 /// Generic path-based filter class. 96 97 class BasePathFilter : public IntVarLocalSearchFilter { 98 public: 99 BasePathFilter(const std::vector<IntVar*>& nexts, int next_domain_size); ~BasePathFilter()100 ~BasePathFilter() override {} 101 bool Accept(const Assignment* delta, const Assignment* deltadelta, 102 int64_t objective_min, int64_t objective_max) override; 103 void OnSynchronize(const Assignment* delta) override; 104 105 protected: 106 static const int64_t kUnassigned; 107 GetNext(int64_t node)108 int64_t GetNext(int64_t node) const { 109 return (new_nexts_[node] == kUnassigned) 110 ? (IsVarSynced(node) ? Value(node) : kUnassigned) 111 : new_nexts_[node]; 112 } NumPaths()113 int NumPaths() const { return starts_.size(); } Start(int i)114 int64_t Start(int i) const { return starts_[i]; } GetPath(int64_t node)115 int GetPath(int64_t node) const { return paths_[node]; } Rank(int64_t node)116 int Rank(int64_t node) const { return ranks_[node]; } IsDisabled()117 bool IsDisabled() const { return status_ == DISABLED; } GetTouchedPathStarts()118 const std::vector<int64_t>& GetTouchedPathStarts() const { 119 return touched_paths_.PositionsSetAtLeastOnce(); 120 } PathStartTouched(int64_t start)121 bool PathStartTouched(int64_t start) const { return touched_paths_[start]; } GetNewSynchronizedUnperformedNodes()122 const std::vector<int64_t>& GetNewSynchronizedUnperformedNodes() const { 123 return new_synchronized_unperformed_nodes_.PositionsSetAtLeastOnce(); 124 } 125 126 private: 127 enum Status { UNKNOWN, ENABLED, DISABLED }; 128 DisableFiltering()129 virtual bool DisableFiltering() const { return false; } OnBeforeSynchronizePaths()130 virtual void OnBeforeSynchronizePaths() {} OnAfterSynchronizePaths()131 virtual void OnAfterSynchronizePaths() {} OnSynchronizePathFromStart(int64_t start)132 virtual void OnSynchronizePathFromStart(int64_t start) {} InitializeAcceptPath()133 virtual bool InitializeAcceptPath() { return true; } 134 virtual bool AcceptPath(int64_t path_start, int64_t chain_start, 135 int64_t chain_end) = 0; FinalizeAcceptPath(int64_t objective_min,int64_t objective_max)136 virtual bool FinalizeAcceptPath(int64_t objective_min, 137 int64_t objective_max) { 138 return true; 139 } 140 /// Detects path starts, used to track which node belongs to which path. 141 void ComputePathStarts(std::vector<int64_t>* path_starts, 142 std::vector<int>* index_to_path); 143 bool HavePathsChanged(); 144 void SynchronizeFullAssignment(); 145 void UpdateAllRanks(); 146 void UpdatePathRanksFromStart(int start); 147 148 std::vector<int64_t> node_path_starts_; 149 std::vector<int64_t> starts_; 150 std::vector<int> paths_; 151 SparseBitset<int64_t> new_synchronized_unperformed_nodes_; 152 std::vector<int64_t> new_nexts_; 153 std::vector<int> delta_touched_; 154 SparseBitset<> touched_paths_; 155 // clang-format off 156 std::vector<std::pair<int64_t, int64_t> > touched_path_chain_start_ends_; 157 // clang-format on 158 std::vector<int> ranks_; 159 160 Status status_; 161 }; 162 163 } // namespace operations_research 164 165 #endif // OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_FILTERS_H_ 166