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