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