forked from google/or-tools
-
Notifications
You must be signed in to change notification settings - Fork 9
/
bop_solution.h
122 lines (104 loc) · 4.21 KB
/
bop_solution.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// Copyright 2010-2024 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef OR_TOOLS_BOP_BOP_SOLUTION_H_
#define OR_TOOLS_BOP_BOP_SOLUTION_H_
#include <stddef.h>
#include <cstdint>
#include <string>
#include "absl/strings/string_view.h"
#include "ortools/base/strong_vector.h"
#include "ortools/bop/bop_types.h"
#include "ortools/sat/boolean_problem.h"
#include "ortools/sat/boolean_problem.pb.h"
#include "ortools/sat/pb_constraint.h"
namespace operations_research {
namespace bop {
// A Bop solution is a Boolean assignment for each variable of the problem. The
// cost value associated to the solution is the instantiation of the objective
// cost of the problem.
//
// Note that a solution might not be a feasible solution, i.e. might violate
// some constraints of the problem. The IsFeasible() method can be used to test
// the feasibility.
class BopSolution {
public:
BopSolution(const sat::LinearBooleanProblem& problem, absl::string_view name);
void SetValue(VariableIndex var, bool value) {
recompute_cost_ = true;
recompute_is_feasible_ = true;
values_[var] = value;
}
size_t Size() const { return values_.size(); }
bool Value(VariableIndex var) const { return values_[var]; }
const std::string& name() const { return name_; }
void set_name(absl::string_view name) { name_ = name; }
// Returns the objective cost of the solution.
// Note that this code is lazy but not incremental and might run in the
// problem size. Use with care during search.
int64_t GetCost() const {
if (recompute_cost_) {
cost_ = ComputeCost();
}
return cost_;
}
// Returns the objective cost of the solution taking into account the problem
// cost scaling and offset. This is mainly useful for displaying the current
// problem cost, while internally, the algorithm works directly with the
// integer version of the cost returned by GetCost().
double GetScaledCost() const {
return sat::AddOffsetAndScaleObjectiveValue(*problem_,
sat::Coefficient(GetCost()));
}
// Returns true iff the solution is feasible.
// Note that this code is lazy but not incremental and might run in the
// problem size. Use with care during search.
bool IsFeasible() const {
if (recompute_is_feasible_) {
is_feasible_ = ComputeIsFeasible();
}
return is_feasible_;
}
// For range based iteration, i.e. for (const bool value : solution) {...}.
util_intops::StrongVector<VariableIndex, bool>::const_iterator begin() const {
return values_.begin();
}
util_intops::StrongVector<VariableIndex, bool>::const_iterator end() const {
return values_.end();
}
// Returns true when the cost of the argument solution is strictly greater
// than the cost of the object.
// This is used to sort solutions.
bool operator<(const BopSolution& solution) const {
return IsFeasible() == solution.IsFeasible()
? GetCost() < solution.GetCost()
: IsFeasible() > solution.IsFeasible();
}
private:
bool ComputeIsFeasible() const;
int64_t ComputeCost() const;
const sat::LinearBooleanProblem* problem_;
std::string name_;
util_intops::StrongVector<VariableIndex, bool> values_;
// Those are mutable because they behave as const values for a given solution
// but for performance reasons we want to be lazy on their computation,
// e.g. not compute the cost each time set_value() is called.
mutable bool recompute_cost_;
mutable bool recompute_is_feasible_;
mutable int64_t cost_;
mutable bool is_feasible_;
// Note that assign/copy are defined to allow usage of
// STL collections / algorithms.
};
} // namespace bop
} // namespace operations_research
#endif // OR_TOOLS_BOP_BOP_SOLUTION_H_