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"
32 #include "ortools/util/fp_utils.h"
34 
36  double, model_validator_infinity, 1e100,
37  "Anything above or equal to this magnitude will be considered infinity.");
38 
39 namespace operations_research {
40 namespace {
41 
42 bool 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.
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());
57  }
58  return "";
59 }
60 
61 // Internal method to detect errors in a single variable.
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;
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.
83 template <typename Iterable>
84 std::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.
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;
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 
142 std::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 
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();
166 }
167 
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.";
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 
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()";
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 
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();
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 
279 std::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 
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.";
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 
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.";
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 
359 std::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 
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());
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 
416 std::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 
530 absl::optional<LazyMutableCopy<MPModelProto>>
531 ExtractValidMPModelOrPopulateResponseStatus(const MPModelRequest& request,
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();
579  error = FindErrorInMPModelDeltaProto(delta, model.get());
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.
621 std::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 
682 std::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 
774 void 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 
785 namespace {
786 void 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.
810 template <class T>
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();
814 }
815 } // namespace
816 
817 void 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...
bool IsSmallerWithinTolerance(FloatType x, FloatType y, FloatType tolerance)
Definition: fp_utils.h:153
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)
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.
void MergeMPConstraintProtoExceptTerms(const MPConstraintProto &from, MPConstraintProto *to)
int64 delta
Definition: resource.cc:1684
std::vector< int > var_indices