Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
matchers.cc
Go to the documentation of this file.
1// Copyright 2010-2025 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 <cstdlib>
19#include <optional>
20#include <ostream>
21#include <sstream>
22#include <string>
23#include <utility>
24#include <vector>
25
26#include "absl/container/flat_hash_map.h"
27#include "absl/log/check.h"
28#include "absl/log/log.h"
29#include "absl/strings/str_cat.h"
30#include "absl/types/span.h"
31#include "gtest/gtest.h"
32#include "ortools/base/gmock.h"
37
38namespace operations_research {
39namespace math_opt {
40
41namespace {
42
43using ::testing::AllOf;
44using ::testing::AllOfArray;
45using ::testing::AnyOf;
46using ::testing::AnyOfArray;
47using ::testing::Contains;
48using ::testing::DoubleNear;
49using ::testing::Eq;
50using ::testing::ExplainMatchResult;
51using ::testing::Field;
52using ::testing::IsEmpty;
53using ::testing::Matcher;
54using ::testing::MatcherInterface;
55using ::testing::MatchResultListener;
56using ::testing::Optional;
57using ::testing::PrintToString;
58using ::testing::Property;
59
60} // namespace
61
63// Printing
65
66namespace {
67
68template <typename T>
69struct Printer {
70 explicit Printer(const T& t) : value(t) {}
71
72 const T& value;
73
74 friend std::ostream& operator<<(std::ostream& os, const Printer& printer) {
75 os << PrintToString(printer.value);
76 return os;
77 }
78};
79
80template <typename T>
81Printer<T> Print(const T& t) {
82 return Printer<T>(t);
83}
84
85} // namespace
86
87void PrintTo(const PrimalSolution& primal_solution, std::ostream* const os) {
88 *os << "{variable_values: " << Print(primal_solution.variable_values)
89 << ", objective_value: " << Print(primal_solution.objective_value)
90 << ", feasibility_status: " << Print(primal_solution.feasibility_status)
91 << "}";
92}
93
94void PrintTo(const DualSolution& dual_solution, std::ostream* const os) {
95 *os << "{dual_values: " << Print(dual_solution.dual_values)
96 << ", quadratic_dual_values: "
97 << Print(dual_solution.quadratic_dual_values)
98 << ", reduced_costs: " << Print(dual_solution.reduced_costs)
99 << ", objective_value: " << Print(dual_solution.objective_value)
100 << ", feasibility_status: " << Print(dual_solution.feasibility_status)
101 << "}";
102}
103
104void PrintTo(const PrimalRay& primal_ray, std::ostream* const os) {
105 *os << "{variable_values: " << Print(primal_ray.variable_values) << "}";
107
108void PrintTo(const DualRay& dual_ray, std::ostream* const os) {
109 *os << "{dual_values: " << Print(dual_ray.dual_values)
110 << ", reduced_costs: " << Print(dual_ray.reduced_costs) << "}";
111}
112
113void PrintTo(const Basis& basis, std::ostream* const os) {
114 *os << "{variable_status: " << Print(basis.variable_status)
115 << ", constraint_status: " << Print(basis.constraint_status)
116 << ", basic_dual_feasibility: " << Print(basis.basic_dual_feasibility)
117 << "}";
118}
119
120void PrintTo(const Solution& solution, std::ostream* const os) {
121 *os << "{primal_solution: " << Print(solution.primal_solution)
122 << ", dual_solution: " << Print(solution.dual_solution)
123 << ", basis: " << Print(solution.basis) << "}";
124}
125
126void PrintTo(const SolveResult& result, std::ostream* const os) {
127 *os << "{termination: " << Print(result.termination)
128 << ", solve_stats: " << Print(result.solve_stats)
129 << ", solutions: " << Print(result.solutions)
130 << ", primal_rays: " << Print(result.primal_rays)
131 << ", dual_rays: " << Print(result.dual_rays) << "}";
132}
133
135// absl::flat_hash_map<K, double> Matchers
137
138namespace {
139
140template <typename K>
141class MapToDoubleMatcher
142 : public MatcherInterface<absl::flat_hash_map<K, double>> {
143 public:
144 MapToDoubleMatcher(absl::flat_hash_map<K, double> expected,
145 const bool all_keys, const double tolerance)
146 : expected_(std::move(expected)),
147 all_keys_(all_keys),
148 tolerance_(tolerance) {
149 for (const auto [k, v] : expected_) {
150 CHECK(!std::isnan(v)) << "Illegal NaN for key: " << k;
151 }
152 }
153
154 bool MatchAndExplain(absl::flat_hash_map<K, double> actual,
155 MatchResultListener* const os) const override {
156 for (const auto& [key, value] : expected_) {
157 if (!actual.contains(key)) {
158 *os << "expected key " << key << " not found";
159 return false;
160 }
161 if (!(std::abs(value - actual.at(key)) <= tolerance_)) {
162 *os << "value for key " << key
163 << " not within tolerance, expected: " << value
164 << " but found: " << actual.at(key);
165 return false;
166 }
167 }
168 // Post condition: expected_ is a subset of actual.
169 if (all_keys_ && expected_.size() != actual.size()) {
170 for (const auto& [key, value] : actual) {
171 if (!expected_.contains(key)) {
172 *os << "found unexpected key " << key << " in actual";
173 return false;
174 }
175 }
176 // expected_ subset of actual && expected_.size() != actual.size() implies
177 // that there is a member A of actual not in expected. When the loop above
178 // hits A, it will return, thus this line is unreachable.
179 LOG(FATAL) << "unreachable";
180 }
181 return true;
182 }
183
184 void DescribeTo(std::ostream* const os) const override {
185 if (all_keys_) {
186 *os << "has identical keys to ";
187 } else {
188 *os << "keys are contained in ";
189 }
190 PrintTo(expected_, os);
191 *os << " and values within " << tolerance_;
192 }
193
194 void DescribeNegationTo(std::ostream* const os) const override {
195 if (all_keys_) {
196 *os << "either keys differ from ";
197 } else {
198 *os << "either has a key not in ";
199 }
200 PrintTo(expected_, os);
201 *os << " or a value differs by more than " << tolerance_;
202 }
203
204 private:
205 const absl::flat_hash_map<K, double> expected_;
206 const bool all_keys_;
207 const double tolerance_;
208};
209
210} // namespace
211
212Matcher<VariableMap<double>> IsNearlySubsetOf(VariableMap<double> expected,
213 double tolerance) {
214 return Matcher<VariableMap<double>>(new MapToDoubleMatcher<Variable>(
215 std::move(expected), /*all_keys=*/false, tolerance));
217
218Matcher<VariableMap<double>> IsNear(VariableMap<double> expected,
219 const double tolerance) {
220 return Matcher<VariableMap<double>>(new MapToDoubleMatcher<Variable>(
221 std::move(expected), /*all_keys=*/true, tolerance));
223
224Matcher<LinearConstraintMap<double>> IsNearlySubsetOf(
225 LinearConstraintMap<double> expected, double tolerance) {
226 return Matcher<LinearConstraintMap<double>>(
227 new MapToDoubleMatcher<LinearConstraint>(std::move(expected),
228 /*all_keys=*/false, tolerance));
229}
230
231Matcher<LinearConstraintMap<double>> IsNear(
232 LinearConstraintMap<double> expected, const double tolerance) {
233 return Matcher<LinearConstraintMap<double>>(
234 new MapToDoubleMatcher<LinearConstraint>(std::move(expected),
235 /*all_keys=*/true, tolerance));
236}
237
238Matcher<absl::flat_hash_map<QuadraticConstraint, double>> IsNear(
239 absl::flat_hash_map<QuadraticConstraint, double> expected,
240 const double tolerance) {
241 return Matcher<absl::flat_hash_map<QuadraticConstraint, double>>(
242 new MapToDoubleMatcher<QuadraticConstraint>(
243 std::move(expected), /*all_keys=*/true, tolerance));
244}
245
246Matcher<absl::flat_hash_map<QuadraticConstraint, double>> IsNearlySubsetOf(
247 absl::flat_hash_map<QuadraticConstraint, double> expected,
248 double tolerance) {
249 return Matcher<absl::flat_hash_map<QuadraticConstraint, double>>(
250 new MapToDoubleMatcher<QuadraticConstraint>(std::move(expected),
251 /*all_keys=*/false,
252 tolerance));
253}
254
255template <typename K>
256Matcher<absl::flat_hash_map<K, double>> IsNear(
257 absl::flat_hash_map<K, double> expected, const double tolerance) {
258 return Matcher<absl::flat_hash_map<K, double>>(new MapToDoubleMatcher<K>(
259 std::move(expected), /*all_keys=*/true, tolerance));
261
262template <typename K>
263Matcher<absl::flat_hash_map<K, double>> IsNearlySubsetOf(
264 absl::flat_hash_map<K, double> expected, const double tolerance) {
265 return Matcher<absl::flat_hash_map<K, double>>(new MapToDoubleMatcher<K>(
266 std::move(expected), /*all_keys=*/false, tolerance));
268
270// Matchers for LinearExpression and QuadraticExpression
272
273testing::Matcher<LinearExpression> IsIdentical(LinearExpression expected) {
274 return LinearExpressionIsNear(expected, 0.0);
275}
276
277testing::Matcher<LinearExpression> LinearExpressionIsNear(
278 const LinearExpression expected, const double tolerance) {
279 CHECK(!std::isnan(expected.offset())) << "Illegal NaN-valued offset";
280 return AllOf(
281 Property("storage", &LinearExpression::storage, Eq(expected.storage())),
282 Property("offset", &LinearExpression::offset,
283 testing::DoubleNear(expected.offset(), tolerance)),
284 Property("terms", &LinearExpression::terms,
285 IsNear(expected.terms(), tolerance)));
286}
287
288namespace {
289testing::Matcher<BoundedLinearExpression> IsNearForSign(
290 const BoundedLinearExpression& expected, const double tolerance) {
291 return AllOf(Property("upper_bound_minus_offset",
293 testing::DoubleNear(expected.upper_bound_minus_offset(),
294 tolerance)),
295 Property("lower_bound_minus_offset",
297 testing::DoubleNear(expected.lower_bound_minus_offset(),
298 tolerance)),
299 Field("expression", &BoundedLinearExpression::expression,
300 Property("terms", &LinearExpression::terms,
301 IsNear(expected.expression.terms(), tolerance))));
302}
303} // namespace
304
305testing::Matcher<BoundedLinearExpression> IsNearlyEquivalent(
306 const BoundedLinearExpression& expected, const double tolerance) {
307 const BoundedLinearExpression expected_negation(
308 -expected.expression, /*lower_bound=*/-expected.upper_bound,
309 /*upper_bound=*/-expected.lower_bound);
310 return AnyOf(IsNearForSign(expected, tolerance),
311 IsNearForSign(expected_negation, tolerance));
312}
313
314testing::Matcher<QuadraticExpression> IsIdentical(
315 QuadraticExpression expected) {
316 CHECK(!std::isnan(expected.offset())) << "Illegal NaN-valued offset";
317 return AllOf(
318 Property("storage", &QuadraticExpression::storage,
319 Eq(expected.storage())),
320 Property("offset", &QuadraticExpression::offset,
321 testing::Eq(expected.offset())),
322 Property("linear_terms", &QuadraticExpression::linear_terms,
323 IsNear(expected.linear_terms(), /*tolerance=*/0)),
324 Property("quadratic_terms", &QuadraticExpression::quadratic_terms,
325 IsNear(expected.quadratic_terms(), /*tolerance=*/0)));
326}
327
329// Matcher helpers
331
332namespace {
333
334template <typename RayType>
335class RayMatcher : public MatcherInterface<RayType> {
336 public:
337 RayMatcher(RayType expected, const double tolerance)
338 : expected_(std::move(expected)), tolerance_(tolerance) {}
339 void DescribeTo(std::ostream* os) const final {
340 *os << "after L_inf normalization, is within tolerance: " << tolerance_
341 << " of expected: ";
342 PrintTo(expected_, os);
343 }
344 void DescribeNegationTo(std::ostream* const os) const final {
345 *os << "after L_inf normalization, is not within tolerance: " << tolerance_
346 << " of expected: ";
347 PrintTo(expected_, os);
348 }
349
350 protected:
351 const RayType expected_;
352 const double tolerance_;
353};
354
355// Alias to use the std::optional templated adaptor.
356Matcher<double> IsNear(double expected, const double tolerance) {
357 return DoubleNear(expected, tolerance);
358}
359
360template <typename Type>
361Matcher<std::optional<Type>> IsNear(std::optional<Type> expected,
362 const double tolerance) {
363 if (expected.has_value()) {
364 return Optional(IsNear(*expected, tolerance));
365 }
366 return testing::Eq(std::nullopt);
367}
368
369template <typename Type>
370Matcher<std::optional<Type>> IsNear(std::optional<Type> expected,
371 const double tolerance,
372 const bool allow_undetermined) {
373 if (expected.has_value()) {
374 return Optional(IsNear(*expected, tolerance, allow_undetermined));
375 }
376 return testing::Eq(std::nullopt);
377}
378
379// Custom std::optional for basis.
380Matcher<std::optional<Basis>> BasisIs(const std::optional<Basis>& expected) {
381 if (expected.has_value()) {
382 return Optional(BasisIs(*expected));
383 }
384 return testing::Eq(std::nullopt);
385}
386
387testing::Matcher<std::vector<Solution>> IsNear(
388 absl::Span<const Solution> expected_solutions,
389 const SolutionMatcherOptions options) {
390 if (expected_solutions.empty()) {
391 return IsEmpty();
392 }
393 std::vector<Matcher<Solution>> matchers;
394 for (const Solution& sol : expected_solutions) {
395 matchers.push_back(IsNear(sol, options));
396 }
397 return ::testing::ElementsAreArray(matchers);
398}
399
400} // namespace
401
403// Matchers for Solutions
405
406Matcher<SolutionStatus> SolutionStatusIs(const SolutionStatus expected,
407 const bool allow_undetermined) {
408 if (allow_undetermined) {
409 return AnyOf(Eq(expected), Eq(SolutionStatus::kUndetermined));
410 }
411 return Eq(expected);
412}
413
414Matcher<PrimalSolution> IsNear(PrimalSolution expected, const double tolerance,
415 const bool allow_undetermined) {
416 return AllOf(
417 Field("variable_values", &PrimalSolution::variable_values,
418 IsNear(expected.variable_values, tolerance)),
419 Field("objective_value", &PrimalSolution::objective_value,
420 IsNear(expected.objective_value, tolerance)),
421 Field("feasibility_status", &PrimalSolution::feasibility_status,
422 SolutionStatusIs(expected.feasibility_status, allow_undetermined)));
423}
425Matcher<DualSolution> IsNear(DualSolution expected, const double tolerance,
426 const bool allow_undetermined) {
427 return AllOf(
428 Field("dual_values", &DualSolution::dual_values,
429 IsNear(expected.dual_values, tolerance)),
430 Field("quadratic_dual_values", &DualSolution::quadratic_dual_values,
431 IsNear(expected.quadratic_dual_values, tolerance)),
432 Field("reduced_costs", &DualSolution::reduced_costs,
433 IsNear(expected.reduced_costs, tolerance)),
434 Field("objective_value", &DualSolution::objective_value,
435 IsNear(expected.objective_value, tolerance)),
436 Field("feasibility_status", &DualSolution::feasibility_status,
437 SolutionStatusIs(expected.feasibility_status, allow_undetermined)));
438}
439
440Matcher<Basis> BasisIs(const Basis& expected) {
441 return AllOf(Field("variable_status", &Basis::variable_status,
442 expected.variable_status),
443 Field("constraint_status", &Basis::constraint_status,
444 expected.constraint_status),
445 Field("basic_dual_feasibility", &Basis::basic_dual_feasibility,
446 expected.basic_dual_feasibility));
447}
448
449Matcher<Solution> IsNear(Solution expected,
450 const SolutionMatcherOptions options) {
451 std::vector<Matcher<Solution>> to_check;
452 if (options.check_primal) {
453 to_check.push_back(Field("primal_solution", &Solution::primal_solution,
454 IsNear(expected.primal_solution, options.tolerance,
455 options.allow_undetermined)));
456 }
457 if (options.check_dual) {
458 to_check.push_back(Field("dual_solution", &Solution::dual_solution,
459 IsNear(expected.dual_solution, options.tolerance,
460 options.allow_undetermined)));
461 }
462 if (options.check_basis) {
463 to_check.push_back(
464 Field("basis", &Solution::basis, BasisIs(expected.basis)));
465 }
466 return AllOfArray(to_check);
467}
468
470// Primal Ray Matcher
472
473namespace {
474
475template <typename K>
476double InfinityNorm(const absl::flat_hash_map<K, double>& vector) {
477 double infinity_norm = 0.0;
478 for (auto [id, value] : vector) {
479 infinity_norm = std::max(infinity_norm, std::abs(value));
480 }
481 return infinity_norm;
482}
483
484// Returns a normalized primal ray.
485//
486// The normalization is done using infinity norm:
487//
488// ray / ||ray||_inf
489//
490// If the input ray norm is zero, the ray is returned unchanged.
491PrimalRay NormalizePrimalRay(PrimalRay ray) {
492 const double norm = InfinityNorm(ray.variable_values);
493 if (norm != 0.0) {
494 for (auto& entry : ray.variable_values) {
495 entry.second /= norm;
496 }
497 }
498 return ray;
499}
500
501class PrimalRayMatcher : public RayMatcher<PrimalRay> {
502 public:
503 PrimalRayMatcher(PrimalRay expected, const double tolerance)
504 : RayMatcher(std::move(expected), tolerance) {}
505
506 bool MatchAndExplain(PrimalRay actual,
507 MatchResultListener* const os) const override {
508 auto normalized_actual = NormalizePrimalRay(actual);
509 auto normalized_expected = NormalizePrimalRay(expected_);
510 if (os->IsInterested()) {
511 *os << "actual normalized: " << PrintToString(normalized_actual)
512 << ", expected normalized: " << PrintToString(normalized_expected);
513 }
514 return ExplainMatchResult(
515 IsNear(normalized_expected.variable_values, tolerance_),
516 normalized_actual.variable_values, os);
517 }
518};
519
520} // namespace
521
522Matcher<PrimalRay> IsNear(PrimalRay expected, const double tolerance) {
523 return Matcher<PrimalRay>(
524 new PrimalRayMatcher(std::move(expected), tolerance));
525}
526
527Matcher<PrimalRay> PrimalRayIsNear(VariableMap<double> expected_var_values,
528 const double tolerance) {
529 PrimalRay expected;
530 expected.variable_values = std::move(expected_var_values);
531 return IsNear(expected, tolerance);
532}
533
534////////////////////////////////////////////////////////////////////////////////
535// Dual Ray Matcher
537
538namespace {
540// Returns a normalized dual ray.
541//
542// The normalization is done using infinity norm:
543//
544// ray / ||ray||_inf
545//
546// If the input ray norm is zero, the ray is returned unchanged.
547DualRay NormalizeDualRay(DualRay ray) {
548 const double norm =
549 std::max(InfinityNorm(ray.dual_values), InfinityNorm(ray.reduced_costs));
550 if (norm != 0.0) {
551 for (auto& entry : ray.dual_values) {
552 entry.second /= norm;
553 }
554 for (auto& entry : ray.reduced_costs) {
555 entry.second /= norm;
556 }
557 }
558 return ray;
559}
560
561class DualRayMatcher : public RayMatcher<DualRay> {
562 public:
563 DualRayMatcher(DualRay expected, const double tolerance)
564 : RayMatcher(std::move(expected), tolerance) {}
565
566 bool MatchAndExplain(DualRay actual, MatchResultListener* os) const override {
567 auto normalized_actual = NormalizeDualRay(actual);
568 auto normalized_expected = NormalizeDualRay(expected_);
569 if (os->IsInterested()) {
570 *os << "actual normalized: " << PrintToString(normalized_actual)
571 << ", expected normalized: " << PrintToString(normalized_expected);
572 }
573 return ExplainMatchResult(
574 IsNear(normalized_expected.dual_values, tolerance_),
575 normalized_actual.dual_values, os) &&
576 ExplainMatchResult(
577 IsNear(normalized_expected.reduced_costs, tolerance_),
578 normalized_actual.reduced_costs, os);
579 }
580};
581
582} // namespace
583
584Matcher<DualRay> IsNear(DualRay expected, const double tolerance) {
585 return Matcher<DualRay>(new DualRayMatcher(std::move(expected), tolerance));
586}
587
589// SolveResult termination reason matchers
591
592Matcher<ObjectiveBounds> ObjectiveBoundsNear(const ObjectiveBounds& expected,
593 const double tolerance) {
594 return AllOf(Field("primal_bound", &ObjectiveBounds::primal_bound,
595 DoubleNear(expected.primal_bound, tolerance)),
596 Field("dual_bound", &ObjectiveBounds::dual_bound,
597 DoubleNear(expected.dual_bound, tolerance)));
599
600Matcher<SolveResult> TerminatesWithOneOf(
601 const std::vector<TerminationReason>& allowed) {
602 return Field("termination", &SolveResult::termination,
603 Field("reason", &Termination::reason, AnyOfArray(allowed)));
604}
605
606Matcher<SolveResult> TerminatesWith(const TerminationReason expected) {
607 return Field("termination", &SolveResult::termination,
608 Field("reason", &Termination::reason, expected));
609}
610
611namespace {
612
613// Returns a matcher matching only Termination.limit.
614//
615// Note that this is different from LimitIs() which tests both the
616// Termination.limit and the Termination.reason.
617//
618// It matches if either the limit is the expected one, or if it is kUndetermined
619// and when allow_limit_undetermined is true.
620testing::Matcher<SolveResult> TerminationLimitIs(
621 const Limit expected, const bool allow_limit_undetermined) {
622 if (allow_limit_undetermined) {
623 return Field("termination", &SolveResult::termination,
624 Field("limit", &Termination::limit,
625 AnyOf(Limit::kUndetermined, expected)));
626 }
627 return Field("termination", &SolveResult::termination,
628 Field("limit", &Termination::limit, expected));
629}
630
631} // namespace
632
633testing::Matcher<SolveResult> TerminatesWithLimit(
634 const Limit expected, const bool allow_limit_undetermined) {
635 std::vector<Matcher<SolveResult>> matchers;
636 matchers.push_back(TerminationLimitIs(expected, allow_limit_undetermined));
637 matchers.push_back(TerminatesWithOneOf(
639 return AllOfArray(matchers);
640}
641
642testing::Matcher<SolveResult> TerminatesWithReasonFeasible(
643 const Limit expected, const bool allow_limit_undetermined) {
644 std::vector<Matcher<SolveResult>> matchers;
645 matchers.push_back(TerminationLimitIs(expected, allow_limit_undetermined));
646 matchers.push_back(TerminatesWith(TerminationReason::kFeasible));
647 return AllOfArray(matchers);
648}
650testing::Matcher<SolveResult> TerminatesWithReasonNoSolutionFound(
651 const Limit expected, const bool allow_limit_undetermined) {
652 std::vector<Matcher<SolveResult>> matchers;
653 matchers.push_back(TerminationLimitIs(expected, allow_limit_undetermined));
655 return AllOfArray(matchers);
656}
657
658template <typename MatcherType>
659std::string MatcherToStringImpl(const MatcherType& matcher, const bool negate) {
660 std::ostringstream os;
661 if (negate) {
662 matcher.DescribeNegationTo(&os);
663 } else {
664 matcher.DescribeTo(&os);
665 }
666 return os.str();
667}
668
669template <typename T>
670std::string MatcherToString(const Matcher<T>& matcher, bool negate) {
671 return MatcherToStringImpl(matcher, negate);
672}
673
674// clang-format off
675// Polymorphic matchers do not always define DescribeTo,
676// The <T> type may not be a matcher, but it will implement DescribeTo.
677// clang-format on
678template <typename T>
679std::string MatcherToString(const ::testing::PolymorphicMatcher<T>& matcher,
680 bool negate) {
681 return MatcherToStringImpl(matcher.impl(), negate);
682}
683
684MATCHER_P(FirstElementIs, first_element_matcher,
685 (negation
686 ? absl::StrCat("is empty or first element ",
687 MatcherToString(first_element_matcher, true))
688 : absl::StrCat("has at least one element and first element ",
689 MatcherToString(first_element_matcher, false)))) {
690 return ExplainMatchResult(UnorderedElementsAre(first_element_matcher),
691 absl::MakeSpan(arg).subspan(0, 1), result_listener);
692}
693
694Matcher<Termination> LimitIs(math_opt::Limit limit,
695 const Matcher<std::string> detail_matcher) {
696 return AllOf(Field("reason", &Termination::reason,
699 Field("limit", &Termination::limit, limit),
700 Field("detail", &Termination::detail, detail_matcher));
701}
702
703Matcher<Termination> ReasonIs(TerminationReason reason) {
704 return Field("reason", &Termination::reason, reason);
705}
706
707Matcher<Termination> ReasonIsOptimal() {
709}
711Matcher<ProblemStatus> ProblemStatusIs(const ProblemStatus& expected) {
712 return AllOf(
713 Field("primal_status", &ProblemStatus::primal_status,
714 expected.primal_status),
715 Field("dual_status", &ProblemStatus::dual_status, expected.dual_status),
716 Field("primal_or_dual_infeasible",
718 expected.primal_or_dual_infeasible));
720
721Matcher<Termination> TerminationIsOptimal() {
722 return AllOf(
726 .dual_status = FeasibilityStatus::kFeasible,
727 .primal_or_dual_infeasible = false})));
728}
729
730Matcher<Termination> TerminationIsOptimal(
731 const double primal_objective_value,
732 const std::optional<double> dual_objective_value, const double tolerance) {
733 return AllOf(
735 Field("objective_bounds", &Termination::objective_bounds,
736 ObjectiveBoundsNear({.primal_bound = primal_objective_value,
737 .dual_bound = dual_objective_value.value_or(
738 primal_objective_value)},
739 tolerance)));
740}
741
742Matcher<Termination> TerminationIsIgnoreDetail(const Termination& expected) {
743 return AllOf(Field("reason", &Termination::reason, expected.reason),
744 Field("limit", &Termination::limit, expected.limit));
745}
747Matcher<SolveResult> IsOptimal(
748 const std::optional<double> expected_primal_objective,
749 const double tolerance) {
750 if (expected_primal_objective.has_value()) {
751 return AllOf(
752 Field("termination", &SolveResult::termination, TerminationIsOptimal()),
753 Property("has_primal_feasible_solution",
754 &SolveResult::has_primal_feasible_solution, true),
755 Property("objective_value", &SolveResult::objective_value,
756 DoubleNear(*expected_primal_objective, tolerance)));
757 }
758 return Field("termination", &SolveResult::termination,
760}
761
762Matcher<SolveResult> IsOptimalWithSolution(
763 const double expected_objective,
764 const VariableMap<double> expected_variable_values,
765 const double tolerance) {
766 return AllOf(
767 IsOptimal(std::make_optional(expected_objective), tolerance),
769 PrimalSolution{.variable_values = expected_variable_values,
770 .objective_value = expected_objective,
771 .feasibility_status = SolutionStatus::kFeasible},
772 tolerance));
773}
774
775Matcher<SolveResult> IsOptimalWithDualSolution(
776 const double expected_objective,
777 const LinearConstraintMap<double> expected_dual_values,
778 const VariableMap<double> expected_reduced_costs, const double tolerance) {
779 return AllOf(
780 IsOptimal(std::make_optional(expected_objective), tolerance),
783 .dual_values = expected_dual_values,
784 .reduced_costs = expected_reduced_costs,
785 .objective_value = std::make_optional(expected_objective),
786 .feasibility_status = SolutionStatus::kFeasible},
787 tolerance));
788}
789
790Matcher<SolveResult> IsOptimalWithDualSolution(
791 const double expected_objective,
792 const LinearConstraintMap<double> expected_dual_values,
793 const absl::flat_hash_map<QuadraticConstraint, double>
794 expected_quadratic_dual_values,
795 const VariableMap<double> expected_reduced_costs, const double tolerance) {
796 return AllOf(
797 IsOptimal(std::make_optional(expected_objective), tolerance),
800 .dual_values = expected_dual_values,
801 .quadratic_dual_values = expected_quadratic_dual_values,
802 .reduced_costs = expected_reduced_costs,
803 .objective_value = std::make_optional(expected_objective),
804 .feasibility_status = SolutionStatus::kFeasible},
805 tolerance));
807
808Matcher<SolveResult> HasSolution(PrimalSolution expected,
809 const double tolerance) {
810 return Field(
811 "solutions", &SolveResult::solutions,
812 Contains(Field("primal_solution", &Solution::primal_solution,
813 Optional(IsNear(std::move(expected), tolerance)))));
814}
815
816Matcher<SolveResult> HasDualSolution(DualSolution expected,
817 const double tolerance) {
818 return Field(
819 "solutions", &SolveResult::solutions,
820 Contains(Field("dual_solution", &Solution::dual_solution,
821 Optional(IsNear(std::move(expected), tolerance)))));
822}
823
824Matcher<SolveResult> HasPrimalRay(PrimalRay expected, const double tolerance) {
825 return Field("primal_rays", &SolveResult::primal_rays,
826 Contains(IsNear(std::move(expected), tolerance)));
827}
828
829Matcher<SolveResult> HasPrimalRay(VariableMap<double> expected_vars,
830 const double tolerance) {
831 PrimalRay ray;
832 ray.variable_values = std::move(expected_vars);
833 return HasPrimalRay(std::move(ray), tolerance);
834}
835
836Matcher<SolveResult> HasDualRay(DualRay expected, const double tolerance) {
837 return Field("dual_rays", &SolveResult::dual_rays,
838 Contains(IsNear(std::move(expected), tolerance)));
839}
841namespace {
842
843bool MightTerminateWithRays(const TerminationReason reason) {
844 switch (reason) {
848 return true;
849 default:
850 return false;
851 }
853
854std::vector<TerminationReason> CompatibleReasons(
855 const TerminationReason expected, const bool inf_or_unb_soft_match) {
856 if (!inf_or_unb_soft_match) {
857 return {expected};
858 }
859 switch (expected) {
869 default:
870 return {expected};
871 }
872}
873
874Matcher<std::vector<Solution>> CheckSolutions(
875 absl::Span<const Solution> expected_solutions,
876 const SolveResultMatcherOptions& options) {
877 if (options.first_solution_only && !expected_solutions.empty()) {
878 return FirstElementIs(
879 IsNear(expected_solutions[0],
880 SolutionMatcherOptions{.tolerance = options.tolerance,
881 .check_primal = true,
882 .check_dual = options.check_dual,
883 .check_basis = options.check_basis}));
884 }
885 return IsNear(expected_solutions,
886 SolutionMatcherOptions{.tolerance = options.tolerance,
887 .check_primal = true,
888 .check_dual = options.check_dual,
889 .check_basis = options.check_basis});
890}
891
892template <typename RayType>
893Matcher<std::vector<RayType>> AnyRayNear(
894 const std::vector<RayType>& expected_rays, const double tolerance) {
895 std::vector<Matcher<RayType>> matchers;
896 for (const RayType& ray : expected_rays) {
897 matchers.push_back(IsNear(ray, tolerance));
898 }
899 return Contains(AnyOfArray(matchers));
900}
901
902template <typename RayType>
903Matcher<std::vector<RayType>> AllRaysNear(
904 const std::vector<RayType>& expected_rays, const double tolerance) {
905 std::vector<Matcher<RayType>> matchers;
906 for (const RayType& ray : expected_rays) {
907 matchers.push_back(IsNear(ray, tolerance));
908 }
909 return ::testing::UnorderedElementsAreArray(matchers);
910}
911
912template <typename RayType>
913Matcher<std::vector<RayType>> CheckRays(
914 const std::vector<RayType>& expected_rays, const double tolerance,
915 bool check_all) {
916 if (expected_rays.empty()) {
917 return IsEmpty();
918 }
919 if (check_all) {
920 return AllRaysNear(expected_rays, tolerance);
921 }
922 return AnyRayNear(expected_rays, tolerance);
923}
924
925} // namespace
926
927Matcher<SolveResult> IsConsistentWith(
928 const SolveResult& expected, const SolveResultMatcherOptions& options) {
929 std::vector<Matcher<SolveResult>> to_check;
930 to_check.push_back(TerminatesWithOneOf(CompatibleReasons(
931 expected.termination.reason, options.inf_or_unb_soft_match)));
932 const bool skip_solution =
933 MightTerminateWithRays(expected.termination.reason) &&
934 !options.check_solutions_if_inf_or_unbounded;
935 if (!skip_solution) {
936 to_check.push_back(Field("solutions", &SolveResult::solutions,
937 CheckSolutions(expected.solutions, options)));
938 }
939 if (options.check_rays) {
940 to_check.push_back(Field("primal_rays", &SolveResult::primal_rays,
941 CheckRays(expected.primal_rays, options.tolerance,
942 !options.first_solution_only)));
943 to_check.push_back(Field("dual_rays", &SolveResult::dual_rays,
944 CheckRays(expected.dual_rays, options.tolerance,
945 !options.first_solution_only)));
946 }
947
948 return AllOfArray(to_check);
949}
950
952// ComputeInfeasibleSubsystemResult matchers
954
955testing::Matcher<ComputeInfeasibleSubsystemResult> IsFeasible() {
956 return AllOf(
959 Field("infeasible_subsystem",
961 Property("empty", &ModelSubset::empty, true)),
963 false));
964}
965
966testing::Matcher<ComputeInfeasibleSubsystemResult> IsUndetermined() {
967 return AllOf(
970 Field("infeasible_subsystem",
972 Property("empty", &ModelSubset::empty, true)),
974 false));
975}
976
977testing::Matcher<ComputeInfeasibleSubsystemResult> IsInfeasible(
978 const std::optional<bool> expected_is_minimal,
979 const std::optional<ModelSubset> expected_infeasible_subsystem) {
980 std::vector<Matcher<ComputeInfeasibleSubsystemResult>> matchers;
981 matchers.push_back(Field("feasibility",
984 matchers.push_back(
985 Field("infeasible_subsystem",
987 Property("empty", &ModelSubset::empty, false)));
988 if (expected_is_minimal.has_value()) {
989 matchers.push_back(Field("is_minimal",
991 Eq(expected_is_minimal.value())));
992 }
993 if (expected_infeasible_subsystem.has_value()) {
994 matchers.push_back(
995 Field("infeasible_subsystem",
997 Property(&ModelSubset::Proto,
999 expected_infeasible_subsystem.value().Proto()))));
1000 }
1001 return AllOfArray(matchers);
1002}
1003
1005// Rarely used
1007
1008Matcher<UpdateResult> DidUpdate() {
1009 return Field("did_update", &UpdateResult::did_update, true);
1010}
1011
1012} // namespace math_opt
1013} // namespace operations_research
const VariableMap< double > & terms() const
Returns the terms in this expression.
const QuadraticTermMap< double > & quadratic_terms() const
Fractional InfinityNorm(const DenseColumn &v)
Returns the maximum of the coefficients of 'v'.
Definition lp_utils.cc:151
An object oriented wrapper for quadratic constraints in ModelStorage.
Definition gurobi_isv.cc:28
Matcher< SolveResult > IsOptimalWithSolution(const double expected_objective, const VariableMap< double > expected_variable_values, const double tolerance)
Definition matchers.cc:778
Matcher< SolveResult > HasPrimalRay(PrimalRay expected, const double tolerance)
Definition matchers.cc:840
Matcher< Termination > TerminationIsOptimal()
Definition matchers.cc:737
absl::flat_hash_map< Variable, V > VariableMap
Matcher< Termination > ReasonIsOptimal()
Definition matchers.cc:723
Matcher< ObjectiveBounds > ObjectiveBoundsNear(const ObjectiveBounds &expected, const double tolerance)
Definition matchers.cc:608
Matcher< SolutionStatus > SolutionStatusIs(const SolutionStatus expected, const bool allow_undetermined)
Definition matchers.cc:416
TerminationReason
The reason a call to Solve() terminates.
@ kOptimal
A provably optimal solution (up to numerical tolerances) has been found.
@ kInfeasible
The primal problem has no feasible solutions.
absl::flat_hash_map< LinearConstraint, V > LinearConstraintMap
Matcher< Termination > ReasonIs(TerminationReason reason)
Definition matchers.cc:719
Matcher< SolveResult > TerminatesWithOneOf(const std::vector< TerminationReason > &allowed)
Checks that the result has one of the allowed termination reasons.
Definition matchers.cc:616
Matcher< ProblemStatus > ProblemStatusIs(const ProblemStatus &expected)
Definition matchers.cc:727
testing::Matcher< ComputeInfeasibleSubsystemResult > IsInfeasible(const std::optional< bool > expected_is_minimal, const std::optional< ModelSubset > expected_infeasible_subsystem)
Definition matchers.cc:995
Matcher< Termination > LimitIs(math_opt::Limit limit, const Matcher< std::string > detail_matcher)
Definition matchers.cc:710
testing::Matcher< BoundedLinearExpression > IsNearlyEquivalent(const BoundedLinearExpression &expected, const double tolerance)
Definition matchers.cc:311
Matcher< SolveResult > IsConsistentWith(const SolveResult &expected, const SolveResultMatcherOptions &options)
Definition matchers.cc:943
Matcher< Termination > TerminationIsIgnoreDetail(const Termination &expected)
Definition matchers.cc:758
Matcher< SolveResult > HasSolution(PrimalSolution expected, const double tolerance)
SolveResult has a primal solution matching expected within tolerance.
Definition matchers.cc:824
SolutionStatus
Feasibility of a primal or dual solution as claimed by the solver.
Definition solution.h:39
@ kUndetermined
Solver does not claim a feasibility status.
Definition solution.h:41
@ kFeasible
Solver claims the solution is feasible.
Definition solution.h:44
Matcher< SolveResult > HasDualRay(DualRay expected, const double tolerance)
Definition matchers.cc:852
testing::Matcher< SolveResult > TerminatesWithReasonFeasible(const Limit expected, const bool allow_limit_undetermined)
Definition matchers.cc:658
Matcher< SolveResult > TerminatesWith(const TerminationReason expected)
Definition matchers.cc:622
std::string MatcherToString(const Matcher< T > &matcher, bool negate)
Definition matchers.cc:686
testing::Matcher< SolveResult > TerminatesWithLimit(const Limit expected, const bool allow_limit_undetermined)
Definition matchers.cc:649
Matcher< PrimalRay > PrimalRayIsNear(VariableMap< double > expected_var_values, const double tolerance)
Definition matchers.cc:539
std::string MatcherToStringImpl(const MatcherType &matcher, const bool negate)
Definition matchers.cc:675
std::ostream & operator<<(std::ostream &ostr, const SecondOrderConeConstraint &constraint)
testing::Matcher< LinearExpression > IsIdentical(LinearExpression expected)
Definition matchers.cc:279
Matcher< VariableMap< double > > IsNear(VariableMap< double > expected, const double tolerance)
Definition matchers.cc:222
Matcher< VariableMap< double > > IsNearlySubsetOf(VariableMap< double > expected, double tolerance)
Definition matchers.cc:216
Matcher< UpdateResult > DidUpdate()
Actual UpdateResult.did_update is true.
Definition matchers.cc:1028
void PrintTo(const PrimalSolution &primal_solution, std::ostream *const os)
Definition matchers.cc:89
MATCHER_P(FirstElementIs, first_element_matcher,(negation ? absl::StrCat("is empty or first element ", MatcherToString(first_element_matcher, true)) :absl::StrCat("has at least one element and first element ", MatcherToString(first_element_matcher, false))))
Definition matchers.cc:700
testing::Matcher< LinearExpression > LinearExpressionIsNear(const LinearExpression expected, const double tolerance)
Definition matchers.cc:283
Matcher< SolveResult > IsOptimalWithDualSolution(const double expected_objective, const LinearConstraintMap< double > expected_dual_values, const VariableMap< double > expected_reduced_costs, const double tolerance)
Definition matchers.cc:791
Matcher< SolveResult > HasDualSolution(DualSolution expected, const double tolerance)
Definition matchers.cc:832
Matcher< Basis > BasisIs(const Basis &expected)
Definition matchers.cc:450
testing::Matcher< ComputeInfeasibleSubsystemResult > IsFeasible()
Definition matchers.cc:973
testing::Matcher< ComputeInfeasibleSubsystemResult > IsUndetermined()
Definition matchers.cc:984
Matcher< SolveResult > IsOptimal(const std::optional< double > expected_primal_objective, const double tolerance)
Definition matchers.cc:763
@ kUndetermined
Solver does not claim a status.
@ kFeasible
Solver claims the problem is feasible.
@ kInfeasible
Solver claims the problem is infeasible.
testing::Matcher< SolveResult > TerminatesWithReasonNoSolutionFound(const Limit expected, const bool allow_limit_undetermined)
Definition matchers.cc:666
dual_gradient T(y - `dual_solution`) class DiagonalTrustRegionProblemFromQp
In SWIG mode, we don't want anything besides these top-level includes.
Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid
STL namespace.
internal::ProtoMatcher EqualsProto(const ::google::protobuf::Message &message)
LinearConstraintMap< BasisStatus > constraint_status
Definition solution.h:233
VariableMap< BasisStatus > variable_status
Definition solution.h:234
std::optional< SolutionStatus > basic_dual_feasibility
Definition solution.h:248
A LinearExpression with upper and lower bounds.
FeasibilityStatus feasibility
The primal feasibility status of the model, as determined by the solver.
LinearConstraintMap< double > dual_values
Definition solution.h:187
VariableMap< double > reduced_costs
Definition solution.h:188
LinearConstraintMap< double > dual_values
Definition solution.h:146
absl::flat_hash_map< QuadraticConstraint, double > quadratic_dual_values
Definition solution.h:151
std::optional< double > objective_value
Definition solution.h:153
bool empty() const
True if this object corresponds to the empty subset.
Bounds on the optimal objective value.
VariableMap< double > variable_values
Definition solution.h:119
FeasibilityStatus primal_status
Status for the primal problem.
FeasibilityStatus dual_status
Status for the dual problem (or for the dual of a continuous relaxation).
std::optional< PrimalSolution > primal_solution
Definition solution.h:269
std::optional< DualSolution > dual_solution
Definition solution.h:270
Configures SolveResult matcher IsConsistentWith() below.
Definition matchers.h:385
ProblemStatus problem_status
Feasibility statuses for primal and dual problems.
ObjectiveBounds objective_bounds
Bounds on the optimal objective value.