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