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
22#include "ortools/sat/boolean_problem.pb.h"
23
24namespace operations_research {
25namespace 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.
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 {
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
void SetValue(VariableIndex var, bool value)
Definition: bop_solution.h:39
const std::string & name() const
Definition: bop_solution.h:47
absl::StrongVector< VariableIndex, bool >::const_iterator begin() const
Definition: bop_solution.h:80
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
absl::StrongVector< VariableIndex, bool >::const_iterator end() const
Definition: bop_solution.h:83
void set_name(const std::string &name)
Definition: bop_solution.h:48
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...