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_BOP_BOP_SOLUTION_H_ 15 #define OR_TOOLS_BOP_BOP_SOLUTION_H_ 16 17 #include <cstdint> 18 19 #include "ortools/base/strong_vector.h" 20 #include "ortools/bop/bop_types.h" 21 #include "ortools/sat/boolean_problem.h" 22 #include "ortools/sat/boolean_problem.pb.h" 23 24 namespace operations_research { 25 namespace bop { 26 27 // A Bop solution is a Boolean assignment for each variable of the problem. The 28 // cost value associated to the solution is the instantiation of the objective 29 // cost of the problem. 30 // 31 // Note that a solution might not be a feasible solution, i.e. might violate 32 // some constraints of the problem. The IsFeasible() method can be used to test 33 // the feasibility. 34 class BopSolution { 35 public: LocalSearchOptimizer(const std::string & name,int max_num_decisions,absl::BitGenRef random,sat::SatSolver * sat_propagator)36 BopSolution(const sat::LinearBooleanProblem& problem, 37 const std::string& name); 38 39 void SetValue(VariableIndex var, bool value) { 40 recompute_cost_ = true; 41 recompute_is_feasible_ = true; 42 values_[var] = value; 43 } 44 45 size_t Size() const { return values_.size(); } 46 bool Value(VariableIndex var) const { return values_[var]; } ~LocalSearchOptimizer()47 const std::string& name() const { return name_; } 48 void set_name(const std::string& name) { name_ = name; } ShouldBeRun(const ProblemState & problem_state) const49 50 // Returns the objective cost of the solution. 51 // Note that this code is lazy but not incremental and might run in the 52 // problem size. Use with care during search. 53 int64_t GetCost() const { 54 if (recompute_cost_) { 55 cost_ = ComputeCost(); 56 } 57 return cost_; 58 } 59 60 // Returns the objective cost of the solution taking into account the problem 61 // cost scaling and offset. This is mainly useful for displaying the current 62 // problem cost, while internally, the algorithm works directly with the 63 // integer version of the cost returned by GetCost(). 64 double GetScaledCost() const { 65 return sat::AddOffsetAndScaleObjectiveValue(*problem_, 66 sat::Coefficient(GetCost())); 67 } 68 69 // Returns true iff the solution is feasible. 70 // Note that this code is lazy but not incremental and might run in the 71 // problem size. Use with care during search. 72 bool IsFeasible() const { 73 if (recompute_is_feasible_) { 74 is_feasible_ = ComputeIsFeasible(); 75 } 76 return is_feasible_; 77 } 78 79 // For range based iteration, i.e. for (const bool value : solution) {...}. 80 absl::StrongVector<VariableIndex, bool>::const_iterator begin() const { 81 return values_.begin(); 82 } 83 absl::StrongVector<VariableIndex, bool>::const_iterator end() const { 84 return values_.end(); 85 } 86 87 // Returns true when the cost of the argument solution is strictly greater 88 // than the cost of the object. 89 // This is used to sort solutions. 90 bool operator<(const BopSolution& solution) const { 91 return IsFeasible() == solution.IsFeasible() 92 ? GetCost() < solution.GetCost() 93 : IsFeasible() > solution.IsFeasible(); 94 } 95 96 private: 97 bool ComputeIsFeasible() const; 98 int64_t ComputeCost() const; 99 100 const sat::LinearBooleanProblem* problem_; 101 std::string name_; 102 absl::StrongVector<VariableIndex, bool> values_; 103 104 // Those are mutable because they behave as const values for a given solution 105 // but for performance reasons we want to be lazy on their computation, 106 // e.g. not compute the cost each time set_value() is called. 107 mutable bool recompute_cost_; 108 mutable bool recompute_is_feasible_; 109 mutable int64_t cost_; 110 mutable bool is_feasible_; 111 112 // Note that assign/copy are defined to allow usage of 113 // STL collections / algorithms. 114 }; 115 116 } // namespace bop 117 } // namespace operations_research 118 #endif // OR_TOOLS_BOP_BOP_SOLUTION_H_ 119