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"
29 #include "ortools/sat/sat_base.h"
30 #include "ortools/util/stats.h"
32 
33 namespace operations_research {
34 namespace bop {
35 
36 // Forward declaration.
37 struct LearnedInfo;
38 class 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 
106 inline std::ostream& operator<<(std::ostream& os,
107  BopOptimizerBase::Status status) {
108  os << BopOptimizerBase::GetStatusString(status);
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.
149  LearnedInfo GetLearnedInfo() const;
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.
248 struct LearnedInfo {
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();
261  lp_values.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
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 std::string & name() const
Definition: bop_base.h:49
const BopParameters & GetParameters() const
Definition: bop_base.h:123
const sat::LinearBooleanProblem & original_problem() const
Definition: bop_base.h:201
const std::vector< bool > assignment_preference() const
Definition: bop_base.h:130
const glop::DenseRow & lp_values() const
Definition: bop_base.h:191
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
bool IsVariableFixed(VariableIndex var) const
Definition: bop_base.h:175
static const int64_t kInitialStampValue
Definition: bop_base.h:155
bool GetVariableFixedValue(VariableIndex var) const
Definition: bop_base.h:182
void SetParameters(const BopParameters &parameters)
Definition: bop_base.h:119
ProblemState(const sat::LinearBooleanProblem &problem)
Definition: bop_base.cc:67
const BopSolution & solution() const
Definition: bop_base.h:196
void set_assignment_preference(const std::vector< bool > &a)
Definition: bop_base.h:127
const absl::StrongVector< VariableIndex, bool > & is_fixed() const
Definition: bop_base.h:176
const absl::StrongVector< VariableIndex, bool > & fixed_values() const
Definition: bop_base.h:185
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...
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