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
28namespace operations_research {
29namespace sat {
30
31// Links IntegerVariable with model variable and its lp constraint if any.
32struct LPVariable {
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.
45 std::vector<LPVariable> vars;
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