Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
objective_storage.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 <algorithm>
17#include <cstdint>
18#include <optional>
19#include <string>
20#include <utility>
21#include <vector>
22
23#include "absl/algorithm/container.h"
24#include "absl/container/flat_hash_set.h"
25#include "absl/log/check.h"
26#include "absl/strings/string_view.h"
27#include "absl/types/span.h"
36
38
40 const VariableId deleted_variable, const VariableId variable_checkpoint,
42 if (deleted_variable >= variable_checkpoint) {
43 return;
44 }
45 linear_coefficients.erase(deleted_variable);
46 for (const VariableId v2 :
47 quadratic_terms.RelatedVariables(deleted_variable)) {
48 if (v2 < variable_checkpoint) {
50 {std::min(deleted_variable, v2), std::max(deleted_variable, v2)});
51 }
52 }
53}
54
55ObjectiveProto ObjectiveStorage::ObjectiveData::Proto() const {
56 ObjectiveProto proto;
59 proto.set_offset(offset);
62 proto.set_name(name);
63 return proto;
64}
65
67 const int64_t priority, const absl::string_view name) {
68 const AuxiliaryObjectiveId id = next_id_;
69 ++next_id_;
70 CHECK(!auxiliary_objectives_.contains(id));
71 {
72 ObjectiveData& data = auxiliary_objectives_[id];
73 data.priority = priority;
74 data.name = std::string(name);
75 }
76 return id;
77}
78
79std::vector<AuxiliaryObjectiveId> ObjectiveStorage::AuxiliaryObjectives()
80 const {
81 std::vector<AuxiliaryObjectiveId> ids;
82 ids.reserve(num_auxiliary_objectives());
83 for (const auto& [id, unused] : auxiliary_objectives_) {
84 ids.push_back(id);
85 }
86 return ids;
87}
88
89std::vector<AuxiliaryObjectiveId> ObjectiveStorage::SortedAuxiliaryObjectives()
90 const {
91 std::vector<AuxiliaryObjectiveId> ids = AuxiliaryObjectives();
92 absl::c_sort(ids);
93 return ids;
94}
95
96std::pair<ObjectiveProto, google::protobuf::Map<int64_t, ObjectiveProto>>
98 google::protobuf::Map<int64_t, ObjectiveProto> auxiliary_objectives;
99 for (const auto& [id, objective] : auxiliary_objectives_) {
100 auxiliary_objectives[id.value()] = objective.Proto();
101 }
102 return {primary_objective_.Proto(), std::move(auxiliary_objectives)};
103}
104
105namespace {
106
107void EnsureHasValue(std::optional<ObjectiveUpdatesProto>& update) {
108 if (!update.has_value()) {
109 update.emplace();
110 }
111}
112
113} // namespace
114
115std::optional<ObjectiveUpdatesProto> ObjectiveStorage::ObjectiveData::Update(
116 const Diff::SingleObjective& diff_data,
117 const absl::flat_hash_set<VariableId>& deleted_variables,
118 absl::Span<const VariableId> new_variables) const {
119 std::optional<ObjectiveUpdatesProto> update_proto;
120
121 if (diff_data.direction) {
122 EnsureHasValue(update_proto);
123 update_proto->set_direction_update(maximize);
124 }
125 if (diff_data.priority) {
126 EnsureHasValue(update_proto);
127 update_proto->set_priority_update(priority);
128 }
129 if (diff_data.offset) {
130 EnsureHasValue(update_proto);
131 update_proto->set_offset_update(offset);
132 }
133 for (const VariableId v : SortedSetElements(diff_data.linear_coefficients)) {
134 EnsureHasValue(update_proto);
135 update_proto->mutable_linear_coefficients()->add_ids(v.value());
136 update_proto->mutable_linear_coefficients()->add_values(
137 linear_terms.get(v));
138 }
139 for (const VariableId v : new_variables) {
140 const double val = linear_terms.get(v);
141 if (val != 0.0) {
142 EnsureHasValue(update_proto);
143 update_proto->mutable_linear_coefficients()->add_ids(v.value());
144 update_proto->mutable_linear_coefficients()->add_values(val);
145 }
146 }
147 SparseDoubleMatrixProto quadratic_update = quadratic_terms.Update(
148 deleted_variables, new_variables, diff_data.quadratic_coefficients);
149 if (!quadratic_update.row_ids().empty()) {
150 // Do not set the field if there is no quadratic term changes.
151 EnsureHasValue(update_proto);
152 *update_proto->mutable_quadratic_coefficients() =
153 std::move(quadratic_update);
154 }
155 return update_proto;
156}
157
158std::pair<ObjectiveUpdatesProto, AuxiliaryObjectivesUpdatesProto>
160 const Diff& diff, const absl::flat_hash_set<VariableId>& deleted_variables,
161 absl::Span<const VariableId> new_variables) const {
162 AuxiliaryObjectivesUpdatesProto auxiliary_result;
163
164 for (const AuxiliaryObjectiveId id : diff.deleted) {
165 auxiliary_result.add_deleted_objective_ids(id.value());
166 }
167 absl::c_sort(*auxiliary_result.mutable_deleted_objective_ids());
168
169 for (const auto& [id, objective] : auxiliary_objectives_) {
170 // Note that any `Delete()`d objective will not be in the `objectives_` map.
171 // Hence, each entry is either new (if not extracted) or potentially an
172 // update on an existing objective.
173 if (!diff.objective_tracked(id)) {
174 // An un-extracted objective goes in the `new_objectives` map. It is fresh
175 // and so there is no need to update, so we continue.
176 (*auxiliary_result.mutable_new_objectives())[id.value()] =
177 auxiliary_objectives_.at(id).Proto();
178 continue;
179 }
180
181 // `Diff` provides no guarantees on which objectives will have entries in
182 // `objective_diffs`; a missing entry is equivalent to one with an empty
183 // key.
184 std::optional<ObjectiveUpdatesProto> update_proto =
185 objective.Update(gtl::FindWithDefault(diff.objective_diffs, id),
186 deleted_variables, new_variables);
187 if (update_proto.has_value()) {
188 // If the update message is empty we do not export it. This is
189 // particularly important for auxiliary objectives as we do not want to
190 // add empty map entries.
191 (*auxiliary_result.mutable_objective_updates())[id.value()] =
192 *std::move(update_proto);
193 }
194 }
195
196 return {primary_objective_
199 deleted_variables, new_variables)
200 .value_or(ObjectiveUpdatesProto{}),
201 std::move(auxiliary_result)};
202}
203
205 const VariableId variable_checkpoint, Diff& diff) const {
206 diff.objective_checkpoint = std::max(diff.objective_checkpoint, next_id_);
209 diff.objective_diffs.clear();
210 diff.deleted.clear();
211}
212
213} // namespace operations_research::math_opt
::google::protobuf::RepeatedField<::int64_t > *PROTOBUF_NONNULL mutable_deleted_objective_ids()
::google::protobuf::Map<::int64_t, ::operations_research::math_opt::ObjectiveProto > *PROTOBUF_NONNULL mutable_new_objectives()
::google::protobuf::Map<::int64_t, ::operations_research::math_opt::ObjectiveUpdatesProto > *PROTOBUF_NONNULL mutable_objective_updates()
::operations_research::math_opt::SparseDoubleVectorProto *PROTOBUF_NONNULL mutable_linear_coefficients()
Definition model.pb.h:2945
::operations_research::math_opt::SparseDoubleMatrixProto *PROTOBUF_NONNULL mutable_quadratic_coefficients()
Definition model.pb.h:3038
void set_name(Arg_ &&arg, Args_... args)
const SparseSymmetricMatrix & quadratic_terms(ObjectiveId id) const
std::pair< ObjectiveProto, google::protobuf::Map< int64_t, ObjectiveProto > > Proto() const
std::vector< AuxiliaryObjectiveId > SortedAuxiliaryObjectives() const
const absl::flat_hash_map< VariableId, double > & linear_terms(ObjectiveId id) const
const std::string & name(ObjectiveId id) const
void AdvanceCheckpointInDiff(VariableId variable_checkpoint, Diff &diff) const
Updates the checkpoint and clears all stored changes in diff.
std::vector< AuxiliaryObjectiveId > AuxiliaryObjectives() const
The AuxiliaryObjectivesIds in use (not deleted), order not defined.
AuxiliaryObjectiveId AddAuxiliaryObjective(int64_t priority, absl::string_view name)
std::pair< ObjectiveUpdatesProto, AuxiliaryObjectivesUpdatesProto > Update(const Diff &diff, const absl::flat_hash_set< VariableId > &deleted_variables, absl::Span< const VariableId > new_variables) const
SparseDoubleMatrixProto Update(const absl::flat_hash_set< VariableId > &deleted_variables, absl::Span< const VariableId > new_variables, const absl::flat_hash_set< std::pair< VariableId, VariableId > > &dirty) const
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::kAuxiliaryObjective > AuxiliaryObjectiveId
Definition elements.h:266
ElementId< ElementType::kVariable > VariableId
Definition elements.h:264
constexpr ObjectiveId kPrimaryObjectiveId
std::vector< T > SortedSetElements(const absl::flat_hash_set< T > &elements)
Definition sorted.h:28
absl::flat_hash_set< std::pair< VariableId, VariableId > > quadratic_coefficients
void DeleteVariable(VariableId deleted_variable, VariableId variable_checkpoint, const SparseSymmetricMatrix &quadratic_terms)
absl::flat_hash_map< ObjectiveId, SingleObjective > objective_diffs
absl::flat_hash_set< AuxiliaryObjectiveId > deleted