Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
storage.h
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
14#ifndef OR_TOOLS_MATH_OPT_CONSTRAINTS_SOS_STORAGE_H_
15#define OR_TOOLS_MATH_OPT_CONSTRAINTS_SOS_STORAGE_H_
16
17#include <cstdint>
18#include <optional>
19#include <string>
20#include <type_traits>
21#include <utility>
22#include <vector>
23
24#include "absl/container/flat_hash_set.h"
25#include "absl/log/check.h"
32
34namespace internal {
35
36// Internal storage representation for a single SOS constraint.
37//
38// Implements the interface specified for the `ConstraintData` parameter of
39// `AtomicConstraintStorage`.
40template <typename ConstraintId>
42 public:
43 using IdType = ConstraintId;
46 static constexpr bool kSupportsElemental = false;
47
48 static_assert(
49 std::disjunction_v<std::is_same<ConstraintId, Sos1ConstraintId>,
50 std::is_same<ConstraintId, Sos2ConstraintId>>,
51 "ID type may only be Sos1ConstraintId or Sos2ConstraintId");
52
53 // `weights` must either be empty or the same length as `expressions`. If it
54 // is empty, default weights of 1, 2, ... will be used.
55 SosConstraintData(std::vector<LinearExpressionData> expressions,
56 std::vector<double> weights, std::string name)
57 : expressions_(std::move(expressions)), name_(std::move(name)) {
58 if (!weights.empty()) {
59 CHECK_EQ(weights.size(), expressions_.size());
60 weights_ = std::move(weights);
61 }
62 }
63
64 // The `in_proto` must be in a valid state; see the inline comments on
65 // `SosConstraintProto` for details.
66 static SosConstraintData FromProto(const ProtoType& in_proto);
68 std::vector<VariableId> RelatedVariables() const;
70
71 bool has_weights() const { return weights_.has_value(); }
72
73 double weight(const int index) const {
74 AssertInbounds(index);
75 return weights_.has_value() ? (*weights_)[index] : index + 1;
76 }
77 const LinearExpressionData& expression(const int index) const {
78 AssertInbounds(index);
79 return expressions_[index];
80 }
81 int64_t num_expressions() const { return expressions_.size(); }
82 const std::string& name() const { return name_; }
83
84 private:
85 SosConstraintData() = default;
86 void AssertInbounds(const int index) const {
87 CHECK_GE(index, 0);
88 CHECK_LT(index, expressions_.size());
89 }
90 // If present, length must be the same as that of `expressions_`.
91 // If absent, default weights of 1, 2, ... are used.
92 std::optional<std::vector<double>> weights_;
93 std::vector<LinearExpressionData> expressions_;
94 std::string name_;
95};
96
97} // namespace internal
98
101
102template <>
103struct AtomicConstraintTraits<Sos1ConstraintId> {
105 static constexpr bool kSupportsElemental = false;
106};
107
108template <>
109struct AtomicConstraintTraits<Sos2ConstraintId> {
111 static constexpr bool kSupportsElemental = false;
112};
113
115// Inline implementations
117
118namespace internal {
119
120template <typename ConstraintId>
121SosConstraintData<ConstraintId> SosConstraintData<ConstraintId>::FromProto(
122 const ProtoType& in_proto) {
123 const int num_expressions = in_proto.expressions_size();
125 data.name_ = in_proto.name();
126 for (int i = 0; i < num_expressions; ++i) {
127 data.expressions_.push_back(
128 LinearExpressionData::FromProto(in_proto.expressions(i)));
129 }
130 // Otherwise proto has default weights, so leave data.weights_ as unset.
131 if (!in_proto.weights().empty()) {
132 data.weights_.emplace().reserve(num_expressions);
133 for (int i = 0; i < num_expressions; ++i) {
134 data.weights_->push_back(in_proto.weights(i));
135 }
136 }
137 return data;
138}
139
140template <typename ConstraintId>
143 ProtoType constraint;
144 constraint.set_name(name());
145 for (int i = 0; i < num_expressions(); ++i) {
146 *constraint.add_expressions() = expression(i).Proto();
147 }
148 if (weights_.has_value()) {
149 for (int i = 0; i < num_expressions(); ++i) {
150 constraint.add_weights(weight(i));
151 }
152 }
153 return constraint;
154}
155
156template <typename ConstraintId>
158 const {
159 absl::flat_hash_set<VariableId> vars;
160 for (const LinearExpressionData& expression : expressions_) {
161 for (const auto [var, _] : expression.coeffs.terms()) {
162 vars.insert(var);
163 }
164 }
165 return std::vector<VariableId>(vars.begin(), vars.end());
166}
167
168template <typename ConstraintId>
170 for (LinearExpressionData& expression : expressions_) {
171 expression.coeffs.erase(var);
172 }
173}
174
175} // namespace internal
176} // namespace operations_research::math_opt
177
178#endif // OR_TOOLS_MATH_OPT_CONSTRAINTS_SOS_STORAGE_H_
void set_name(Arg_ &&arg, Args_... args)
const LinearExpressionData & expression(const int index) const
Definition storage.h:77
static SosConstraintData FromProto(const ProtoType &in_proto)
Definition storage.h:123
std::vector< VariableId > RelatedVariables() const
Definition storage.h:159
SosConstraintData(std::vector< LinearExpressionData > expressions, std::vector< double > weights, std::string name)
Definition storage.h:55
An object oriented wrapper for quadratic constraints in ModelStorage.
Definition gurobi_isv.cc:28
internal::SosConstraintData< Sos1ConstraintId > Sos1ConstraintData
Definition storage.h:99
ElementId< ElementType::kVariable > VariableId
Definition elements.h:264
internal::SosConstraintData< Sos2ConstraintId > Sos2ConstraintData
Definition storage.h:100
STL namespace.
static LinearExpressionData FromProto(const LinearExpressionProto &expr_proto)