Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
solve_impl.cc
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
15
16#include <memory>
17#include <optional>
18#include <utility>
19
20#include "absl/functional/any_invocable.h"
21#include "absl/log/check.h"
22#include "absl/memory/memory.h"
23#include "absl/status/status.h"
24#include "absl/status/statusor.h"
25#include "absl/synchronization/mutex.h"
39
41namespace {
42
43absl::StatusOr<SolveResult> CallSolve(BaseSolver& solver,
44 const ModelStorageCPtr expected_storage,
45 const SolveArguments& arguments,
46 SolveInterrupter& local_canceller) {
47 RETURN_IF_ERROR(arguments.CheckModelStorageAndCallback(expected_storage));
48
49 BaseSolver::Callback cb = nullptr;
50 absl::Mutex mutex;
51 absl::Status cb_status; // Guarded by `mutex`.
52 if (arguments.callback != nullptr) {
53 cb = [&](const CallbackDataProto& callback_data_proto) {
54 const CallbackData data(expected_storage, callback_data_proto);
55 const CallbackResult result = arguments.callback(data);
56 if (const absl::Status status =
57 result.CheckModelStorage(expected_storage);
58 !status.ok()) {
59 // Note that we use util::StatusBuilder() here as util::Annotate() is
60 // not available in open-source code.
61 util::StatusBuilder builder(status);
62 builder << "invalid CallbackResult returned by user callback";
63
64 { // Limit `lock` scope.
65 const absl::MutexLock lock(&mutex);
66 cb_status.Update(builder);
67 }
68
69 // Trigger subprocess cancellation.
70 local_canceller.Interrupt();
71
72 // Trigger early termination of the solve if cancellation is not
73 // supported (i.e. in in-process solve).
74 CallbackResultProto result_proto;
75 result_proto.set_terminate(true);
76 return result_proto;
77 }
78 return result.Proto();
79 };
80 }
81
82 ASSIGN_OR_RETURN(ModelSolveParametersProto model_parameters,
83 arguments.model_parameters.Proto());
84 const absl::StatusOr<SolveResultProto> solve_result_proto = solver.Solve(
85 {.parameters = arguments.parameters.Proto(),
86 .model_parameters = std::move(model_parameters),
87 .message_callback = arguments.message_callback,
88 .callback_registration = arguments.callback_registration.Proto(),
89 .user_cb = std::move(cb),
90 .interrupter = arguments.interrupter});
91
92 // solver.Solve() returns an error on cancellation by local_canceller but in
93 // that case we want to ignore this error and return status generated in the
94 // callback instead.
95 { // Limit `lock` scope.
96 const absl::MutexLock lock(&mutex);
97 RETURN_IF_ERROR(cb_status);
98 }
99
100 if (!solve_result_proto.ok()) {
101 return solve_result_proto.status();
102 }
103
104 return SolveResult::FromProto(expected_storage, solve_result_proto.value());
105}
106
107absl::StatusOr<ComputeInfeasibleSubsystemResult> CallComputeInfeasibleSubsystem(
108 BaseSolver& solver, const ModelStorageCPtr expected_storage,
109 const ComputeInfeasibleSubsystemArguments& arguments,
110 SolveInterrupter& local_canceller) {
112 const ComputeInfeasibleSubsystemResultProto compute_result_proto,
113 solver.ComputeInfeasibleSubsystem(
114 {.parameters = arguments.parameters.Proto(),
115 .message_callback = arguments.message_callback,
116 .interrupter = arguments.interrupter}));
117
118 return ComputeInfeasibleSubsystemResult::FromProto(expected_storage,
119 compute_result_proto);
120}
121
122} // namespace
123
124absl::StatusOr<SolveResult> SolveImpl(
125 const BaseSolverFactory solver_factory, const Model& model,
126 const SolverType solver_type, const SolveArguments& solve_args,
127 const SolveInterrupter* const user_canceller, const bool remove_names) {
128 SolveInterrupter local_canceller;
129 const ScopedSolveInterrupterCallback user_canceller_cb(
130 user_canceller, [&]() { local_canceller.Interrupt(); });
132 const std::unique_ptr<BaseSolver> solver,
133 solver_factory(EnumToProto(solver_type), model.ExportModel(remove_names),
134 &local_canceller));
135 return CallSolve(*solver, model.storage(), solve_args, local_canceller);
136}
137
138absl::StatusOr<ComputeInfeasibleSubsystemResult> ComputeInfeasibleSubsystemImpl(
139 const BaseSolverFactory solver_factory, const Model& model,
140 const SolverType solver_type,
141 const ComputeInfeasibleSubsystemArguments& compute_args,
142 const SolveInterrupter* const user_canceller, const bool remove_names) {
143 SolveInterrupter local_canceller;
144 const ScopedSolveInterrupterCallback user_canceller_cb(
145 user_canceller, [&]() { local_canceller.Interrupt(); });
147 const std::unique_ptr<BaseSolver> subprocess_solver,
148 solver_factory(EnumToProto(solver_type), model.ExportModel(remove_names),
149 &local_canceller));
150 return CallComputeInfeasibleSubsystem(*subprocess_solver, model.storage(),
151 compute_args, local_canceller);
152}
153
154absl::StatusOr<std::unique_ptr<IncrementalSolverImpl>>
157 const SolveInterrupter* const user_canceller,
158 const bool remove_names) {
159 if (model == nullptr) {
160 return absl::InvalidArgumentError("input model can't be null");
161 }
162 auto local_canceller = std::make_shared<SolveInterrupter>();
163 auto user_canceller_cb =
164 std::make_unique<const ScopedSolveInterrupterCallback>(
165 user_canceller,
166 [local_canceller]() { local_canceller->Interrupt(); });
167 std::unique_ptr<UpdateTracker> update_tracker = model->NewUpdateTracker();
168 ASSIGN_OR_RETURN(ModelProto model_proto,
169 update_tracker->ExportModel(remove_names));
171 std::unique_ptr<BaseSolver> solver,
172 solver_factory(EnumToProto(solver_type), std::move(model_proto),
173 local_canceller.get()));
174 return absl::WrapUnique<IncrementalSolverImpl>(new IncrementalSolverImpl(
175 std::move(solver_factory), solver_type, remove_names,
176 std::move(local_canceller), std::move(user_canceller_cb),
177 model->storage(), std::move(update_tracker), std::move(solver)));
178}
179
180IncrementalSolverImpl::IncrementalSolverImpl(
181 BaseSolverFactory solver_factory, SolverType solver_type,
182 const bool remove_names, std::shared_ptr<SolveInterrupter> local_canceller,
183 std::unique_ptr<const ScopedSolveInterrupterCallback> user_canceller_cb,
184 const ModelStorageCPtr expected_storage,
185 std::unique_ptr<UpdateTracker> update_tracker,
186 std::unique_ptr<BaseSolver> solver)
187 : solver_factory_(std::move(solver_factory)),
188 solver_type_(solver_type),
189 remove_names_(remove_names),
190 local_canceller_(std::move(local_canceller)),
191 user_canceller_cb_(std::move(user_canceller_cb)),
192 expected_storage_(expected_storage),
193 update_tracker_(std::move(update_tracker)),
194 solver_(std::move(solver)) {}
195
196absl::StatusOr<SolveResult> IncrementalSolverImpl::Solve(
197 const SolveArguments& arguments) {
198 // TODO: b/260337466 - Add permanent errors and concurrency protection.
199 RETURN_IF_ERROR(Update().status());
200 return SolveWithoutUpdate(arguments);
201}
202
203absl::StatusOr<ComputeInfeasibleSubsystemResult>
205 const ComputeInfeasibleSubsystemArguments& arguments) {
206 // TODO: b/260337466 - Add permanent errors and concurrency protection.
207 RETURN_IF_ERROR(Update().status());
209}
210
211absl::StatusOr<UpdateResult> IncrementalSolverImpl::Update() {
212 // TODO: b/260337466 - Add permanent errors and concurrency protection.
213 ASSIGN_OR_RETURN(std::optional<ModelUpdateProto> model_update,
214 update_tracker_->ExportModelUpdate(remove_names_));
215 if (!model_update.has_value()) {
216 return UpdateResult(true);
217 }
218
219 OR_ASSIGN_OR_RETURN3(const bool did_update,
220 solver_->Update(*std::move(model_update)),
221 _ << "update failed");
222 RETURN_IF_ERROR(update_tracker_->AdvanceCheckpoint());
223
224 if (did_update) {
225 return UpdateResult(true);
226 }
227
228 ASSIGN_OR_RETURN(ModelProto model_proto,
229 update_tracker_->ExportModel(remove_names_));
231 solver_,
232 solver_factory_(EnumToProto(solver_type_), std::move(model_proto),
233 local_canceller_.get()),
234 _ << "solver re-creation failed");
235
236 return UpdateResult(false);
237}
238
240 const SolveArguments& arguments) const {
241 // TODO: b/260337466 - Add permanent errors and concurrency protection.
242 return CallSolve(*solver_, expected_storage_, arguments, *local_canceller_);
243}
244
245absl::StatusOr<ComputeInfeasibleSubsystemResult>
247 const ComputeInfeasibleSubsystemArguments& arguments) const {
248 // TODO: b/260337466 - Add permanent errors and concurrency protection.
249 return CallComputeInfeasibleSubsystem(*solver_, expected_storage_, arguments,
250 *local_canceller_);
251}
252
253} // namespace operations_research::math_opt::internal
#define ASSIGN_OR_RETURN(lhs, rexpr)
#define RETURN_IF_ERROR(expr)
std::function< CallbackResultProto(const CallbackDataProto &)> Callback
Callback function type for MIP/LP callbacks.
Definition base_solver.h:54
absl::StatusOr< SolveResult > SolveWithoutUpdate() const
absl::StatusOr< ComputeInfeasibleSubsystemResult > ComputeInfeasibleSubsystemWithoutUpdate() const
absl::StatusOr< ComputeInfeasibleSubsystemResult > ComputeInfeasibleSubsystem()
ModelProto ExportModel(bool remove_names=false) const
Definition model.cc:300
std::unique_ptr< UpdateTracker > NewUpdateTracker()
Definition model.cc:304
ModelStorageCPtr storage() const
Definition model.h:917
absl::StatusOr< UpdateResult > Update() override
SolverType solver_type() const override
Returns the underlying solver used.
Definition solve_impl.h:98
static absl::StatusOr< std::unique_ptr< IncrementalSolverImpl > > New(BaseSolverFactory solver_factory, Model *model, SolverType solver_type, const SolveInterrupter *user_canceller, bool remove_names)
absl::StatusOr< ComputeInfeasibleSubsystemResult > ComputeInfeasibleSubsystemImpl(const BaseSolverFactory solver_factory, const Model &model, const SolverType solver_type, const ComputeInfeasibleSubsystemArguments &compute_args, const SolveInterrupter *const user_canceller, const bool remove_names)
absl::AnyInvocable< absl::StatusOr< std::unique_ptr< BaseSolver > >( SolverTypeProto solver_type, ModelProto model, SolveInterrupter *local_canceller) const > BaseSolverFactory
Definition solve_impl.h:50
absl::StatusOr< SolveResult > SolveImpl(const BaseSolverFactory solver_factory, const Model &model, const SolverType solver_type, const SolveArguments &solve_args, const SolveInterrupter *const user_canceller, const bool remove_names)
absl::Nonnull< const ModelStorage * > ModelStorageCPtr
SolverType
The solvers supported by MathOpt.
Definition parameters.h:41
Enum< E >::Proto EnumToProto(std::optional< E > value)
Definition enums.h:270
STL namespace.
Arguments passed to ComputeInfeasibleSubsystem() to control the solver.
static absl::StatusOr< ComputeInfeasibleSubsystemResult > FromProto(ModelStorageCPtr model, const ComputeInfeasibleSubsystemResultProto &result_proto)
Result of the Update() on an incremental solver.
#define OR_ASSIGN_OR_RETURN3(lhs, rexpr, error_expression)