Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
cp_model_solver_helpers.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_CP_MODEL_SOLVER_HELPERS_H_
15#define OR_TOOLS_SAT_CP_MODEL_SOLVER_HELPERS_H_
16
17#include <cstdint>
18#include <memory>
19#include <utility>
20#include <vector>
21
22#include "absl/types/span.h"
23#include "ortools/base/timer.h"
26#include "ortools/sat/model.h"
30#include "ortools/sat/util.h"
33
34namespace operations_research {
35namespace sat {
36
37// Small wrapper containing all the shared classes between our subsolver
38// threads. Note that all these classes can also be retrieved with something
39// like global_model->GetOrCreate<Class>() but it is not thread-safe to do so.
40//
41// All the classes here should be thread-safe, or at least safe in the way they
42// are accessed. For instance the model_proto will be kept constant for the
43// whole duration of the solve.
45 SharedClasses(const CpModelProto* proto, Model* global_model);
46
47 // These are never nullptr.
57
58 // These can be nullptr depending on the options.
59 std::unique_ptr<SharedBoundsManager> bounds;
60 std::unique_ptr<SharedLPSolutionRepository> lp_solutions;
61 std::unique_ptr<SharedIncompleteSolutionManager> incomplete_solutions;
62 std::unique_ptr<SharedClausesManager> clauses;
63
64 // call local_model->Register() on most of the class here, this allow to
65 // more easily depends on one of the shared class deep within the solver.
67
68 bool SearchIsDone();
69};
70
71// Loads a CpModelProto inside the given model.
72// This should only be called once on a given 'Model' class.
73void LoadCpModel(const CpModelProto& model_proto, Model* model);
74
75// Solves an already loaded cp_model_proto.
76// The final CpSolverResponse must be read from the shared_response_manager.
77//
78// TODO(user): This should be transformed so that it can be called many times
79// and resume from the last search state as if it wasn't interrupted. That would
80// allow use to easily interleave different heuristics in the same thread.
81void SolveLoadedCpModel(const CpModelProto& model_proto, Model* model);
82
83// Registers a callback that will export variables bounds fixed at level 0 of
84// the search. This should not be registered to a LNS search.
86 const CpModelProto& /*model_proto*/,
87 SharedBoundsManager* shared_bounds_manager, Model* model);
88
89// Registers a callback to import new variables bounds stored in the
90// shared_bounds_manager. These bounds are imported at level 0 of the search
91// in the linear scan minimize function.
93 const CpModelProto& model_proto, SharedBoundsManager* shared_bounds_manager,
94 Model* model);
95
96// Registers a callback that will report improving objective best bound.
97// It will be called each time new objective bound are propagated at level zero.
99 IntegerVariable objective_var,
100 SharedResponseManager* shared_response_manager, Model* model);
101
102// Registers a callback to import new objective bounds. It will be called each
103// time the search main loop is back to level zero. Note that it the presence of
104// assumptions, this will not happen until the set of assumptions is changed.
106 SharedResponseManager* shared_response_manager, Model* model);
107
108// Registers a callback that will export good clauses discovered during search.
109void RegisterClausesExport(int id, SharedClausesManager* shared_clauses_manager,
110 Model* model);
111
112// Registers a callback to import new clauses stored in the
113// shared_clausess_manager. These clauses are imported at level 0 of the search
114// in the linear scan minimize function.
115// it returns the id of the worker in the shared clause manager.
116//
117// TODO(user): Can we import them in the core worker ?
119 SharedClausesManager* shared_clauses_manager,
120 Model* model);
121
122void PostsolveResponseWrapper(const SatParameters& params,
123 int num_variable_in_original_model,
124 const CpModelProto& mapping_proto,
125 absl::Span<const int> postsolve_mapping,
126 std::vector<int64_t>* solution);
127
128// Try to find a solution by following the hint and using a low conflict limit.
129// The CpModelProto must already be loaded in the Model.
130void QuickSolveWithHint(const CpModelProto& model_proto, Model* model);
131
132// Solve a model with a different objective consisting of minimizing the L1
133// distance with the provided hint. Note that this method creates an in-memory
134// copy of the model and loads a local Model object from the copied model.
135void MinimizeL1DistanceWithHint(const CpModelProto& model_proto, Model* model);
136
137void LoadFeasibilityPump(const CpModelProto& model_proto, Model* model);
138
139void AdaptGlobalParameters(const CpModelProto& model_proto, Model* model);
140
141// This should be called on the presolved model. It will read the file
142// specified by --cp_model_load_debug_solution and properly fill the
143// model->Get<DebugSolution>() proto vector.
144void LoadDebugSolution(const CpModelProto& model_proto, Model* model);
145
146} // namespace sat
147} // namespace operations_research
148
149#endif // OR_TOOLS_SAT_CP_MODEL_SOLVER_HELPERS_H_
The model "singleton" shared time limit.
Definition util.h:354
Contains the table we display after the solver is done.
Definition stat_tables.h:33
Simple class to add statistics by name and print them at the end.
void SolveLoadedCpModel(const CpModelProto &model_proto, Model *model)
void RegisterObjectiveBoundsImport(SharedResponseManager *shared_response_manager, Model *model)
void RegisterClausesExport(int id, SharedClausesManager *shared_clauses_manager, Model *model)
Registers a callback that will export good clauses discovered during search.
void MinimizeL1DistanceWithHint(const CpModelProto &model_proto, Model *model)
void LoadFeasibilityPump(const CpModelProto &model_proto, Model *model)
void AdaptGlobalParameters(const CpModelProto &model_proto, Model *model)
void QuickSolveWithHint(const CpModelProto &model_proto, Model *model)
void LoadDebugSolution(const CpModelProto &model_proto, Model *model)
void RegisterVariableBoundsLevelZeroExport(const CpModelProto &, SharedBoundsManager *shared_bounds_manager, Model *model)
void PostsolveResponseWrapper(const SatParameters &params, int num_variable_in_original_model, const CpModelProto &mapping_proto, absl::Span< const int > postsolve_mapping, std::vector< int64_t > *solution)
void RegisterVariableBoundsLevelZeroImport(const CpModelProto &model_proto, SharedBoundsManager *shared_bounds_manager, Model *model)
void LoadCpModel(const CpModelProto &model_proto, Model *model)
void RegisterObjectiveBestBoundExport(IntegerVariable objective_var, SharedResponseManager *shared_response_manager, Model *model)
int RegisterClausesLevelZeroImport(int id, SharedClausesManager *shared_clauses_manager, Model *model)
In SWIG mode, we don't want anything besides these top-level includes.
Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid
const CpModelProto & model_proto
These are never nullptr.
SharedLsSolutionRepository *const ls_hints
std::unique_ptr< SharedIncompleteSolutionManager > incomplete_solutions
std::unique_ptr< SharedClausesManager > clauses
SharedClasses(const CpModelProto *proto, Model *global_model)
std::unique_ptr< SharedLPSolutionRepository > lp_solutions
std::unique_ptr< SharedBoundsManager > bounds
These can be nullptr depending on the options.