Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
atomic_constraint_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_STORAGE_ATOMIC_CONSTRAINT_STORAGE_H_
15#define OR_TOOLS_MATH_OPT_STORAGE_ATOMIC_CONSTRAINT_STORAGE_H_
16
17#include <algorithm>
18#include <cstdint>
19#include <vector>
20
21#include "absl/algorithm/container.h"
22#include "absl/container/flat_hash_map.h"
23#include "absl/container/flat_hash_set.h"
24#include "absl/log/check.h"
25#include "google/protobuf/map.h"
31
33
34// Storage for a "mapped" constraint type whose only supported updates are
35// constraint addition, and variable or constraint deletion.
36//
37// The constraints are "atomic" in the sense that they can be added or deleted
38// individually, but direct data updates (e.g., to coefficients) are not
39// permitted. Note that they are not strictly immutable, though, as variable
40// deletions may have side effects (e.g., a constraint considers a deleted
41// variable as implicitly fixed to zero).
42//
43// Implementers of new constraint families should provide a conforming
44// `ConstraintData` definition, along with a template specialization of
45// `AtomicConstraintTraits` (defined below). These should likely be placed in
46// `math_opt/constraints/$new_constraint_family/storage.h`.
47//
48// The `ConstraintData` parameter should refer to a class to represent a single
49// constraint in memory. It must satisfy a duck-typed interface:
50// * A `IdType` alias to the (strong int) ID type for the constraint class.
51// * A `ProtoType` alias to the proto message for a single constraint.
52// * An `UpdatesProtoType` alias to the proto message for updates for the given
53// constraint type, as represented by two fields:
54// - repeated int64_t deleted_constraint_ids
55// - Map<int64_t, ProtoType> new_constraints
56// * A member function to return all variables involved in the constraint:
57// std::vector<VariableId> RelatedVariables() const;
58// * A member function to delete a variable from the constraint:
59// void DeleteVariable(VariableId var);
60// * A member function that returns a proto representation of the constraint:
61// ProtoType Proto() const;
62// * A static member function that initializes a constraint from its proto
63// representation:
64// static ConstraintData FromProto(const ProtoType& in_proto);
65//
66// The setter functions all accept a `DiffIter`, which must be an iterator over
67// non-const references to AtomicConstraintStorage<ConstraintData>::Diff. These
68// functions will modify the diff objects.
69template <typename ConstraintData>
71 public:
72 using IdType = typename ConstraintData::IdType;
73 using ProtoType = typename ConstraintData::ProtoType;
74 using UpdatesProtoType = typename ConstraintData::UpdatesProtoType;
75
76 // Tracks a "checkpoint" and changes to constraints of a given class that are
77 // before the checkpoint. Advancing the checkpoint throws away tracked
78 // changes.
79 //
80 // An instance of this class is owned by each update tracker of ModelStorage.
81 struct Diff {
83 : checkpoint(storage.next_id()) {}
84
86 absl::flat_hash_set<IdType> deleted_constraints;
87 };
88
89 // Add a single constraint to the storage.
90 IdType AddConstraint(ConstraintData constraint);
91
92 // Adds a collection of constraints to the storage, from an "id-to-proto" map.
93 // The keys for the input map will be used as the associated IDs in storage.
94 //
95 // Will CHECK-fail if any ID is less than next_id().
96 void AddConstraints(
97 const google::protobuf::Map<int64_t, ProtoType>& constraints);
98
99 // Delete a single constraint.
100 template <typename DiffIter>
101 void Delete(IdType id, const iterator_range<DiffIter>& diffs);
102
103 // Delete a single variable from each constraint in the storage.
104 void DeleteVariable(VariableId variable_id);
105
106 // The number of constraints stored (includes everything created and not yet
107 // deleted).
108 int64_t size() const { return constraint_data_.size(); }
109
110 // The smallest ID which is valid for a new constraint.
111 IdType next_id() const { return next_id_; }
112
113 // Sets the next variable id to be the maximum of next_id() and `minimum`.
114 void ensure_next_id_at_least(const IdType minimum) {
115 next_id_ = std::max(minimum, next_id_);
116 }
117
118 // Returns true if this id has been created and not yet deleted.
119 bool contains(const IdType id) const { return constraint_data_.contains(id); }
120
121 const absl::flat_hash_set<IdType>& RelatedConstraints(
122 const VariableId variable_id) const {
123 return gtl::FindWithDefault(constraints_by_variable_, variable_id);
124 }
125
126 // The ids in use (not deleted). The order is not defined.
127 std::vector<IdType> Constraints() const;
128
129 // Returns a sorted vector of all existing (not deleted) constraints in the
130 // model.
131 //
132 // Runs in O(n log(n)), where n is the number of constraints returned.
133 std::vector<IdType> SortedConstraints() const;
134
135 // Returns a proto representation of the constraint class.
136 google::protobuf::Map<int64_t, ProtoType> Proto() const {
137 google::protobuf::Map<int64_t, ProtoType> constraints;
138 for (const auto& [id, data] : constraint_data_) {
139 constraints[id.value()] = data.Proto();
140 }
141 return constraints;
142 }
143
144 // Returns the underlying data for constraint `id`.
145 // Will crash if `id` is not present (i.e., if `contains(id)` returns false).
146 const ConstraintData& data(const IdType id) const {
147 return constraint_data_.at(id);
148 }
149
151 // Functions for working with Diff
153
154 // Returns true if there are no changes (tracked changes before the checkpoint
155 // or new constraints after the checkpoint).
156 inline bool diff_is_empty(const Diff& diff) const;
157
158 // Return a proto representation of the current update.
159 typename ConstraintData::UpdatesProtoType Update(const Diff& diff) const;
160
161 // Updates the checkpoint and clears all stored changes in diff.
162 void AdvanceCheckpointInDiff(Diff& diff) const;
163
164 private:
165 IdType next_id_{0};
166 absl::flat_hash_map<IdType, ConstraintData> constraint_data_;
167 // TODO(b/232619901): Use std::vector<IdType> as values and lazily compact it.
168 absl::flat_hash_map<VariableId, absl::flat_hash_set<IdType>>
169 constraints_by_variable_;
170};
171
172// A placeholder templated definition for traits-based parameter inference when
173// working with atomic constraint families.
174//
175// For template specializations on `IdType`: the `ConstraintData` typedef must
176// satisfy IdType == AtomicConstraintStorage<ConstraintData>::IdType.
177template <typename IdType>
178struct AtomicConstraintTraits {
179 using ConstraintData = void;
183// Inlined implementations
185
186template <typename ConstraintData>
189 ConstraintData constraint) {
190 const std::vector<VariableId> vars = constraint.RelatedVariables();
191 const IdType id = next_id_;
192 ++next_id_;
193 CHECK(constraint_data_.insert({id, std::move(constraint)}).second);
194 for (const VariableId v : vars) {
195 constraints_by_variable_[v].insert(id);
196 }
197 return id;
198}
199
200template <typename ConstraintData>
202 const google::protobuf::Map<int64_t, ProtoType>& constraints) {
203 for (const int64_t raw_id : SortedMapKeys(constraints)) {
204 const IdType id(raw_id);
205 CHECK_GE(id, next_id())
206 << "constraint ID in map: " << raw_id
207 << " is smaller than next_id(): " << next_id().value();
209 AddConstraint(ConstraintData::FromProto(constraints.at(raw_id)));
210 }
211}
212
213template <typename ConstraintData>
214template <typename DiffIter>
216 IdType id, const iterator_range<DiffIter>& diffs) {
217 for (Diff& diff : diffs) {
218 // if the constraint >= checkpoint_, we don't store any info.
219 if (id >= diff.checkpoint) {
220 continue;
221 }
222 diff.deleted_constraints.insert(id);
223 }
224 const auto data = constraint_data_.find(id);
225 CHECK(data != constraint_data_.end());
226 for (const VariableId v : data->second.RelatedVariables()) {
227 constraints_by_variable_[v].erase(id);
228 }
229 constraint_data_.erase(id);
230}
231
232template <typename ConstraintData>
234 VariableId variable_id) {
235 const auto it = constraints_by_variable_.find(variable_id);
236 if (it == constraints_by_variable_.end()) {
237 return;
238 }
239 for (const IdType constraint_id : it->second) {
240 constraint_data_.at(constraint_id).DeleteVariable(variable_id);
241 }
242 constraints_by_variable_.erase(it);
243}
244
245template <typename ConstraintData>
246std::vector<typename AtomicConstraintStorage<ConstraintData>::IdType>
248 std::vector<IdType> result;
249 for (const auto& [id, _] : constraint_data_) {
250 result.push_back(id);
252 return result;
253}
254
255template <typename ConstraintData>
256std::vector<typename AtomicConstraintStorage<ConstraintData>::IdType>
258 std::vector<IdType> result = Constraints();
259 absl::c_sort(result);
260 return result;
262
263template <typename ConstraintData>
265 const Diff& diff) const {
266 return next_id_ <= diff.checkpoint && diff.deleted_constraints.empty();
267}
269template <typename ConstraintData>
271 Diff& diff) const {
272 diff.checkpoint = std::max(diff.checkpoint, next_id_);
273 diff.deleted_constraints.clear();
275
276template <typename ConstraintData>
277typename ConstraintData::UpdatesProtoType
279 UpdatesProtoType update;
280 for (const IdType deleted_id : diff.deleted_constraints) {
281 update.mutable_deleted_constraint_ids()->Add(deleted_id.value());
283 absl::c_sort(*update.mutable_deleted_constraint_ids());
284 for (const IdType id :
285 util_intops::MakeStrongIntRange(diff.checkpoint, next_id_)) {
286 if (contains(id)) {
287 (*update.mutable_new_constraints())[id.value()] = data(id).Proto();
288 }
289 }
290 return update;
291}
292
293} // namespace operations_research::math_opt
294
295#endif // OR_TOOLS_MATH_OPT_STORAGE_ATOMIC_CONSTRAINT_STORAGE_H_
ConstraintData::UpdatesProtoType Update(const Diff &diff) const
Return a proto representation of the current update.
google::protobuf::Map< int64_t, ProtoType > Proto() const
Returns a proto representation of the constraint class.
void ensure_next_id_at_least(const IdType minimum)
Sets the next variable id to be the maximum of next_id() and minimum.
typename ConstraintData::UpdatesProtoType UpdatesProtoType
bool contains(const IdType id) const
Returns true if this id has been created and not yet deleted.
std::vector< IdType > Constraints() const
The ids in use (not deleted). The order is not defined.
void AdvanceCheckpointInDiff(Diff &diff) const
Updates the checkpoint and clears all stored changes in diff.
void AddConstraints(const google::protobuf::Map< int64_t, ProtoType > &constraints)
IdType next_id() const
The smallest ID which is valid for a new constraint.
void DeleteVariable(VariableId variable_id)
Delete a single variable from each constraint in the storage.
const absl::flat_hash_set< IdType > & RelatedConstraints(const VariableId variable_id) const
IdType AddConstraint(ConstraintData constraint)
Add a single constraint to the storage.
void Delete(IdType id, const iterator_range< DiffIter > &diffs)
Delete a single constraint.
const ConstraintData & data(const IdType id) const
int64_t checkpoint(const ElementType e) const
Definition diff.h:70
const MapUtilMappedT< Collection > & FindWithDefault(const Collection &collection, const KeyType &key, const MapUtilMappedT< Collection > &value)
Definition map_util.h:36
An object oriented wrapper for quadratic constraints in ModelStorage.
Definition gurobi_isv.cc:28
ElementId< ElementType::kVariable > VariableId
Definition elements.h:264
std::vector< K > SortedMapKeys(const absl::flat_hash_map< K, V > &in_map)
Definition sorted.h:55
Diff(const AtomicConstraintStorage< ConstraintData > &storage)