21#include "absl/log/check.h"
22#include "absl/log/log.h"
23#include "absl/types/span.h"
37 DCHECK(model_->ComputeFeasibility());
38 model_->CreateSparseRowView();
46 is_cost_consistent_ =
true;
48 const BaseInt num_subsets = model_->num_subsets();
49 const BaseInt num_elements = model_->num_elements();
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);
57 for (
const SubsetIndex subset : model_->SubsetRange()) {
58 num_free_elements_[subset] = columns[subset].size();
59 num_non_overcovered_elements_[subset] = columns[subset].size();
62 coverage_.assign(num_elements, 0);
67 newly_removable_subsets_.clear();
68 newly_non_removable_subsets_.clear();
70 num_uncovered_elements_ = num_elements;
71 consistency_level_ = CL::kRedundancy;
75 CHECK(consistency <= CL::kRedundancy);
76 if (consistency == CL::kInconsistent) {
79 auto [cst, cvrg] = ComputeCostAndCoverage(is_selected_);
81 <<
"cost_ = " << cost_ <<
" vs recomputed cst = " << cst;
82 for (
const ElementIndex element : model_->ElementRange()) {
83 CHECK_EQ(cvrg[element], coverage_[element]);
85 if (consistency == CL::kCostAndCoverage) {
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]);
93 if (consistency == CL::kFreeAndUncovered) {
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);
101 if (consistency == CL::kRedundancy) {
104 LOG(FATAL) <<
"Consistency level not supported: "
105 <<
static_cast<int>(consistency);
112 SubsetIndex subset(0);
117 if (!is_selected_[subset]) {
118 cost_ += model_->subset_costs()[subset];
119 for (
const ElementIndex element : columns[subset]) {
120 ++coverage_[element];
124 if (is_selected_[subset]) {
125 cost_ -= model_->subset_costs()[subset];
126 for (
const ElementIndex element : columns[subset]) {
127 --coverage_[element];
131 is_selected_[subset] = b;
134 consistency_level_ = CL::kCostAndCoverage;
138 const std::vector<SetCoverDecision>&
trace,
141 is_selected_.assign(model_->num_subsets(),
false);
146 if (decision.decision()) {
147 const SubsetIndex subset(decision.subset());
148 is_selected_[subset] =
true;
149 cost_ += model_->subset_costs()[subset];
152 consistency_level_ = CL::kCostAndCoverage;
156bool SetCoverInvariant::NeedToRecompute(ConsistencyLevel cheched_consistency,
157 ConsistencyLevel target_consistency) {
158 return consistency_level_ < cheched_consistency &&
159 cheched_consistency <= target_consistency;
163 CHECK(target_consistency >= CL::kCostAndCoverage);
164 CHECK(target_consistency <= CL::kRedundancy);
166 if (NeedToRecompute(CL::kCostAndCoverage, target_consistency)) {
167 std::tie(cost_, coverage_) = ComputeCostAndCoverage(is_selected_);
169 if (NeedToRecompute(CL::kFreeAndUncovered, target_consistency)) {
170 std::tie(num_uncovered_elements_, num_free_elements_) =
171 ComputeNumUncoveredAndFreeElements(coverage_);
173 if (NeedToRecompute(CL::kRedundancy, target_consistency)) {
174 std::tie(num_non_overcovered_elements_, is_redundant_) =
175 ComputeRedundancyInfo(coverage_);
177 consistency_level_ = target_consistency;
203std::tuple<Cost, ElementToIntVector> SetCoverInvariant::ComputeCostAndCoverage(
211 SubsetIndex subset(0);
212 for (
const bool b : choices) {
214 cst += subset_costs[subset];
215 for (
const ElementIndex element : columns[subset]) {
225 const absl::Span<const SubsetIndex> focus)
const {
227 for (
const SubsetIndex subset : focus) {
228 if (is_selected_[subset]) {
229 for (
const ElementIndex element : model_->columns()[subset]) {
237std::tuple<BaseInt, SubsetToIntVector>
238SetCoverInvariant::ComputeNumUncoveredAndFreeElements(
248 for (
const SubsetIndex subset : model_->
SubsetRange()) {
249 num_free_elts[subset] = columns[subset].size();
253 for (
const ElementIndex element : model_->
ElementRange()) {
254 if (cvrg[element] >= 1) {
256 for (
const SubsetIndex subset : rows[element]) {
257 --num_free_elts[subset];
261 return {num_uncvrd_elts, num_free_elts};
264std::tuple<SubsetToIntVector, SubsetBoolVector>
266 const BaseInt num_subsets(model_->num_subsets());
273 for (
const SubsetIndex subset : model_->SubsetRange()) {
274 num_cvrg_le_1_elts[subset] = columns[subset].size();
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;
288 return {num_cvrg_le_1_elts, is_rdndnt};
296 const SubsetIndex num_subsets(model_->num_subsets());
298 for (
BaseInt i = 0; i < trace_.size(); ++i) {
299 const SubsetIndex subset(trace_[i].subset());
300 last_value_seen[subset] = trace_[i].decision();
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;
315 if (consistency_level_ >= CL::kRedundancy) {
316 return is_redundant_[subset];
318 if (is_selected_[subset]) {
319 for (
const ElementIndex element : model_->columns()[subset]) {
320 if (coverage_[element] <= 1) {
325 for (
const ElementIndex element : model_->columns()[subset]) {
326 if (coverage_[element] == 0) {
336 for (
const ElementIndex element : model_->columns()[subset]) {
337 if (coverage_[element] != 0) {
346 if (is_selected_[subset])
return false;
348 const bool update_redundancy_info = target_consistency >= CL::kRedundancy;
349 if (update_redundancy_info) {
352 consistency_level_ = std::min(consistency_level_, target_consistency);
353 DVLOG(1) <<
"Selecting subset " << subset;
357 is_selected_[subset] =
true;
359 cost_ += subset_costs[subset];
363 if (target_consistency == CL::kCostAndCoverage) {
364 for (
const ElementIndex element : columns[subset]) {
365 ++coverage_[element];
369 for (
const ElementIndex element : columns[subset]) {
370 if (coverage_[element] == 0) {
372 --num_uncovered_elements_;
373 for (
const SubsetIndex impacted_subset : rows[element]) {
374 --num_free_elements_[impacted_subset];
376 }
else if (update_redundancy_info && coverage_[element] == 1) {
378 for (
const SubsetIndex impacted_subset : rows[element]) {
379 --num_non_overcovered_elements_[impacted_subset];
380 if (num_non_overcovered_elements_[impacted_subset] == 0) {
384 DCHECK(!is_redundant_[impacted_subset]);
385 if (is_selected_[impacted_subset]) {
386 newly_removable_subsets_.push_back(impacted_subset);
388 is_redundant_[impacted_subset] =
true;
396 ++coverage_[element];
398 if (update_redundancy_info) {
399 if (is_redundant_[subset]) {
400 newly_removable_subsets_.push_back(subset);
402 newly_non_removable_subsets_.push_back(subset);
405 DCHECK_EQ(num_free_elements_[subset], 0);
414 if (!is_selected_[subset])
return false;
416 const bool update_redundancy_info = target_consistency >= CL::kRedundancy;
417 if (update_redundancy_info) {
420 consistency_level_ = std::min(consistency_level_, target_consistency);
421 DVLOG(1) <<
"Deselecting subset " << subset;
423 DCHECK(is_selected_[subset]);
425 is_selected_[subset] =
false;
427 cost_ -= subset_costs[subset];
431 if (target_consistency == CL::kCostAndCoverage) {
432 for (
const ElementIndex element : columns[subset]) {
433 --coverage_[element];
439 DCHECK_EQ(num_free_elements_[subset], 0);
440 for (
const ElementIndex element : columns[subset]) {
443 --coverage_[element];
444 if (coverage_[element] == 0) {
446 ++num_uncovered_elements_;
447 for (
const SubsetIndex impacted_subset : rows[element]) {
448 ++num_free_elements_[impacted_subset];
450 }
else if (update_redundancy_info && coverage_[element] == 1) {
452 for (
const SubsetIndex impacted_subset : rows[element]) {
453 if (num_non_overcovered_elements_[impacted_subset] == 0) {
456 DCHECK(is_redundant_[impacted_subset]);
457 if (is_selected_[impacted_subset]) {
458 newly_non_removable_subsets_.push_back(impacted_subset);
460 is_redundant_[impacted_subset] =
false;
462 ++num_non_overcovered_elements_[impacted_subset];
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());
481 lower_bound = std::min(model_->subset_costs()[subset], lower_bound);
483 message.set_cost(cost_);
484 message.set_cost_lower_bound(lower_bound);
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;
static bool AlmostEquals(const T x, const T y)
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.
void ClearTrace()
Clears the trace.
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.
BaseInt num_elements() const
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.
BaseInt num_subsets() const
In SWIG mode, we don't want anything besides these top-level includes.
util_intops::StrongVector< SubsetIndex, Cost > SubsetCostVector
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
util_intops::StrongVector< ElementIndex, BaseInt > ElementToIntVector
util_intops::StrongVector< SubsetIndex, bool > SubsetBoolVector
util_intops::StrongVector< SubsetIndex, SparseColumn > SparseColumnView
Views of the sparse vectors.
double Cost
Basic non-strict type for cost. The speed penalty for using double is ~2%.
util_intops::StrongVector< ElementIndex, SparseRow > SparseRowView
trees with all degrees equal w the current value of w