OR-Tools  8.2
bop_solution.h
Go to the documentation of this file.
1 // Copyright 2010-2018 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 
20 #include "ortools/bop/bop_types.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:
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]; }
47  const std::string& name() const { return name_; }
48  void set_name(const std::string& name) { name_ = name; }
49 
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) {...}.
81  return values_.begin();
82  }
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_;
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_
size_type size() const
ParentType::const_iterator const_iterator
Definition: strong_vector.h:90
absl::StrongVector< VariableIndex, bool >::const_iterator end() const
Definition: bop_solution.h:83
void SetValue(VariableIndex var, bool value)
Definition: bop_solution.h:39
bool operator<(const BopSolution &solution) const
Definition: bop_solution.h:90
BopSolution(const sat::LinearBooleanProblem &problem, const std::string &name)
Definition: bop_solution.cc:28
bool Value(VariableIndex var) const
Definition: bop_solution.h:46
void set_name(const std::string &name)
Definition: bop_solution.h:48
const std::string & name() const
Definition: bop_solution.h:47
absl::StrongVector< VariableIndex, bool >::const_iterator begin() const
Definition: bop_solution.h:80
int64 value
IntVar * var
Definition: expr_array.cc:1858
double AddOffsetAndScaleObjectiveValue(const LinearBooleanProblem &problem, Coefficient v)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...