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
25#include "ortools/base/macros.h"
26#include "ortools/base/random.h"
29#include "ortools/bop/bop_parameters.pb.h"
34#include "ortools/sat/boolean_problem.pb.h"
36#include "ortools/util/stats.h"
38
39namespace operations_research {
40namespace 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);
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...