forked from google/or-tools
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathcp_model_search.h
136 lines (114 loc) · 5.54 KB
/
cp_model_search.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
// Copyright 2010-2024 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef OR_TOOLS_SAT_CP_MODEL_SEARCH_H_
#define OR_TOOLS_SAT_CP_MODEL_SEARCH_H_
#include <cstdint>
#include <functional>
#include <string>
#include <vector>
#include "absl/container/flat_hash_map.h"
#include "ortools/base/types.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_mapping.h"
#include "ortools/sat/integer.h"
#include "ortools/sat/integer_search.h"
#include "ortools/sat/model.h"
#include "ortools/sat/sat_base.h"
#include "ortools/sat/sat_parameters.pb.h"
namespace operations_research {
namespace sat {
// This class allows to query information about the current bounds of the loaded
// cp_model.proto variables during the search. It is a "view" of the current
// solver state using the indices of the proto.
//
// TODO(user): For now it uses proto indices of the loaded model. We will need
// to add a mapping to use proto indices of the non-presolved model to allow for
// a client custom search with presolve. The main API shouldn't change though
// and the change will be transparent.
class CpModelView {
public:
explicit CpModelView(Model* model);
// The valid indices for the calls below are in [0, num_variables).
int NumVariables() const;
// Getters about the current domain of the given variable.
bool IsFixed(int var) const;
int64_t Min(int var) const;
int64_t Max(int var) const;
// Helpers to generate a decision.
BooleanOrIntegerLiteral GreaterOrEqual(int var, int64_t value) const;
BooleanOrIntegerLiteral LowerOrEqual(int var, int64_t value) const;
BooleanOrIntegerLiteral MedianValue(int var) const;
private:
const CpModelMapping& mapping_;
const VariablesAssignment& boolean_assignment_;
const IntegerTrail& integer_trail_;
const IntegerEncoder& integer_encoder_;
};
// Constructs the search strategy specified in the given CpModelProto.
std::function<BooleanOrIntegerLiteral()> ConstructUserSearchStrategy(
const CpModelProto& cp_model_proto, Model* model);
// Constructs a search strategy tailored for the current model.
std::function<BooleanOrIntegerLiteral()> ConstructHeuristicSearchStrategy(
const CpModelProto& cp_model_proto, Model* model);
// Constructs an integer completion search strategy.
std::function<BooleanOrIntegerLiteral()>
ConstructIntegerCompletionSearchStrategy(
const std::vector<IntegerVariable>& variable_mapping,
IntegerVariable objective_var, Model* model);
// Constructs a search strategy that follows the hints from the model.
std::function<BooleanOrIntegerLiteral()> ConstructHintSearchStrategy(
const CpModelProto& cp_model_proto, CpModelMapping* mapping, Model* model);
// Constructs our "fixed" search strategy which start with
// ConstructUserSearchStrategy() but is completed by a couple of automatic
// heuristics.
std::function<BooleanOrIntegerLiteral()> ConstructFixedSearchStrategy(
std::function<BooleanOrIntegerLiteral()> user_search,
std::function<BooleanOrIntegerLiteral()> heuristic_search,
std::function<BooleanOrIntegerLiteral()> integer_completion);
// For debugging fixed-search: display information about the named variables
// domain before taking each decision. Note that we copy the instrumented
// strategy so it doesn't have to outlive the returned functions like the other
// arguments.
std::function<BooleanOrIntegerLiteral()> InstrumentSearchStrategy(
const CpModelProto& cp_model_proto,
const std::vector<IntegerVariable>& variable_mapping,
const std::function<BooleanOrIntegerLiteral()>& instrumented_strategy,
Model* model);
// Returns all the named set of parameters known to the solver. This include our
// default strategies like "max_lp", "core", etc... It is visible here so that
// this can be reused by parameter validation.
//
// Usually, named strategies just override a few field from the base_params.
absl::flat_hash_map<std::string, SatParameters> GetNamedParameters(
const SatParameters& base_params);
// Returns up to base_params.num_workers() different parameters.
// We do not always return num_worker parameters to leave room for strategies
// like LNS that do not consume a full worker and can always be interleaved.
std::vector<SatParameters> GetDiverseSetOfParameters(
const SatParameters& base_params, const CpModelProto& cp_model);
// Returns a vector of num_params_to_generate set of parameters to specify
// solvers specialized to find a initial solution.
std::vector<SatParameters> GetFirstSolutionParams(
const SatParameters& base_params, const CpModelProto& cp_model,
int num_params_to_generate);
// Returns a vector of num_params_to_generate set of parameters to specify
// solvers that cooperatively explore a search tree.
std::vector<SatParameters> GetWorkSharingParams(
const SatParameters& base_params, const CpModelProto& cp_model,
int num_params_to_generate);
// This generates a valid random seed (base_seed + delta) without overflow.
// We assume |delta| is small.
int ValidSumSeed(int base_seed, int delta);
} // namespace sat
} // namespace operations_research
#endif // OR_TOOLS_SAT_CP_MODEL_SEARCH_H_