18 #include "absl/status/statusor.h"
19 #include "ortools/linear_solver/linear_solver.pb.h"
23 #include "ortools/sat/cp_model.pb.h"
26 #include "ortools/sat/sat_parameters.pb.h"
33 #if defined(PROTOBUF_INTERNAL_IMPL)
34 using google::protobuf::Message;
36 using google::protobuf::Message;
43 constexpr
bool kProtoLiteSatParameters =
46 MPSolverResponseStatus ToMPSolverResponseStatus(sat::CpSolverStatus status,
49 case sat::CpSolverStatus::UNKNOWN:
50 return MPSOLVER_NOT_SOLVED;
51 case sat::CpSolverStatus::MODEL_INVALID:
52 return MPSOLVER_MODEL_INVALID;
53 case sat::CpSolverStatus::FEASIBLE:
54 return has_objective ? MPSOLVER_FEASIBLE : MPSOLVER_OPTIMAL;
55 case sat::CpSolverStatus::INFEASIBLE:
56 return MPSOLVER_INFEASIBLE;
57 case sat::CpSolverStatus::OPTIMAL:
58 return MPSOLVER_OPTIMAL;
62 return MPSOLVER_ABNORMAL;
67 MPModelRequest request, std::atomic<bool>* interrupt_solve) {
70 sat::SatParameters params;
71 params.set_num_search_workers(8);
72 params.set_log_search_progress(request.enable_internal_solver_output());
73 if (request.has_solver_specific_parameters()) {
75 if (kProtoLiteSatParameters) {
76 if (!params.MergeFromString(request.solver_specific_parameters())) {
77 return absl::InvalidArgumentError(
78 "solver_specific_parameters is not a valid binary stream of the "
79 "SatParameters proto");
83 request.solver_specific_parameters(), ¶ms)) {
84 return absl::InvalidArgumentError(
85 "solver_specific_parameters is not a valid textual representation "
86 "of the SatParameters proto");
90 if (request.has_solver_time_limit_seconds()) {
91 params.set_max_time_in_seconds(
92 static_cast<double>(request.solver_time_limit_seconds()) / 1000.0);
98 if (params.log_search_progress()) {
100 sat::CpSolverResponse cp_response;
101 cp_response.set_status(sat::CpSolverStatus::MODEL_INVALID);
109 const glop::GlopParameters glop_params;
110 MPModelProto*
const mp_model = request.mutable_model();
111 std::vector<std::unique_ptr<glop::Preprocessor>> for_postsolve;
112 const bool log_info =
VLOG_IS_ON(1) || params.log_search_progress();
115 if (status == MPSolverResponseStatus::MPSOLVER_INFEASIBLE) {
116 if (params.log_search_progress()) {
118 sat::CpSolverResponse cp_response;
119 cp_response.set_status(sat::CpSolverStatus::INFEASIBLE);
122 response.set_status(MPSolverResponseStatus::MPSOLVER_INFEASIBLE);
123 response.set_status_str(
"Problem proven infeasible during MIP presolve");
130 const int num_variables = mp_model->variable_size();
131 std::vector<double> var_scaling(num_variables, 1.0);
132 if (params.mip_automatically_scale_variables()) {
135 if (params.mip_var_scaling() != 1.0) {
137 params.mip_var_scaling(), params.mip_max_bound(), mp_model);
138 for (
int i = 0; i < var_scaling.size(); ++i) {
139 var_scaling[i] *= other_scaling[i];
143 sat::CpModelProto cp_model;
145 if (params.log_search_progress()) {
147 sat::CpSolverResponse cp_response;
148 cp_response.set_status(sat::CpSolverStatus::MODEL_INVALID);
151 response.set_status(MPSOLVER_MODEL_INVALID);
152 response.set_status_str(
"Failed to convert model into CP-SAT model");
155 DCHECK_EQ(cp_model.variables().size(), var_scaling.size());
156 DCHECK_EQ(cp_model.variables().size(), mp_model->variable().size());
159 if (request.model().has_solution_hint()) {
160 auto* cp_model_hint = cp_model.mutable_solution_hint();
161 const int size = request.model().solution_hint().var_index().size();
162 for (
int i = 0; i < size; ++i) {
163 const int var = request.model().solution_hint().var_index(i);
164 if (
var >= var_scaling.size())
continue;
170 request.model().solution_hint().var_value(i) * var_scaling[
var];
171 if (std::abs(
value) > params.mip_max_bound()) {
172 value =
value > 0 ? params.mip_max_bound() : -params.mip_max_bound();
175 cp_model_hint->add_vars(
var);
176 cp_model_hint->add_values(
static_cast<int64>(std::round(
value)));
181 const int old_num_variables = mp_model->variable().size();
182 const int old_num_constraints = mp_model->constraint().size();
188 if (interrupt_solve !=
nullptr) {
192 const sat::CpSolverResponse cp_response =
199 ToMPSolverResponseStatus(cp_response.status(), cp_model.has_objective()));
200 if (
response.status() == MPSOLVER_FEASIBLE ||
201 response.status() == MPSOLVER_OPTIMAL) {
202 response.set_objective_value(cp_response.objective_value());
203 response.set_best_objective_bound(cp_response.best_objective_bound());
207 (glop::ColIndex(old_num_variables)));
210 static_cast<double>(cp_response.solution(v)) / var_scaling[v];
212 for (
int i = for_postsolve.size(); --i >= 0;) {
213 for_postsolve[i]->RecoverSolution(&solution);
224 if (kProtoLiteSatParameters) {
#define DCHECK_EQ(val1, val2)
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Class that owns everything related to a particular optimization model.
T Add(std::function< T(Model *)> f)
This makes it possible to have a nicer API on the client side, and it allows both of these forms:
T * GetOrCreate()
Returns an object of type T that is unique to this model (like a "local" singleton).
SharedResponseManager * response
void RemoveNearZeroTerms(const SatParameters ¶ms, MPModelProto *mp_model)
std::function< SatParameters(Model *)> NewSatParameters(const std::string ¶ms)
Creates parameters for the solver, which you can add to the model with.
std::string CpSolverResponseStats(const CpSolverResponse &response, bool has_objective)
Returns a string with some statistics on the solver response.
std::vector< double > DetectImpliedIntegers(bool log_info, MPModelProto *mp_model)
CpSolverResponse SolveCpModel(const CpModelProto &model_proto, Model *model)
Solves the given CpModelProto.
std::vector< double > ScaleContinuousVariables(double scaling, double max_bound, MPModelProto *mp_model)
bool ConvertMPModelProtoToCpModelProto(const SatParameters ¶ms, const MPModelProto &mp_model, CpModelProto *cp_model)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool ExtractValidMPModelInPlaceOrPopulateResponseStatus(MPModelRequest *request, MPSolutionResponse *response)
Like ExtractValidMPModelOrPopulateResponseStatus(), but works in-place: if the MPModel needed extract...
MPSolverResponseStatus ApplyMipPresolveSteps(bool log_info, const glop::GlopParameters &glop_params, MPModelProto *model, std::vector< std::unique_ptr< glop::Preprocessor >> *for_postsolve)
bool ProtobufTextFormatMergeFromString(const std::string &proto_text_string, ProtoType *proto)
std::string EncodeSatParametersAsString(const sat::SatParameters ¶meters)
absl::StatusOr< MPSolutionResponse > SatSolveProto(MPModelRequest request, std::atomic< bool > *interrupt_solve)
#define VLOG_IS_ON(verboselevel)