24#include "absl/base/casts.h"
25#include "absl/log/check.h"
26#include "absl/log/log.h"
27#include "absl/numeric/bits.h"
28#include "absl/random/distributions.h"
29#include "absl/random/random.h"
30#include "absl/types/span.h"
41static constexpr double kInfinity = std::numeric_limits<float>::infinity();
52 absl::Span<const SubsetIndex> focus) {
56 for (
const SubsetIndex subset : focus) {
57 choices[subset] =
true;
67 absl::Span<const SubsetIndex> focus) {
70 std::vector<SubsetIndex> shuffled(focus.begin(), focus.end());
71 std::shuffle(shuffled.begin(), shuffled.end(), absl::BitGen());
72 for (
const SubsetIndex subset : shuffled) {
73 if (
inv()->is_selected()[subset])
continue;
74 if (
inv()->num_free_elements()[subset] != 0) {
75 inv()->
Select(subset, CL::kFreeAndUncovered);
79 DCHECK(
inv()->CheckConsistency(CL::kFreeAndUncovered));
86 absl::Span<const SubsetIndex> focus) {
88 DCHECK(
inv()->CheckConsistency(CL::kCostAndCoverage));
91 std::vector<std::pair<float, SubsetIndex::ValueType>> subset_priorities;
92 DVLOG(1) <<
"focus.size(): " << focus.size();
93 subset_priorities.reserve(focus.size());
95 for (
const SubsetIndex subset : focus) {
96 if (!
inv()->is_selected()[subset] &&
97 inv()->num_free_elements()[subset] != 0) {
100 subset_priorities.push_back({priority, subset.value()});
112 std::vector<SubsetIndex> subsets_to_remove;
113 subsets_to_remove.reserve(focus.size());
114 while (!pq.
IsEmpty() ||
inv()->num_uncovered_elements() > 0) {
115 VLOG_EVERY_N_SEC(1, 5) <<
"Queue size: " << pq.
heap_size()
116 <<
", #uncovered elements: "
118 const SubsetIndex best_subset(pq.
TopIndex());
120 inv()->
Select(best_subset, CL::kFreeAndUncovered);
122 subset_seen[best_subset] =
true;
123 subsets_to_remove.push_back(best_subset);
124 for (
const ElementIndex element : colunms[best_subset]) {
125 for (
const SubsetIndex subset : rows[element]) {
126 if (subset_seen[subset])
continue;
127 subset_seen[subset] =
true;
128 const BaseInt marginal_impact(
inv()->num_free_elements()[subset]);
129 if (marginal_impact > 0) {
130 const float priority = marginal_impact / costs[subset];
131 pq.
Update({priority, subset.value()});
133 pq.
Remove(subset.value());
135 subsets_to_remove.push_back(subset);
138 for (
const SubsetIndex subset : subsets_to_remove) {
139 subset_seen[subset] =
false;
141 subsets_to_remove.clear();
142 DVLOG(1) <<
"Cost = " <<
inv()->
cost()
147 DCHECK(
inv()->CheckConsistency(CL::kFreeAndUncovered));
153class ComputationUsefulnessStats {
160 is_active_(is_active),
161 num_ratio_computations_(),
162 num_useless_computations_(),
165 BaseInt num_subsets = inv_->model()->num_subsets();
166 num_ratio_computations_.assign(num_subsets, 0);
167 num_useless_computations_.assign(num_subsets, 0);
173 void Update(SubsetIndex subset,
BaseInt new_num_free_elements) {
175 if (new_num_free_elements == num_free_elements_[subset]) {
176 ++num_useless_computations_[subset];
178 ++num_ratio_computations_[subset];
179 num_free_elements_[subset] = new_num_free_elements;
186 BaseInt num_subsets_considered = 0;
188 BaseInt num_wasted_ratio_updates = 0;
189 for (
const SubsetIndex subset : inv_->model()->SubsetRange()) {
190 if (num_ratio_computations_[subset] > 0) {
191 ++num_subsets_considered;
192 if (num_ratio_computations_[subset] > 1) {
193 num_ratio_updates += num_ratio_computations_[subset] - 1;
196 num_wasted_ratio_updates += num_useless_computations_[subset];
198 LOG(INFO) <<
"num_subsets_considered = " << num_subsets_considered;
199 LOG(INFO) <<
"num_ratio_updates = " << num_ratio_updates;
200 LOG(INFO) <<
"num_wasted_ratio_updates = " << num_wasted_ratio_updates;
206 const SetCoverInvariant* inv_;
243uint32_t RawBits(uint32_t x) {
return x; }
244uint32_t RawBits(
int x) {
return absl::bit_cast<uint32_t>(x); }
245uint32_t RawBits(
float x) {
return absl::bit_cast<uint32_t>(x); }
246uint64_t RawBits(uint64_t x) {
return x; }
247uint64_t RawBits(int64_t x) {
return absl::bit_cast<uint64_t>(x); }
248uint64_t RawBits(
double x) {
return absl::bit_cast<uint64_t>(x); }
250inline uint32_t Bucket(uint32_t x, uint32_t shift, uint32_t radix) {
251 DCHECK_EQ(0, radix & (radix - 1));
254 return (RawBits(x) >> shift) & (radix - 1);
258int NumBitsToRepresent(T value) {
259 DCHECK_LE(absl::countl_zero(RawBits(value)),
sizeof(T) * CHAR_BIT);
260 return sizeof(
T) * CHAR_BIT - absl::countl_zero(RawBits(value));
263template <
typename Key,
typename Counter>
264void UpdateCounters(uint32_t radix,
int shift, std::vector<Key>& keys,
265 std::vector<Counter>& counts) {
266 std::fill(counts.begin(), counts.end(), 0);
267 DCHECK_EQ(counts[0], 0);
268 DCHECK_EQ(0, radix & (radix - 1));
269 const auto num_keys = keys.size();
270 for (int64_t i = 0;
i < num_keys; ++
i) {
271 ++counts[Bucket(keys[i], shift, radix)];
275 for (uint64_t i = 1;
i < radix; ++
i) {
276 counts[
i] += counts[
i - 1];
280template <
typename Key,
typename Payload,
typename Counter>
281void IncreasingCountingSort(uint32_t radix,
int shift, std::vector<Key>& keys,
282 std::vector<Payload>& payloads,
283 std::vector<Key>& scratch_keys,
284 std::vector<Payload>& scratch_payloads,
285 std::vector<Counter>& counts) {
286 DCHECK_EQ(0, radix & (radix - 1));
287 UpdateCounters(radix, shift, keys, counts);
288 const auto num_keys = keys.size();
290 for (int64_t i = num_keys - 1;
i >= 0; --
i) {
291 Counter
c = --counts[Bucket(keys[i], shift, radix)];
292 scratch_keys[
c] = keys[
i];
293 scratch_payloads[
c] = payloads[
i];
295 std::swap(keys, scratch_keys);
296 std::swap(payloads, scratch_payloads);
300template <
typename Key,
typename Payload>
301void RadixSort(
int radix_log, std::vector<Key>& keys,
302 std::vector<Payload>& payloads, Key , Key max_key) {
306 const int range_log = internal::NumBitsToRepresent(max_key);
307 DCHECK_EQ(internal::NumBitsToRepresent(0), 0);
308 DCHECK_LE(internal::NumBitsToRepresent(std::numeric_limits<Key>::max()),
309 std::numeric_limits<Key>::digits);
310 const int radix = 1 << radix_log;
311 std::vector<uint32_t> counters(radix, 0);
312 std::vector<Key> scratch_keys(keys.size());
313 std::vector<Payload> scratch_payloads(payloads.size());
314 for (
int shift = 0; shift < range_log; shift += radix_log) {
315 DCHECK_LE(1 << shift, max_key);
316 internal::IncreasingCountingSort(radix, shift, keys, payloads, scratch_keys,
317 scratch_payloads, counters);
323std::vector<ElementIndex> GetUncoveredElementsSortedByDegree(
325 const BaseInt num_elements = inv->model()->num_elements();
326 std::vector<ElementIndex> degree_sorted_elements;
327 degree_sorted_elements.reserve(num_elements);
328 std::vector<BaseInt> keys;
329 keys.reserve(num_elements);
332 for (
const ElementIndex element : inv->model()->ElementRange()) {
334 if (inv->coverage()[element] != 0)
continue;
335 degree_sorted_elements.push_back(element);
336 const BaseInt size = rows[element].size();
337 max_degree = std::max(max_degree, size);
338 keys.push_back(size);
340 RadixSort(11, keys, degree_sorted_elements, 1, max_degree);
343 for (
const auto key : keys) {
344 DCHECK_LE(prev_key, key);
348 return degree_sorted_elements;
357 return c1 * n2 - n1 * c2;
369 DVLOG(1) <<
"Entering ElementDegreeSolutionGenerator::NextSolution";
372 std::vector<ElementIndex> degree_sorted_elements =
373 GetUncoveredElementsSortedByDegree(
inv());
374 ComputationUsefulnessStats stats(
inv(),
false);
377 for (
const ElementIndex element : degree_sorted_elements) {
379 if (
inv()->coverage()[element] != 0)
continue;
380 SubsetIndex best_subset(-1);
381 Cost best_subset_cost = 0.0;
382 BaseInt best_subset_num_free_elts = 0;
383 for (
const SubsetIndex subset : rows[element]) {
384 if (!in_focus[subset])
continue;
386 stats.Update(subset, num_free_elements);
387 const Cost det = Determinant(costs[subset], num_free_elements,
388 best_subset_cost, best_subset_num_free_elts);
397 (det == 0 && num_free_elements > best_subset_num_free_elts)) {
398 best_subset = subset;
399 best_subset_cost = costs[subset];
400 best_subset_num_free_elts = num_free_elements;
403 if (best_subset.value() == -1) {
404 LOG(WARNING) <<
"Best subset not found. Algorithmic error or invalid "
408 DCHECK_NE(best_subset.value(), -1);
409 inv()->
Select(best_subset, CL::kFreeAndUncovered);
410 DVLOG(1) <<
"Cost = " <<
inv()->
cost()
415 DCHECK(
inv()->CheckConsistency(CL::kFreeAndUncovered));
428 DVLOG(1) <<
"Entering LazyElementDegreeSolutionGenerator::NextSolution";
429 DCHECK(
inv()->CheckConsistency(CL::kCostAndCoverage));
431 std::vector<ElementIndex> degree_sorted_elements =
432 GetUncoveredElementsSortedByDegree(
inv());
435 ComputationUsefulnessStats stats(
inv(),
false);
437 for (
const ElementIndex element : degree_sorted_elements) {
439 if (
inv()->coverage()[element] != 0)
continue;
440 SubsetIndex best_subset(-1);
441 Cost best_subset_cost = 0.0;
442 BaseInt best_subset_num_free_elts = 0;
443 for (
const SubsetIndex subset : rows[element]) {
444 if (!in_focus[subset])
continue;
445 const Cost filtering_det =
446 Determinant(costs[subset], columns[subset].size(), best_subset_cost,
447 best_subset_num_free_elts);
450 if (filtering_det > 0)
continue;
452 stats.Update(subset, num_free_elements);
453 const Cost det = Determinant(costs[subset], num_free_elements,
454 best_subset_cost, best_subset_num_free_elts);
457 (det == 0 && num_free_elements > best_subset_num_free_elts)) {
458 best_subset = subset;
459 best_subset_cost = costs[subset];
460 best_subset_num_free_elts = num_free_elements;
463 DCHECK_NE(best_subset, SubsetIndex(-1));
464 inv()->
Select(best_subset, CL::kCostAndCoverage);
465 DVLOG(1) <<
"Cost = " <<
inv()->
cost()
468 DCHECK(
inv()->CheckConsistency(CL::kCostAndCoverage));
478 DCHECK(
inv()->CheckConsistency(CL::kCostAndCoverage));
480 DVLOG(1) <<
"Entering SteepestSearch::NextSolution, num_iterations = "
484 if (
inv()->num_uncovered_elements() != 0) {
491 std::vector<std::pair<float, SubsetIndex::ValueType>> subset_priorities;
492 subset_priorities.reserve(in_focus.size());
494 const SubsetIndex subset = decision.subset();
495 if (in_focus[subset] &&
inv()->is_selected()[subset] &&
496 inv()->ComputeIsRedundant(subset)) {
497 const float delta_per_element = costs[subset];
498 subset_priorities.push_back({delta_per_element, subset.value()});
501 DVLOG(1) <<
"subset_priorities.size(): " << subset_priorities.size();
504 for (
int iteration = 0; iteration < num_iterations && !pq.
IsEmpty();
506 const SubsetIndex best_subset(pq.
TopIndex());
508 DCHECK(
inv()->is_selected()[best_subset]);
509 DCHECK(
inv()->ComputeIsRedundant(best_subset));
510 DCHECK_GT(costs[best_subset], 0.0);
511 inv()->
Deselect(best_subset, CL::kFreeAndUncovered);
512 for (
const SubsetIndex subset :
514 if (!
inv()->ComputeIsRedundant(subset)) {
515 pq.
Remove(subset.value());
518 DVLOG(1) <<
"Cost = " <<
inv()->
cost();
522 DCHECK_EQ(
inv()->num_uncovered_elements(), 0);
523 DCHECK(
inv()->CheckConsistency(CL::kFreeAndUncovered));
532 DCHECK(
inv()->CheckConsistency(CL::kCostAndCoverage));
533 DVLOG(1) <<
"Entering LazySteepestSearch::NextSolution, num_iterations = "
536 std::vector<Cost> selected_costs;
537 selected_costs.reserve(num_selected_subsets);
543 if (in_focus[decision.subset()]) {
544 selected_costs.push_back(costs[decision.subset()]);
547 std::vector<BaseInt> cost_permutation(selected_costs.size());
548 std::iota(cost_permutation.begin(), cost_permutation.end(), 0);
550 std::sort(cost_permutation.begin(), cost_permutation.end(),
552 if (selected_costs[i] == selected_costs[j]) {
555 return selected_costs[i] > selected_costs[j];
557 std::vector<SubsetIndex> cost_sorted_subsets;
558 cost_sorted_subsets.reserve(num_selected_subsets);
559 for (
const BaseInt i : cost_permutation) {
560 cost_sorted_subsets.push_back(inv()->trace()[i].subset());
562 for (
const SubsetIndex subset : cost_sorted_subsets) {
574 if (inv()->is_selected()[subset] && inv()->ComputeIsRedundant(subset)) {
575 inv()->Deselect(subset, CL::kCostAndCoverage);
578 inv()->CompressTrace();
579 DCHECK(inv()->CheckConsistency(CL::kCostAndCoverage));
589 augmented_costs_ = subset_costs;
590 utilities_ = subset_costs;
596 return absl::Bernoulli(absl::BitGen(), 0.5);
600void GuidedTabuSearch::UpdatePenalties(absl::Span<const SubsetIndex> focus) {
602 Cost max_utility = -1.0;
603 for (
const SubsetIndex subset : focus) {
604 if (inv()->is_selected()[subset]) {
605 max_utility = std::max(max_utility, utilities_[subset]);
608 const double epsilon_utility = epsilon_ * max_utility;
609 for (
const SubsetIndex subset : focus) {
610 if (inv()->is_selected()[subset]) {
611 const double utility = utilities_[subset];
612 if ((max_utility - utility <= epsilon_utility) && FlipCoin()) {
613 ++times_penalized_[subset];
614 const int times_penalized = times_penalized_[subset];
616 subset_costs[subset];
617 utilities_[subset] = cost / (1 + times_penalized);
618 augmented_costs_[subset] =
619 cost * (1 + penalty_factor_ * times_penalized);
628 DCHECK(
inv()->CheckConsistency(CL::kFreeAndUncovered));
629 DVLOG(1) <<
"Entering GuidedTabuSearch::NextSolution, num_iterations = "
632 Cost best_cost =
inv()->cost();
634 Cost augmented_cost =
635 std::accumulate(augmented_costs_.begin(), augmented_costs_.end(), 0.0);
637 for (
int iteration = 0; iteration < num_iterations; ++iteration) {
638 if (
inv()->trace().size() > 2 * trace_size) {
639 inv()->CompressTrace();
640 trace_size =
inv()->trace().size();
644 for (
const SubsetIndex subset : focus) {
645 const Cost delta = augmented_costs_[subset];
646 DVLOG(1) <<
"Subset, " << subset.value() <<
", at ,"
647 <<
inv()->is_selected()[subset] <<
", delta =, " << delta
648 <<
", best_delta =, " << best_delta;
649 if (
inv()->is_selected()[subset]) {
652 if (-delta < best_delta &&
654 inv()->ComputeIsRedundant(subset) &&
656 (!tabu_list_.Contains(subset) ||
657 inv()->
cost() - subset_costs[subset] < best_cost)) {
659 best_subset = subset;
663 if (delta < best_delta) {
666 if (!tabu_list_.Contains(subset)) {
668 best_subset = subset;
674 inv()->LoadSolution(best_choices);
677 DVLOG(1) <<
"Best subset, " << best_subset.value() <<
", at ,"
678 <<
inv()->is_selected()[best_subset] <<
", best_delta = ,"
681 UpdatePenalties(focus);
682 tabu_list_.Add(best_subset);
683 if (
inv()->is_selected()[best_subset]) {
684 inv()->Deselect(best_subset, CL::kFreeAndUncovered);
686 inv()->Select(best_subset, CL::kFreeAndUncovered);
690 std::accumulate(augmented_costs_.begin(), augmented_costs_.end(), 0.0);
692 DVLOG(1) <<
"Iteration, " << iteration <<
", current cost = ,"
693 <<
inv()->cost() <<
", best cost = ," << best_cost
694 <<
", penalized cost = ," << augmented_cost;
695 if (
inv()->
cost() < best_cost) {
696 VLOG(1) <<
"Updated best cost, " <<
"Iteration, " << iteration
697 <<
", current cost = ," <<
inv()->cost() <<
", best cost = ,"
698 << best_cost <<
", penalized cost = ," << augmented_cost;
699 best_cost =
inv()->cost();
700 best_choices =
inv()->is_selected();
703 inv()->LoadSolution(best_choices);
704 inv()->CompressTrace();
705 DCHECK(
inv()->CheckConsistency(CL::kFreeAndUncovered));
710void GuidedLocalSearch::Initialize() {
712 penalties_.assign(columns.size(), 0);
713 penalization_factor_ = alpha_ *
inv()->cost() * 1.0 / (columns.size());
715 const SubsetIndex subset = decision.subset();
716 if (
inv()->is_selected()[subset]) {
717 utility_heap_.Insert({
static_cast<float>(
model()->subset_costs()[subset] /
718 (1 + penalties_[subset])),
724Cost GuidedLocalSearch::ComputeDelta(SubsetIndex subset)
const {
725 const float delta = (penalization_factor_ * penalties_[subset] +
726 model()->subset_costs()[subset]);
727 if (inv()->is_selected()[subset] && inv()->ComputeIsRedundant(subset)) {
729 }
else if (!inv()->is_selected()[subset]) {
735bool GuidedLocalSearch::NextSolution(absl::Span<const SubsetIndex> focus) {
738 inv()->Recompute(CL::kRedundancy);
739 Cost best_cost =
inv()->cost();
742 for (
const SubsetIndex& subset : focus) {
743 const float delta = ComputeDelta(subset);
745 priority_heap_.Insert({delta, subset.value()});
749 for (
int iteration = 0;
750 !priority_heap_.IsEmpty() && iteration < num_iterations; ++iteration) {
753 const SubsetIndex best_subset(priority_heap_.TopIndex());
754 if (
inv()->is_selected()[best_subset]) {
755 utility_heap_.Insert({0, best_subset.value()});
756 inv()->Deselect(best_subset, CL::kRedundancy);
758 utility_heap_.Insert(
759 {
static_cast<float>(
model()->subset_costs()[best_subset] /
760 (1 + penalties_[best_subset])),
761 best_subset.value()});
762 inv()->Select(best_subset, CL::kRedundancy);
764 DCHECK(!utility_heap_.IsEmpty());
768 const SubsetIndex penalized_subset(utility_heap_.TopIndex());
770 ++penalties_[penalized_subset];
771 utility_heap_.Insert(
772 {
static_cast<float>(
model()->subset_costs()[penalized_subset] /
773 (1 + penalties_[penalized_subset])),
774 penalized_subset.value()});
775 DCHECK(!utility_heap_.IsEmpty());
778 for (
const SubsetIndex subset :
inv()->newly_removable_subsets()) {
779 const float delta_selected = (penalization_factor_ * penalties_[subset] +
780 model()->subset_costs()[subset]);
781 priority_heap_.Insert({delta_selected, subset.value()});
783 DCHECK(!priority_heap_.IsEmpty());
785 for (
const SubsetIndex subset : {penalized_subset, best_subset}) {
786 const float delta = ComputeDelta(subset);
788 priority_heap_.Insert({delta, subset.value()});
791 DCHECK(!priority_heap_.IsEmpty());
796 for (
const SubsetIndex subset :
inv()->newly_non_removable_subsets()) {
797 priority_heap_.Remove(subset.value());
800 if (
inv()->
cost() < best_cost) {
801 best_cost =
inv()->cost();
802 best_choices =
inv()->is_selected();
805 inv()->LoadSolution(best_choices);
808 for (
const SubsetIndex& subset : focus) {
809 if (
inv()->is_selected()[subset] &&
inv()->ComputeIsRedundant(subset))
810 inv()->Deselect(subset, CL::kRedundancy);
812 DCHECK_EQ(
inv()->num_uncovered_elements(), 0);
817void SampleSubsets(std::vector<SubsetIndex>* list,
BaseInt num_subsets) {
818 num_subsets = std::min<BaseInt>(num_subsets, list->size());
819 CHECK_GE(num_subsets, 0);
820 std::shuffle(list->begin(), list->end(), absl::BitGen());
821 list->resize(num_subsets);
833 num_subsets_to_choose =
834 std::min<BaseInt>(num_subsets_to_choose, focus.size());
835 CHECK_GE(num_subsets_to_choose, 0);
836 std::vector<SubsetIndex> chosen_indices;
837 for (
const SubsetIndex subset : focus) {
839 chosen_indices.push_back(subset);
842 SampleSubsets(&chosen_indices, num_subsets_to_choose);
844 for (
const SubsetIndex subset : chosen_indices) {
847 inv->
Deselect(subset, CL::kCostAndCoverage);
850 for (
const SubsetIndex connected_subset :
854 inv->
Deselect(connected_subset, CL::kCostAndCoverage);
859 if (num_deselected > num_subsets_to_choose)
break;
861 return chosen_indices;
871 absl::Span<const SubsetIndex> focus,
BaseInt max_num_subsets,
874 std::vector<SubsetIndex> sampled_subsets;
884 if (coverage[element] <= 1)
continue;
885 for (
const SubsetIndex subset : rows[element]) {
886 if (inv->
is_selected()[subset] && !subset_is_collected[subset]) {
887 subset_is_collected[subset] =
true;
895 for (
const SubsetIndex subset : focus) {
896 if (subset_is_collected[subset]) {
897 sampled_subsets.push_back(subset);
903 std::shuffle(sampled_subsets.begin(), sampled_subsets.end(), absl::BitGen());
904 sampled_subsets.resize(
905 std::min<BaseInt>(sampled_subsets.size(), max_num_subsets));
909 for (
const SubsetIndex subset : sampled_subsets) {
910 inv->
Deselect(subset, CL::kCostAndCoverage);
912 return sampled_subsets;
void Update(Aggregate element)
Change the value of an element.
bool IsEmpty() const
True iff the heap is empty.
HeapIndex heap_size() const
Returns the number of elements in the heap.
bool NextSolution() final
Virtual methods that must be implemented by derived classes.
bool NextSolution() final
Virtual methods that must be implemented by derived classes.
void Initialize()
Initializes the Guided Tabu Search algorithm.
bool NextSolution(absl::Span< const SubsetIndex > focus) final
bool NextSolution() final
Virtual methods that must be implemented by derived classes.
bool NextSolution() final
Virtual methods that must be implemented by derived classes.
bool NextSolution() final
Virtual methods that must be implemented by derived classes.
A helper class used to store the decisions made during a search.
void Recompute(ConsistencyLevel target_consistency)
Recomputes the invariant to the given consistency level.
const SubsetToIntVector & num_free_elements() const
const std::vector< SetCoverDecision > & trace() const
Returns the vector of the decisions which have led to the current solution.
void LoadSolution(const SubsetBoolVector &solution)
Loads the solution and recomputes the data in the invariant.
bool Deselect(SubsetIndex subset, ConsistencyLevel consistency)
const SubsetBoolVector & is_selected() const
Returns the subset assignment vector.
SetCoverModel * model() const
Returns the weighted set covering model to which the state applies.
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.
Cost cost() const
Returns the cost of current solution.
BaseInt num_uncovered_elements() const
Returns the number of uncovered elements.
util_intops::StrongIntRange< ElementIndex > ElementRange() const
const SparseRowView & rows() const
Row view of the set covering problem.
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
std::vector< SubsetIndex > all_subsets() const
Returns the list of indices for all the subsets in the model.
SetCoverInvariant::ConsistencyLevel consistency_level_
The consistency needed by the solution generator.
BaseInt num_subsets() const
int64_t max_iterations() const
Returns the maximum number of iterations.
absl::Duration run_time_
run_time_ is an abstract duration for the time spent in NextSolution().
SetCoverModel * model() const
Accessors.
SetCoverInvariant * inv() const
Cost cost() const
Returns the current cost of the solution in the invariant.
bool CheckInvariantConsistency() const
bool NextSolution() final
Virtual methods that must be implemented by derived classes.
bool NextSolution() final
Virtual methods that must be implemented by derived classes.
constexpr Fractional kInfinity
Infinity for type Fractional.
End of the interface. Below is the implementation.
dual_gradient T(y - `dual_solution`) class DiagonalTrustRegionProblemFromQp
In SWIG mode, we don't want anything besides these top-level includes.
constexpr SubsetIndex kNotFound(-1)
static constexpr double kInfinity
util_intops::StrongVector< SubsetIndex, Cost > SubsetCostVector
SetCoverInvariant::ConsistencyLevel CL
std::vector< SubsetIndex > ClearRandomSubsets(BaseInt num_subsets, SetCoverInvariant *inv)
The consistency level is maintained up to kCostAndCoverage.
util_intops::StrongVector< SubsetIndex, BaseInt > SubsetToIntVector
static constexpr Cost kMaxPossibleCost
std::vector< SubsetIndex > ClearMostCoveredElements(BaseInt max_num_subsets, SetCoverInvariant *inv)
The consistency level is maintained up to kCostAndCoverage.
util_intops::StrongVector< ElementIndex, BaseInt > ElementToIntVector
util_intops::StrongVector< SubsetIndex, bool > SubsetBoolVector
void RadixSort(absl::Span< T > values, int num_bits=sizeof(T) *8)
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%.
num_free_elements_[subset]
util_intops::StrongVector< ElementIndex, SparseRow > SparseRowView
trees with all degrees equal w the current value of int max_iterations