25#include "absl/container/flat_hash_set.h"
26#include "absl/log/check.h"
27#include "absl/memory/memory.h"
28#include "absl/status/status.h"
29#include "absl/status/statusor.h"
30#include "absl/strings/match.h"
31#include "absl/strings/str_cat.h"
32#include "absl/strings/str_join.h"
33#include "absl/strings/str_split.h"
34#include "absl/strings/string_view.h"
35#include "absl/time/clock.h"
36#include "absl/time/time.h"
37#include "absl/types/span.h"
41#include "ortools/linear_solver/linear_solver.pb.h"
44#include "ortools/math_opt/callback.pb.h"
49#include "ortools/math_opt/infeasible_subsystem.pb.h"
51#include "ortools/math_opt/model.pb.h"
52#include "ortools/math_opt/model_parameters.pb.h"
53#include "ortools/math_opt/model_update.pb.h"
54#include "ortools/math_opt/parameters.pb.h"
55#include "ortools/math_opt/result.pb.h"
56#include "ortools/math_opt/solution.pb.h"
57#include "ortools/math_opt/sparse_containers.pb.h"
60#include "ortools/sat/sat_parameters.pb.h"
77bool ApplyCutoff(
const double cutoff, MPModelProto* model) {
80 if (model->has_quadratic_objective()) {
86 MPConstraintProto*
const cutoff_constraint = model->add_constraint();
87 for (
int i = 0;
i < model->variable_size(); ++
i) {
88 const double obj_coef = model->variable(i).objective_coefficient();
90 cutoff_constraint->add_var_index(i);
91 cutoff_constraint->add_coefficient(obj_coef);
94 const double cutoff_minus_offset = cutoff - model->objective_offset();
95 if (model->maximize()) {
97 cutoff_constraint->set_lower_bound(cutoff_minus_offset);
100 cutoff_constraint->set_upper_bound(cutoff_minus_offset);
107std::vector<std::string> SetSolveParameters(
108 const SolveParametersProto& parameters,
const bool has_message_callback,
109 MPModelRequest& request) {
110 std::vector<std::string> warnings;
111 if (parameters.has_time_limit()) {
112 request.set_solver_time_limit_seconds(absl::ToDoubleSeconds(
115 if (parameters.has_iteration_limit()) {
117 "The iteration_limit parameter is not supported for CP-SAT.");
119 if (parameters.has_node_limit()) {
120 warnings.push_back(
"The node_limit parameter is not supported for CP-SAT.");
130 sat::SatParameters sat_parameters;
134 sat_parameters.set_catch_sigint_signal(
false);
136 if (parameters.has_random_seed()) {
137 sat_parameters.set_random_seed(parameters.random_seed());
139 if (parameters.has_threads()) {
140 sat_parameters.set_num_search_workers(parameters.threads());
142 if (parameters.has_relative_gap_tolerance()) {
143 sat_parameters.set_relative_gap_limit(parameters.relative_gap_tolerance());
146 if (parameters.has_absolute_gap_tolerance()) {
147 sat_parameters.set_absolute_gap_limit(parameters.absolute_gap_tolerance());
150 if (parameters.has_best_bound_limit()) {
152 "The best_bound_limit parameter is not supported for CP-SAT.");
154 if (parameters.has_objective_limit()) {
156 "The objective_limit parameter is not supported for CP-SAT.");
158 if (parameters.has_solution_limit()) {
159 if (parameters.solution_limit() == 1) {
160 sat_parameters.set_stop_after_first_solution(
true);
162 warnings.push_back(absl::StrCat(
163 "The CP-SAT solver only supports value 1 for solution_limit, found: ",
164 parameters.solution_limit()));
167 if (parameters.has_solution_pool_size()) {
168 sat_parameters.set_solution_pool_size(parameters.solution_pool_size());
169 sat_parameters.set_fill_additional_solutions_in_response(
true);
171 if (parameters.lp_algorithm() != LP_ALGORITHM_UNSPECIFIED) {
173 absl::StrCat(
"Setting lp_algorithm (was set to ",
175 ") is not supported for CP_SAT solver"));
177 if (parameters.presolve() != EMPHASIS_UNSPECIFIED) {
178 switch (parameters.presolve()) {
180 sat_parameters.set_cp_model_presolve(
false);
183 case EMPHASIS_MEDIUM:
185 case EMPHASIS_VERY_HIGH:
186 sat_parameters.set_cp_model_presolve(
true);
189 LOG(FATAL) <<
"Presolve emphasis: "
191 <<
" unknown, error setting CP-SAT parameters";
194 if (parameters.scaling() != EMPHASIS_UNSPECIFIED) {
195 warnings.push_back(absl::StrCat(
"Setting the scaling (was set to ",
197 ") is not supported for CP_SAT solver"));
199 if (parameters.cuts() != EMPHASIS_UNSPECIFIED) {
200 switch (parameters.cuts()) {
204 sat_parameters.set_add_cg_cuts(
false);
205 sat_parameters.set_add_mir_cuts(
false);
206 sat_parameters.set_add_zero_half_cuts(
false);
207 sat_parameters.set_add_clique_cuts(
false);
208 sat_parameters.set_max_all_diff_cut_size(0);
209 sat_parameters.set_add_lin_max_cuts(
false);
212 case EMPHASIS_MEDIUM:
214 case EMPHASIS_VERY_HIGH:
218 <<
" unknown, error setting CP-SAT parameters";
221 if (parameters.heuristics() != EMPHASIS_UNSPECIFIED) {
222 warnings.push_back(absl::StrCat(
"Setting the heuristics (was set to ",
224 ") is not supported for CP_SAT solver"));
226 sat_parameters.MergeFrom(parameters.cp_sat());
231 if (has_message_callback) {
234 sat_parameters.set_log_search_progress(
true);
238 sat_parameters.set_log_to_stdout(
false);
242 request.set_enable_internal_solver_output(parameters.enable_output());
245 request.set_solver_specific_parameters(
250absl::StatusOr<TerminationProto> GetTermination(
251 const bool is_interrupted,
const bool maximize,
const bool used_cutoff,
252 const MPSolutionResponse& response) {
253 switch (response.status()) {
254 case MPSOLVER_OPTIMAL:
256 response.best_objective_bound(),
257 response.status_str());
259 case MPSOLVER_INFEASIBLE:
265 maximize, FEASIBILITY_STATUS_FEASIBLE,
266 response.status_str());
269 case MPSOLVER_UNKNOWN_STATUS:
283 if (absl::StrContains(response.status_str(),
"infeasible or unbounded")) {
286 FEASIBILITY_STATUS_UNDETERMINED,
287 response.status_str());
290 response.status_str());
293 case MPSOLVER_FEASIBLE:
295 maximize, is_interrupted ? LIMIT_INTERRUPTED : LIMIT_UNDETERMINED,
296 response.objective_value(), response.best_objective_bound(),
297 response.status_str());
299 case MPSOLVER_NOT_SOLVED:
301 maximize, is_interrupted ? LIMIT_INTERRUPTED : LIMIT_UNDETERMINED,
302 std::nullopt, response.status_str());
304 case MPSOLVER_MODEL_INVALID:
305 return absl::InternalError(
306 absl::StrCat(
"cp-sat solver returned MODEL_INVALID, details: ",
307 response.status_str()));
308 case MPSOLVER_MODEL_INVALID_SOLVER_PARAMETERS:
310 <<
"invalid cp-sat parameters: " << response.status_str();
312 return absl::InternalError(
313 absl::StrCat(
"unexpected solve status: ", response.status()));
315 return absl::InternalError(
316 absl::StrCat(
"unimplemented solve status: ", response.status()));
322 const ModelProto& model,
const InitArgs&) {
326 std::vector variable_ids(model.variables().ids().begin(),
327 model.variables().ids().end());
328 std::vector linear_constraint_ids(model.linear_constraints().ids().begin(),
329 model.linear_constraints().ids().end());
330 return absl::WrapUnique(
new CpSatSolver(
331 std::move(cp_sat_model),
332 std::move(variable_ids),
333 std::move(linear_constraint_ids)));
337 const SolveParametersProto& parameters,
338 const ModelSolveParametersProto& model_parameters,
340 const CallbackRegistrationProto& callback_registration,
const Callback cb,
343 model_parameters, kCpSatSupportedStructures,
"CP-SAT"));
344 const absl::Time start = absl::Now();
347 callback_registration,
348 {CALLBACK_EVENT_MIP_SOLUTION}));
349 if (callback_registration.add_lazy_constraints()) {
350 return absl::InvalidArgumentError(
351 "CallbackRegistrationProto.add_lazy_constraints=true is not supported "
357 SolveResultProto result;
361 *req.mutable_model() = cp_sat_model_;
363 req.set_solver_type(MPModelRequest::SAT_INTEGER_PROGRAMMING);
364 bool used_cutoff =
false;
366 std::vector<std::string> param_warnings =
367 SetSolveParameters(parameters,
368 message_cb !=
nullptr, req);
369 if (parameters.has_cutoff_limit()) {
370 used_cutoff = ApplyCutoff(parameters.cutoff_limit(), req.mutable_model());
372 param_warnings.push_back(
373 "The cutoff_limit parameter not supported for quadratic objectives "
377 if (!param_warnings.empty()) {
378 return absl::InvalidArgumentError(absl::StrJoin(param_warnings,
"; "));
382 if (!model_parameters.solution_hints().empty()) {
384 for (
const auto [
id, val] :
385 MakeView(model_parameters.solution_hints(0).variable_values())) {
386 while (variable_ids_[i] <
id) {
389 req.mutable_model()->mutable_solution_hint()->add_var_index(i);
390 req.mutable_model()->mutable_solution_hint()->add_var_value(val);
398 std::atomic<bool> interrupt_solve =
false;
403 interrupter, [&]() { local_interrupter.
Interrupt(); });
405 std::function<void(
const std::string&)> logging_callback;
406 if (message_cb !=
nullptr) {
407 logging_callback = [&](absl::string_view message) {
408 message_cb(absl::StrSplit(message,
'\n'));
412 const absl::flat_hash_set<CallbackEventProto> events =
414 std::function<void(
const MPSolution&)> solution_callback;
415 absl::Status callback_error = absl::OkStatus();
416 if (events.contains(CALLBACK_EVENT_MIP_SOLUTION)) {
418 [
this, &cb, &callback_error, &local_interrupter,
419 &callback_registration](
const MPSolution& mp_solution) {
420 if (!callback_error.ok()) {
424 CallbackDataProto cb_data;
425 cb_data.set_event(CALLBACK_EVENT_MIP_SOLUTION);
426 *cb_data.mutable_primal_solution_vector() =
427 ExtractSolution(mp_solution.variable_value(),
428 callback_registration.mip_solution_filter());
429 const absl::StatusOr<CallbackResultProto> cb_result = cb(cb_data);
430 if (!cb_result.ok()) {
431 callback_error = cb_result.status();
434 local_interrupter.Interrupt();
435 }
else if (cb_result->terminate()) {
436 local_interrupter.Interrupt();
447 std::move(req), &interrupt_solve, logging_callback, solution_callback);
451 cp_sat_model_.maximize(),
452 used_cutoff, response));
453 const SparseVectorFilterProto& var_values_filter =
454 model_parameters.variable_values_filter();
456 [
this, &result, &var_values_filter](
457 const google::protobuf::RepeatedField<double>& variable_values,
460 *result.add_solutions()->mutable_primal_solution();
461 *
solution.mutable_variable_values() =
462 ExtractSolution(variable_values, var_values_filter);
463 solution.set_objective_value(objective);
464 solution.set_feasibility_status(SOLUTION_STATUS_FEASIBLE);
466 if (response.status() == MPSOLVER_OPTIMAL ||
467 response.status() == MPSOLVER_FEASIBLE) {
468 add_solution(response.variable_value(), response.objective_value());
469 for (
const MPSolution& extra_solution : response.additional_solutions()) {
470 add_solution(extra_solution.variable_value(),
471 extra_solution.objective_value());
476 absl::Now() - start, result.mutable_solve_stats()->mutable_solve_time()));
485CpSatSolver::CpSatSolver(MPModelProto cp_sat_model,
486 std::vector<int64_t> variable_ids,
487 std::vector<int64_t> linear_constraint_ids)
488 : cp_sat_model_(
std::move(cp_sat_model)),
489 variable_ids_(
std::move(variable_ids)),
490 linear_constraint_ids_(
std::move(linear_constraint_ids)) {}
492SparseDoubleVectorProto CpSatSolver::ExtractSolution(
493 const absl::Span<const double> cp_sat_variable_values,
494 const SparseVectorFilterProto& filter)
const {
497 CHECK_EQ(cp_sat_variable_values.size(), variable_ids_.size());
499 SparseVectorFilterPredicate predicate(filter);
500 SparseDoubleVectorProto result;
501 for (
int i = 0; i < variable_ids_.size(); ++i) {
502 const int64_t
id = variable_ids_[i];
503 const double value = cp_sat_variable_values[i];
504 if (predicate.AcceptsAndUpdate(
id, value)) {
506 result.add_values(value);
513 InvertedBounds inverted_bounds;
514 for (
int v = 0; v < cp_sat_model_.variable_size(); ++v) {
515 const MPVariableProto& var = cp_sat_model_.variable(v);
516 if (var.lower_bound() > var.upper_bound()) {
517 inverted_bounds.variables.push_back(variable_ids_[v]);
520 for (
int c = 0;
c < cp_sat_model_.constraint_size(); ++
c) {
521 const MPConstraintProto& cstr = cp_sat_model_.constraint(
c);
522 if (cstr.lower_bound() > cstr.upper_bound()) {
523 inverted_bounds.linear_constraints.push_back(linear_constraint_ids_[
c]);
527 return inverted_bounds;
530absl::StatusOr<ComputeInfeasibleSubsystemResultProto>
534 return absl::UnimplementedError(
535 "CPSAT does not provide a method to compute an infeasible subsystem");
#define ASSIGN_OR_RETURN(lhs, rexpr)
#define RETURN_IF_ERROR(expr)
bool IsInterrupted() const
CallbackId AddInterruptionCallback(Callback callback) const
absl::StatusOr< SolveResultProto > Solve(const SolveParametersProto ¶meters, const ModelSolveParametersProto &model_parameters, MessageCallback message_cb, const CallbackRegistrationProto &callback_registration, Callback cb, const SolveInterrupter *interrupter) override
absl::StatusOr< ComputeInfeasibleSubsystemResultProto > ComputeInfeasibleSubsystem(const SolveParametersProto ¶meters, MessageCallback message_cb, const SolveInterrupter *interrupter) override
static absl::StatusOr< std::unique_ptr< SolverInterface > > New(const ModelProto &model, const InitArgs &init_args)
absl::StatusOr< bool > Update(const ModelUpdateProto &model_update) override
std::function< void(const std::vector< std::string > &)> MessageCallback
std::function< absl::StatusOr< CallbackResultProto >( const CallbackDataProto &)> Callback
An object oriented wrapper for quadratic constraints in ModelStorage.
TerminationProto TerminateForReason(const TerminationReasonProto reason, const absl::string_view detail)
absl::Status ModelIsSupported(const ModelProto &model, const SupportedProblemStructures &support_menu, const absl::string_view solver_name)
absl::Status ModelSolveParametersAreSupported(const ModelSolveParametersProto &model_parameters, const SupportedProblemStructures &support_menu, const absl::string_view solver_name)
absl::flat_hash_set< CallbackEventProto > EventSet(const CallbackRegistrationProto &callback_registration)
Returns the callback_registration.request_registration as a set of enums.
TerminationProto OptimalTerminationProto(const double finite_primal_objective, const double dual_objective, const absl::string_view detail)
TerminationProto InfeasibleOrUnboundedTerminationProto(bool is_maximize, const FeasibilityStatusProto dual_feasibility_status, const absl::string_view detail)
absl::StatusOr<::operations_research::MPModelProto > MathOptModelToMPModelProto(const ::operations_research::math_opt::ModelProto &model)
TerminationProto FeasibleTerminationProto(const bool is_maximize, const LimitProto limit, const double primal_objective, const std::optional< double > optional_dual_objective, const absl::string_view detail)
TerminationProto NoSolutionFoundTerminationProto(const bool is_maximize, const LimitProto limit, const std::optional< double > optional_dual_objective, const absl::string_view detail)
absl::Status CheckRegisteredCallbackEvents(const CallbackRegistrationProto ®istration, const absl::flat_hash_set< CallbackEventProto > &supported_events)
SparseVectorView< T > MakeView(absl::Span< const int64_t > ids, const Collection &values)
TerminationProto CutoffTerminationProto(bool is_maximize, const absl::string_view detail)
Calls NoSolutionFoundTerminationProto() with LIMIT_CUTOFF LIMIT.
TerminationProto InfeasibleTerminationProto(bool is_maximize, const FeasibilityStatusProto dual_feasibility_status, const absl::string_view detail)
In SWIG mode, we don't want anything besides these top-level includes.
MPSolutionResponse SatSolveProto(LazyMutableCopy< MPModelRequest > request, std::atomic< bool > *interrupt_solve, std::function< void(const std::string &)> logging_callback, std::function< void(const MPSolution &)> solution_callback)
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
std::string ProtoEnumToString(ProtoEnumType enum_value)
std::string EncodeParametersAsString(const P ¶meters)
inline ::absl::StatusOr< absl::Duration > DecodeGoogleApiProto(const google::protobuf::Duration &proto)
inline ::absl::StatusOr< google::protobuf::Duration > EncodeGoogleApiProto(absl::Duration d)
StatusBuilder InvalidArgumentErrorBuilder()
#define MATH_OPT_REGISTER_SOLVER(solver_type, solver_factory)
Initialization arguments.