OR-Tools  8.2
rins.cc
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#include "ortools/sat/rins.h"
15
16#include <limits>
17
19#include "ortools/sat/integer.h"
21
22namespace operations_research {
23namespace sat {
24
27 if (lp_solutions == nullptr) return;
28
29 const LPVariables& lp_vars = *model->GetOrCreate<LPVariables>();
30 std::vector<double> relaxation_values(
31 lp_vars.model_vars_size, std::numeric_limits<double>::infinity());
32
33 auto* integer_trail = model->GetOrCreate<IntegerTrail>();
34 for (const LPVariable& lp_var : lp_vars.vars) {
35 const IntegerVariable positive_var = lp_var.positive_var;
36 if (integer_trail->IsCurrentlyIgnored(positive_var)) continue;
37
39 if (lp == nullptr || !lp->HasSolution()) continue;
40
41 relaxation_values[lp_var.model_var] = lp->GetSolutionValue(positive_var);
42 }
43 lp_solutions->NewLPSolution(std::move(relaxation_values));
44}
45
46namespace {
47
48std::vector<double> GetLPRelaxationValues(
49 const SharedLPSolutionRepository* lp_solutions, absl::BitGenRef random) {
50 std::vector<double> relaxation_values;
51
52 if (lp_solutions == nullptr || lp_solutions->NumSolutions() == 0) {
53 return relaxation_values;
54 }
55
56 // TODO(user): Experiment with random biased solutions.
57 const SharedSolutionRepository<double>::Solution lp_solution =
59
60 for (int model_var = 0; model_var < lp_solution.variable_values.size();
61 ++model_var) {
62 relaxation_values.push_back(lp_solution.variable_values[model_var]);
63 }
64 return relaxation_values;
65}
66
67std::vector<double> GetGeneralRelaxationValues(
68 const SharedRelaxationSolutionRepository* relaxation_solutions,
69 absl::BitGenRef random) {
70 std::vector<double> relaxation_values;
71
72 if (relaxation_solutions == nullptr ||
74 return relaxation_values;
75 }
76 const SharedSolutionRepository<int64>::Solution relaxation_solution =
78
79 for (int model_var = 0;
80 model_var < relaxation_solution.variable_values.size(); ++model_var) {
81 relaxation_values.push_back(relaxation_solution.variable_values[model_var]);
82 }
83 return relaxation_values;
84}
85
86std::vector<double> GetIncompleteSolutionValues(
87 SharedIncompleteSolutionManager* incomplete_solutions) {
88 std::vector<double> empty_solution_values;
89
90 if (incomplete_solutions == nullptr ||
92 return empty_solution_values;
93 }
94
96}
97} // namespace
98
100 const SharedResponseManager* response_manager,
104 absl::BitGenRef random) {
105 RINSNeighborhood rins_neighborhood;
106
107 const bool use_only_relaxation_values =
108 (response_manager == nullptr ||
109 response_manager->SolutionsRepository().NumSolutions() == 0);
110
111 if (use_only_relaxation_values && lp_solutions == nullptr &&
112 incomplete_solutions == nullptr) {
113 // As of now RENS doesn't generate good neighborhoods from integer
114 // relaxation solutions.
115 return rins_neighborhood;
116 }
117
118 std::vector<double> relaxation_values;
119 if (incomplete_solutions != nullptr) {
120 relaxation_values = GetIncompleteSolutionValues(incomplete_solutions);
121 } else if (lp_solutions != nullptr) {
122 relaxation_values = GetLPRelaxationValues(lp_solutions, random);
123 } else {
124 CHECK(relaxation_solutions != nullptr)
125 << "No relaxation solutions repository or lp solutions repository "
126 "provided.";
127 relaxation_values =
128 GetGeneralRelaxationValues(relaxation_solutions, random);
129 }
130 if (relaxation_values.empty()) return rins_neighborhood;
131
132 const double tolerance = 1e-6;
134 use_only_relaxation_values
136 : response_manager->SolutionsRepository().GetRandomBiasedSolution(
137 random);
138 for (int model_var = 0; model_var < relaxation_values.size(); ++model_var) {
139 const double relaxation_value = relaxation_values[model_var];
140
141 if (relaxation_value == std::numeric_limits<double>::infinity()) {
142 continue;
143 }
144
145 if (use_only_relaxation_values) {
146 // The tolerance make sure that if the relaxation_value is close to an
147 // integer, then we fix the variable to this integer value.
148 //
149 // Important: the LP relaxation doesn't know about holes in the variable
150 // domains, so the intersection of [domain_lb, domain_ub] with the
151 // initial variable domain might be empty.
152 const int64 domain_lb =
153 static_cast<int64>(std::floor(relaxation_value + tolerance));
154 const int64 domain_ub =
155 static_cast<int64>(std::ceil(relaxation_value - tolerance));
156 if (domain_lb == domain_ub) {
157 rins_neighborhood.fixed_vars.push_back({model_var, domain_lb});
158 } else {
159 rins_neighborhood.reduced_domain_vars.push_back(
160 {model_var, {domain_lb, domain_ub}});
161 }
162
163 } else {
164 const IntegerValue best_solution_value =
165 IntegerValue(solution.variable_values[model_var]);
166 if (std::abs(best_solution_value.value() - relaxation_value) < 1e-4) {
167 rins_neighborhood.fixed_vars.push_back(
168 {model_var, best_solution_value.value()});
169 }
170 }
171 }
172
173 return rins_neighborhood;
174}
175
176} // namespace sat
177} // namespace operations_research
#define CHECK(condition)
Definition: base/logging.h:495
Class that owns everything related to a particular optimization model.
Definition: sat/model.h:38
void NewLPSolution(std::vector< double > lp_solution)
const SharedSolutionRepository< int64 > & SolutionsRepository() const
Solution GetRandomBiasedSolution(absl::BitGenRef random) const
SharedRelaxationSolutionRepository * relaxation_solutions
SharedLPSolutionRepository * lp_solutions
SharedIncompleteSolutionManager * incomplete_solutions
GRBmodel * model
int64_t int64
void RecordLPRelaxationValues(Model *model)
Definition: rins.cc:25
RINSNeighborhood GetRINSNeighborhood(const SharedResponseManager *response_manager, const SharedRelaxationSolutionRepository *relaxation_solutions, const SharedLPSolutionRepository *lp_solutions, SharedIncompleteSolutionManager *incomplete_solutions, absl::BitGenRef random)
Definition: rins.cc:99
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
IntegerVariable positive_var
Definition: rins.h:33
LinearProgrammingConstraint * lp
Definition: rins.h:34
std::vector< LPVariable > vars
Definition: rins.h:45
std::vector< std::pair< int, std::pair< int64, int64 > > > reduced_domain_vars
Definition: rins.h:60
std::vector< std::pair< int, int64 > > fixed_vars
Definition: rins.h:58