14#ifndef OR_TOOLS_SET_COVER_SET_COVER_MODEL_H_
15#define OR_TOOLS_SET_COVER_SET_COVER_MODEL_H_
21#include "absl/log/check.h"
22#include "absl/strings/string_view.h"
23#include "absl/time/time.h"
24#include "absl/types/span.h"
28#include "ortools/set_cover/set_cover.pb.h"
66 row_view_is_valid_(false),
67 elements_in_subsets_are_sorted_(false),
70 is_unicost_valid_(false),
75 std::string
name()
const {
return name_; }
105 bool IsEmpty()
const {
return rows_.empty() || columns_.empty(); }
114 CHECK_NE(
this,
nullptr);
129 BaseInt num_singleton_columns = 0;
131 if (column.size() == 1) {
132 ++num_singleton_columns;
135 return num_singleton_columns;
141 BaseInt num_singleton_rows = 0;
143 if (row.size() == 1) {
144 ++num_singleton_rows;
147 return num_singleton_rows;
156 if (is_unicost_valid_) {
160 for (
const Cost cost : subset_costs_) {
166 is_unicost_valid_ =
true;
175 DCHECK(row_view_is_valid_);
184 return util_intops::StrongIntRange<SubsetIndex>(SubsetIndex(num_subsets_));
188 return util_intops::StrongIntRange<ElementIndex>(
189 ElementIndex(num_elements_));
193 std::vector<SubsetIndex>
all_subsets()
const {
return all_subsets_; }
199 return create_sparse_row_view_duration_;
203 return compute_sparse_row_view_using_slices_duration_;
250 SubsetIndex end_subset);
255 absl::Span<const SubsetIndex> partition_points);
261 absl::Span<const SparseRowView> row_slices);
293 std::string
ToString(absl::string_view sep)
const;
310 std::string
ToString(absl::string_view sep)
const;
343 void UpdateAllSubsetsList();
356 int64_t num_nonzeros_;
359 bool row_view_is_valid_;
362 bool elements_in_subsets_are_sorted_;
371 bool is_unicost_valid_;
375 absl::Duration create_sparse_row_view_duration_;
378 absl::Duration compute_sparse_row_view_using_slices_duration_;
381 absl::Duration generation_duration_;
385 absl::Duration feasibility_duration_;
408 std::vector<SubsetIndex> all_subsets_;
421 SubsetIndex seed_subset,
bool at_end =
false)
423 seed_subset_(seed_subset),
424 seed_column_(model_.columns()[seed_subset]),
425 seed_column_size_(ColumnEntryIndex(seed_column_.size())),
426 intersecting_subset_(0),
428 rows_(model_.rows()),
435 DCHECK(model_.row_view_is_valid());
437 element_entry_ = seed_column_size_;
440 for (; element_entry_ < seed_column_size_; ++element_entry_) {
441 const ElementIndex current_element = seed_column_[element_entry_];
442 const SparseRow& current_row = rows_[current_element];
443 const RowEntryIndex current_row_size = RowEntryIndex(current_row.size());
444 for (; subset_entry_ < current_row_size; ++subset_entry_) {
445 if (intersecting_subset_ == seed_subset_)
continue;
446 intersecting_subset_ = current_row[subset_entry_];
449 subset_entry_ = RowEntryIndex(0);
454 bool at_end()
const {
return element_entry_ == seed_column_size_; }
457 SubsetIndex
operator*()
const {
return intersecting_subset_; }
461 return element_entry_ != other.element_entry_ ||
462 subset_entry_ != other.subset_entry_ ||
463 seed_subset_ != other.seed_subset_;
468 DCHECK(!
at_end()) <<
"element_entry_ = " << element_entry_
469 <<
" subset_entry_ = " << subset_entry_
470 <<
" seed_column_size_ = " << seed_column_size_;
471 if (subset_seen_.empty()) {
472 subset_seen_.resize(model_.num_subsets(),
false);
473 subset_seen_[seed_subset_] =
true;
475 subset_seen_[intersecting_subset_] =
true;
476 for (; element_entry_ < seed_column_size_; ++element_entry_) {
477 const ElementIndex current_element = seed_column_[element_entry_];
478 const SparseRow& current_row = rows_[current_element];
479 const RowEntryIndex current_row_size = RowEntryIndex(current_row.size());
480 for (; subset_entry_ < current_row_size; ++subset_entry_) {
481 intersecting_subset_ = current_row[subset_entry_];
482 if (!subset_seen_[intersecting_subset_]) {
486 subset_entry_ = RowEntryIndex(0);
496 SubsetIndex seed_subset_;
502 ColumnEntryIndex seed_column_size_;
505 SubsetIndex intersecting_subset_;
508 ColumnEntryIndex element_entry_;
511 RowEntryIndex subset_entry_;
529 : model_(model), seed_subset_(seed_subset) {}
550 SubsetIndex seed_subset_;
bool at_end() const
Returns (true) whether the iterator is at the end.
SubsetIndex operator*() const
Returns the intersecting subset.
IntersectingSubsetsIterator & operator++()
Advances the iterator to the next intersecting subset.
bool operator!=(const IntersectingSubsetsIterator &other) const
Disequality operator.
IntersectingSubsetsIterator(const SetCoverModel &model, SubsetIndex seed_subset, bool at_end=false)
const_iterator begin() const
const_iterator end() const
IntersectingSubsetsIterator iterator
IntersectingSubsetsRange(const SetCoverModel &model, SubsetIndex seed_subset)
IntersectingSubsetsIterator const_iterator
Main class for describing a weighted set-covering problem.
void ImportModelFromProto(const SetCoverProto &message)
Imports the model from a SetCoverProto.
SparseRowView ComputeSparseRowViewUsingSlices()
Stats ComputeCostStats() const
Computes basic statistics on costs and returns a Stats structure.
std::string ToString(absl::string_view sep) const
Returns a string representation of the model, using the given separator.
double FillRate() const
Returns the fill rate of the matrix.
static SetCoverModel GenerateRandomModelFrom(const SetCoverModel &seed_model, BaseInt num_elements, BaseInt num_subsets, double row_scale, double column_scale, double cost_scale)
void ResizeNumSubsets(BaseInt num_subsets)
void ReserveNumElementsInSubset(BaseInt num_elements, BaseInt subset)
Reserves num_elements rows in the column indexed by subset.
absl::Duration create_sparse_row_view_duration() const
std::vector< int64_t > ComputeRowDeciles() const
Computes deciles on rows and returns a vector of deciles.
SetCoverModel(const absl::string_view name="SetCoverModel")
Constructs an empty weighted set-covering problem.
std::vector< SubsetIndex > ComputeSliceIndices(int num_partitions)
util_intops::StrongIntRange< ElementIndex > ElementRange() const
void AddElementToLastSubset(BaseInt element)
void AddEmptySubset(Cost cost)
const SparseRowView & rows() const
Row view of the set covering problem.
std::vector< SparseRowView > CutSparseRowViewInSlices(absl::Span< const SubsetIndex > partition_points)
Stats ComputeRowStats() const
Computes basic statistics on rows and returns a Stats structure.
int64_t num_nonzeros() const
Current number of nonzeros in the matrix.
BaseInt ComputeNumSingletonRows() const
BaseInt num_elements() const
void SetName(const absl::string_view name)
void SortElementsInSubsets()
util_intops::StrongIntRange< SubsetIndex > SubsetRange() const
Access to the ranges of subsets and elements.
std::string ToVerboseString(absl::string_view sep) const
absl::Duration compute_sparse_row_view_using_slices_duration() const
Stats ComputeColumnDeltaSizeStats() const
SparseRowView ComputeSparseRowViewSlice(SubsetIndex begin_subset, SubsetIndex end_subset)
bool ComputeFeasibility()
void AddElementToSubset(BaseInt element, BaseInt subset)
Stats ComputeRowDeltaSizeStats() const
void SetSubsetCost(BaseInt subset, Cost cost)
absl::Duration generation_duration() const
Accessors to the durations of the different stages of the model creation.
bool row_view_is_valid() const
Returns true if rows_ and columns_ represent the same problem.
const SubsetCostVector & subset_costs() const
Vector of costs for each subset.
void CreateSparseRowView()
SetCoverProto ExportModelAsProto() const
BaseInt ComputeNumSingletonColumns() const
Stats ComputeColumnStats() const
Computes basic statistics on columns and returns a Stats structure.
std::vector< int64_t > ComputeColumnDeciles() const
Computes deciles on columns and returns a vector of deciles.
const SparseColumnView & columns() const
Column view of the set covering problem.
BaseInt num_subsets() const
SparseRowView ReduceSparseRowViewSlices(absl::Span< const SparseRowView > row_slices)
std::vector< SubsetIndex > all_subsets() const
Returns the list of indices for all the subsets in the model.
In SWIG mode, we don't want anything besides these top-level includes.
util_intops::StrongVector< RowEntryIndex, SubsetIndex > SparseRow
util_intops::StrongVector< SubsetIndex, Cost > SubsetCostVector
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< ColumnEntryIndex, ElementIndex > SparseColumn
util_intops::StrongVector< ElementIndex, SparseRow > SparseRowView
std::string DebugString() const
std::string ToVerboseString(absl::string_view sep) const
std::string ToString(absl::string_view sep) const
Returns a string representation of the stats, using the given separator.