Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
elemental.cc
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
15
16#include <array>
17#include <cstdint>
18#include <memory>
19#include <optional>
20#include <ostream>
21#include <string>
22#include <utility>
23#include <vector>
24
25#include "absl/log/check.h"
26#include "absl/log/log.h"
27#include "absl/status/status.h"
28#include "absl/status/statusor.h"
29#include "absl/strings/string_view.h"
35
37
39 : model_name_(std::move(model_name)),
40 primary_objective_name_(std::move(primary_objective_name)) {
41 // NOLINTNEXTLINE(clang-diagnostic-pre-c++20-compat)
42 ForEachIndex<AllAttrs::kNumAttrTypes>([this]<int attr_type_index>() {
44 for (const auto a : Descriptor::Enumerate()) {
45 const int index = static_cast<int>(a);
46 attrs_[a] = StorageForAttrType<attr_type_index>(
47 Descriptor::kAttrDescriptors[index].default_value);
48 }
49 });
50}
51
52std::optional<Elemental::DiffHandle> Elemental::GetDiffHandle(
53 const int64_t id) const {
54 if (diffs_->Get(id) == nullptr) {
55 return std::nullopt;
56 }
57 return DiffHandle(id, diffs_.get());
58}
59
61 auto diff = std::make_unique<Diff>();
62 diff->Advance(CurrentCheckpoint());
63 const int64_t diff_id = diffs_->Insert(std::move(diff));
64 return DiffHandle(diff_id, diffs_.get());
65}
66
68 if (&diff.diffs_ != diffs_.get()) {
69 return false;
70 }
71 return diffs_->Erase(diff.diff_id_);
72}
73
75 if (diffs_.get() != &diff.diffs_) {
76 return false;
77 }
78 Diff* d = diffs_->UpdateAndGet(diff.diff_id_);
79 if (d == nullptr) {
80 return false;
81 }
82 d->Advance(CurrentCheckpoint());
83 return true;
84}
85
87 if (!mutable_element_storage(e).Erase(id)) {
88 return false;
89 }
90 for (auto& [unused, diff] : diffs_->UpdateAndGetAll()) {
91 diff->DeleteElement(e, id);
92 }
93 // NOLINTNEXTLINE(clang-diagnostic-pre-c++20-compat)
94 AllAttrs::ForEachAttr([this, e, id]<typename AttrType>(AttrType a) {
96 // NOLINTNEXTLINE(clang-diagnostic-pre-c++20-compat)
97 [&]<int i>() {
98 if (GetElementTypes(a)[i] == e) {
99 UpdateAttrOnElementDeleted<AttrType, i>(a, id);
100 }
101 });
102 // If `a` is element-valued, we need to remove all keys that refer to the
103 // deleted element.
105 if (e == ValueTypeFor<AttrType>::type()) {
106 const auto keys = element_ref_trackers_[a].GetKeysReferencing(
108 for (const auto key : keys) {
110 }
111 }
112 }
113 });
114
115 return true;
116}
117
118template <typename AttrType, int i>
119void Elemental::UpdateAttrOnElementDeleted(const AttrType a, const int64_t id) {
120 auto& attr_storage = attrs_[a];
121 // We consider the case of n == 1 separately so that we can ensure that
122 // for any attribute with a key size of one, the AttrDiff has no deleted
123 // elements. (If we did not specialize this code, we would need to check for
124 // deleted elements when building our ModelUpdateProto, see
125 // README.md#checkpoints-and-model-updates for an explanation.)
126 if constexpr (GetAttrKeySize<AttrType>() == 1) {
127 for (auto& [unused, diff] : diffs_->UpdateAndGetAll()) {
128 diff->EraseKeysForAttr(a, {AttrKey(id)});
129 }
130 attr_storage.Erase(AttrKey(id));
131 } else {
132 // NOTE: We explicitly spell out the type here, so that if `Slice` ever
133 // returns a reference in `attr_storage` instead of a copy, we are forced
134 // to update this code to make a copy of the slice (otherwise the slice
135 // would be invalidated by calls to `Erase()` below).
136 const std::vector<AttrKeyFor<AttrType>> keys =
137 attr_storage.template Slice<i>(id);
138 for (auto& [unused, diff] : diffs_->UpdateAndGetAll()) {
139 diff->EraseKeysForAttr(a, keys);
140 }
141 for (const auto& key : keys) {
142 attr_storage.Erase(key);
143 }
144 }
145}
146
147std::array<int64_t, kNumElements> Elemental::CurrentCheckpoint() const {
148 std::array<int64_t, kNumElements> result;
149 for (int i = 0; i < kNumElements; ++i) {
150 result[i] = elements_[i].next_id();
151 }
152 return result;
153}
154
156 std::optional<absl::string_view> new_model_name) const {
157 Elemental result(std::string(new_model_name.value_or(model_name_)),
158 primary_objective_name_);
159 result.elements_ = elements_;
160 result.attrs_ = attrs_;
161 return result;
162}
163
164std::ostream& operator<<(std::ostream& ostr, const Elemental& elemental) {
165 ostr << elemental.DebugString();
166 return ostr;
167}
168
169} // namespace operations_research::math_opt
void Advance(const std::array< int64_t, kNumElements > &checkpoints)
Definition diff.cc:23
Elemental(std::string model_name="", std::string primary_objective_name="")
Definition elemental.cc:38
Policy::CheckResultT SetAttr(AttrType a, AttrKeyFor< AttrType > key, ValueTypeFor< AttrType > value)
Definition elemental.h:448
std::optional< DiffHandle > GetDiffHandle(int64_t id) const
Returns the DiffHandle for id, if one exists, or nullopt otherwise.
Definition elemental.cc:52
const std::string & primary_objective_name() const
The name of the primary objective of this optimization model.
Definition elemental.h:75
std::string DebugString(bool print_diffs=true) const
const std::string & model_name() const
The name of this optimization model.
Definition elemental.h:72
bool DeleteElementUntyped(ElementType e, int64_t id)
Type-erased version of DeleteElement. Prefer the latter.
Definition elemental.cc:86
Policy::template Wrapped< std::vector< AttrKeyFor< AttrType > > > Slice(AttrType a, int64_t key_elem) const
Definition elemental.h:470
Elemental Clone(std::optional< absl::string_view > new_model_name=std::nullopt) const
Definition elemental.cc:155
An object oriented wrapper for quadratic constraints in ModelStorage.
Definition gurobi_isv.cc:28
static constexpr bool is_element_id_v
Definition elements.h:262
AttrKey(Ints... dims) -> AttrKey< sizeof...(Ints), NoSymmetry >
CTAD for AttrKey(1,2).
std::ostream & operator<<(std::ostream &ostr, const SecondOrderConeConstraint &constraint)
constexpr decltype(auto) ForEachIndex(Fn &&fn)
Definition arrays.h:56
constexpr std::array< ElementType, GetAttrKeySize< attr >()> GetElementTypes()
typename AttrTypeDescriptorT< AttrType >::ValueType ValueTypeFor
The value type for attribute type AttrType.
STL namespace.
std::tuple_element_t< i, AllAttrTypeDescriptors > TypeDescriptor
Returns the descriptor of the i-th attribute type in the list.