Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
shaving_solver.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_SHAVING_SOLVER_H_
15#define OR_TOOLS_SAT_SHAVING_SOLVER_H_
16
17#include <atomic>
18#include <cstdint>
19#include <functional>
20#include <memory>
21#include <string>
22#include <vector>
23
24#include "absl/base/thread_annotations.h"
25#include "absl/synchronization/mutex.h"
26#include "ortools/sat/cp_model.pb.h"
30#include "ortools/sat/model.h"
31#include "ortools/sat/sat_parameters.pb.h"
34
35namespace operations_research {
36namespace sat {
37
39 public:
40 ObjectiveShavingSolver(const SatParameters& local_parameters,
42 SharedClasses* shared);
43
44 ~ObjectiveShavingSolver() override;
45
46 bool TaskIsAvailable() override;
47
48 std::function<void()> GenerateTask(int64_t task_id) override;
49 void Synchronize() override;
50
51 private:
52 std::string Info();
53
54 bool ResetAndSolveModel(int64_t task_id);
55
56 // This is fixed at construction.
57 SatParameters local_params_;
59 SharedClasses* shared_;
60
61 // Allow to control the local time limit in addition to a potential user
62 // defined external Boolean.
63 std::atomic<bool> stop_current_chunk_;
64
65 // Local singleton repository and presolved local model.
66 std::unique_ptr<Model> local_sat_model_;
67 CpModelProto local_proto_;
68
69 // For postsolving a feasible solution or improving objective lb.
70 std::vector<int> postsolve_mapping_;
71 CpModelProto mapping_proto_;
72
73 absl::Mutex mutex_;
74 IntegerValue objective_lb_ ABSL_GUARDED_BY(mutex_);
75 IntegerValue objective_ub_ ABSL_GUARDED_BY(mutex_);
76 IntegerValue current_objective_target_ub_ ABSL_GUARDED_BY(mutex_);
77 bool task_in_flight_ ABSL_GUARDED_BY(mutex_) = false;
78};
79
81 public:
82 struct State {
85
86 // We have two modes:
87 // - When "shave_using_objective" is true, we shave by minimizing the value
88 // of a variable.
89 // - When false, we restrict its domain and detect feasible/infeasible.
92 };
93
94 VariablesShavingSolver(const SatParameters& local_parameters,
96 SharedClasses* shared);
97
98 ~VariablesShavingSolver() override;
99
100 bool TaskIsAvailable() override;
101
102 void ProcessLocalResponse(const CpSolverResponse& local_response,
103 const State& state);
104
105 std::function<void()> GenerateTask(int64_t task_id) override;
106
107 void Synchronize() override;
108
109 private:
110 std::string Info();
111
112 int64_t DomainSize(int var) const ABSL_SHARED_LOCKS_REQUIRED(mutex_);
113
114 bool VarIsFixed(int int_var) const ABSL_SHARED_LOCKS_REQUIRED(mutex_);
115
116 bool ConstraintIsInactive(int c) const ABSL_SHARED_LOCKS_REQUIRED(mutex_);
117
118 bool FindNextVar(State* state) ABSL_SHARED_LOCKS_REQUIRED(mutex_);
119
120 void CopyModelConnectedToVar(State* state, Model* local_model,
121 CpModelProto* shaving_proto,
122 bool* has_no_overlap_2d)
123 ABSL_SHARED_LOCKS_REQUIRED(mutex_);
124
125 bool ResetAndSolveModel(int64_t task_id, State* state, Model* local_model,
126 CpModelProto* shaving_proto);
127
128 // This is fixed at construction.
129 SatParameters local_params_;
130 SharedClasses* shared_;
131 int shared_bounds_id_ = -1;
132
133 // Allow to control the local time limit in addition to a potential user
134 // defined external Boolean.
135 std::atomic<bool> stop_current_chunk_;
136
137 const CpModelProto& model_proto_;
138
139 absl::Mutex mutex_;
140 int64_t current_index_ = -1;
141 std::vector<Domain> var_domains_ ABSL_GUARDED_BY(mutex_);
142
143 // Stats.
144 int num_vars_tried_ ABSL_GUARDED_BY(mutex_) = 0;
145 int num_vars_shaved_ ABSL_GUARDED_BY(mutex_) = 0;
146 int num_infeasible_found_ ABSL_GUARDED_BY(mutex_) = 0;
147};
148
149} // namespace sat
150} // namespace operations_research
151
152#endif // OR_TOOLS_SAT_SHAVING_SOLVER_H_
ObjectiveShavingSolver(const SatParameters &local_parameters, NeighborhoodGeneratorHelper *helper, SharedClasses *shared)
std::function< void()> GenerateTask(int64_t task_id) override
SubSolver(absl::string_view name, SubsolverType type)
Definition subsolver.h:48
std::function< void()> GenerateTask(int64_t task_id) override
VariablesShavingSolver(const SatParameters &local_parameters, NeighborhoodGeneratorHelper *helper, SharedClasses *shared)
void ProcessLocalResponse(const CpSolverResponse &local_response, const State &state)
In SWIG mode, we don't want anything besides these top-level includes.