Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
bop_base.h
Go to the documentation of this file.
1// Copyright 2010-2025 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_BASE_H_
15#define OR_TOOLS_BOP_BOP_BASE_H_
16
17#include <cstdint>
18#include <limits>
19#include <ostream>
20#include <string>
21#include <vector>
22
23#include "absl/base/thread_annotations.h"
24#include "absl/strings/string_view.h"
25#include "absl/synchronization/mutex.h"
32#include "ortools/sat/clause.h"
34#include "ortools/util/stats.h"
36
37namespace operations_research {
38namespace bop {
39
40class ProblemState;
41// Forward declaration.
42struct LearnedInfo;
43
44// Base class used to optimize a ProblemState.
45// Optimizers implementing this class are used in a sort of portfolio and
46// are run sequentially or concurrently. See for instance BopRandomLNSOptimizer.
48 public:
49 explicit BopOptimizerBase(absl::string_view name);
50 virtual ~BopOptimizerBase();
51
52 // Returns the name given at construction.
53 const std::string& name() const { return name_; }
54
55 // Returns true if this optimizer should be run on the given problem state.
56 // Some optimizer requires a feasible solution to run for instance.
57 //
58 // Note that a similar effect can be achieved if Optimize() returns ABORT
59 // right away. However, doing the later will lower the chance of this
60 // optimizer to be called again since it will count as a failure to improve
61 // the current state.
62 virtual bool ShouldBeRun(const ProblemState& problem_state) const = 0;
63
64 // Return status of the Optimize() function below.
65 //
66 // TODO(user): To redesign, some are not needed anymore thanks to the
67 // problem state, e.g. IsOptimal().
68 enum Status {
73
74 // Some information was learned and the problem state will need to be
75 // updated. This will trigger a new optimization round.
76 //
77 // TODO(user): replace by learned_info->IsEmpty()? but we will need to clear
78 // the BopSolution there first.
80
81 // This optimizer didn't learn any information yet but can be called again
82 // on the same problem state to resume its work.
84
85 // There is no need to call this optimizer again on the same problem state.
87 };
88
89 // Tries to infer more information about the problem state, i.e. reduces the
90 // gap by increasing the lower bound or finding a better solution.
91 // Returns SOLUTION_FOUND when a new solution with a better objective cost is
92 // found before a time limit.
93 // The learned information is cleared and the filled with any new information
94 // about the problem, e.g. a new lower bound.
95 //
96 // Preconditions: ShouldBeRun() must returns true.
97 virtual Status Optimize(const BopParameters& parameters,
98 const ProblemState& problem_state,
99 LearnedInfo* learned_info, TimeLimit* time_limit) = 0;
100
101 // Returns a string describing the status.
102 static std::string GetStatusString(Status status);
103
104 protected:
105 const std::string name_;
106
108};
109
110inline std::ostream& operator<<(std::ostream& os,
113 return os;
114}
115
116// This class represents the current state of the problem with all the
117// information that the solver learned about it at a given time.
119 public:
120 explicit ProblemState(const sat::LinearBooleanProblem& problem);
121
122 // This type is neither copyable nor movable.
123 ProblemState(const ProblemState&) = delete;
125
126 // Sets parameters, used for instance to get the tolerance, the gap limit...
127 void SetParameters(const BopParameters& parameters) {
128 parameters_ = parameters;
129 }
130
131 const BopParameters& GetParameters() const { return parameters_; }
132
133 // Sets an assignment preference for each variable.
134 // This is only used for warm start.
135 void set_assignment_preference(const std::vector<bool>& a) {
136 assignment_preference_ = a;
137 }
138 std::vector<bool> assignment_preference() const {
139 return assignment_preference_;
140 }
141
142 // Merges the learned information with the current problem state. For
143 // instance, if variables x, and y are fixed in the current state, and z is
144 // learned to be fixed, the result of the merge will be x, y, and z being
145 // fixed in the problem state.
146 // Note that the LP values contained in the learned information (if any)
147 // will replace the LP values of the problem state, whatever the cost is.
148 // Returns true when the merge has changed the problem state.
149 bool MergeLearnedInfo(const LearnedInfo& learned_info,
150 BopOptimizerBase::Status optimization_status);
151
152 // Returns all the information learned so far.
153 // TODO(user): In the current implementation the learned information only
154 // contains binary clauses added since the last call to
155 // SynchronizationDone().
156 // Add an iterator on the sat::BinaryClauseManager.
158
159 // The stamp represents an upper bound on the number of times the problem
160 // state has been updated. If the stamp changed since last time one has
161 // checked the state, it's worth trying again as it might have changed
162 // (no guarantee).
163 static const int64_t kInitialStampValue;
164 int64_t update_stamp() const { return update_stamp_; }
165
166 // Marks the problem state as optimal.
167 void MarkAsOptimal();
168
169 // Marks the problem state as infeasible.
170 void MarkAsInfeasible();
171
172 // Returns true when the current state is proved to be optimal. In such a case
173 // solution() returns the optimal solution.
174 bool IsOptimal() const {
175 return solution_.IsFeasible() && solution_.GetCost() == lower_bound();
176 }
177
178 // Returns true when the problem is proved to be infeasible.
179 bool IsInfeasible() const { return lower_bound() > upper_bound(); }
180
181 // Returns true when the variable var is fixed in the current problem state.
182 // The value of the fixed variable is returned by GetVariableFixedValue(var).
183 bool IsVariableFixed(VariableIndex var) const { return is_fixed_[var]; }
185 return is_fixed_;
186 }
187
188 // Returns the value of the fixed variable var. Should be only called on fixed
189 // variables (CHECKed).
190 bool GetVariableFixedValue(VariableIndex var) const {
191 return fixed_values_[var];
192 }
194 return fixed_values_;
195 }
196
197 // Returns the values of the LP relaxation of the problem. Returns an empty
198 // vector when the LP has not been populated.
199 const glop::DenseRow& lp_values() const { return lp_values_; }
200
201 // Returns the solution to the current state problem.
202 // Note that the solution might not be feasible because until we find one, it
203 // will just be the all-false assignment.
204 const BopSolution& solution() const { return solution_; }
205
206 // Returns the original problem. Note that the current problem might be
207 // different, e.g. fixed variables, but equivalent, i.e. a solution to one
208 // should be a solution to the other too.
210 return original_problem_;
211 }
212
213 // Returns the current lower (resp. upper) bound of the objective cost.
214 // For internal use only: this is the unscaled version of the lower (resp.
215 // upper) bound, and so should be compared only to the unscaled cost given by
216 // solution.GetCost().
217 int64_t lower_bound() const { return lower_bound_; }
218 int64_t upper_bound() const { return upper_bound_; }
219
220 // Returns the scaled lower bound of the original problem.
221 double GetScaledLowerBound() const {
222 return (lower_bound() + original_problem_.objective().offset()) *
223 original_problem_.objective().scaling_factor();
224 }
225
226 // Returns the newly added binary clause since the last SynchronizationDone().
227 const std::vector<sat::BinaryClause>& NewlyAddedBinaryClauses() const;
228
229 // Resets what is considered "new" information. This is meant to be called
230 // once all the optimize have been synchronized.
231 void SynchronizationDone();
232
233 private:
234 const sat::LinearBooleanProblem& original_problem_;
235 BopParameters parameters_;
236 int64_t update_stamp_;
239 glop::DenseRow lp_values_;
240 BopSolution solution_;
241 std::vector<bool> assignment_preference_;
242
243 int64_t lower_bound_;
244 int64_t upper_bound_;
245
246 // Manage the set of the problem binary clauses (including the learned ones).
247 sat::BinaryClauseManager binary_clause_manager_;
248};
249
250// This struct represents what has been learned on the problem state by
251// running an optimizer. The goal is then to merge the learned information
252// with the problem state in order to get a more constrained problem to be used
253// by the next called optimizer.
255 explicit LearnedInfo(const sat::LinearBooleanProblem& problem)
256 : fixed_literals(),
257 solution(problem, "AllZero"),
258 lower_bound(std::numeric_limits<int64_t>::min()),
259 lp_values(),
260 binary_clauses() {}
261
262 // Clears all just as if the object were a brand new one. This can be used
263 // to reduce the number of creation / deletion of objects.
264 void Clear() {
265 fixed_literals.clear();
266 lower_bound = std::numeric_limits<int64_t>::min();
267 lp_values.clear();
268 binary_clauses.clear();
269 }
270
271 // Vector of all literals that have been fixed.
272 std::vector<sat::Literal> fixed_literals;
273
274 // New solution. Note that the solution might be infeasible.
276
277 // A lower bound (for multi-threading purpose).
278 int64_t lower_bound;
279
280 // An assignment for the relaxed linear programming problem (can be empty).
281 // This is meant to be the optimal LP solution, but can just be a feasible
282 // solution or any floating point assignment if the LP solver didn't solve
283 // the relaxed problem optimally.
285
286 // New binary clauses.
287 std::vector<sat::BinaryClause> binary_clauses;
288};
289} // namespace bop
290} // namespace operations_research
291#endif // OR_TOOLS_BOP_BOP_BASE_H_
Base class to print a nice summary of a group of statistics.
Definition stats.h:131
BopOptimizerBase(absl::string_view name)
Definition bop_base.cc:44
virtual Status Optimize(const BopParameters &parameters, const ProblemState &problem_state, LearnedInfo *learned_info, TimeLimit *time_limit)=0
@ ABORT
There is no need to call this optimizer again on the same problem state.
Definition bop_base.h:86
virtual bool ShouldBeRun(const ProblemState &problem_state) const =0
const std::string & name() const
Returns the name given at construction.
Definition bop_base.h:53
static std::string GetStatusString(Status status)
Returns a string describing the status.
Definition bop_base.cc:53
bool IsVariableFixed(VariableIndex var) const
Definition bop_base.h:183
void set_assignment_preference(const std::vector< bool > &a)
Definition bop_base.h:135
void MarkAsInfeasible()
Marks the problem state as infeasible.
Definition bop_base.cc:253
const BopSolution & solution() const
Definition bop_base.h:204
const util_intops::StrongVector< VariableIndex, bool > & fixed_values() const
Definition bop_base.h:193
void SetParameters(const BopParameters &parameters)
Sets parameters, used for instance to get the tolerance, the gap limit...
Definition bop_base.h:127
const std::vector< sat::BinaryClause > & NewlyAddedBinaryClauses() const
Returns the newly added binary clause since the last SynchronizationDone().
Definition bop_base.cc:265
std::vector< bool > assignment_preference() const
Definition bop_base.h:138
bool MergeLearnedInfo(const LearnedInfo &learned_info, BopOptimizerBase::Status optimization_status)
Definition bop_base.cc:108
ProblemState(const ProblemState &)=delete
This type is neither copyable nor movable.
const glop::DenseRow & lp_values() const
Definition bop_base.h:199
void MarkAsOptimal()
Marks the problem state as optimal.
Definition bop_base.cc:247
ProblemState(const sat::LinearBooleanProblem &problem)
Definition bop_base.cc:83
ProblemState & operator=(const ProblemState &)=delete
const BopParameters & GetParameters() const
Definition bop_base.h:131
static const int64_t kInitialStampValue
Definition bop_base.h:163
double GetScaledLowerBound() const
Returns the scaled lower bound of the original problem.
Definition bop_base.h:221
const util_intops::StrongVector< VariableIndex, bool > & is_fixed() const
Definition bop_base.h:184
bool IsInfeasible() const
Returns true when the problem is proved to be infeasible.
Definition bop_base.h:179
const sat::LinearBooleanProblem & original_problem() const
Definition bop_base.h:209
bool GetVariableFixedValue(VariableIndex var) const
Definition bop_base.h:190
A simple class to manage a set of binary clauses.
Definition clause.h:414
time_limit
Definition solve.cc:22
std::ostream & operator<<(std::ostream &os, BopOptimizerBase::Status status)
Definition bop_base.h:110
StrictITIVector< ColIndex, Fractional > DenseRow
Row-vector types. Row-vector types are indexed by a column index.
Definition lp_types.h:351
In SWIG mode, we don't want anything besides these top-level includes.
STL namespace.
int64_t lower_bound
A lower bound (for multi-threading purpose).
Definition bop_base.h:278
BopSolution solution
New solution. Note that the solution might be infeasible.
Definition bop_base.h:275
LearnedInfo(const sat::LinearBooleanProblem &problem)
Definition bop_base.h:255
std::vector< sat::BinaryClause > binary_clauses
New binary clauses.
Definition bop_base.h:287
std::vector< sat::Literal > fixed_literals
Vector of all literals that have been fixed.
Definition bop_base.h:272