1 // Copyright 2010-2021 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 
14 #include "ortools/math_opt/validators/callback_validator.h"
15 
16 #include <cmath>
17 #include <cstdint>
18 #include <limits>
19 #include <string>
20 
21 #include "ortools/base/integral_types.h"
22 #include "ortools/base/logging.h"
23 #include "google/protobuf/duration.pb.h"
24 #include "absl/status/status.h"
25 #include "absl/strings/match.h"
26 #include "absl/strings/str_cat.h"
27 #include "absl/strings/string_view.h"
28 #include "ortools/math_opt/callback.pb.h"
29 #include "ortools/math_opt/core/model_summary.h"
30 #include "ortools/math_opt/core/sparse_vector_view.h"
31 #include "ortools/math_opt/solution.pb.h"
32 #include "ortools/math_opt/sparse_containers.pb.h"
33 #include "ortools/math_opt/validators/model_parameters_validator.h"
34 #include "ortools/math_opt/validators/scalar_validator.h"
35 #include "ortools/math_opt/validators/solution_validator.h"
36 #include "ortools/math_opt/validators/sparse_vector_validator.h"
37 #include "ortools/port/proto_utils.h"
38 #include "absl/status/status.h"
39 #include "ortools/base/status_macros.h"
40 
41 namespace operations_research {
42 namespace math_opt {
43 namespace {
44 
45 constexpr double kInf = std::numeric_limits<double>::infinity();
46 
IsEventRegistered(const CallbackEventProto event,const CallbackRegistrationProto & callback_registration)47 absl::Status IsEventRegistered(
48     const CallbackEventProto event,
49     const CallbackRegistrationProto& callback_registration) {
50   // Unfortunatelly the range iterator return ints and not CallbackEventProtos.
51   const int num_events = callback_registration.request_registration_size();
52   for (int k = 0; k < num_events; ++k) {
53     if (callback_registration.request_registration(k) == event) {
54       return absl::OkStatus();
55     }
56   }
57   return absl::InvalidArgumentError(absl::StrCat(
58       "Event ", ProtoEnumToString(event),
59       " not part of the registered_events in callback_registration"));
60 }
61 
ValidateGeneratedLinearConstraint(const CallbackResultProto::GeneratedLinearConstraint & linear_constraint,const bool add_cuts,const bool add_lazy_constraints,const ModelSummary & model_summary)62 absl::Status ValidateGeneratedLinearConstraint(
63     const CallbackResultProto::GeneratedLinearConstraint& linear_constraint,
64     const bool add_cuts, const bool add_lazy_constraints,
65     const ModelSummary& model_summary) {
66   const auto coefficients = MakeView(linear_constraint.linear_expression());
67   RETURN_IF_ERROR(CheckIdsAndValues(
68       coefficients,
69       {.allow_positive_infinity = false, .allow_negative_infinity = false}))
70       << "Invalid linear_constraint coefficients";
71   RETURN_IF_ERROR(CheckIdsSubset(coefficients.ids(), model_summary.variables,
72                                  "cut variables", "model IDs"));
73   RETURN_IF_ERROR(CheckScalar(linear_constraint.lower_bound(),
74                               {.allow_positive_infinity = false}))
75       << "for GeneratedLinearConstraint.lower_bound";
76   RETURN_IF_ERROR(CheckScalar(linear_constraint.upper_bound(),
77                               {.allow_negative_infinity = false}))
78       << "for GeneratedLinearConstraint.upper_bound";
79   if (linear_constraint.lower_bound() == -kInf &&
80       linear_constraint.upper_bound() == kInf) {
81     return absl::InvalidArgumentError(
82         "Invalid GeneratedLinearConstraint, bounds [-inf,inf]");
83   }
84   if (linear_constraint.is_lazy() && !add_lazy_constraints) {
85     return absl::InvalidArgumentError(
86         "Invalid GeneratedLinearConstraint with lazy attribute set to true, "
87         "adding lazy constraints requires "
88         "CallbackRegistrationProto.add_lazy_constraints=true.");
89   }
90   if (!linear_constraint.is_lazy() && !add_cuts) {
91     return absl::InvalidArgumentError(
92         "Invalid GeneratedLinearConstraint with lazy attribute set to false, "
93         "adding cuts requires CallbackRegistrationProto.add_cuts=true.");
94   }
95   return absl::OkStatus();
96 }
97 
98 }  // namespace
ValidateCallbackRegistration(const CallbackRegistrationProto & callback_registration,const ModelSummary & model_summary)99 absl::Status ValidateCallbackRegistration(
100     const CallbackRegistrationProto& callback_registration,
101     const ModelSummary& model_summary) {
102   RETURN_IF_ERROR(ValidateSparseVectorFilter(
103       callback_registration.mip_solution_filter(), model_summary.variables))
104       << "Invalid CallbackRegistrationProto.mip_solution_filter";
105   RETURN_IF_ERROR(ValidateSparseVectorFilter(
106       callback_registration.mip_node_filter(), model_summary.variables))
107       << "Invalid CallbackRegistrationProto.mip_node_filter";
108   // Unfortunatelly the range iterator return ints and not CallbackEventProtos.
109   const int num_events = callback_registration.request_registration_size();
110   for (int k = 0; k < num_events; ++k) {
111     const CallbackEventProto requested_event =
112         callback_registration.request_registration(k);
113     if (requested_event == CALLBACK_EVENT_UNSPECIFIED ||
114         !CallbackEventProto_IsValid(requested_event)) {
115       return absl::InvalidArgumentError(absl::StrCat(
116           "Invalid event ", requested_event, " can not be registered"));
117     }
118   }
119   return absl::OkStatus();
120 }
121 
ValidateCallbackDataProto(const CallbackDataProto & cb_data,const CallbackRegistrationProto & callback_registration,const ModelSummary & model_summary)122 absl::Status ValidateCallbackDataProto(
123     const CallbackDataProto& cb_data,
124     const CallbackRegistrationProto& callback_registration,
125     const ModelSummary& model_summary) {
126   const CallbackEventProto event = cb_data.event();
127   RETURN_IF_ERROR(IsEventRegistered(event, callback_registration))
128       << "Invalid CallbackDataProto.event for given CallbackRegistrationProto";
129 
130   if (!cb_data.messages().empty() && event != CALLBACK_EVENT_MESSAGE) {
131     return absl::InvalidArgumentError(
132         absl::StrCat("Can't provide message(s) for event ", event, " (",
133                      ProtoEnumToString(event), ")"));
134   }
135 
136   const bool has_primal_solution = cb_data.has_primal_solution();
137   if (has_primal_solution && event != CALLBACK_EVENT_MIP_SOLUTION &&
138       event != CALLBACK_EVENT_MIP_NODE) {
139     return absl::InvalidArgumentError(
140         absl::StrCat("Can't provide primal_solution for event ", event, " (",
141                      ProtoEnumToString(event), ")"));
142   }
143 
144 #ifdef RETURN_IF_SCALAR
145 #error Collision in macro definition RETURN_IF_SCALAR
146 #endif
147 #define RETURN_IF_SCALAR(stat, value, option)                                 \
148   do {                                                                        \
149     if (stat.has_##value()) {                                                 \
150       RETURN_IF_ERROR(CheckScalar(static_cast<double>(stat.value()), option)) \
151           << "Invalid CallbackDataProto." << #stat << "." << #value;          \
152     }                                                                         \
153   } while (false)
154   const DoubleOptions nonan;
155   const DoubleOptions finite = {.allow_positive_infinity = false,
156                                 .allow_negative_infinity = false};
157   const DoubleOptions noneg = {.allow_positive_infinity = false,
158                                .allow_negative = false};
159   // Check PresolveStats.
160   const auto& presolve_stats = cb_data.presolve_stats();
161   RETURN_IF_SCALAR(presolve_stats, bound_changes, noneg);
162   RETURN_IF_SCALAR(presolve_stats, coefficient_changes, noneg);
163 
164   // Check SimplexStats.
165   const auto& simplex_stats = cb_data.simplex_stats();
166   RETURN_IF_SCALAR(simplex_stats, iteration_count, noneg);
167   RETURN_IF_SCALAR(simplex_stats, objective_value, finite);
168   RETURN_IF_SCALAR(simplex_stats, primal_infeasibility, noneg);
169   RETURN_IF_SCALAR(simplex_stats, dual_infeasibility, noneg);
170 
171   // Check BarrierStats.
172   const auto& barrier_stats = cb_data.barrier_stats();
173   RETURN_IF_SCALAR(barrier_stats, iteration_count, noneg);
174   RETURN_IF_SCALAR(barrier_stats, primal_objective, finite);
175   RETURN_IF_SCALAR(barrier_stats, dual_objective, finite);
176   RETURN_IF_SCALAR(barrier_stats, complementarity, finite);
177   RETURN_IF_SCALAR(barrier_stats, primal_infeasibility, noneg);
178   RETURN_IF_SCALAR(barrier_stats, dual_infeasibility, noneg);
179 
180   // Check MipStats.
181   const auto& mip_stats = cb_data.mip_stats();
182   RETURN_IF_SCALAR(mip_stats, primal_bound, nonan);
183   RETURN_IF_SCALAR(mip_stats, dual_bound, nonan);
184   RETURN_IF_SCALAR(mip_stats, explored_nodes, noneg);
185   RETURN_IF_SCALAR(mip_stats, open_nodes, noneg);
186   RETURN_IF_SCALAR(mip_stats, simplex_iterations, noneg);
187   RETURN_IF_SCALAR(mip_stats, number_of_solutions_found, noneg);
188   RETURN_IF_SCALAR(mip_stats, cutting_planes_in_lp, noneg);
189 
190   // Check runtime.
191   RETURN_IF_ERROR(CheckScalar(cb_data.runtime().seconds(), noneg))
192       << "Invalid CallbackDataProto.runtime.seconds";
193   RETURN_IF_ERROR(CheckScalar(cb_data.runtime().nanos(), noneg))
194       << "Invalid CallbackDataProto.runtime.nanos";
195 #undef RETURN_IF_SCALAR
196 
197   // Ensure required fields are available depending on event.
198   switch (event) {
199     case CALLBACK_EVENT_MIP_NODE:
200     case CALLBACK_EVENT_MIP_SOLUTION: {
201       if (has_primal_solution) {
202         const SparseVectorFilterProto& filter =
203             event == CALLBACK_EVENT_MIP_NODE
204                 ? callback_registration.mip_node_filter()
205                 : callback_registration.mip_solution_filter();
206         RETURN_IF_ERROR(ValidatePrimalSolution(cb_data.primal_solution(),
207                                                filter, model_summary))
208             << "Invalid CallbackDataProto.primal_solution";
209       } else if (event == CALLBACK_EVENT_MIP_SOLUTION) {
210         return absl::InvalidArgumentError(
211             absl::StrCat("Must provide primal_solution for event ", event, " (",
212                          ProtoEnumToString(event), ")"));
213       }
214       break;
215     }
216 
217     case CALLBACK_EVENT_MESSAGE: {
218       if (!!cb_data.messages().empty()) {
219         return absl::InvalidArgumentError(
220             absl::StrCat("Invalid CallbackDataProto.messages, must provide "
221                          "message(s) for event ",
222                          event, " (", ProtoEnumToString(event), ")"));
223       }
224       for (absl::string_view message : cb_data.messages()) {
225         // TODO(b/184047243): prefer StrContains on absl version bump
226         if (message.find('\n') != message.npos) {
227           return absl::InvalidArgumentError(
228               absl::StrCat("Invalid CallbackDataProto.messages[], message '",
229                            message, "' contains a new line character '\\n'"));
230         }
231       }
232       break;
233     }
234 
235     case CALLBACK_EVENT_UNSPECIFIED:
236       // This can not happen as a valid callback_registration can not register
237       // a CALLBACK_EVENT_UNSPECIFIED.
238       LOG(FATAL)
239           << "CALLBACK_EVENT_UNSPECIFIED can not be a registered event, this "
240              "points to either an invalid CallbackRegistrationProto (which "
241              "violates "
242              "one of the assumptions of this function), or memory corruption";
243     default:
244       // The remaining events are just for information collection. No further
245       // test required.
246       break;
247   }
248 
249   return absl::OkStatus();
250 }
251 
ValidateCallbackResultProto(const CallbackResultProto & callback_result,const CallbackEventProto callback_event,const CallbackRegistrationProto & callback_registration,const ModelSummary & model_summary)252 absl::Status ValidateCallbackResultProto(
253     const CallbackResultProto& callback_result,
254     const CallbackEventProto callback_event,
255     const CallbackRegistrationProto& callback_registration,
256     const ModelSummary& model_summary) {
257   // We assume that all arguments but the first are valid and concordant with
258   // each other. Otherwise this is an internal implementation error.
259   CHECK_OK(IsEventRegistered(callback_event, callback_registration));
260 
261   if (!callback_result.cuts().empty()) {
262     if (callback_event != CALLBACK_EVENT_MIP_NODE &&
263         callback_event != CALLBACK_EVENT_MIP_SOLUTION) {
264       return absl::InvalidArgumentError(absl::StrCat(
265           "Invalid CallbackResultProto, can't return cuts for callback_event ",
266           callback_event, "(", ProtoEnumToString(callback_event), ")"));
267     }
268     for (const CallbackResultProto::GeneratedLinearConstraint& cut :
269          callback_result.cuts()) {
270       RETURN_IF_ERROR(ValidateGeneratedLinearConstraint(
271           cut, callback_registration.add_cuts(),
272           callback_registration.add_lazy_constraints(), model_summary));
273     }
274   }
275   if (!callback_result.suggested_solution().empty()) {
276     if (callback_event != CALLBACK_EVENT_MIP_NODE) {
277       return absl::InvalidArgumentError(absl::StrCat(
278           "Invalid CallbackResultProto, can't return suggested solutions for "
279           "callback_event ",
280           callback_event, "(", ProtoEnumToString(callback_event), ")"));
281     }
282     for (const PrimalSolutionProto& primal_solution :
283          callback_result.suggested_solution()) {
284       RETURN_IF_ERROR(ValidatePrimalSolution(
285           primal_solution, SparseVectorFilterProto(), model_summary))
286           << "Invalid CallbackResultProto.suggested_solution";
287     }
288   }
289 
290   return absl::OkStatus();
291 }
292 
293 }  // namespace math_opt
294 }  // namespace operations_research
295