OR-Tools  8.2
model_validator.cc
Go to the documentation of this file.
1// Copyright 2010-2018 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 <algorithm>
17#include <cmath>
18#include <limits>
19
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"
30#include "ortools/port/file.h"
34
36 double, model_validator_infinity, 1e100,
37 "Anything above or equal to this magnitude will be considered infinity.");
38
39namespace operations_research {
40namespace {
41
42bool IsNanOrAbsGreaterThanOrEqual(double value, double abs_value_threshold) {
43 return std::isnan(value) || std::abs(value) >= abs_value_threshold;
44}
45
46// Internal method to detect errors in bounds. The object passed as parameter
47// must have "lower_bound" and "upper_bound" fields.
48template <typename BoundedElement>
49std::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());
57 }
58 return "";
59}
60
61// Internal method to detect errors in a single variable.
62std::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;
67
68 if (variable.is_integer() &&
69 ceil(variable.lower_bound()) > floor(variable.upper_bound())) {
70 return absl::StrCat(
71 "Infeasible bounds for integer variable: [", (variable.lower_bound()),
72 ", ", (variable.upper_bound()), "]", " translate to the empty set");
73 }
74 if (IsNanOrAbsGreaterThanOrEqual(variable.objective_coefficient(),
75 abs_value_threshold)) {
76 return absl::StrCat("Invalid objective_coefficient: ",
77 (variable.objective_coefficient()));
78 }
79 return std::string();
80}
81
82// Returns an error message if 'var_indices' contains a duplicate index.
83template <typename Iterable>
84std::string FindDuplicateVarIndex(const Iterable& var_indices,
85 std::vector<bool>* var_mask) {
86 int duplicate_var_index = -1;
87 for (const int var_index : var_indices) {
88 if ((*var_mask)[var_index]) duplicate_var_index = var_index;
89 (*var_mask)[var_index] = true;
90 }
91 // Reset "var_mask" to all false, sparsely.
92 for (const int var_index : var_indices) {
93 (*var_mask)[var_index] = false;
94 }
95 if (duplicate_var_index >= 0) {
96 return absl::StrCat("var_index #", duplicate_var_index,
97 " appears several times");
98 }
99 return "";
100}
101
102// Internal method to detect errors in a single constraint.
103// "var_mask" is a vector<bool> whose size is the number of variables in
104// the model, and it will be all set to false before and after the call.
105std::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;
111
112 // TODO(user): clarify explicitly, at least in a comment, whether we want
113 // to accept empty constraints (i.e. without variables).
114
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);
121 }
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");
127 }
128 const double coeff = constraint.coefficient(i);
129 if (IsNanOrAbsGreaterThanOrEqual(coeff, abs_value_threshold)) {
130 return absl::StrCat("coefficient(", i, ")=", (coeff), " is invalid");
131 }
132 }
133
134 const std::string error =
135 FindDuplicateVarIndex(constraint.var_index(), var_mask);
136 if (!error.empty()) return error;
137
138 // We found no error, all is fine.
139 return std::string();
140}
141
142std::string CroppedConstraintDebugString(const MPConstraintProto& constraint) {
143 const int kMaxPrintedVars = 10;
144
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(),
151 ").");
152 }
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(), ").");
157 }
158 return absl::StrCat("Constraint proto: ",
159 ProtobufShortDebugString(constraint_light), suffix_str);
160}
161
162bool 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();
166}
167
168std::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.";
173 }
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.");
177 }
178 if (!IsBoolean(model.variable(var_index))) {
179 return absl::StrCat("var_index=", var_index, " is not Boolean.");
180 }
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.");
184 }
185 const MPConstraintProto& constraint = indicator.constraint();
186 std::string error =
187 FindErrorInMPConstraint(constraint, var_mask, abs_value_threshold);
188 if (!error.empty()) {
189 // Constraint protos can be huge, theoretically. So we guard against
190 // that.
191 return absl::StrCat(error, " in constraint ",
192 CroppedConstraintDebugString(constraint));
193 }
194 return "";
195}
196
197std::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()";
203 }
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.");
207 }
208 }
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));
212 }
213 if (i == 0) continue;
214 if (sos.weight(i - 1) >= sos.weight(i)) {
215 return "SOS weights must be strictly increasing";
216 }
217 }
218
219 const std::string error = FindDuplicateVarIndex(sos.var_index(), var_mask);
220 if (!error.empty()) return error;
221
222 return "";
223}
224
225std::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();
230
231 if (qcst.var_index_size() != qcst.coefficient_size()) {
232 return "var_index_size() != coefficient_size()";
233 }
234
235 const std::string bound_error = FindErrorInBounds(qcst, abs_value_threshold);
236 if (!bound_error.empty()) return bound_error;
237
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, ")");
242 }
243
244 if (IsNanOrAbsGreaterThanOrEqual(qcst.coefficient(i),
245 abs_value_threshold)) {
246 return absl::StrCat("coefficient(", i, ")=", qcst.coefficient(i),
247 " is invalid");
248 }
249 }
250 const std::string duplicate_error =
251 FindDuplicateVarIndex(qcst.var_index(), var_mask);
252 if (!duplicate_error.empty()) return duplicate_error;
253
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";
257 }
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, ")");
262 }
263
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, ")");
267 }
268
269 if (IsNanOrAbsGreaterThanOrEqual(qcst.qcoefficient(i),
270 abs_value_threshold)) {
271 return absl::StrCat("qcoefficient(", i, ")=", qcst.qcoefficient(i),
272 " is invalid");
273 }
274 }
275
276 return "";
277}
278
279std::string FindErrorInMPAbsConstraint(const MPModelProto& model,
280 const MPAbsConstraint& abs) {
281 if (!abs.has_var_index()) {
282 return "var_index is required.";
283 }
284 if (!abs.has_resultant_var_index()) {
285 return "resultant_var_index is required.";
286 }
287
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, ")");
292 }
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, ")");
296 }
297 return "";
298}
299
300std::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.";
304 }
305 if (!and_or.has_resultant_var_index()) {
306 return "resultant_var_index is required.";
307 }
308
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, ")");
314 }
315 if (!IsBoolean(model.variable(and_or.var_index(i)))) {
316 return absl::StrCat("var_index=", i, " is not Boolean.");
317 }
318 }
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, ")");
323 }
324 if (!IsBoolean(model.variable(and_or.resultant_var_index()))) {
325 return absl::StrCat("resultant_var_index is not Boolean.");
326 }
327 return "";
328}
329
330std::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.";
335 }
336 if (!min_max.has_resultant_var_index()) {
337 return "resultant_var_index is required.";
338 }
339
340 if (IsNanOrAbsGreaterThanOrEqual(min_max.constant(), abs_value_threshold)) {
341 return absl::StrCat("Invalid constant: ", (min_max.constant()));
342 }
343
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, ")");
349 }
350 }
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, ")");
355 }
356 return "";
357}
358
359std::string FindErrorInQuadraticObjective(const MPQuadraticObjective& qobj,
360 int num_vars,
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";
365 }
366
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, ")");
371 }
372
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, ")");
376 }
377
378 if (IsNanOrAbsGreaterThanOrEqual(qobj.coefficient(i),
379 abs_value_threshold)) {
380 return absl::StrCat("coefficient(", i, ")=", (qobj.coefficient(i)),
381 " is invalid");
382 }
383 }
384 return "";
385}
386
387std::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());
394 }
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, ")");
401 }
402 if (var_in_hint[var_index]) {
403 return absl::StrCat("Duplicate var_index = ", var_index);
404 }
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)),
409 " is invalid");
410 }
411 }
412 return std::string();
413}
414} // namespace
415
416std::string FindErrorInMPModelProto(const MPModelProto& model,
417 double abs_value_threshold) {
418 // NOTE(user): Empty models are considered fine by this function, although
419 // it is not clear whether MPSolver::Solve() will always respond in the same
420 // way, depending on the solvers.
421 if (abs_value_threshold == 0.0) {
422 abs_value_threshold = absl::GetFlag(FLAGS_model_validator_infinity);
423 }
424
425 if (IsNanOrAbsGreaterThanOrEqual(model.objective_offset(),
426 abs_value_threshold)) {
427 return absl::StrCat("Invalid objective_offset: ",
428 (model.objective_offset()));
429 }
430 const int num_vars = model.variable_size();
431 const int num_cts = model.constraint_size();
432
433 // Validate variables.
434 std::string error;
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: ",
439 ProtobufShortDebugString(model.variable(i)));
440 }
441 }
442
443 // Validate constraints.
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()) {
450 // Constraint protos can be huge, theoretically. So we guard against that.
451 return absl::StrCat("In constraint #", i, ": ", error, ". ",
452 CroppedConstraintDebugString(constraint));
453 }
454 }
455
456 // Validate general constraints.
457 for (int i = 0; i < model.general_constraint_size(); ++i) {
458 const MPGeneralConstraintProto& gen_constraint =
459 model.general_constraint(i);
460 std::string error;
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);
466 break;
467
468 case MPGeneralConstraintProto::kSosConstraint:
469 error =
470 FindErrorInMPSosConstraint(model, gen_constraint.sos_constraint(),
471 &variable_appears, abs_value_threshold);
472 break;
473
474 case MPGeneralConstraintProto::kQuadraticConstraint:
475 error = FindErrorInMPQuadraticConstraint(
476 model, gen_constraint.quadratic_constraint(), &variable_appears,
477 abs_value_threshold);
478 break;
479
480 case MPGeneralConstraintProto::kAbsConstraint:
481 error =
482 FindErrorInMPAbsConstraint(model, gen_constraint.abs_constraint());
483 break;
484
485 case MPGeneralConstraintProto::kAndConstraint:
486 error = FindErrorInMPAndOrConstraint(model,
487 gen_constraint.and_constraint());
488 break;
489
490 case MPGeneralConstraintProto::kOrConstraint:
491 error =
492 FindErrorInMPAndOrConstraint(model, gen_constraint.or_constraint());
493 break;
494
495 case MPGeneralConstraintProto::kMinConstraint:
496 error = FindErrorInMPMinMaxConstraint(
497 model, gen_constraint.min_constraint(), abs_value_threshold);
498 break;
499
500 case MPGeneralConstraintProto::kMaxConstraint:
501 error = FindErrorInMPMinMaxConstraint(
502 model, gen_constraint.max_constraint(), abs_value_threshold);
503 break;
504 default:
505 return absl::StrCat("Unknown general constraint type ",
506 gen_constraint.general_constraint_case());
507 }
508 if (!error.empty()) {
509 return absl::StrCat("In general constraint #", i, ": ", error);
510 }
511 }
512
513 // Validate objectives.
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);
518 }
519
520 // Validate the solution hint.
521 error = FindErrorInSolutionHint(model.solution_hint(), num_vars,
522 abs_value_threshold);
523 if (!error.empty()) {
524 return absl::StrCat("In solution_hint(): ", error);
525 }
526
527 return std::string();
528}
529
530absl::optional<LazyMutableCopy<MPModelProto>>
532 MPSolutionResponse* response) {
533 CHECK(response != nullptr);
534
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;
539 }
540 if (request.has_model() && request.has_model_delta()) {
541 response->set_status(MPSOLVER_MODEL_INVALID);
542 response->set_status_str(
543 "Fields 'model' and 'model_delta' are mutually exclusive");
544 return absl::nullopt;
545 }
546
547 // Extract the baseline model.
548 LazyMutableCopy<MPModelProto> model(request.model());
549 if (request.has_model_delta()) {
550 // NOTE(user): This library needs to be portable, so we can't include
551 // ortools/base/file.h; see ../port/file.h.
552 std::string contents;
553 const absl::Status file_read_status = PortableFileGetContents(
554 request.model_delta().baseline_model_file_path(), &contents);
555 if (!file_read_status.ok()) {
556 response->set_status(MPSOLVER_MODEL_INVALID);
557 response->set_status_str(
558 "Error when reading model_delta.baseline_model_file_path: '" +
559 file_read_status.ToString());
560 return absl::nullopt;
561 }
562 if (!model.get_mutable()->ParseFromString(contents)) {
563 response->set_status(MPSOLVER_MODEL_INVALID);
564 response->set_status_str(
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;
569 }
570 }
571
572 // Validate the baseline model.
573 std::string error = FindErrorInMPModelProto(model.get());
574
575 // If the baseline is valid and we have a model delta, validate the delta,
576 // then apply it.
577 if (error.empty() && request.has_model_delta()) {
578 const MPModelDeltaProto& delta = request.model_delta();
580 if (error.empty()) ApplyVerifiedMPModelDelta(delta, model.get_mutable());
581 }
582
583 // Deal with errors.
584 if (!error.empty()) {
585 if (request.enable_internal_solver_output()) {
586 LOG(ERROR) << absl::StrCat("Invalid model: ", error);
587 }
588 response->set_status(absl::StrContains(error, "Infeasible")
589 ? MPSOLVER_INFEASIBLE
590 : MPSOLVER_MODEL_INVALID);
591 response->set_status_str(error);
592 return absl::nullopt;
593 }
594
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());
599 response->set_best_objective_bound(response->objective_value());
600 response->set_status_str(
601 "Requests without variables and constraints are considered OPTIMAL");
602 return absl::nullopt;
603 }
604
605 return std::move(model);
606}
607
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());
615 }
616 return true;
617}
618
619// TODO(user): Add a general FindFeasibilityErrorInSolution() and factor out the
620// common code.
621std::string FindFeasibilityErrorInSolutionHint(const MPModelProto& model,
622 double tolerance) {
623 const int num_vars = model.variable_size();
624
625 // First, we validate the solution hint.
626 std::string error =
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);
630
631 // Special error message for the empty case.
632 if (num_vars > 0 && model.solution_hint().var_index_size() == 0) {
633 return "Empty solution_hint.";
634 }
635
636 // To be feasible, the hint must not be partial.
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.");
641 }
642
643 // All the values must be exactly in the variable bounds.
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();
651 if (!IsSmallerWithinTolerance(value, ub, tolerance) ||
652 !IsSmallerWithinTolerance(lb, value, tolerance)) {
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), ".");
657 }
658 }
659
660 // All the constraints must be satisfiable.
661 for (int cst_index = 0; cst_index < model.constraint_size(); ++cst_index) {
662 const MPConstraintProto& constraint = model.constraint(cst_index);
663 AccurateSum<double> activity;
664 for (int j = 0; j < constraint.var_index_size(); ++j) {
665 activity.Add(constraint.coefficient(j) *
666 var_value[constraint.var_index(j)]);
667 }
668 const double lb = model.constraint(cst_index).lower_bound();
669 const double ub = model.constraint(cst_index).upper_bound();
670 if (!IsSmallerWithinTolerance(activity.Value(), ub, tolerance) ||
671 !IsSmallerWithinTolerance(lb, activity.Value(), tolerance)) {
672 return absl::StrCat(
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), ".");
676 }
677 }
678
679 return "";
680}
681
682std::string FindErrorInMPModelDeltaProto(const MPModelDeltaProto& delta,
683 const MPModelProto& model) {
684 const double abs_value_threshold =
685 absl::GetFlag(FLAGS_model_validator_infinity);
686 int num_vars = model.variable_size();
687 // Validate delta variables.
688 std::string error;
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;
695 if (var_index < 0) {
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);
701 } else {
702 tmp_var_proto = model.variable(var_index);
703 // NOTE(user): It is OK for the override proto to be empty, i.e. be a
704 // non-override.
705 tmp_var_proto.MergeFrom(var_override_proto);
706 error = FindErrorInMPVariable(tmp_var_proto, abs_value_threshold);
707 }
708 if (!error.empty()) {
709 return absl::StrFormat(
710 "variable_overrides with key (eg. var index) = %d: %s", var_index,
711 error);
712 }
713 }
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());
719 }
720 // Now we "officially" add the new variables to "num_vars".
721 num_vars += new_var_indices.size();
722
723 // Validate delta constraints. We can avoid going over the full
724 // var_index/coefficient of the original constraint, since the overrides are
725 // self-sufficient (i.e. the override var_index/coefficients are valid iff
726 // they would be valid in a standalone, new constraint). So we use a partial
727 // proto merger to avoid those in the baseline constraint.
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;
736 if (ct_index < 0) {
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);
743 } else {
744 // NOTE(user): We don't need to do the merging of var_index/coefficient:
745 // that part of the merged constraint will be valid iff the override is
746 // valid as a standalone var_index/coefficient map.
747 // So we simply validate a reduced version of the actual "merged"
748 // constraint, by removing the var_index/coefficient of the baseline.
749 // Benefit: the complexity is O(|constraint override|) even if the
750 // baseline constraint was huge.
751 tmp_constraint_proto.Clear();
752 MergeMPConstraintProtoExceptTerms(model.constraint(ct_index),
753 &tmp_constraint_proto);
754 tmp_constraint_proto.MergeFrom(constraint_override_proto);
755 error = FindErrorInMPConstraint(tmp_constraint_proto, &variable_appears,
756 abs_value_threshold);
757 }
758 if (!error.empty()) {
759 return absl::StrFormat(
760 "constraint_overrides with key (eg. constraint index) = %d: %s",
761 ct_index, error);
762 }
763 }
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());
769 }
770
771 return "";
772}
773
774void MergeMPConstraintProtoExceptTerms(const MPConstraintProto& from,
775 MPConstraintProto* to) {
776#define COPY_FIELD_IF_PRESENT(field) \
777 if (from.has_##field()) to->set_##field(from.field())
778 COPY_FIELD_IF_PRESENT(lower_bound);
779 COPY_FIELD_IF_PRESENT(upper_bound);
781 COPY_FIELD_IF_PRESENT(is_lazy);
782#undef COPY_FIELD_IF_PRESENT
783}
784
785namespace {
786void PruneZeroTermsInMpConstraint(MPConstraintProto* ct) {
787 // Optimize the fast path (when no term is pruned) by doing a first quick scan
788 // until the first zero.
789 int first_zero = 0;
790 while (first_zero < ct->var_index_size() &&
791 ct->coefficient(first_zero) != 0.0) {
792 ++first_zero;
793 }
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;
797 if (num_kept != i) {
798 ct->set_var_index(num_kept, ct->var_index(i));
799 ct->set_coefficient(num_kept, ct->coefficient(i));
800 }
801 ++num_kept;
802 }
803 ct->mutable_var_index()->Truncate(num_kept);
804 ct->mutable_coefficient()->Truncate(num_kept);
805}
806
807// Adds default entries to a repeated message field until it has the wanted
808// size. We don't use google::protobuf::util::Resize() because it's not
809// compatible with 'light' protos.
810template <class T>
811void ExtendRepeatedPtrFieldToSize(const int size, T* repeated_messages) {
812 DCHECK_GE(size, repeated_messages->size());
813 while (repeated_messages->size() < size) repeated_messages->Add();
814}
815} // namespace
816
817void ApplyVerifiedMPModelDelta(const MPModelDeltaProto& delta,
818 MPModelProto* model) {
819 // Apply the delta to the variables: first, resize the variable array.
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);
823 }
824 if (max_var_index >= model->variable_size()) {
825 ExtendRepeatedPtrFieldToSize(max_var_index + 1, model->mutable_variable());
826 }
827 // Then, apply the variable overrides.
828 for (const auto& p : delta.variable_overrides()) {
829 model->mutable_variable(p.first)->MergeFrom(p.second);
830 }
831
832 // Apply the delta to the constraints: first, resize the constraint array.
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);
836 }
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());
840 }
841 // Then, apply the constraint overrides.
842 for (const auto& p : delta.constraint_overrides()) {
843 const MPConstraintProto& override_ct = p.second;
844 MPConstraintProto* baseline = model->mutable_constraint(p.first);
845 // Fast path for added constraints.
846 if (p.first >= old_num_constraints) {
847 *baseline = override_ct;
848 continue;
849 }
850 MergeMPConstraintProtoExceptTerms(/*from=*/override_ct, /*to=*/baseline);
851 // Special case: the override is neutralized.
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();
860 continue;
861 }
862 // Otherwise we have to apply the term overrides. We can't do that in less
863 // than O(|baseline| + |override_ct|) because the baseline doesn't have a
864 // lookup-friendly data structure. But we still try to do it as efficiently
865 // as possible. In particular, we only use O(|override_ct|) extra memory.
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);
870 }
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);
875 it->second = 0.0; // To mark this term override as 'has been applied'.
876 }
877 PruneZeroTermsInMpConstraint(baseline);
878 // Add the term overrides which haven't been used: those are added terms.
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);
883 }
884 }
885 }
886}
887
888} // namespace operations_research
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define LOG(severity)
Definition: base/logging.h:420
void Add(const FpNumber &value)
Definition: accurate_sum.h:29
SharedResponseManager * response
const std::string name
const Constraint * ct
int64 value
GRBmodel * model
const int ERROR
Definition: log_severity.h:32
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...
std::string FindErrorInMPModelDeltaProto(const MPModelDeltaProto &delta, const MPModelProto &model)
Like FindErrorInMPModelProto, but for a MPModelDeltaProto applied to a given baseline model (assumed ...
bool IsSmallerWithinTolerance(FloatType x, FloatType y, FloatType tolerance)
Definition: fp_utils.h:153
void ApplyVerifiedMPModelDelta(const MPModelDeltaProto &delta, MPModelProto *model)
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)
Definition: file_nonport.cc:32
std::string FindFeasibilityErrorInSolutionHint(const MPModelProto &model, double tolerance)
Returns an empty string if the solution hint given in the model is a feasible solution.
std::string ProtobufShortDebugString(const P &message)
void MergeMPConstraintProtoExceptTerms(const MPConstraintProto &from, MPConstraintProto *to)
int64 delta
Definition: resource.cc:1684
std::vector< int > var_indices