25#include "absl/algorithm/container.h"
26#include "absl/container/flat_hash_map.h"
27#include "absl/log/check.h"
28#include "absl/status/status.h"
29#include "absl/status/statusor.h"
30#include "absl/strings/string_view.h"
31#include "absl/types/span.h"
46absl::Status IsSupported(
const MPModelProto& model) {
48 if (!validity_string.empty()) {
49 return absl::InvalidArgumentError(validity_string);
51 for (
const MPGeneralConstraintProto& general_constraint :
52 model.general_constraint()) {
53 if (!(general_constraint.has_quadratic_constraint() ||
54 general_constraint.has_sos_constraint() ||
55 general_constraint.has_indicator_constraint())) {
56 return absl::InvalidArgumentError(
"Unsupported general constraint");
59 return absl::OkStatus();
62bool AnyVarNamed(
const MPModelProto& model) {
63 for (
const MPVariableProto& var : model.variable()) {
64 if (!var.name().empty()) {
71bool AnyConstraintNamed(
const MPModelProto& model) {
72 for (
const MPConstraintProto& constraint : model.constraint()) {
73 if (!constraint.name().empty()) {
80void LinearTermsFromMPModelToMathOpt(
81 const absl::Span<const int32_t> in_ids,
82 const absl::Span<const double> in_coeffs,
83 google::protobuf::RepeatedField<int64_t>& out_ids,
84 google::protobuf::RepeatedField<double>& out_coeffs) {
85 CHECK_EQ(in_ids.size(), in_coeffs.size());
86 const int num_terms =
static_cast<int>(in_ids.size());
87 std::vector<std::pair<int, double>> linear_terms_in_order;
88 for (
int i = 0;
i < num_terms; ++
i) {
89 linear_terms_in_order.push_back({in_ids[
i], in_coeffs[
i]});
91 absl::c_sort(linear_terms_in_order);
92 out_ids.Resize(num_terms, -1);
93 out_coeffs.Resize(num_terms, std::numeric_limits<double>::quiet_NaN());
94 for (
int i = 0;
i < num_terms; ++
i) {
95 out_ids.Set(i, linear_terms_in_order[i].first);
96 out_coeffs.Set(i, linear_terms_in_order[i].second);
106 const absl::Span<const int32_t> in_row_var_indices,
107 const absl::Span<const int32_t> in_col_var_indices,
108 const absl::Span<const double> in_coefficients) {
109 CHECK_EQ(in_row_var_indices.size(), in_col_var_indices.size());
110 CHECK_EQ(in_row_var_indices.size(), in_coefficients.size());
113 std::vector<std::pair<std::pair<int32_t, int32_t>,
double>> qp_terms_in_order;
114 for (
int k = 0; k < in_row_var_indices.size(); ++k) {
115 int32_t first_index = in_row_var_indices[k];
116 int32_t second_index = in_col_var_indices[k];
117 if (first_index > second_index) {
118 std::swap(first_index, second_index);
120 qp_terms_in_order.push_back(
121 {{first_index, second_index}, in_coefficients[k]});
123 absl::c_sort(qp_terms_in_order);
124 std::pair<int32_t, int32_t> previous = {-1, -1};
125 for (
const auto& [indices, coeff] : qp_terms_in_order) {
126 if (indices == previous) {
127 *out_expression.mutable_coefficients()->rbegin() += coeff;
129 out_expression.add_row_ids(indices.first);
130 out_expression.add_column_ids(indices.second);
131 out_expression.add_coefficients(coeff);
135 return out_expression;
139 const MPQuadraticConstraint& in_constraint,
const absl::string_view name) {
142 out_constraint.set_upper_bound(in_constraint.upper_bound());
143 out_constraint.set_name(std::string(name));
144 LinearTermsFromMPModelToMathOpt(
145 in_constraint.var_index(), in_constraint.coefficient(),
146 *out_constraint.mutable_linear_terms()->mutable_ids(),
147 *out_constraint.mutable_linear_terms()->mutable_values());
148 *out_constraint.mutable_quadratic_terms() =
149 QuadraticTermsFromMPModelToMathOpt(in_constraint.qvar1_index(),
150 in_constraint.qvar2_index(),
151 in_constraint.qcoefficient());
152 return out_constraint;
156 const MPSosConstraint& in_constraint,
const absl::string_view name) {
158 out_constraint.
set_name(std::string(name));
159 for (
const int j : in_constraint.var_index()) {
162 expr.add_coefficients(1.0);
164 for (
const double weight : in_constraint.weight()) {
165 out_constraint.add_weights(weight);
167 return out_constraint;
171absl::StatusOr<IndicatorConstraintProto>
172IndicatorConstraintFromMPModelToMathOpt(
173 const MPIndicatorConstraint& in_constraint,
const absl::string_view name) {
175 out_constraint.
set_name(std::string(name));
176 out_constraint.set_indicator_id(in_constraint.var_index());
177 out_constraint.set_activate_on_zero(in_constraint.has_var_value() &&
178 in_constraint.var_value() == 0);
179 out_constraint.set_lower_bound(in_constraint.constraint().lower_bound());
180 out_constraint.set_upper_bound(in_constraint.constraint().upper_bound());
181 LinearTermsFromMPModelToMathOpt(
182 in_constraint.constraint().var_index(),
183 in_constraint.constraint().coefficient(),
184 *out_constraint.mutable_expression()->mutable_ids(),
185 *out_constraint.mutable_expression()->mutable_values());
186 return out_constraint;
189absl::StatusOr<MPGeneralConstraintProto> SosConstraintFromMathOptToMPModel(
192 const absl::flat_hash_map<int64_t, int>& variable_id_to_mp_position) {
193 MPGeneralConstraintProto out_general_constraint;
194 out_general_constraint.set_name(in_constraint.name());
195 MPSosConstraint& out_constraint =
196 *out_general_constraint.mutable_sos_constraint();
197 out_constraint.set_type(sos_type);
198 for (
const double weight : in_constraint.weights()) {
199 out_constraint.add_weight(weight);
202 if (expression.ids_size() != 1 || expression.coefficients(0) != 1.0 ||
203 expression.offset() != 0.0) {
204 return absl::InvalidArgumentError(
205 "MPModelProto does not support SOS constraints with "
206 "expressions that are not equivalent to a single variable");
208 out_constraint.add_var_index(
209 variable_id_to_mp_position.at(expression.ids(0)));
211 return out_general_constraint;
216absl::StatusOr<::operations_research::math_opt::ModelProto>
224 int linear_objective_non_zeros = 0;
225 const int num_vars = model.variable_size();
226 const bool vars_have_name = AnyVarNamed(model);
230 if (vars_have_name) {
233 for (
int i = 0; i < model.variable_size(); ++i) {
236 ++linear_objective_non_zeros;
242 if (vars_have_name) {
248 if (linear_objective_non_zeros > 0) {
250 linear_objective_non_zeros);
252 linear_objective_non_zeros);
253 for (
int j = 0; j < num_vars; ++j) {
254 const double value = model.variable(j).objective_coefficient();
255 if (value == 0.0)
continue;
261 const int num_qp_terms = origin_qp_terms.
coefficient().size();
262 if (num_qp_terms > 0) {
264 QuadraticTermsFromMPModelToMathOpt(origin_qp_terms.
qvar1_index(),
269 objective->
set_offset(model.objective_offset());
273 const int num_constraints = model.constraint_size();
274 const bool constraints_have_name = AnyConstraintNamed(model);
275 int num_non_zeros = 0;
278 if (constraints_have_name) {
281 for (
int i = 0; i < num_constraints; ++i) {
286 if (constraints_have_name) {
298 std::vector<std::pair<int, double>> terms_in_order;
299 for (
int i = 0; i < num_constraints; ++i) {
302 for (
int k = 0; k < constraint_non_zeros; ++k) {
303 const double coefficient = constraint.
coefficient(k);
304 if (coefficient == 0.0) {
307 terms_in_order.emplace_back(constraint.
var_index(k), coefficient);
309 std::sort(terms_in_order.begin(), terms_in_order.end());
310 for (
const auto& term : terms_in_order) {
315 terms_in_order.clear();
319 model.general_constraint()) {
320 absl::string_view in_name = general_constraint.name();
321 switch (general_constraint.general_constraint_case()) {
325 QuadraticConstraintFromMPModelToMathOpt(
326 general_constraint.quadratic_constraint(), in_name);
331 general_constraint.sos_constraint();
332 switch (in_constraint.
type()) {
336 SosConstraintFromMPModelToMathOpt(in_constraint, in_name);
342 SosConstraintFromMPModelToMathOpt(in_constraint, in_name);
351 auto& new_indicator_constraint =
355 new_indicator_constraint,
356 IndicatorConstraintFromMPModelToMathOpt(
357 general_constraint.indicator_constraint(), in_name));
361 return absl::InternalError(
362 "Reached unrecognized general constraint in MPModelProto");
369absl::StatusOr<std::optional<SolutionHintProto>>
372 if (!validity_string.empty()) {
373 return absl::InvalidArgumentError(validity_string);
382 LinearTermsFromMPModelToMathOpt(
384 *variable_values.mutable_ids(), *variable_values.mutable_values());
390 const ::operations_research::math_opt::ModelProto& model) {
392 if (!model.second_order_cone_constraints().empty()) {
393 return absl::InvalidArgumentError(
394 "translating models with second-order cone constraints is not "
398 const bool vars_have_name = model.variables().names_size() > 0;
399 const bool constraints_have_name =
400 model.linear_constraints().names_size() > 0;
401 absl::flat_hash_map<int64_t, int> variable_id_to_mp_position;
402 absl::flat_hash_map<int64_t, MPConstraintProto*>
403 constraint_id_to_mp_constraint;
410 for (
int j = 0; j < num_vars; ++j) {
412 variable_id_to_mp_position.emplace(model.variables().ids(j), j);
416 if (vars_have_name) {
417 variable->
set_name(model.variables().names(j));
421 const int num_constraints =
NumConstraints(model.linear_constraints());
423 for (
int i = 0; i < num_constraints; ++i) {
425 constraint_id_to_mp_constraint.emplace(model.linear_constraints().ids(i),
427 constraint->
set_lower_bound(model.linear_constraints().lower_bounds(i));
428 constraint->
set_upper_bound(model.linear_constraints().upper_bounds(i));
429 if (constraints_have_name) {
430 constraint->
set_name(model.linear_constraints().names(i));
436 for (
const auto& [var, coef] :
437 MakeView(model.objective().linear_coefficients())) {
438 const int var_position = variable_id_to_mp_position[var];
443 model.objective().quadratic_coefficients();
447 for (
int k = 0; k < origin_qp_terms.
coefficients().size(); ++k) {
449 variable_id_to_mp_position[origin_qp_terms.
row_ids(k)]);
451 variable_id_to_mp_position[origin_qp_terms.
column_ids(k)]);
457 const int constraint_non_zeros =
459 for (
int k = 0; k < constraint_non_zeros; ++k) {
460 const int64_t constraint_id = model.linear_constraint_matrix().row_ids(k);
462 constraint_id_to_mp_constraint[constraint_id];
463 const int64_t variable_id = model.linear_constraint_matrix().column_ids(k);
464 const int variable_position = variable_id_to_mp_position[variable_id];
466 const double value = model.linear_constraint_matrix().coefficients(k);
470 for (
const auto& [
id, in_constraint] : model.quadratic_constraints()) {
473 out_general_constraint.
set_name(in_constraint.name());
478 for (
const auto [index, coeff] :
MakeView(in_constraint.linear_terms())) {
479 out_constraint.
add_var_index(variable_id_to_mp_position[index]);
482 for (
int k = 0; k < in_constraint.quadratic_terms().row_ids_size(); ++k) {
484 variable_id_to_mp_position[in_constraint.quadratic_terms().row_ids(
487 variable_id_to_mp_position[in_constraint.quadratic_terms().column_ids(
490 in_constraint.quadratic_terms().coefficients(k));
493 for (
const auto& [
id, in_constraint] : model.sos1_constraints()) {
495 SosConstraintFromMathOptToMPModel(
497 variable_id_to_mp_position));
500 for (
const auto& [
id, in_constraint] : model.sos2_constraints()) {
504 variable_id_to_mp_position));
507 for (
const auto& [
id, in_constraint] : model.indicator_constraints()) {
508 if (!in_constraint.has_indicator_id()) {
513 out_general_constraint.
set_name(in_constraint.name());
517 variable_id_to_mp_position[in_constraint.indicator_id()]);
518 out_constraint.
set_var_value(in_constraint.activate_on_zero() ? 0 : 1);
520 in_constraint.lower_bound());
522 in_constraint.upper_bound());
523 for (
const auto [index, coeff] :
MakeView(in_constraint.expression())) {
525 variable_id_to_mp_position[index]);
#define ASSIGN_OR_RETURN(lhs, rexpr)
#define RETURN_IF_ERROR(expr)
void set_name(Arg_ &&arg, Args_... args)
double lower_bound() const
const ::std::string & name() const
int var_index_size() const
repeated int32 var_index = 6 [packed = true];
void set_lower_bound(double value)
void add_coefficient(double value)
void set_upper_bound(double value)
double coefficient(int index) const
void add_var_index(::int32_t value)
::int32_t var_index(int index) const
double upper_bound() const
::operations_research::MPIndicatorConstraint *PROTOBUF_NONNULL mutable_indicator_constraint()
::operations_research::MPQuadraticConstraint *PROTOBUF_NONNULL mutable_quadratic_constraint()
void set_name(Arg_ &&arg, Args_... args)
void set_var_index(::int32_t value)
void set_var_value(::int32_t value)
::operations_research::MPConstraintProto *PROTOBUF_NONNULL mutable_constraint()
void set_maximize(bool value)
::operations_research::MPConstraintProto *PROTOBUF_NONNULL add_constraint()
::operations_research::MPConstraintProto *PROTOBUF_NONNULL mutable_constraint(int index)
::operations_research::MPVariableProto *PROTOBUF_NONNULL add_variable()
::operations_research::MPGeneralConstraintProto *PROTOBUF_NONNULL add_general_constraint()
void set_objective_offset(double value)
::operations_research::MPQuadraticObjective *PROTOBUF_NONNULL mutable_quadratic_objective()
void set_name(Arg_ &&arg, Args_... args)
::operations_research::MPVariableProto *PROTOBUF_NONNULL mutable_variable(int index)
const ::operations_research::PartialVariableAssignment & solution_hint() const
void add_var_index(::int32_t value)
void add_qvar1_index(::int32_t value)
void add_coefficient(double value)
void add_qcoefficient(double value)
void set_lower_bound(double value)
void set_upper_bound(double value)
void add_qvar2_index(::int32_t value)
::int32_t qvar1_index(int index) const
void add_coefficient(double value)
double coefficient(int index) const
::int32_t qvar2_index(int index) const
void add_qvar2_index(::int32_t value)
void add_qvar1_index(::int32_t value)
::operations_research::MPSosConstraint_Type type() const
MPSosConstraint_Type Type
nested types -------------------------------------------------—
static constexpr Type SOS1_DEFAULT
static constexpr Type SOS2
void set_upper_bound(double value)
void set_name(Arg_ &&arg, Args_... args)
void set_is_integer(bool value)
void set_objective_coefficient(double value)
double lower_bound() const
double upper_bound() const
void set_lower_bound(double value)
const ::std::string & name() const
double objective_coefficient() const
::int32_t var_index(int index) const
double var_value(int index) const
int var_index_size() const
repeated int32 var_index = 1 [packed = true];
void set_name(Arg_ &&arg, Args_... args)
::std::string *PROTOBUF_NONNULL add_names()
::google::protobuf::RepeatedField< double > *PROTOBUF_NONNULL mutable_lower_bounds()
::std::string *PROTOBUF_NONNULL mutable_names(int index)
void add_ids(::int64_t value)
::google::protobuf::RepeatedField< double > *PROTOBUF_NONNULL mutable_upper_bounds()
void add_lower_bounds(double value)
void add_upper_bounds(double value)
void add_ids(::int64_t value)
int sos1_constraints_size() const
map<int64, .operations_research.math_opt.SosConstraintProto> sos1_constraints = 7;
::operations_research::math_opt::VariablesProto *PROTOBUF_NONNULL mutable_variables()
::operations_research::math_opt::SparseDoubleMatrixProto *PROTOBUF_NONNULL mutable_linear_constraint_matrix()
::google::protobuf::Map<::int64_t, ::operations_research::math_opt::SosConstraintProto > *PROTOBUF_NONNULL mutable_sos2_constraints()
::operations_research::math_opt::ObjectiveProto *PROTOBUF_NONNULL mutable_objective()
void set_name(Arg_ &&arg, Args_... args)
int quadratic_constraints_size() const
map<int64, .operations_research.math_opt.QuadraticConstraintProto> quadratic_constraints = 6;
int indicator_constraints_size() const
map<int64, .operations_research.math_opt.IndicatorConstraintProto> indicator_constraints = 9;
::google::protobuf::Map<::int64_t, ::operations_research::math_opt::QuadraticConstraintProto > *PROTOBUF_NONNULL mutable_quadratic_constraints()
::operations_research::math_opt::LinearConstraintsProto *PROTOBUF_NONNULL mutable_linear_constraints()
::google::protobuf::Map<::int64_t, ::operations_research::math_opt::IndicatorConstraintProto > *PROTOBUF_NONNULL mutable_indicator_constraints()
int sos2_constraints_size() const
map<int64, .operations_research.math_opt.SosConstraintProto> sos2_constraints = 8;
::google::protobuf::Map<::int64_t, ::operations_research::math_opt::SosConstraintProto > *PROTOBUF_NONNULL mutable_sos1_constraints()
::operations_research::math_opt::SparseDoubleVectorProto *PROTOBUF_NONNULL mutable_linear_coefficients()
::operations_research::math_opt::SparseDoubleMatrixProto *PROTOBUF_NONNULL mutable_quadratic_coefficients()
void set_offset(double value)
void set_maximize(bool value)
void set_lower_bound(double value)
::operations_research::math_opt::SparseDoubleVectorProto *PROTOBUF_NONNULL mutable_variable_values()
void set_name(Arg_ &&arg, Args_... args)
void add_column_ids(::int64_t value)
void add_coefficients(double value)
double coefficients(int index) const
void add_row_ids(::int64_t value)
::int64_t row_ids(int index) const
int coefficients_size() const
repeated double coefficients = 3;
::google::protobuf::RepeatedField<::int64_t > *PROTOBUF_NONNULL mutable_column_ids()
::int64_t column_ids(int index) const
::google::protobuf::RepeatedField<::int64_t > *PROTOBUF_NONNULL mutable_row_ids()
::google::protobuf::RepeatedField< double > *PROTOBUF_NONNULL mutable_coefficients()
::google::protobuf::RepeatedField<::int64_t > *PROTOBUF_NONNULL mutable_ids()
void add_ids(::int64_t value)
void add_values(double value)
::google::protobuf::RepeatedField< double > *PROTOBUF_NONNULL mutable_values()
::std::string *PROTOBUF_NONNULL add_names()
::google::protobuf::RepeatedField< double > *PROTOBUF_NONNULL mutable_upper_bounds()
void add_lower_bounds(double value)
::google::protobuf::RepeatedField< double > *PROTOBUF_NONNULL mutable_lower_bounds()
void add_upper_bounds(double value)
void add_ids(::int64_t value)
void add_integers(bool value)
::google::protobuf::RepeatedField< bool > *PROTOBUF_NONNULL mutable_integers()
::std::string *PROTOBUF_NONNULL mutable_names(int index)
An object oriented wrapper for quadratic constraints in ModelStorage.
absl::StatusOr< std::optional< SolutionHintProto > > MPModelProtoSolutionHintToMathOptHint(const MPModelProto &model)
int NumVariables(const VariablesProto &variables)
absl::StatusOr<::operations_research::MPModelProto > MathOptModelToMPModelProto(const ::operations_research::math_opt::ModelProto &model)
SparseVectorView< T > MakeView(absl::Span< const int64_t > ids, const Collection &values)
int NumConstraints(const LinearConstraintsProto &linear_constraints)
absl::StatusOr<::operations_research::math_opt::ModelProto > MPModelProtoToMathOptModel(const ::operations_research::MPModelProto &model)
absl::StatusOr< ModelSummary > ValidateModel(const ModelProto &model, const bool check_names)
In SWIG mode, we don't want anything besides these top-level includes.
std::string FindErrorInMPModelProto(const MPModelProto &model, double abs_value_threshold, const bool accept_trivially_infeasible_bounds)