Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
math_opt_proto_utils.h
Go to the documentation of this file.
1// Copyright 2010-2024 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#ifndef OR_TOOLS_MATH_OPT_CORE_MATH_OPT_PROTO_UTILS_H_
15#define OR_TOOLS_MATH_OPT_CORE_MATH_OPT_PROTO_UTILS_H_
16
17#include <cstdint>
18#include <optional>
19
20#include "absl/base/attributes.h"
21#include "absl/container/flat_hash_set.h"
22#include "absl/log/check.h"
23#include "absl/status/status.h"
24#include "absl/strings/string_view.h"
25#include "ortools/math_opt/callback.pb.h"
26#include "ortools/math_opt/infeasible_subsystem.pb.h"
27#include "ortools/math_opt/model.pb.h"
28#include "ortools/math_opt/model_parameters.pb.h"
29#include "ortools/math_opt/model_update.pb.h"
30#include "ortools/math_opt/result.pb.h"
31#include "ortools/math_opt/solution.pb.h"
32#include "ortools/math_opt/sparse_containers.pb.h"
33
35
36// Returns solve_result.termination.objective_bounds if present. Otherwise,
37// it builds ObjectiveBoundsProto from
38// solve_result.solve_stats.best_primal/dual_bound
39// TODO(b/290091715): Remove once solve_stats.best_primal/dual_bound is removed
40// and we know termination.objective_bounds will always be present.
41ObjectiveBoundsProto GetObjectiveBounds(const SolveResultProto& solve_result);
42
43// Returns solve_result.termination.problem_status if present. Otherwise,
44// it returns solve_result.solve_stats.problem_status
45// TODO(b/290091715): Remove once solve_stats.problem_status is removed and we
46// know termination.problem_status will always be present.
47ProblemStatusProto GetProblemStatus(const SolveResultProto& solve_result);
48
49inline int NumVariables(const VariablesProto& variables) {
50 return variables.ids_size();
51}
52
53inline int NumConstraints(const LinearConstraintsProto& linear_constraints) {
54 return linear_constraints.ids_size();
55}
56
57inline int NumMatrixNonzeros(const SparseDoubleMatrixProto& matrix) {
58 return matrix.row_ids_size();
59}
60
61// Returns the id of the first variable if there is one. If the input proto is
62// valid, this will also be the smallest id.
63inline std::optional<int64_t> FirstVariableId(const VariablesProto& variables) {
64 return variables.ids().empty() ? std::nullopt
65 : std::make_optional(variables.ids()[0]);
66}
67
68// Returns the id of the first linear constraint if there is one. If the input
69// proto is valid, this will also be the smallest id.
70inline std::optional<int64_t> FirstLinearConstraintId(
71 const LinearConstraintsProto& linear_constraints) {
72 return linear_constraints.ids().empty()
73 ? std::nullopt
74 : std::make_optional(linear_constraints.ids()[0]);
75}
76
77// Removes the items in the sparse double vector for all indices whose value is
78// exactly 0.0.
79//
80// NaN values are kept in place.
81//
82// The function asserts that input is a valid sparse vector, i.e. that the
83// number of values and ids match.
84void RemoveSparseDoubleVectorZeros(SparseDoubleVectorProto& sparse_vector);
85
86// A utility class that tests if a pair (id, value) should be filtered based on
87// an input SparseVectorFilterProto.
88//
89// This predicate expects the input is sorted by ids. In non-optimized builds,
90// it will check that this is the case.
92 public:
93 // Builds a predicate based on the input filter. A reference to this filter is
94 // kept so the caller must make sure this filter outlives the predicate.
95 //
96 // The filter.filtered_ids is expected to be sorted and not contain
97 // duplicates. In non-optimized builds, it will be CHECKed.
98 explicit SparseVectorFilterPredicate(const SparseVectorFilterProto& filter);
99
100 // Returns true if the input value should be kept, false if it should be
101 // ignored since it is not selected by the filter.
102 //
103 // This function is expected to be called with strictly increasing ids. In
104 // non-optimized builds it will CHECK that this is the case. It updates an
105 // internal counter when filtering by ids.
106 template <typename Value>
107 bool AcceptsAndUpdate(int64_t id, const Value& value);
108
109 private:
110 const SparseVectorFilterProto& filter_;
111
112 // Index of the next element to consider in filter_.filtered_ids().
113 int next_filtered_id_index_ = 0;
114
115#ifndef NDEBUG
116 // Invariant: next input id must be >= next_input_id_lower_bound_.
117 //
118 // The initial value is 0 since all ids are expected to be non-negative.
119 int64_t next_input_id_lower_bound_ = 0;
120#endif // NDEBUG
121};
122
123// Applies filter to each element of input and returns the elements that remain.
124//
125// TODO(b/261603235): this function is not very efficient, decide if this
126// matters.
127SparseDoubleVectorProto FilterSparseVector(
128 const SparseDoubleVectorProto& input,
129 const SparseVectorFilterProto& filter);
130
131// Applies the primal, dual and reduced costs filters from model_solve_params
132// to the primal solution variable values, dual solution dual values, and dual
133// solution reduced costs, respectively, and overwriting these values with
134// the results.
135//
136// Warning: solution is modified in place.
137//
138// TODO(b/261603235): this function is not very efficient, decide if this
139// matters.
140void ApplyAllFilters(const ModelSolveParametersProto& model_solve_params,
141 SolutionProto& solution);
142
143// Returns the callback_registration.request_registration as a set of enums.
144absl::flat_hash_set<CallbackEventProto> EventSet(
145 const CallbackRegistrationProto& callback_registration);
146
147// Sets the reason to TERMINATION_REASON_FEASIBLE if feasible = true and
148// TERMINATION_REASON_NO_SOLUTION_FOUND otherwise.
149ABSL_DEPRECATED("Use LimitTerminationProto() instead")
150TerminationProto TerminateForLimit(LimitProto limit, bool feasible,
151 absl::string_view detail = {});
152
153ABSL_DEPRECATED("Use FeasibleTerminationProto() instead")
154TerminationProto FeasibleTermination(LimitProto limit,
155 absl::string_view detail = {});
156
157ABSL_DEPRECATED("Use NoSolutionFound() instead")
158TerminationProto NoSolutionFoundTermination(LimitProto limit,
159 absl::string_view detail = {});
160
162 "Use TerminateForReason(bool, TerminationReasonProto, absl::string_view) "
163 "instead")
164TerminationProto TerminateForReason(TerminationReasonProto reason,
165 absl::string_view detail = {});
166
167// Returns trivial bounds.
168//
169// Trivial bounds are:
170// * for a maximization:
171// - primal_bound: -inf
172// - dual_bound : +inf
173// * for a minimization:
174// - primal_bound: +inf
175// - dual_bound : -inf
176ObjectiveBoundsProto MakeTrivialBounds(bool is_maximize);
177
178// Returns a TerminationProto with the provided reason and details along with
179// trivial bounds and FEASIBILITY_STATUS_UNDETERMINED statuses.
180TerminationProto TerminateForReason(bool is_maximize,
181 TerminationReasonProto reason,
182 absl::string_view detail = {});
183
184// Returns a TERMINATION_REASON_OPTIMAL termination with the provided objective
185// bounds and FEASIBILITY_STATUS_FEASIBLE primal and dual statuses.
186//
187// finite_primal_objective must be finite for a valid TerminationProto to be
188// returned.
189//
190// TODO(b/290359402): additionally require dual_objective to be finite.
191TerminationProto OptimalTerminationProto(double finite_primal_objective,
192 double dual_objective,
193 absl::string_view detail = {});
194
195// Returns a TERMINATION_REASON_INFEASIBLE termination with
196// FEASIBILITY_STATUS_INFEASIBLE primal status and the provided dual status.
197//
198// It sets a trivial primal bound and a dual bound based on the provided dual
199// status, which should be FEASIBILITY_STATUS_FEASIBLE or
200// FEASIBILITY_STATUS_UNDETERMINED. If the dual status is
201// FEASIBILITY_STATUS_UNDETERMINED, then the dual bound will be trivial and if
202// the dual status is FEASIBILITY_STATUS_FEASIBLE, then the dual bound will be
203// equal to the primal bound.
204//
205// The convention for infeasible MIPs is that dual_feasibility_status is
206// feasible (There always exist a dual feasible convex relaxation of an
207// infeasible MIP).
208//
209// dual_feasibility_status must not be FEASIBILITY_STATUS_UNSPECIFIED for a
210// valid TerminationProto to be returned.
211TerminationProto InfeasibleTerminationProto(
212 bool is_maximize,
213 FeasibilityStatusProto dual_feasibility_status =
214 FEASIBILITY_STATUS_UNDETERMINED,
215 absl::string_view detail = {});
216
217// Returns a TERMINATION_REASON_INFEASIBLE_OR_UNBOUNDED termination with
218// FEASIBILITY_STATUS_UNDETERMINED primal status and the provided dual status
219// along with trivial bounds.
220//
221// primal_or_dual_infeasible is set if dual_feasibility_status is
222// FEASIBILITY_STATUS_UNDETERMINED.
223//
224// dual_feasibility_status must be infeasible or undetermined for a valid
225// TerminationProto to be returned.
227 bool is_maximize,
228 FeasibilityStatusProto dual_feasibility_status =
229 FEASIBILITY_STATUS_UNDETERMINED,
230 absl::string_view detail = {});
231
232// Returns a TERMINATION_REASON_UNBOUNDED termination with a
233// FEASIBILITY_STATUS_FEASIBLE primal status and FEASIBILITY_STATUS_INFEASIBLE
234// dual one along with corresponding trivial bounds.
235TerminationProto UnboundedTerminationProto(bool is_maximize,
236 absl::string_view detail = {});
237
238// Returns a TERMINATION_REASON_NO_SOLUTION_FOUND termination with
239// FEASIBILITY_STATUS_UNDETERMINED primal status.
240//
241// Assumes dual solution exists iff optional_dual_objective is set even if
242// infinite (some solvers return feasible dual solutions without an objective
243// value). optional_dual_objective should not be set when limit is LIMIT_CUTOFF
244// for a valid TerminationProto to be returned (use
245// LimitCutoffTerminationProto() below instead).
246//
247// It sets a trivial primal bound. The dual bound is either set to the
248// optional_dual_objective if set, else to a trivial value.
249//
250// TODO(b/290359402): Consider improving to require a finite dual bound when
251// dual feasible solutions are returned.
252TerminationProto NoSolutionFoundTerminationProto(
253 bool is_maximize, LimitProto limit,
254 std::optional<double> optional_dual_objective = std::nullopt,
255 absl::string_view detail = {});
256
257// Returns a TERMINATION_REASON_FEASIBLE termination with a
258// FEASIBILITY_STATUS_FEASIBLE primal status. The dual status depends on
259// optional_dual_objective.
260//
261// finite_primal_objective should be finite and limit should not be LIMIT_CUTOFF
262// for a valid TerminationProto to be returned (use
263// LimitCutoffTerminationProto() below instead).
264//
265// Assumes dual solution exists iff optional_dual_objective is set even if
266// infinite (some solvers return feasible dual solutions without an objective
267// value). If set the dual status is set to FEASIBILITY_STATUS_FEASIBLE, else it
268// is FEASIBILITY_STATUS_UNDETERMINED.
269//
270// It sets the primal bound based on the primal objective. The dual bound is
271// either set to the optional_dual_objective if set, else to a trivial value.
272//
273// TODO(b/290359402): Consider improving to require a finite dual bound when
274// dual feasible solutions are returned.
275TerminationProto FeasibleTerminationProto(
276 bool is_maximize, LimitProto limit, double finite_primal_objective,
277 std::optional<double> optional_dual_objective = std::nullopt,
278 absl::string_view detail = {});
279
280// Either calls FeasibleTerminationProto() or NoSolutionFoundTerminationProto()
281// based on optional_finite_primal_objective having a value.
282//
283// That is it assumes a primal feasible solution exists iff
284// optional_finite_primal_objective has a value.
285TerminationProto LimitTerminationProto(
286 bool is_maximize, LimitProto limit,
287 std::optional<double> optional_finite_primal_objective,
288 std::optional<double> optional_dual_objective = std::nullopt,
289 absl::string_view detail = {});
290
291// Returns either a TERMINATION_REASON_FEASIBLE or
292// TERMINATION_REASON_NO_SOLUTION_FOUND termination depending on
293// primal_objective being finite or not. That is it assumes there is a primal
294// feasible solution iff primal_objective is finite.
295//
296// If claim_dual_feasible_solution_exists is true, the dual_status is set as
297// FEASIBILITY_STATUS_FEASIBLE, else FEASIBILITY_STATUS_UNDETERMINED.
298//
299// This function assumes dual solution exists if
300// claim_dual_feasible_solution_exists is true even if dual_objective is
301// infinite (some solvers return feasible dual solutions without an objective
302// value). If dual_objective is finite then claim_dual_feasible_solution_exists
303// must be true for a valid termination to be returned.
304//
305// TODO(b/290359402): Consider improving to require a finite dual bound when
306// dual feasible solutions are returned.
307TerminationProto LimitTerminationProto(LimitProto limit,
308 double primal_objective,
309 double dual_objective,
310 bool claim_dual_feasible_solution_exists,
311 absl::string_view detail = {});
312
313// Calls NoSolutionFoundTerminationProto() with LIMIT_CUTOFF LIMIT.
314TerminationProto CutoffTerminationProto(bool is_maximize,
315 absl::string_view detail = {});
316
317enum class SupportType {
318 kNotSupported = 1,
319 kSupported = 2,
320 kNotImplemented = 3,
321};
322
333
334// Returns an InvalidArgumentError (respectively, UnimplementedError) if a
335// problem structure is present in `model` and not supported (resp., not yet
336// implemented) according to `support_menu`.
337absl::Status ModelIsSupported(const ModelProto& model,
338 const SupportedProblemStructures& support_menu,
339 absl::string_view solver_name);
340
341// Returns false if a problem structure is present in `update` and not
342// not implemented or supported according to `support_menu`.
343bool UpdateIsSupported(const ModelUpdateProto& update,
344 const SupportedProblemStructures& support_menu);
345
347 SolveResultProto& solve_result_proto);
348
350// Inline functions implementations.
352
353template <typename Value>
355 const Value& value) {
356#ifndef NDEBUG
357 CHECK_GE(id, next_input_id_lower_bound_)
358 << "This function must be called with strictly increasing ids.";
359
360 // Update the range of the next expected id. We expect input to be strictly
361 // increasing.
362 next_input_id_lower_bound_ = id + 1;
363#endif // NDEBUG
364
365 // For this predicate we use `0` as the zero to test with since as of today we
366 // only have SparseDoubleVectorProto and SparseBoolVectorProto. The `bool`
367 // type is an integral type so the comparison with 0 will indeed be equivalent
368 // to keeping only `true` values.
369 if (filter_.skip_zero_values() && value == 0) {
370 return false;
371 }
372
373 if (!filter_.filter_by_ids()) {
374 return true;
375 }
376
377 // Skip all filtered_ids that are smaller than the input id.
378 while (next_filtered_id_index_ < filter_.filtered_ids_size() &&
379 filter_.filtered_ids(next_filtered_id_index_) < id) {
380 ++next_filtered_id_index_;
381 }
382
383 if (next_filtered_id_index_ == filter_.filtered_ids_size()) {
384 // We filter by ids and there are no more ids that should pass.
385 return false;
386 }
387
388 // The previous loop ensured that the element at next_filtered_id_index_ is
389 // the first element greater or equal to id.
390 return id == filter_.filtered_ids(next_filtered_id_index_);
391}
392
393} // namespace operations_research::math_opt
394
395#endif // OR_TOOLS_MATH_OPT_CORE_MATH_OPT_PROTO_UTILS_H_
SparseVectorFilterPredicate(const SparseVectorFilterProto &filter)
int64_t value
GRBmodel * model
double solution
An object oriented wrapper for quadratic constraints in ModelStorage.
Definition gurobi_isv.cc:28
TerminationProto TerminateForReason(const TerminationReasonProto reason, const absl::string_view detail)
absl::Status ModelIsSupported(const ModelProto &model, const SupportedProblemStructures &support_menu, const absl::string_view solver_name)
TerminationProto FeasibleTermination(const LimitProto limit, const absl::string_view detail)
void UpgradeSolveResultProtoForStatsMigration(SolveResultProto &solve_result_proto)
std::optional< int64_t > FirstLinearConstraintId(const LinearConstraintsProto &linear_constraints)
TerminationProto TerminateForLimit(const LimitProto limit, const bool feasible, const absl::string_view detail)
int NumMatrixNonzeros(const SparseDoubleMatrixProto &matrix)
int NumVariables(const VariablesProto &variables)
absl::flat_hash_set< CallbackEventProto > EventSet(const CallbackRegistrationProto &callback_registration)
Returns the callback_registration.request_registration as a set of enums.
TerminationProto OptimalTerminationProto(const double finite_primal_objective, const double dual_objective, const absl::string_view detail)
TerminationProto LimitTerminationProto(const bool is_maximize, const LimitProto limit, const std::optional< double > optional_finite_primal_objective, const std::optional< double > optional_dual_objective, const absl::string_view detail)
TerminationProto InfeasibleOrUnboundedTerminationProto(bool is_maximize, const FeasibilityStatusProto dual_feasibility_status, const absl::string_view detail)
bool UpdateIsSupported(const ModelUpdateProto &update, const SupportedProblemStructures &support_menu)
ProblemStatusProto GetProblemStatus(const SolveResultProto &solve_result)
TerminationProto FeasibleTerminationProto(const bool is_maximize, const LimitProto limit, const double primal_objective, const std::optional< double > optional_dual_objective, const absl::string_view detail)
ObjectiveBoundsProto GetObjectiveBounds(const SolveResultProto &solve_result)
TerminationProto NoSolutionFoundTerminationProto(const bool is_maximize, const LimitProto limit, const std::optional< double > optional_dual_objective, const absl::string_view detail)
TerminationProto CutoffTerminationProto(bool is_maximize, const absl::string_view detail)
Calls NoSolutionFoundTerminationProto() with LIMIT_CUTOFF LIMIT.
TerminationProto NoSolutionFoundTermination(const LimitProto limit, const absl::string_view detail)
int NumConstraints(const LinearConstraintsProto &linear_constraints)
std::optional< int64_t > FirstVariableId(const VariablesProto &variables)
TerminationProto InfeasibleTerminationProto(bool is_maximize, const FeasibilityStatusProto dual_feasibility_status, const absl::string_view detail)
SparseDoubleVectorProto FilterSparseVector(const SparseDoubleVectorProto &input, const SparseVectorFilterProto &filter)
ABSL_DEPRECATED("Use TerminateForReason(bool, TerminationReasonProto, absl::string_view) " "instead") TerminationProto TerminateForReason(TerminationReasonProto reason
TerminationProto UnboundedTerminationProto(const bool is_maximize, const absl::string_view detail)
void RemoveSparseDoubleVectorZeros(SparseDoubleVectorProto &sparse_vector)
void ApplyAllFilters(const ModelSolveParametersProto &model_solve_params, SolutionProto &solution)
ObjectiveBoundsProto MakeTrivialBounds(const bool is_maximize)
static int input(yyscan_t yyscanner)