Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
set_cover_invariant.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 <limits>
18#include <tuple>
19#include <vector>
20
21#include "absl/log/check.h"
22#include "absl/log/log.h"
23#include "absl/types/span.h"
28
29namespace operations_research {
30
32
33// Note: in many of the member functions, variables have "crypterse" names
34// to avoid confusing them with member data. For example mrgnl_impcts is used
35// to avoid confusion with num_free_elements_.
37 DCHECK(model_->ComputeFeasibility());
38 model_->CreateSparseRowView();
39 Clear();
40}
41
43 cost_ = 0.0;
44
45 lower_bound_ = 0.0;
46 is_cost_consistent_ = true;
47
48 const BaseInt num_subsets = model_->num_subsets();
49 const BaseInt num_elements = model_->num_elements();
50
51 is_selected_.assign(num_subsets, false);
52 num_free_elements_.assign(num_subsets, 0);
53 num_non_overcovered_elements_.assign(num_subsets, 0);
54 is_redundant_.assign(num_subsets, false);
55
56 const SparseColumnView& columns = model_->columns();
57 for (const SubsetIndex subset : model_->SubsetRange()) {
58 num_free_elements_[subset] = columns[subset].size();
59 num_non_overcovered_elements_[subset] = columns[subset].size();
60 }
61
62 coverage_.assign(num_elements, 0);
63
64 // No need to reserve for trace_ and other vectors as extending with
65 // push_back is fast enough.
66 trace_.clear();
67 newly_removable_subsets_.clear();
68 newly_non_removable_subsets_.clear();
69
70 num_uncovered_elements_ = num_elements;
71 consistency_level_ = CL::kRedundancy;
72}
73
75 CHECK(consistency <= CL::kRedundancy);
76 if (consistency == CL::kInconsistent) {
77 return true;
78 }
79 auto [cst, cvrg] = ComputeCostAndCoverage(is_selected_);
80 CHECK(MathUtil::AlmostEquals(cost_, cst))
81 << "cost_ = " << cost_ << " vs recomputed cst = " << cst;
82 for (const ElementIndex element : model_->ElementRange()) {
83 CHECK_EQ(cvrg[element], coverage_[element]);
84 }
85 if (consistency == CL::kCostAndCoverage) {
86 return true;
87 }
88 auto [num_uncvrd_elts, num_free_elts] =
89 ComputeNumUncoveredAndFreeElements(coverage_);
90 for (const SubsetIndex subset : model_->SubsetRange()) {
91 CHECK_EQ(num_free_elts[subset], num_free_elements_[subset]);
92 }
93 if (consistency == CL::kFreeAndUncovered) {
94 return true;
95 }
96 auto [num_non_ovrcvrd_elts, is_rdndnt] = ComputeRedundancyInfo(coverage_);
97 for (const SubsetIndex subset : model_->SubsetRange()) {
98 CHECK_EQ(is_rdndnt[subset], is_redundant_[subset]);
99 CHECK_EQ(is_rdndnt[subset], num_non_ovrcvrd_elts[subset] == 0);
100 }
101 if (consistency == CL::kRedundancy) {
102 return true;
103 }
104 LOG(FATAL) << "Consistency level not supported: "
105 << static_cast<int>(consistency);
106 return false;
107}
108
110 ClearTrace();
112 SubsetIndex subset(0);
113 const SparseColumnView& columns = model_->columns();
114 for (const bool b : solution) {
115 if (b) {
116 trace_.push_back(SetCoverDecision(subset, true));
117 if (!is_selected_[subset]) {
118 cost_ += model_->subset_costs()[subset];
119 for (const ElementIndex element : columns[subset]) {
120 ++coverage_[element];
121 }
122 }
123 } else {
124 if (is_selected_[subset]) {
125 cost_ -= model_->subset_costs()[subset];
126 for (const ElementIndex element : columns[subset]) {
127 --coverage_[element];
128 }
129 }
130 }
131 is_selected_[subset] = b;
132 ++subset;
133 }
134 consistency_level_ = CL::kCostAndCoverage;
135}
136
138 const std::vector<SetCoverDecision>& trace,
141 is_selected_.assign(model_->num_subsets(), false);
142 trace_ = trace;
143 coverage_ = coverage;
144 cost_ = 0.0;
145 for (const SetCoverDecision& decision : trace) {
146 if (decision.decision()) {
147 const SubsetIndex subset(decision.subset());
148 is_selected_[subset] = true;
149 cost_ += model_->subset_costs()[subset];
150 }
151 }
152 consistency_level_ = CL::kCostAndCoverage;
153 DCHECK(CheckConsistency(CL::kCostAndCoverage));
154}
155
156bool SetCoverInvariant::NeedToRecompute(ConsistencyLevel cheched_consistency,
157 ConsistencyLevel target_consistency) {
158 return consistency_level_ < cheched_consistency &&
159 cheched_consistency <= target_consistency;
160}
161
163 CHECK(target_consistency >= CL::kCostAndCoverage);
164 CHECK(target_consistency <= CL::kRedundancy);
165 DCHECK(CheckConsistency(consistency_level_));
166 if (NeedToRecompute(CL::kCostAndCoverage, target_consistency)) {
167 std::tie(cost_, coverage_) = ComputeCostAndCoverage(is_selected_);
168 }
169 if (NeedToRecompute(CL::kFreeAndUncovered, target_consistency)) {
170 std::tie(num_uncovered_elements_, num_free_elements_) =
171 ComputeNumUncoveredAndFreeElements(coverage_);
172 }
173 if (NeedToRecompute(CL::kRedundancy, target_consistency)) {
174 std::tie(num_non_overcovered_elements_, is_redundant_) =
175 ComputeRedundancyInfo(coverage_);
176 }
177 consistency_level_ = target_consistency;
178}
179
180// NOTE(user): This piece of code is for reference because it seems to be
181// faster to update the invariant. const BaseInt num_subsets =
182// model_->num_subsets(); is_redundant_.assign(num_subsets, false);
183// num_non_overcovered_elements_.assign(num_subsets, 0);
184// const SparseColumnView& columns = model_->columns();
185// for (const ElementIndex element : model_->ElementRange()) {
186// if (coverage_[element] >= 1) {
187// --num_uncovered_elements_;
188// }
189// }
190// for (const SubsetIndex subset : model_->SubsetRange()) {
191// for (const ElementIndex element : columns[subset]) {
192// if (coverage_[element] <= 1) {
193// ++num_non_overcovered_elements_[subset];
194// }
195// if (coverage_[element] >= 1) {
196// --num_free_elements_[subset];
197// }
198// }
199// is_redundant_[subset] = (num_non_overcovered_elements_[subset] ==
200// 0);
201// }
202
203std::tuple<Cost, ElementToIntVector> SetCoverInvariant::ComputeCostAndCoverage(
204 const SubsetBoolVector& choices) const {
205 Cost cst = 0.0;
206 ElementToIntVector cvrg(model_->num_elements(), 0);
207 const SparseColumnView& columns = model_->columns();
208 // Initialize coverage, update cost, and compute the coverage for
209 // all the elements covered by the selected subsets.
210 const SubsetCostVector& subset_costs = model_->subset_costs();
211 SubsetIndex subset(0);
212 for (const bool b : choices) {
213 if (b) {
214 cst += subset_costs[subset];
215 for (const ElementIndex element : columns[subset]) {
216 ++cvrg[element];
217 }
218 }
219 ++subset;
220 }
221 return {cst, cvrg};
222}
223
225 const absl::Span<const SubsetIndex> focus) const {
226 ElementToIntVector coverage(coverage_.size());
227 for (const SubsetIndex subset : focus) {
228 if (is_selected_[subset]) {
229 for (const ElementIndex element : model_->columns()[subset]) {
230 ++coverage[element];
231 }
232 }
233 }
234 return coverage;
235}
236
237std::tuple<BaseInt, SubsetToIntVector>
238SetCoverInvariant::ComputeNumUncoveredAndFreeElements(
239 const ElementToIntVector& cvrg) const {
240 BaseInt num_uncvrd_elts = model_->num_elements();
241
242 const BaseInt num_subsets(model_->num_subsets());
243 SubsetToIntVector num_free_elts(num_subsets, 0);
244
245 const SparseColumnView& columns = model_->columns();
246 // Initialize number of free elements and number of elements covered 0
247 // or 1.
248 for (const SubsetIndex subset : model_->SubsetRange()) {
249 num_free_elts[subset] = columns[subset].size();
250 }
251
252 const SparseRowView& rows = model_->rows();
253 for (const ElementIndex element : model_->ElementRange()) {
254 if (cvrg[element] >= 1) {
255 --num_uncvrd_elts;
256 for (const SubsetIndex subset : rows[element]) {
257 --num_free_elts[subset];
258 }
259 }
260 }
261 return {num_uncvrd_elts, num_free_elts};
262}
263
264std::tuple<SubsetToIntVector, SubsetBoolVector>
265SetCoverInvariant::ComputeRedundancyInfo(const ElementToIntVector& cvrg) const {
266 const BaseInt num_subsets(model_->num_subsets());
267 SubsetToIntVector num_cvrg_le_1_elts(num_subsets, 0);
268 SubsetBoolVector is_rdndnt(num_subsets, false);
269
270 const SparseColumnView& columns = model_->columns();
271 // Initialize number of free elements and number of elements covered 0
272 // or 1.
273 for (const SubsetIndex subset : model_->SubsetRange()) {
274 num_cvrg_le_1_elts[subset] = columns[subset].size();
275 }
276
277 const SparseRowView& rows = model_->rows();
278 for (const ElementIndex element : model_->ElementRange()) {
279 if (cvrg[element] >= 2) {
280 for (const SubsetIndex subset : rows[element]) {
281 --num_cvrg_le_1_elts[subset];
282 if (num_cvrg_le_1_elts[subset] == 0) {
283 is_rdndnt[subset] = true;
284 }
285 }
286 }
287 }
288 return {num_cvrg_le_1_elts, is_rdndnt};
289}
290
292 // As of 2024-05-14, this is as fast as "smarter" alternatives that
293 // try to avoid some memory writes by keeping track of already visited
294 // subsets. We also tried to use is_selected_ as a helper, which
295 // slowed down everything.
296 const SubsetIndex num_subsets(model_->num_subsets());
297 SubsetBoolVector last_value_seen(num_subsets, false);
298 for (BaseInt i = 0; i < trace_.size(); ++i) {
299 const SubsetIndex subset(trace_[i].subset());
300 last_value_seen[subset] = trace_[i].decision();
301 }
302 BaseInt w = 0; // Write index.
303 for (BaseInt i = 0; i < trace_.size(); ++i) {
304 const SubsetIndex subset(trace_[i].subset());
305 if (last_value_seen[subset]) {
306 last_value_seen[subset] = false;
307 trace_[w] = SetCoverDecision(subset, true);
308 ++w;
309 }
310 }
311 trace_.resize(w);
312}
313
314bool SetCoverInvariant::ComputeIsRedundant(SubsetIndex subset) const {
315 if (consistency_level_ >= CL::kRedundancy) {
316 return is_redundant_[subset];
317 }
318 if (is_selected_[subset]) {
319 for (const ElementIndex element : model_->columns()[subset]) {
320 if (coverage_[element] <= 1) { // If deselected, it will be <= 0...
321 return false;
322 }
323 }
324 } else {
325 for (const ElementIndex element : model_->columns()[subset]) {
326 if (coverage_[element] == 0) { // Cannot be removed from the problem.
327 return false;
328 }
329 }
330 }
331 return true;
332}
333
335 BaseInt num_free_elements = model_->columns()[subset].size();
336 for (const ElementIndex element : model_->columns()[subset]) {
337 if (coverage_[element] != 0) {
339 }
340 }
341 return num_free_elements;
342}
343
344bool SetCoverInvariant::Select(SubsetIndex subset,
345 ConsistencyLevel target_consistency) {
346 if (is_selected_[subset]) return false;
347
348 const bool update_redundancy_info = target_consistency >= CL::kRedundancy;
349 if (update_redundancy_info) {
351 }
352 consistency_level_ = std::min(consistency_level_, target_consistency);
353 DVLOG(1) << "Selecting subset " << subset;
354
355 DCHECK(CheckConsistency(target_consistency));
356 trace_.push_back(SetCoverDecision(subset, true));
357 is_selected_[subset] = true;
358 const SubsetCostVector& subset_costs = model_->subset_costs();
359 cost_ += subset_costs[subset];
360 const SparseColumnView& columns = model_->columns();
361 const SparseRowView& rows = model_->rows();
362 // Fast path for kCostAndCoverage.
363 if (target_consistency == CL::kCostAndCoverage) {
364 for (const ElementIndex element : columns[subset]) {
365 ++coverage_[element];
366 }
367 return true;
368 }
369 for (const ElementIndex element : columns[subset]) {
370 if (coverage_[element] == 0) {
371 // `element` will be newly covered.
372 --num_uncovered_elements_;
373 for (const SubsetIndex impacted_subset : rows[element]) {
374 --num_free_elements_[impacted_subset];
375 }
376 } else if (update_redundancy_info && coverage_[element] == 1) {
377 // `element` will be newly overcovered.
378 for (const SubsetIndex impacted_subset : rows[element]) {
379 --num_non_overcovered_elements_[impacted_subset];
380 if (num_non_overcovered_elements_[impacted_subset] == 0) {
381 // All the elements in impacted_subset are now overcovered, so
382 // it is removable. Note that this happens only when the last
383 // element of impacted_subset becomes overcovered.
384 DCHECK(!is_redundant_[impacted_subset]);
385 if (is_selected_[impacted_subset]) {
386 newly_removable_subsets_.push_back(impacted_subset);
387 }
388 is_redundant_[impacted_subset] = true;
389 }
390 }
391 }
392 // Update coverage. Notice the asymmetry with Deselect where
393 // coverage is
394 // **decremented** before being tested. This allows to have more
395 // symmetrical code for conditions.
396 ++coverage_[element];
397 }
398 if (update_redundancy_info) {
399 if (is_redundant_[subset]) {
400 newly_removable_subsets_.push_back(subset);
401 } else {
402 newly_non_removable_subsets_.push_back(subset);
403 }
404 }
405 DCHECK_EQ(num_free_elements_[subset], 0);
406 DCHECK(CheckConsistency(target_consistency));
407 return true;
408}
409
410bool SetCoverInvariant::Deselect(SubsetIndex subset,
411 ConsistencyLevel target_consistency) {
412 // NOMUTANTS -- This is a short-circuit to avoid doing any work
413 // when the subset is already deselected.
414 if (!is_selected_[subset]) return false;
415 DCHECK(CheckConsistency(target_consistency));
416 const bool update_redundancy_info = target_consistency >= CL::kRedundancy;
417 if (update_redundancy_info) {
419 }
420 consistency_level_ = std::min(consistency_level_, target_consistency);
421 DVLOG(1) << "Deselecting subset " << subset;
422 // If already selected, then num_free_elements == 0.
423 DCHECK(is_selected_[subset]);
424 trace_.push_back(SetCoverDecision(subset, false));
425 is_selected_[subset] = false;
426 const SubsetCostVector& subset_costs = model_->subset_costs();
427 cost_ -= subset_costs[subset];
428 const SparseColumnView& columns = model_->columns();
429 const SparseRowView& rows = model_->rows();
430 // Fast path for kCostAndCoverage.
431 if (target_consistency == CL::kCostAndCoverage) {
432 for (const ElementIndex element : columns[subset]) {
433 --coverage_[element];
434 }
435 return true;
436 }
437 // This is a dissymmetry with Select, and only maintained in
438 // consistency level kFreeAndUncovered and above.
439 DCHECK_EQ(num_free_elements_[subset], 0);
440 for (const ElementIndex element : columns[subset]) {
441 // Update coverage. Notice the asymmetry with Select where coverage
442 // is incremented after being tested.
443 --coverage_[element];
444 if (coverage_[element] == 0) {
445 // `element` is no longer covered.
446 ++num_uncovered_elements_;
447 for (const SubsetIndex impacted_subset : rows[element]) {
448 ++num_free_elements_[impacted_subset];
449 }
450 } else if (update_redundancy_info && coverage_[element] == 1) {
451 // `element` will be no longer overcovered.
452 for (const SubsetIndex impacted_subset : rows[element]) {
453 if (num_non_overcovered_elements_[impacted_subset] == 0) {
454 // There is one element of impacted_subset which is not
455 // overcovered. impacted_subset has just become non-removable.
456 DCHECK(is_redundant_[impacted_subset]);
457 if (is_selected_[impacted_subset]) {
458 newly_non_removable_subsets_.push_back(impacted_subset);
459 }
460 is_redundant_[impacted_subset] = false;
461 }
462 ++num_non_overcovered_elements_[impacted_subset];
463 }
464 }
465 }
466 // Since subset is now deselected, there is no need
467 // nor meaning in adding it a list of removable or non-removable
468 // subsets. This is a dissymmetry with Select.
469 DCHECK(CheckConsistency(target_consistency));
470 return true;
471}
472
473SetCoverSolutionResponse SetCoverInvariant::ExportSolutionAsProto() const {
474 SetCoverSolutionResponse message;
475 message.set_num_subsets(is_selected_.size());
476 Cost lower_bound = std::numeric_limits<Cost>::max();
477 for (const SubsetIndex subset : model_->SubsetRange()) {
478 if (is_selected_[subset]) {
479 message.add_subset(subset.value());
480 }
481 lower_bound = std::min(model_->subset_costs()[subset], lower_bound);
482 }
483 message.set_cost(cost_);
484 message.set_cost_lower_bound(lower_bound);
485 return message;
486}
487
489 const SetCoverSolutionResponse& message) {
490 is_selected_.resize(SubsetIndex(message.num_subsets()), false);
491 for (auto s : message.subset()) {
492 is_selected_[SubsetIndex(s)] = true;
493 }
494 Cost cost = message.cost();
495 CHECK(MathUtil::AlmostEquals(cost, cost_));
496}
497} // namespace operations_research
static bool AlmostEquals(const T x, const T y)
Definition mathutil.h:314
A helper class used to store the decisions made during a search.
bool ComputeIsRedundant(SubsetIndex subset) const
void Recompute(ConsistencyLevel target_consistency)
Recomputes the invariant to the given consistency level.
const SubsetToIntVector & num_free_elements() const
SetCoverSolutionResponse ExportSolutionAsProto() const
Returns the current solution as a proto.
const std::vector< SetCoverDecision > & trace() const
Returns the vector of the decisions which have led to the current solution.
bool CheckConsistency(ConsistencyLevel consistency) const
Checks the consistency of the invariant at the given consistency level.
void LoadSolution(const SubsetBoolVector &solution)
Loads the solution and recomputes the data in the invariant.
void ImportSolutionFromProto(const SetCoverSolutionResponse &message)
Imports the solution from a proto.
bool Deselect(SubsetIndex subset, ConsistencyLevel consistency)
bool Select(SubsetIndex subset, ConsistencyLevel consistency)
const ElementToIntVector & coverage() const
Returns vector containing number of subsets covering each element.
BaseInt ComputeNumFreeElements(SubsetIndex subset) const
Computes the number of free (uncovered) elements in the given subset.
void LoadTraceAndCoverage(const std::vector< SetCoverDecision > &trace, const ElementToIntVector &coverage)
Cost cost() const
Returns the cost of current solution.
ElementToIntVector ComputeCoverageInFocus(absl::Span< const SubsetIndex > focus) const
void Clear()
Clears the invariant. Also called by Initialize.
void ClearRemovabilityInformation()
Clear the removability information.
util_intops::StrongIntRange< ElementIndex > ElementRange() const
const SparseRowView & rows() const
Row view of the set covering problem.
util_intops::StrongIntRange< SubsetIndex > SubsetRange() const
Access to the ranges of subsets and elements.
const SubsetCostVector & subset_costs() const
Vector of costs for each subset.
const SparseColumnView & columns() const
Column view of the set covering problem.
In SWIG mode, we don't want anything besides these top-level includes.
util_intops::StrongVector< SubsetIndex, Cost > SubsetCostVector
Definition base_types.h:58
Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid
SetCoverInvariant::ConsistencyLevel CL
util_intops::StrongVector< SubsetIndex, BaseInt > SubsetToIntVector
Definition base_types.h:65
util_intops::StrongVector< ElementIndex, BaseInt > ElementToIntVector
Definition base_types.h:64
util_intops::StrongVector< SubsetIndex, bool > SubsetBoolVector
Definition base_types.h:71
util_intops::StrongVector< SubsetIndex, SparseColumn > SparseColumnView
Views of the sparse vectors.
Definition base_types.h:68
double Cost
Basic non-strict type for cost. The speed penalty for using double is ~2%.
Definition base_types.h:32
util_intops::StrongVector< ElementIndex, SparseRow > SparseRowView
Definition base_types.h:69
trees with all degrees equal w the current value of w