OR-Tools  8.2
bop_lns.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_LNS_H_
15 #define OR_TOOLS_BOP_BOP_LNS_H_
16 
17 #include <cstdint>
18 #include <string>
19 #include <vector>
20 
22 #include "ortools/base/int_type.h"
24 #include "ortools/base/logging.h"
25 #include "ortools/base/macros.h"
26 #include "ortools/base/random.h"
28 #include "ortools/bop/bop_base.h"
29 #include "ortools/bop/bop_parameters.pb.h"
31 #include "ortools/bop/bop_types.h"
32 #include "ortools/bop/bop_util.h"
33 #include "ortools/glop/lp_solver.h"
34 #include "ortools/sat/boolean_problem.pb.h"
35 #include "ortools/sat/sat_solver.h"
36 #include "ortools/util/stats.h"
38 
39 namespace operations_research {
40 namespace bop {
41 
42 // Uses SAT to solve the full problem under the constraint that the new solution
43 // should be under a given Hamming distance of the current solution.
45  public:
46  BopCompleteLNSOptimizer(const std::string& name,
47  const BopConstraintTerms& objective_terms);
49 
50  private:
51  bool ShouldBeRun(const ProblemState& problem_state) const final;
52  Status Optimize(const BopParameters& parameters,
53  const ProblemState& problem_state, LearnedInfo* learned_info,
54  TimeLimit* time_limit) final;
55 
56  BopOptimizerBase::Status SynchronizeIfNeeded(
57  const ProblemState& problem_state, int num_relaxed_vars);
58 
59  int64_t state_update_stamp_;
60  std::unique_ptr<sat::SatSolver> sat_solver_;
61  const BopConstraintTerms& objective_terms_;
62 };
63 
64 // Interface of the different LNS neighborhood generation algorithm.
65 //
66 // NOTE(user): Using a sat_propagator as the output of the algorithm allows for
67 // a really simple and efficient interface for the generator that relies on it.
68 // However, if a generator doesn't rely on it at all, it may slow down a bit the
69 // code (to investigate). If this happens, we will probably need another
70 // function here and a way to select between which one to call.
72  public:
75 
76  // Interface for the neighborhood generation.
77  //
78  // The difficulty will be in [0, 1] and is related to the asked neighborhood
79  // size (and thus local problem difficulty). A difficulty of 0.0 means empty
80  // neighborhood and a difficulty of 1.0 means the full problem. The algorithm
81  // should try to generate an neighborhood according to this difficulty, which
82  // will be dynamically adjusted depending on whether or not we can solve the
83  // subproblem.
84  //
85  // The given sat_propagator will be reset and then configured so that all the
86  // variables propagated on its trail should be fixed. That is, the
87  // neighborhood will correspond to the unassigned variables in the
88  // sat_propagator. Note that sat_propagator_.IsModelUnsat() will be checked
89  // after this is called so it is okay to abort if this happens.
90  //
91  // Preconditions:
92  // - The given sat_propagator_ should have the current problem loaded (with
93  // the constraint to find a better solution that any current solution).
94  // - The problem state must contains a feasible solution.
95  virtual void GenerateNeighborhood(const ProblemState& problem_state,
96  double difficulty,
97  sat::SatSolver* sat_propagator) = 0;
98 };
99 
100 // A generic LNS optimizer which generates neighborhoods according to the given
101 // NeighborhoodGenerator and automatically adapt the neighborhood size depending
102 // on how easy it is to solve the associated problem.
104  public:
105  // Takes ownership of the given neighborhood_generator.
106  // The sat_propagator is assumed to contains the current problem.
107  BopAdaptiveLNSOptimizer(const std::string& name, bool use_lp_to_guide_sat,
108  NeighborhoodGenerator* neighborhood_generator,
109  sat::SatSolver* sat_propagator);
110  ~BopAdaptiveLNSOptimizer() final;
111 
112  private:
113  bool ShouldBeRun(const ProblemState& problem_state) const final;
114  Status Optimize(const BopParameters& parameters,
115  const ProblemState& problem_state, LearnedInfo* learned_info,
116  TimeLimit* time_limit) final;
117 
118  const bool use_lp_to_guide_sat_;
119  std::unique_ptr<NeighborhoodGenerator> neighborhood_generator_;
120  sat::SatSolver* const sat_propagator_;
121 
122  // Adaptive neighborhood size logic.
123  // The values are kept from one run to the next.
124  LubyAdaptiveParameterValue adaptive_difficulty_;
125 };
126 
127 // Generates a neighborhood by randomly fixing a subset of the objective
128 // variables that are currently at their lower cost.
130  public:
132  MTRandom* random)
133  : objective_terms_(*objective_terms), random_(random) {}
135 
136  private:
137  void GenerateNeighborhood(const ProblemState& problem_state,
138  double difficulty,
139  sat::SatSolver* sat_propagator) final;
140  const BopConstraintTerms& objective_terms_;
141  MTRandom* random_;
142 };
143 
144 // Generates a neighborhood by randomly selecting a subset of constraints and
145 // fixing the objective variables that are currently at their lower cost and
146 // not in the given subset of constraints.
148  public:
150  MTRandom* random)
151  : objective_terms_(*objective_terms), random_(random) {}
153 
154  private:
155  void GenerateNeighborhood(const ProblemState& problem_state,
156  double difficulty,
157  sat::SatSolver* sat_propagator) final;
158  const BopConstraintTerms& objective_terms_;
159  MTRandom* random_;
160 };
161 
162 // Generates a neighborhood by taking a random local neighborhood in an
163 // undirected graph where the nodes are the variables and two nodes are linked
164 // if they appear in the same constraint.
166  public:
167  RelationGraphBasedNeighborhood(const sat::LinearBooleanProblem& problem,
168  MTRandom* random);
170 
171  private:
172  void GenerateNeighborhood(const ProblemState& problem_state,
173  double difficulty,
174  sat::SatSolver* sat_propagator) final;
175 
176  // TODO(user): reuse by_variable_matrix_ from the LS? Note however than we
177  // don't need the coefficients here.
179  MTRandom* random_;
180 };
181 
182 } // namespace bop
183 } // namespace operations_research
184 #endif // OR_TOOLS_BOP_BOP_LNS_H_
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Definition: time_limit.h:105
BopAdaptiveLNSOptimizer(const std::string &name, bool use_lp_to_guide_sat, NeighborhoodGenerator *neighborhood_generator, sat::SatSolver *sat_propagator)
Definition: bop_lns.cc:213
BopCompleteLNSOptimizer(const std::string &name, const BopConstraintTerms &objective_terms)
Definition: bop_lns.cc:57
const std::string & name() const
Definition: bop_base.h:49
ConstraintBasedNeighborhood(const BopConstraintTerms *objective_terms, MTRandom *random)
Definition: bop_lns.h:149
virtual void GenerateNeighborhood(const ProblemState &problem_state, double difficulty, sat::SatSolver *sat_propagator)=0
ObjectiveBasedNeighborhood(const BopConstraintTerms *objective_terms, MTRandom *random)
Definition: bop_lns.h:131
RelationGraphBasedNeighborhood(const sat::LinearBooleanProblem &problem, MTRandom *random)
Definition: bop_lns.cc:508
SatParameters parameters
SharedTimeLimit * time_limit
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...