OR-Tools  8.2
rins.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_SAT_RINS_H_
15 #define OR_TOOLS_SAT_RINS_H_
16 
17 #include <vector>
18 
19 #include "absl/container/flat_hash_map.h"
20 #include "absl/random/bit_gen_ref.h"
21 #include "absl/synchronization/mutex.h"
22 #include "absl/types/optional.h"
23 #include "ortools/sat/integer.h"
25 #include "ortools/sat/model.h"
27 
28 namespace operations_research {
29 namespace sat {
30 
31 // Links IntegerVariable with model variable and its lp constraint if any.
32 struct LPVariable {
33  IntegerVariable positive_var = kNoIntegerVariable;
35  int model_var;
36 
37  bool operator==(const LPVariable other) const {
38  return (positive_var == other.positive_var && lp == other.lp &&
39  model_var == other.model_var);
40  }
41 };
42 
43 // This is used to "cache" in the model the set of relevant LPVariable.
44 struct LPVariables {
45  std::vector<LPVariable> vars;
46  int model_vars_size = 0;
47 };
48 
49 // A RINS Neighborhood is actually just a generic neighborhood where the domain
50 // of some variable have been reduced (fixed or restricted in [lb, ub]).
51 //
52 // Important: It might be possible that the value of the variables here are
53 // outside the domains of these variables! This happens for RENS type of
54 // neighborhood in the presence of holes in the domains because the LP
55 // relaxation ignore those.
57  // A variable will appear only once and not in both vectors.
58  std::vector<std::pair</*model_var*/ int, /*value*/ int64>> fixed_vars;
59  std::vector<std::pair</*model_var*/ int, /*domain*/ std::pair<int64, int64>>>
61 };
62 
63 // Helper method to create a RINS neighborhood by fixing variables with same
64 // values in relaxation solution and the current best solution in the
65 // response_manager. Prioritizes repositories in following order to get a
66 // relaxation solution.
67 // 1. incomplete_solutions
68 // 2. lp_solutions
69 // 3. relaxation_solutions
70 //
71 // If response_manager is not provided, this generates a RENS neighborhood by
72 // ignoring the solutions and using the relaxation values. The domain of the
73 // variables are reduced to integer values around relaxation values. If the
74 // relaxation value is integer, then we fix the domain of the variable to that
75 // value.
77  const SharedResponseManager* response_manager,
81  absl::BitGenRef random);
82 
83 // Adds the current LP solution to the pool.
85 
86 } // namespace sat
87 } // namespace operations_research
88 
89 #endif // OR_TOOLS_SAT_RINS_H_
Class that owns everything related to a particular optimization model.
Definition: sat/model.h:38
SharedRelaxationSolutionRepository * relaxation_solutions
SharedLPSolutionRepository * lp_solutions
SharedIncompleteSolutionManager * incomplete_solutions
GRBmodel * model
int64_t int64
void RecordLPRelaxationValues(Model *model)
Definition: rins.cc:25
const IntegerVariable kNoIntegerVariable(-1)
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
bool operator==(const LPVariable other) const
Definition: rins.h:37
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