Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
rins.h
Go to the documentation of this file.
1// Copyright 2010-2025 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 <cstdint>
18#include <string>
19#include <utility>
20#include <vector>
21
22#include "absl/random/bit_gen_ref.h"
23#include "ortools/sat/model.h"
25
26namespace operations_research {
27namespace sat {
28
29// A RINS Neighborhood is actually just a generic neighborhood where the domain
30// of some variable have been reduced (fixed or restricted in [lb, ub]).
31//
32// Important: It might be possible that the value of the variables here are
33// outside the domains of these variables! This happens for RENS type of
34// neighborhood in the presence of holes in the domains because the LP
35// relaxation ignore those.
37 // A variable will appear only once and not in both vectors.
38 std::vector<std::pair</*model_var*/ int, /*value*/ int64_t>> fixed_vars;
39 std::vector<
40 std::pair</*model_var*/ int, /*domain*/ std::pair<int64_t, int64_t>>>
42 std::string source_info;
43};
44
45// Helper method to create a RINS neighborhood by fixing variables with same
46// values in relaxation solution and the current best solution in the
47// response_manager. Prioritizes repositories in following order to get a
48// neighborhood.
49// 1. incomplete_solutions
50// 2. lp_solutions
51//
52// If response_manager has no solution, this generates a RENS neighborhood by
53// ignoring the solutions and using the relaxation values. The domain of the
54// variables are reduced to integer values around relaxation values. If the
55// relaxation value is integer, then we fix the domain of the variable to that
56// value.
58 const SharedResponseManager* response_manager,
59 const SharedLPSolutionRepository* lp_solutions,
60 SharedIncompleteSolutionManager* incomplete_solutions, double difficulty,
61 absl::BitGenRef random);
62
63// Adds the current LP solution to the pool.
65
66} // namespace sat
67} // namespace operations_research
68
69#endif // OR_TOOLS_SAT_RINS_H_
ReducedDomainNeighborhood GetRinsRensNeighborhood(const SharedResponseManager *response_manager, const SharedLPSolutionRepository *lp_solutions, SharedIncompleteSolutionManager *incomplete_solutions, double difficulty, absl::BitGenRef random)
Definition rins.cc:176
void RecordLPRelaxationValues(Model *model)
Adds the current LP solution to the pool.
Definition rins.cc:40
In SWIG mode, we don't want anything besides these top-level includes.
std::vector< std::pair< int, std::pair< int64_t, int64_t > > > reduced_domain_vars
Definition rins.h:41
std::vector< std::pair< int, int64_t > > fixed_vars
A variable will appear only once and not in both vectors.
Definition rins.h:38