20 #include "absl/container/flat_hash_map.h"
21 #include "absl/container/flat_hash_set.h"
22 #include "absl/status/status.h"
23 #include "absl/strings/match.h"
24 #include "absl/strings/str_cat.h"
25 #include "absl/strings/str_format.h"
26 #include "absl/types/optional.h"
29 #include "ortools/linear_solver/linear_solver.pb.h"
36 double, model_validator_infinity, 1e100,
37 "Anything above or equal to this magnitude will be considered infinity.");
42 bool IsNanOrAbsGreaterThanOrEqual(
double value,
double abs_value_threshold) {
43 return std::isnan(
value) || std::abs(
value) >= abs_value_threshold;
48 template <
typename BoundedElement>
49 std::string FindErrorInBounds(
const BoundedElement& element,
50 double abs_value_threshold) {
51 if (std::isnan(element.lower_bound()) || std::isnan(element.upper_bound()) ||
52 element.lower_bound() >= abs_value_threshold ||
53 element.upper_bound() <= -abs_value_threshold ||
54 element.lower_bound() > element.upper_bound()) {
55 return absl::StrFormat(
"Infeasible bounds: [%f, %f]", element.lower_bound(),
56 element.upper_bound());
62 std::string FindErrorInMPVariable(
const MPVariableProto& variable,
63 double abs_value_threshold) {
64 const std::string bound_error =
65 FindErrorInBounds(variable, abs_value_threshold);
66 if (!bound_error.empty())
return bound_error;
68 if (variable.is_integer() &&
69 ceil(variable.lower_bound()) > floor(variable.upper_bound())) {
71 "Infeasible bounds for integer variable: [", (variable.lower_bound()),
72 ", ", (variable.upper_bound()),
"]",
" translate to the empty set");
74 if (IsNanOrAbsGreaterThanOrEqual(variable.objective_coefficient(),
75 abs_value_threshold)) {
76 return absl::StrCat(
"Invalid objective_coefficient: ",
77 (variable.objective_coefficient()));
83 template <
typename Iterable>
84 std::string FindDuplicateVarIndex(
const Iterable&
var_indices,
85 std::vector<bool>* var_mask) {
86 int duplicate_var_index = -1;
88 if ((*var_mask)[var_index]) duplicate_var_index = var_index;
89 (*var_mask)[var_index] =
true;
93 (*var_mask)[var_index] =
false;
95 if (duplicate_var_index >= 0) {
96 return absl::StrCat(
"var_index #", duplicate_var_index,
97 " appears several times");
105 std::string FindErrorInMPConstraint(
const MPConstraintProto& constraint,
106 std::vector<bool>* var_mask,
107 double abs_value_threshold) {
108 const std::string bound_error =
109 FindErrorInBounds(constraint, abs_value_threshold);
110 if (!bound_error.empty())
return bound_error;
115 const int num_vars_in_model = var_mask->size();
116 const int num_vars_in_ct = constraint.var_index_size();
117 const int num_coeffs_in_ct = constraint.coefficient_size();
118 if (num_vars_in_ct != num_coeffs_in_ct) {
119 return absl::StrCat(
"var_index_size() != coefficient_size() (",
120 num_vars_in_ct,
" VS ", num_coeffs_in_ct);
122 for (
int i = 0; i < num_vars_in_ct; ++i) {
123 const int var_index = constraint.var_index(i);
124 if (var_index >= num_vars_in_model || var_index < 0) {
125 return absl::StrCat(
"var_index(", i,
")=", var_index,
126 " is out of bounds");
128 const double coeff = constraint.coefficient(i);
129 if (IsNanOrAbsGreaterThanOrEqual(coeff, abs_value_threshold)) {
130 return absl::StrCat(
"coefficient(", i,
")=", (coeff),
" is invalid");
134 const std::string error =
135 FindDuplicateVarIndex(constraint.var_index(), var_mask);
136 if (!error.empty())
return error;
139 return std::string();
142 std::string CroppedConstraintDebugString(
const MPConstraintProto& constraint) {
143 const int kMaxPrintedVars = 10;
145 MPConstraintProto constraint_light = constraint;
146 std::string suffix_str;
147 if (constraint.var_index_size() > kMaxPrintedVars) {
148 constraint_light.mutable_var_index()->Truncate(kMaxPrintedVars);
149 absl::StrAppend(&suffix_str,
150 " (var_index cropped; size=", constraint.var_index_size(),
153 if (constraint.coefficient_size() > kMaxPrintedVars) {
154 constraint_light.mutable_coefficient()->Truncate(kMaxPrintedVars);
155 absl::StrAppend(&suffix_str,
" (coefficient cropped; size=",
156 constraint.coefficient_size(),
").");
158 return absl::StrCat(
"Constraint proto: ",
162 bool IsBoolean(
const MPVariableProto& variable) {
163 if (variable.lower_bound() < 0)
return false;
164 if (variable.upper_bound() > 1)
return false;
165 return variable.is_integer();
168 std::string FindErrorInMPIndicatorConstraint(
169 const MPModelProto&
model,
const MPIndicatorConstraint& indicator,
170 std::vector<bool>* var_mask,
double abs_value_threshold) {
171 if (!indicator.has_var_index()) {
172 return "var_index is required.";
174 const int var_index = indicator.var_index();
175 if (var_index < 0 || var_index >=
model.variable_size()) {
176 return absl::StrCat(
"var_index=", var_index,
" is out of bounds.");
178 if (!IsBoolean(
model.variable(var_index))) {
179 return absl::StrCat(
"var_index=", var_index,
" is not Boolean.");
181 const int var_value = indicator.var_value();
182 if (var_value < 0 || var_value > 1) {
183 return absl::StrCat(
"var_value=", var_value,
" must be 0 or 1.");
185 const MPConstraintProto& constraint = indicator.constraint();
187 FindErrorInMPConstraint(constraint, var_mask, abs_value_threshold);
188 if (!error.empty()) {
191 return absl::StrCat(error,
" in constraint ",
192 CroppedConstraintDebugString(constraint));
197 std::string FindErrorInMPSosConstraint(
const MPModelProto&
model,
198 const MPSosConstraint& sos,
199 std::vector<bool>* var_mask,
200 double abs_value_threshold) {
201 if (sos.weight_size() != 0 && sos.weight_size() != sos.var_index_size()) {
202 return "weight_size() > 0 and var_index_size() != weight_size()";
204 for (
const int var_index : sos.var_index()) {
205 if (var_index < 0 || var_index >=
model.variable_size()) {
206 return absl::StrCat(
"var_index=", var_index,
" is out of bounds.");
209 for (
int i = 0; i < sos.weight_size(); ++i) {
210 if (IsNanOrAbsGreaterThanOrEqual(sos.weight(i), abs_value_threshold)) {
211 return absl::StrCat(
"Invalid weight: ", sos.weight(i));
213 if (i == 0)
continue;
214 if (sos.weight(i - 1) >= sos.weight(i)) {
215 return "SOS weights must be strictly increasing";
219 const std::string error = FindDuplicateVarIndex(sos.var_index(), var_mask);
220 if (!error.empty())
return error;
225 std::string FindErrorInMPQuadraticConstraint(
const MPModelProto&
model,
226 const MPQuadraticConstraint& qcst,
227 std::vector<bool>* var_mask,
228 double abs_value_threshold) {
229 const int num_vars =
model.variable_size();
231 if (qcst.var_index_size() != qcst.coefficient_size()) {
232 return "var_index_size() != coefficient_size()";
235 const std::string bound_error = FindErrorInBounds(qcst, abs_value_threshold);
236 if (!bound_error.empty())
return bound_error;
238 for (
int i = 0; i < qcst.var_index_size(); ++i) {
239 if (qcst.var_index(i) < 0 || qcst.var_index(i) >= num_vars) {
240 return absl::StrCat(
"var_index(", i,
")=", qcst.var_index(i),
241 " is invalid.",
" It must be in [0, ", num_vars,
")");
244 if (IsNanOrAbsGreaterThanOrEqual(qcst.coefficient(i),
245 abs_value_threshold)) {
246 return absl::StrCat(
"coefficient(", i,
")=", qcst.coefficient(i),
250 const std::string duplicate_error =
251 FindDuplicateVarIndex(qcst.var_index(), var_mask);
252 if (!duplicate_error.empty())
return duplicate_error;
254 if (qcst.qvar1_index_size() != qcst.qvar2_index_size() ||
255 qcst.qvar1_index_size() != qcst.qcoefficient_size()) {
256 return "quadratic indices and coefficients must have the same size";
258 for (
int i = 0; i < qcst.qvar1_index_size(); ++i) {
259 if (qcst.qvar1_index(i) >= num_vars || qcst.qvar1_index(i) < 0) {
260 return absl::StrCat(
"qvar1_index(", i,
")=", qcst.qvar1_index(i),
261 " is invalid.",
" It must be in [0, ", num_vars,
")");
264 if (qcst.qvar2_index(i) >= num_vars || qcst.qvar2_index(i) < 0) {
265 return absl::StrCat(
"qvar2_index(", i,
")=", qcst.qvar2_index(i),
266 " is invalid.",
" It must be in [0, ", num_vars,
")");
269 if (IsNanOrAbsGreaterThanOrEqual(qcst.qcoefficient(i),
270 abs_value_threshold)) {
271 return absl::StrCat(
"qcoefficient(", i,
")=", qcst.qcoefficient(i),
279 std::string FindErrorInMPAbsConstraint(
const MPModelProto&
model,
280 const MPAbsConstraint& abs) {
281 if (!abs.has_var_index()) {
282 return "var_index is required.";
284 if (!abs.has_resultant_var_index()) {
285 return "resultant_var_index is required.";
288 const int num_vars =
model.variable_size();
289 if (abs.var_index() < 0 || abs.var_index() >= num_vars) {
290 return absl::StrCat(
"var_index=", abs.var_index(),
" is invalid.",
291 " It must be in [0, ", num_vars,
")");
293 if (abs.resultant_var_index() < 0 || abs.resultant_var_index() >= num_vars) {
294 return absl::StrCat(
"var_index=", abs.resultant_var_index(),
" is invalid.",
295 " It must be in [0, ", num_vars,
")");
300 std::string FindErrorInMPAndOrConstraint(
const MPModelProto&
model,
301 const MPArrayConstraint& and_or) {
302 if (and_or.var_index_size() == 0) {
303 return "var_index cannot be empty.";
305 if (!and_or.has_resultant_var_index()) {
306 return "resultant_var_index is required.";
309 const int num_vars =
model.variable_size();
310 for (
int i = 0; i < and_or.var_index_size(); ++i) {
311 if (and_or.var_index(i) < 0 || and_or.var_index(i) >= num_vars) {
312 return absl::StrCat(
"var_index(", i,
")=", and_or.var_index(i),
313 " is invalid.",
" It must be in [0, ", num_vars,
")");
315 if (!IsBoolean(
model.variable(and_or.var_index(i)))) {
316 return absl::StrCat(
"var_index=", i,
" is not Boolean.");
319 if (and_or.resultant_var_index() < 0 ||
320 and_or.resultant_var_index() >= num_vars) {
321 return absl::StrCat(
"resultant_var_index=", and_or.resultant_var_index(),
322 " is invalid.",
" It must be in [0, ", num_vars,
")");
324 if (!IsBoolean(
model.variable(and_or.resultant_var_index()))) {
325 return absl::StrCat(
"resultant_var_index is not Boolean.");
330 std::string FindErrorInMPMinMaxConstraint(
331 const MPModelProto&
model,
const MPArrayWithConstantConstraint& min_max,
332 double abs_value_threshold) {
333 if (min_max.var_index_size() == 0) {
334 return "var_index cannot be empty.";
336 if (!min_max.has_resultant_var_index()) {
337 return "resultant_var_index is required.";
340 if (IsNanOrAbsGreaterThanOrEqual(min_max.constant(), abs_value_threshold)) {
341 return absl::StrCat(
"Invalid constant: ", (min_max.constant()));
344 const int num_vars =
model.variable_size();
345 for (
int i = 0; i < min_max.var_index_size(); ++i) {
346 if (min_max.var_index(i) < 0 || min_max.var_index(i) >= num_vars) {
347 return absl::StrCat(
"var_index(", i,
")=", min_max.var_index(i),
348 " is invalid.",
" It must be in [0, ", num_vars,
")");
351 if (min_max.resultant_var_index() < 0 ||
352 min_max.resultant_var_index() >= num_vars) {
353 return absl::StrCat(
"resultant_var_index=", min_max.resultant_var_index(),
354 " is invalid.",
" It must be in [0, ", num_vars,
")");
359 std::string FindErrorInQuadraticObjective(
const MPQuadraticObjective& qobj,
361 double abs_value_threshold) {
362 if (qobj.qvar1_index_size() != qobj.qvar2_index_size() ||
363 qobj.qvar1_index_size() != qobj.coefficient_size()) {
364 return "indices and coefficients must have the same size";
367 for (
int i = 0; i < qobj.qvar1_index_size(); ++i) {
368 if (qobj.qvar1_index(i) >= num_vars || qobj.qvar1_index(i) < 0) {
369 return absl::StrCat(
"qvar1_index(", i,
")=", qobj.qvar1_index(i),
370 " is invalid.",
" It must be in [0, ", num_vars,
")");
373 if (qobj.qvar2_index(i) >= num_vars || qobj.qvar2_index(i) < 0) {
374 return absl::StrCat(
"qvar2_index(", i,
")=", qobj.qvar2_index(i),
375 " is invalid.",
" It must be in [0, ", num_vars,
")");
378 if (IsNanOrAbsGreaterThanOrEqual(qobj.coefficient(i),
379 abs_value_threshold)) {
380 return absl::StrCat(
"coefficient(", i,
")=", (qobj.coefficient(i)),
387 std::string FindErrorInSolutionHint(
388 const PartialVariableAssignment& solution_hint,
int num_vars,
389 double abs_value_threshold) {
390 if (solution_hint.var_index_size() != solution_hint.var_value_size()) {
391 return absl::StrCat(
"var_index_size() != var_value_size() [",
392 solution_hint.var_index_size(),
" VS ",
393 solution_hint.var_value_size());
395 std::vector<bool> var_in_hint(num_vars,
false);
396 for (
int i = 0; i < solution_hint.var_index_size(); ++i) {
397 const int var_index = solution_hint.var_index(i);
398 if (var_index >= num_vars || var_index < 0) {
399 return absl::StrCat(
"var_index(", i,
")=", var_index,
" is invalid.",
400 " It must be in [0, ", num_vars,
")");
402 if (var_in_hint[var_index]) {
403 return absl::StrCat(
"Duplicate var_index = ", var_index);
405 var_in_hint[var_index] =
true;
406 if (IsNanOrAbsGreaterThanOrEqual(solution_hint.var_value(i),
407 abs_value_threshold)) {
408 return absl::StrCat(
"var_value(", i,
")=", (solution_hint.var_value(i)),
412 return std::string();
417 double abs_value_threshold) {
421 if (abs_value_threshold == 0.0) {
422 abs_value_threshold = absl::GetFlag(FLAGS_model_validator_infinity);
425 if (IsNanOrAbsGreaterThanOrEqual(
model.objective_offset(),
426 abs_value_threshold)) {
427 return absl::StrCat(
"Invalid objective_offset: ",
428 (
model.objective_offset()));
430 const int num_vars =
model.variable_size();
431 const int num_cts =
model.constraint_size();
435 for (
int i = 0; i < num_vars; ++i) {
436 error = FindErrorInMPVariable(
model.variable(i), abs_value_threshold);
437 if (!error.empty()) {
438 return absl::StrCat(
"In variable #", i,
": ", error,
". Variable proto: ",
444 std::vector<bool> variable_appears(num_vars,
false);
445 for (
int i = 0; i < num_cts; ++i) {
446 const MPConstraintProto& constraint =
model.constraint(i);
447 error = FindErrorInMPConstraint(constraint, &variable_appears,
448 abs_value_threshold);
449 if (!error.empty()) {
451 return absl::StrCat(
"In constraint #", i,
": ", error,
". ",
452 CroppedConstraintDebugString(constraint));
457 for (
int i = 0; i <
model.general_constraint_size(); ++i) {
458 const MPGeneralConstraintProto& gen_constraint =
459 model.general_constraint(i);
461 switch (gen_constraint.general_constraint_case()) {
462 case MPGeneralConstraintProto::kIndicatorConstraint:
463 error = FindErrorInMPIndicatorConstraint(
464 model, gen_constraint.indicator_constraint(), &variable_appears,
465 abs_value_threshold);
468 case MPGeneralConstraintProto::kSosConstraint:
470 FindErrorInMPSosConstraint(
model, gen_constraint.sos_constraint(),
471 &variable_appears, abs_value_threshold);
474 case MPGeneralConstraintProto::kQuadraticConstraint:
475 error = FindErrorInMPQuadraticConstraint(
476 model, gen_constraint.quadratic_constraint(), &variable_appears,
477 abs_value_threshold);
480 case MPGeneralConstraintProto::kAbsConstraint:
482 FindErrorInMPAbsConstraint(
model, gen_constraint.abs_constraint());
485 case MPGeneralConstraintProto::kAndConstraint:
486 error = FindErrorInMPAndOrConstraint(
model,
487 gen_constraint.and_constraint());
490 case MPGeneralConstraintProto::kOrConstraint:
492 FindErrorInMPAndOrConstraint(
model, gen_constraint.or_constraint());
495 case MPGeneralConstraintProto::kMinConstraint:
496 error = FindErrorInMPMinMaxConstraint(
497 model, gen_constraint.min_constraint(), abs_value_threshold);
500 case MPGeneralConstraintProto::kMaxConstraint:
501 error = FindErrorInMPMinMaxConstraint(
502 model, gen_constraint.max_constraint(), abs_value_threshold);
505 return absl::StrCat(
"Unknown general constraint type ",
506 gen_constraint.general_constraint_case());
508 if (!error.empty()) {
509 return absl::StrCat(
"In general constraint #", i,
": ", error);
514 if (
model.has_quadratic_objective()) {
515 error = FindErrorInQuadraticObjective(
model.quadratic_objective(), num_vars,
516 abs_value_threshold);
517 if (!error.empty())
return absl::StrCat(
"In quadratic_objective: ", error);
521 error = FindErrorInSolutionHint(
model.solution_hint(), num_vars,
522 abs_value_threshold);
523 if (!error.empty()) {
524 return absl::StrCat(
"In solution_hint(): ", error);
527 return std::string();
530 absl::optional<LazyMutableCopy<MPModelProto>>
535 if (!request.has_model() && !request.has_model_delta()) {
536 response->set_status(MPSOLVER_OPTIMAL);
537 response->set_status_str(
"Requests without model are considered OPTIMAL");
538 return absl::nullopt;
540 if (request.has_model() && request.has_model_delta()) {
541 response->set_status(MPSOLVER_MODEL_INVALID);
543 "Fields 'model' and 'model_delta' are mutually exclusive");
544 return absl::nullopt;
549 if (request.has_model_delta()) {
552 std::string contents;
554 request.model_delta().baseline_model_file_path(), &contents);
555 if (!file_read_status.ok()) {
556 response->set_status(MPSOLVER_MODEL_INVALID);
558 "Error when reading model_delta.baseline_model_file_path: '" +
559 file_read_status.ToString());
560 return absl::nullopt;
562 if (!
model.get_mutable()->ParseFromString(contents)) {
563 response->set_status(MPSOLVER_MODEL_INVALID);
565 absl::StrFormat(
"The contents of baseline model file '%s' couldn't "
566 "be parsed as a raw serialized MPModelProto",
567 request.model_delta().baseline_model_file_path()));
568 return absl::nullopt;
577 if (error.empty() && request.has_model_delta()) {
578 const MPModelDeltaProto&
delta = request.model_delta();
584 if (!error.empty()) {
585 if (request.enable_internal_solver_output()) {
586 LOG(
ERROR) << absl::StrCat(
"Invalid model: ", error);
588 response->set_status(absl::StrContains(error,
"Infeasible")
589 ? MPSOLVER_INFEASIBLE
590 : MPSOLVER_MODEL_INVALID);
592 return absl::nullopt;
595 if (
model.get().variable_size() == 0 &&
model.get().constraint_size() == 0 &&
596 model.get().general_constraint_size() == 0) {
597 response->set_status(MPSOLVER_OPTIMAL);
598 response->set_objective_value(
model.get().objective_offset());
601 "Requests without variables and constraints are considered OPTIMAL");
602 return absl::nullopt;
605 return std::move(
model);
609 MPModelRequest* request, MPSolutionResponse*
response) {
610 absl::optional<LazyMutableCopy<MPModelProto>> lazy_copy =
612 if (!lazy_copy)
return false;
613 if (lazy_copy->was_copied()) {
614 lazy_copy->get_mutable()->Swap(request->mutable_model());
623 const int num_vars =
model.variable_size();
627 FindErrorInSolutionHint(
model.solution_hint(), num_vars,
628 absl::GetFlag(FLAGS_model_validator_infinity));
629 if (!error.empty())
return absl::StrCat(
"Invalid solution_hint: ", error);
632 if (num_vars > 0 &&
model.solution_hint().var_index_size() == 0) {
633 return "Empty solution_hint.";
637 if (
model.solution_hint().var_index_size() != num_vars) {
638 return absl::StrCat(
"Partial solution_hint: only ",
639 model.solution_hint().var_index_size(),
" out of the ",
640 num_vars,
" problem variables are set.");
644 std::vector<double> var_value(num_vars);
645 for (
int i = 0; i <
model.solution_hint().var_index_size(); ++i) {
646 const int var_index =
model.solution_hint().var_index(i);
647 const double value =
model.solution_hint().var_value(i);
648 var_value[var_index] =
value;
649 const double lb =
model.variable(var_index).lower_bound();
650 const double ub =
model.variable(var_index).upper_bound();
653 return absl::StrCat(
"Variable '",
model.variable(var_index).name(),
654 "' is set to ", (
value),
655 " which is not in the variable bounds [", (lb),
", ",
656 (ub),
"] modulo a tolerance of ", (tolerance),
".");
661 for (
int cst_index = 0; cst_index <
model.constraint_size(); ++cst_index) {
662 const MPConstraintProto& constraint =
model.constraint(cst_index);
664 for (
int j = 0; j < constraint.var_index_size(); ++j) {
665 activity.
Add(constraint.coefficient(j) *
666 var_value[constraint.var_index(j)]);
668 const double lb =
model.constraint(cst_index).lower_bound();
669 const double ub =
model.constraint(cst_index).upper_bound();
673 "Constraint '",
model.constraint(cst_index).name(),
"' has activity ",
674 (activity.
Value()),
" which is not in the constraint bounds [", (lb),
675 ", ", (ub),
"] modulo a tolerance of ", (tolerance),
".");
683 const MPModelProto&
model) {
684 const double abs_value_threshold =
685 absl::GetFlag(FLAGS_model_validator_infinity);
686 int num_vars =
model.variable_size();
689 absl::flat_hash_set<int> new_var_indices;
690 int max_var_index = num_vars - 1;
691 MPVariableProto tmp_var_proto;
692 for (
const auto& pair :
delta.variable_overrides()) {
693 const int var_index = pair.first;
694 const MPVariableProto& var_override_proto = pair.second;
696 error =
"Invalid key";
697 }
else if (var_index >= num_vars) {
698 max_var_index =
std::max(max_var_index, var_index);
699 new_var_indices.insert(var_index);
700 error = FindErrorInMPVariable(var_override_proto, abs_value_threshold);
702 tmp_var_proto =
model.variable(var_index);
705 tmp_var_proto.MergeFrom(var_override_proto);
706 error = FindErrorInMPVariable(tmp_var_proto, abs_value_threshold);
708 if (!error.empty()) {
709 return absl::StrFormat(
710 "variable_overrides with key (eg. var index) = %d: %s", var_index,
714 if (max_var_index != num_vars + new_var_indices.size() - 1) {
715 return absl::StrFormat(
716 "The added and existing variable indices do not form a dense integer "
717 "interval: oldmax=%d, max=%d, num added=%d",
718 num_vars - 1, max_var_index, new_var_indices.size());
721 num_vars += new_var_indices.size();
728 std::vector<bool> variable_appears(num_vars,
false);
729 MPConstraintProto tmp_constraint_proto;
730 const int num_constraints =
model.constraint_size();
731 absl::flat_hash_set<int> new_ct_indices;
732 int max_ct_index = num_constraints - 1;
733 for (
const auto& pair :
delta.constraint_overrides()) {
734 const int ct_index = pair.first;
735 const MPConstraintProto& constraint_override_proto = pair.second;
737 error =
"Invalid constraint index";
738 }
else if (ct_index >= num_constraints) {
739 max_ct_index =
std::max(max_ct_index, ct_index);
740 new_ct_indices.insert(ct_index);
741 error = FindErrorInMPConstraint(constraint_override_proto,
742 &variable_appears, abs_value_threshold);
751 tmp_constraint_proto.Clear();
753 &tmp_constraint_proto);
754 tmp_constraint_proto.MergeFrom(constraint_override_proto);
755 error = FindErrorInMPConstraint(tmp_constraint_proto, &variable_appears,
756 abs_value_threshold);
758 if (!error.empty()) {
759 return absl::StrFormat(
760 "constraint_overrides with key (eg. constraint index) = %d: %s",
764 if (max_ct_index != num_constraints + new_ct_indices.size() - 1) {
765 return absl::StrFormat(
766 "The added and existing constraint indices do not form a dense integer "
767 "interval: oldmax=%d, max=%d, num added=%d",
768 num_constraints - 1, max_ct_index, new_ct_indices.size());
775 MPConstraintProto* to) {
776 #define COPY_FIELD_IF_PRESENT(field) \
777 if (from.has_##field()) to->set_##field(from.field())
782 #undef COPY_FIELD_IF_PRESENT
786 void PruneZeroTermsInMpConstraint(MPConstraintProto*
ct) {
790 while (first_zero < ct->var_index_size() &&
791 ct->coefficient(first_zero) != 0.0) {
794 int num_kept = first_zero;
795 for (
int i = first_zero; i <
ct->var_index_size(); ++i) {
796 if (
ct->coefficient(i) == 0.0)
continue;
798 ct->set_var_index(num_kept,
ct->var_index(i));
799 ct->set_coefficient(num_kept,
ct->coefficient(i));
803 ct->mutable_var_index()->Truncate(num_kept);
804 ct->mutable_coefficient()->Truncate(num_kept);
811 void ExtendRepeatedPtrFieldToSize(
const int size, T* repeated_messages) {
812 DCHECK_GE(size, repeated_messages->size());
813 while (repeated_messages->size() < size) repeated_messages->Add();
818 MPModelProto*
model) {
820 int max_var_index = -1;
821 for (
const auto& p :
delta.variable_overrides()) {
822 max_var_index =
std::max(max_var_index, p.first);
824 if (max_var_index >=
model->variable_size()) {
825 ExtendRepeatedPtrFieldToSize(max_var_index + 1,
model->mutable_variable());
828 for (
const auto& p :
delta.variable_overrides()) {
829 model->mutable_variable(p.first)->MergeFrom(p.second);
833 int max_ct_index = -1;
834 for (
const auto& p :
delta.constraint_overrides()) {
835 max_ct_index =
std::max(max_ct_index, p.first);
837 const int old_num_constraints =
model->constraint_size();
838 if (max_ct_index >= old_num_constraints) {
839 ExtendRepeatedPtrFieldToSize(max_ct_index + 1,
model->mutable_constraint());
842 for (
const auto& p :
delta.constraint_overrides()) {
843 const MPConstraintProto& override_ct = p.second;
844 MPConstraintProto* baseline =
model->mutable_constraint(p.first);
846 if (p.first >= old_num_constraints) {
847 *baseline = override_ct;
852 if (override_ct.has_lower_bound() &&
853 override_ct.lower_bound() <=
854 -absl::GetFlag(FLAGS_model_validator_infinity) &&
855 override_ct.has_upper_bound() &&
856 override_ct.upper_bound() >=
857 absl::GetFlag(FLAGS_model_validator_infinity)) {
858 baseline->clear_var_index();
859 baseline->clear_coefficient();
866 absl::flat_hash_map<int, double> term_overrides;
867 term_overrides.reserve(override_ct.var_index_size());
868 for (
int i = 0; i < override_ct.var_index_size(); ++i) {
869 term_overrides[override_ct.var_index(i)] = override_ct.coefficient(i);
871 for (
int i = 0; i < baseline->var_index_size(); ++i) {
872 auto it = term_overrides.find(baseline->var_index(i));
873 if (it == term_overrides.end())
continue;
874 baseline->set_coefficient(i, it->second);
877 PruneZeroTermsInMpConstraint(baseline);
879 for (
const auto& p : term_overrides) {
880 if (p.second != 0.0) {
881 baseline->add_var_index(p.first);
882 baseline->add_coefficient(p.second);
#define DCHECK_GE(val1, val2)
void Add(const FpNumber &value)
SharedResponseManager * response
ABSL_FLAG(double, model_validator_infinity, 1e100, "Anything above or equal to this magnitude will be considered infinity.")
#define COPY_FIELD_IF_PRESENT(field)
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...
bool IsSmallerWithinTolerance(FloatType x, FloatType y, FloatType tolerance)
std::string FindErrorInMPModelDeltaProto(const MPModelDeltaProto &delta, const MPModelProto &model)
Like FindErrorInMPModelProto, but for a MPModelDeltaProto applied to a given baseline model (assumed ...
void ApplyVerifiedMPModelDelta(const MPModelDeltaProto &delta, MPModelProto *model)
std::string ProtobufShortDebugString(const P &message)
absl::optional< LazyMutableCopy< MPModelProto > > ExtractValidMPModelOrPopulateResponseStatus(const MPModelRequest &request, MPSolutionResponse *response)
If the model is valid and non-empty, returns it (possibly after extracting the model_delta).
std::string FindErrorInMPModelProto(const MPModelProto &model, double abs_value_threshold)
Returns an empty string iff the model is valid and not trivially infeasible.
::absl::Status PortableFileGetContents(absl::string_view file_name, std::string *output)
std::string FindFeasibilityErrorInSolutionHint(const MPModelProto &model, double tolerance)
Returns an empty string if the solution hint given in the model is a feasible solution.
void MergeMPConstraintProtoExceptTerms(const MPConstraintProto &from, MPConstraintProto *to)
std::vector< int > var_indices