Main class for describing a weighted set-covering problem. More...

#include <set_cover_model.h>

Inheritance diagram for operations_research::SetCoverModel:

Classes
struct	Stats

Public Member Functions
	SetCoverModel (const absl::string_view name="SetCoverModel")
	Constructs an empty weighted set-covering problem.
std::string	name () const
void	SetName (const absl::string_view name)
bool	IsEmpty () const
BaseInt	num_elements () const
BaseInt	num_subsets () const
int64_t	num_nonzeros () const
	Current number of nonzeros in the matrix.
double	FillRate () const
	Returns the fill rate of the matrix.
BaseInt	ComputeNumSingletonColumns () const
BaseInt	ComputeNumSingletonRows () const
const SubsetCostVector &	subset_costs () const
	Vector of costs for each subset.
bool	is_unicost ()
const SparseColumnView &	columns () const
	Column view of the set covering problem.
const SparseRowView &	rows () const
	Row view of the set covering problem.
bool	row_view_is_valid () const
	Returns true if rows_ and columns_ represent the same problem.
util_intops::StrongIntRange< SubsetIndex >	SubsetRange () const
	Access to the ranges of subsets and elements.
util_intops::StrongIntRange< ElementIndex >	ElementRange () const
std::vector< SubsetIndex >	all_subsets () const
	Returns the list of indices for all the subsets in the model.
absl::Duration	generation_duration () const
	Accessors to the durations of the different stages of the model creation.
absl::Duration	create_sparse_row_view_duration () const
absl::Duration	compute_sparse_row_view_using_slices_duration () const
void	AddEmptySubset (Cost cost)
void	AddElementToLastSubset (BaseInt element)
void	AddElementToLastSubset (ElementIndex element)
void	SetSubsetCost (BaseInt subset, Cost cost)
void	SetSubsetCost (SubsetIndex subset, Cost cost)
void	AddElementToSubset (BaseInt element, BaseInt subset)
void	AddElementToSubset (ElementIndex element, SubsetIndex subset)
void	SortElementsInSubsets ()
void	CreateSparseRowView ()
SparseRowView	ComputeSparseRowViewUsingSlices ()
std::vector< SubsetIndex >	ComputeSliceIndices (int num_partitions)
SparseRowView	ComputeSparseRowViewSlice (SubsetIndex begin_subset, SubsetIndex end_subset)
std::vector< SparseRowView >	CutSparseRowViewInSlices (absl::Span< const SubsetIndex > partition_points)
SparseRowView	ReduceSparseRowViewSlices (absl::Span< const SparseRowView > row_slices)
bool	ComputeFeasibility ()
void	ResizeNumSubsets (BaseInt num_subsets)
void	ResizeNumSubsets (SubsetIndex num_subsets)
void	ReserveNumElementsInSubset (BaseInt num_elements, BaseInt subset)
	Reserves num_elements rows in the column indexed by subset.
SetCoverProto	ExportModelAsProto () const
void	ImportModelFromProto (const SetCoverProto &message)
	Imports the model from a SetCoverProto.
std::string	ToVerboseString (absl::string_view sep) const
std::string	ToString (absl::string_view sep) const
	Returns a string representation of the model, using the given separator.
Stats	ComputeCostStats () const
	Computes basic statistics on costs and returns a Stats structure.
Stats	ComputeRowStats () const
	Computes basic statistics on rows and returns a Stats structure.
Stats	ComputeColumnStats () const
	Computes basic statistics on columns and returns a Stats structure.
std::vector< int64_t >	ComputeRowDeciles () const
	Computes deciles on rows and returns a vector of deciles.
std::vector< int64_t >	ComputeColumnDeciles () const
	Computes deciles on columns and returns a vector of deciles.
Stats	ComputeRowDeltaSizeStats () const
Stats	ComputeColumnDeltaSizeStats () const

Static Public Member Functions
static SetCoverModel	GenerateRandomModelFrom (const SetCoverModel &seed_model, BaseInt num_elements, BaseInt num_subsets, double row_scale, double column_scale, double cost_scale)

Detailed Description

Main class for describing a weighted set-covering problem.

Definition at line 58 of file set_cover_model.h.

Constructor & Destructor Documentation

◆ SetCoverModel()

operations_research::SetCoverModel::SetCoverModel ( const absl::string_view name = "SetCoverModel" )

inlineexplicit

Constructs an empty weighted set-covering problem.

Definition at line 61 of file set_cover_model.h.

Member Function Documentation

◆ AddElementToLastSubset() [1/2]

void operations_research::SetCoverModel::AddElementToLastSubset ( BaseInt element )

Adds an element to the last subset created. In matrix terms, this adds a 1 on row 'element' of the current last column of the matrix.

No need to update the list all_subsets_.

Definition at line 258 of file set_cover_model.cc.

◆ AddElementToLastSubset() [2/2]

void operations_research::SetCoverModel::AddElementToLastSubset ( ElementIndex element )

Definition at line 267 of file set_cover_model.cc.

◆ AddElementToSubset() [1/2]

void operations_research::SetCoverModel::AddElementToSubset	(	BaseInt	element,
		BaseInt	subset )

Adds 'element' to an already existing 'subset'. No check is done if element is already in the subset.

Definition at line 292 of file set_cover_model.cc.

◆ AddElementToSubset() [2/2]

void operations_research::SetCoverModel::AddElementToSubset	(	ElementIndex	element,
		SubsetIndex	subset )

Definition at line 306 of file set_cover_model.cc.

◆ AddEmptySubset()

void operations_research::SetCoverModel::AddEmptySubset ( Cost cost )

Adds an empty subset with a cost to the problem. In matrix terms, this adds a column to the matrix.

Todo: (user): refine the logic for is_unicost_ and is_unicost_valid_.

Definition at line 244 of file set_cover_model.cc.

◆ all_subsets()

std::vector< SubsetIndex > operations_research::SetCoverModel::all_subsets ( ) const

inline

Returns the list of indices for all the subsets in the model.

Definition at line 193 of file set_cover_model.h.

◆ columns()

const SparseColumnView & operations_research::SetCoverModel::columns ( ) const

inline

Column view of the set covering problem.

Definition at line 171 of file set_cover_model.h.

◆ compute_sparse_row_view_using_slices_duration()

absl::Duration operations_research::SetCoverModel::compute_sparse_row_view_using_slices_duration ( ) const

inline

Definition at line 202 of file set_cover_model.h.

◆ ComputeColumnDeciles()

std::vector< int64_t > operations_research::SetCoverModel::ComputeColumnDeciles ( ) const

Computes deciles on columns and returns a vector of deciles.

Definition at line 718 of file set_cover_model.cc.

◆ ComputeColumnDeltaSizeStats()

SetCoverModel::Stats operations_research::SetCoverModel::ComputeColumnDeltaSizeStats ( ) const

Definition at line 734 of file set_cover_model.cc.

◆ ComputeColumnStats()

SetCoverModel::Stats operations_research::SetCoverModel::ComputeColumnStats ( ) const

Computes basic statistics on columns and returns a Stats structure.

Definition at line 688 of file set_cover_model.cc.

◆ ComputeCostStats()

SetCoverModel::Stats operations_research::SetCoverModel::ComputeCostStats ( ) const

Computes basic statistics on costs and returns a Stats structure.

Definition at line 672 of file set_cover_model.cc.

◆ ComputeFeasibility()

bool operations_research::SetCoverModel::ComputeFeasibility ( )

Returns true if the problem is feasible, i.e. if the subsets cover all the elements. Could be const, but it updates the feasibility_duration_ field.

NOMUTANTS – column_index is only used for logging in debug mode.

NOMUTANTS – num_uncoverable_elements is only used for logging.

Definition at line 472 of file set_cover_model.cc.

◆ ComputeNumSingletonColumns()

BaseInt operations_research::SetCoverModel::ComputeNumSingletonColumns ( ) const

inline

Computes the number of singleton columns in the model, i.e. subsets covering only one element.

Definition at line 128 of file set_cover_model.h.

◆ ComputeNumSingletonRows()

BaseInt operations_research::SetCoverModel::ComputeNumSingletonRows ( ) const

inline

Computes the number of singleton rows in the model, i.e. elements in the model that can be covered by one subset only.

Definition at line 140 of file set_cover_model.h.

◆ ComputeRowDeciles()

std::vector< int64_t > operations_research::SetCoverModel::ComputeRowDeciles ( ) const

Computes deciles on rows and returns a vector of deciles.

Definition at line 708 of file set_cover_model.cc.

◆ ComputeRowDeltaSizeStats()

SetCoverModel::Stats operations_research::SetCoverModel::ComputeRowDeltaSizeStats ( ) const

Computes basic statistics on the deltas of the row and column elements and returns a Stats structure. The deltas are computed as the difference between two consecutive indices in rows or columns. The number of bytes computed is meant using a variable-length base-128 encoding.

Todo: (user): actually use this to compress the rows and columns.

Definition at line 747 of file set_cover_model.cc.

◆ ComputeRowStats()

SetCoverModel::Stats operations_research::SetCoverModel::ComputeRowStats ( ) const

Computes basic statistics on rows and returns a Stats structure.

Definition at line 678 of file set_cover_model.cc.

◆ ComputeSliceIndices()

std::vector< SubsetIndex > operations_research::SetCoverModel::ComputeSliceIndices ( int num_partitions )

The following functions are used by CreateSparseRowViewUsingSlices. They are exposed for testing purposes. Returns a vector of subset indices that partition columns into num_partitions partitions of roughly equal size in number of non-zeros. The resulting vector contains the index of the first subset in the next partition. Therefore the last element is the total number of subsets. Also the vector is sorted.

Definition at line 372 of file set_cover_model.cc.

◆ ComputeSparseRowViewSlice()

SparseRowView operations_research::SetCoverModel::ComputeSparseRowViewSlice	(	SubsetIndex	begin_subset,
		SubsetIndex	end_subset )

Returns a view of the rows of the problem with subset in the range [begin_subset, end_subset).

Definition at line 401 of file set_cover_model.cc.

◆ ComputeSparseRowViewUsingSlices()

SparseRowView operations_research::SetCoverModel::ComputeSparseRowViewUsingSlices ( )

Same as CreateSparseRowView, but uses a slicing algorithm, more prone to parallelism.

Definition at line 459 of file set_cover_model.cc.

◆ create_sparse_row_view_duration()

absl::Duration operations_research::SetCoverModel::create_sparse_row_view_duration ( ) const

inline

Definition at line 198 of file set_cover_model.h.

◆ CreateSparseRowView()

void operations_research::SetCoverModel::CreateSparseRowView ( )

Creates the sparse ("dual") representation of the problem. This also sorts the elements in each subset.

Definition at line 337 of file set_cover_model.cc.

◆ CutSparseRowViewInSlices()

std::vector< SparseRowView > operations_research::SetCoverModel::CutSparseRowViewInSlices ( absl::Span< const SubsetIndex > partition_points )

Returns a vector of row views, each corresponding to a partition of the problem. The partitions are defined by the given partition points.

This should be done in parallel. It is a bottleneck.

Definition at line 430 of file set_cover_model.cc.

◆ ElementRange()

util_intops::StrongIntRange< ElementIndex > operations_research::SetCoverModel::ElementRange ( ) const

inline

Definition at line 187 of file set_cover_model.h.

◆ ExportModelAsProto()

SetCoverProto operations_research::SetCoverModel::ExportModelAsProto ( ) const

Returns the model as a SetCoverProto. Note that the elements of each subset are sorted locally before being exported to the proto. This is done to ensure that the proto is deterministic. The function is const because it does not modify the model. Therefore, the model as exported by this function may be different from the initial model.

Definition at line 517 of file set_cover_model.cc.

◆ FillRate()

double operations_research::SetCoverModel::FillRate ( ) const

inline

Returns the fill rate of the matrix.

Definition at line 122 of file set_cover_model.h.

◆ GenerateRandomModelFrom()

SetCoverModel operations_research::SetCoverModel::GenerateRandomModelFrom	(	const SetCoverModel &	seed_model,
		BaseInt	num_elements,
		BaseInt	num_subsets,
		double	row_scale,
		double	column_scale,
		double	cost_scale )

static

Constructs a weighted set-covering problem from a seed model, with num_elements elements and num_subsets subsets.

The distributions of the degrees of the elements and the cardinalities of the subsets are based on those of the seed model. They are scaled affininely by row_scale and column_scale respectively.
By affine scaling, we mean that the minimum value of the distribution is not scaled, but the variation above this minimum value is.
For a given subset with a given cardinality in the generated model, its elements are sampled from the distribution of the degrees as computed above.
The costs of the subsets in the new model are sampled from the distribution of the costs of the subsets in the seed model, scaled by cost_scale. IMPORTANT NOTICE: The algorithm may not succeed in generating a model where all the elements can be covered. In that case, the model will be empty.

Create the distribution of the cardinalities of the subsets based on the histogram of column sizes in the seed model.

Create the distribution of the degrees of the elements based on the histogram of row sizes in the seed model.

Prepare the degrees of the elements in the generated model, and use them in a distribution to generate the columns. This ponderates the columns towards the elements with higher degrees. ???

Vector indicating whether the generated model covers an element.

Number of elements in the generated model, using the above vector.

Maximum number of tries to generate a random element that is not yet in the subset, or a random subset that does not contain the element.

Loop-local vector indicating whether the currently generated subset contains an element.

Choose an element that is not yet in the subset at random with a distribution that is proportional to the degree of the element.

It can happen – rarely in practice – that some of the elements cannot be covered. Let's add them to randomly chosen subsets.

The method is the same as above.

Todo: (user): if necessary, use a better distribution for the costs. The generation of the costs is done in two steps. First, compute the minimum and maximum costs.

Then, generate random numbers in [min_cost, min_cost + cost_range], where cost_range is defined as:

Definition at line 90 of file set_cover_model.cc.

◆ generation_duration()

absl::Duration operations_research::SetCoverModel::generation_duration ( ) const

inline

Accessors to the durations of the different stages of the model creation.

Definition at line 196 of file set_cover_model.h.

◆ ImportModelFromProto()

void operations_research::SetCoverModel::ImportModelFromProto ( const SetCoverProto & message )

Imports the model from a SetCoverProto.

Definition at line 537 of file set_cover_model.cc.

◆ is_unicost()

bool operations_research::SetCoverModel::is_unicost ( )

inline

Returns true if all subset costs are equal to 1.0. This is a fast check that is only valid if the subset costs are not modified.

Definition at line 155 of file set_cover_model.h.

◆ IsEmpty()

bool operations_research::SetCoverModel::IsEmpty ( ) const

inline

Returns true if the model is empty, i.e. has no elements, no subsets, and no nonzeros.

Definition at line 105 of file set_cover_model.h.

◆ name()

std::string operations_research::SetCoverModel::name ( ) const

inline

Definition at line 75 of file set_cover_model.h.

◆ num_elements()

BaseInt operations_research::SetCoverModel::num_elements ( ) const

inline

Current number of elements to be covered in the model, i.e. the number of elements in S. In matrix terms, this is the number of rows.

Definition at line 109 of file set_cover_model.h.

◆ num_nonzeros()

int64_t operations_research::SetCoverModel::num_nonzeros ( ) const

inline

Current number of nonzeros in the matrix.

Definition at line 119 of file set_cover_model.h.

◆ num_subsets()

BaseInt operations_research::SetCoverModel::num_subsets ( ) const

inline

Current number of subsets in the model. In matrix terms, this is the number of columns.

Definition at line 113 of file set_cover_model.h.

◆ ReduceSparseRowViewSlices()

SparseRowView operations_research::SetCoverModel::ReduceSparseRowViewSlices ( absl::Span< const SparseRowView > row_slices )

Returns the union of the rows of the given row views. The returned view is valid only as long as the given row views are valid. The indices in the rows are sorted.

This is not a ReduceTree. This will be done later through parallelism.

This should done as a reduce tree, in parallel.

Definition at line 443 of file set_cover_model.cc.

◆ ReserveNumElementsInSubset()

void operations_research::SetCoverModel::ReserveNumElementsInSubset	(	BaseInt	num_elements,
		BaseInt	subset )

Reserves num_elements rows in the column indexed by subset.

Definition at line 322 of file set_cover_model.cc.

◆ ResizeNumSubsets() [1/2]

void operations_research::SetCoverModel::ResizeNumSubsets ( BaseInt num_subsets )

Resizes the model to have at least num_subsets columns. The new columns correspond to empty subsets. This function will never remove a column, i.e. if num_subsets is smaller than the current instance size the function does nothing.

Definition at line 311 of file set_cover_model.cc.

◆ ResizeNumSubsets() [2/2]

void operations_research::SetCoverModel::ResizeNumSubsets ( SubsetIndex num_subsets )

Definition at line 318 of file set_cover_model.cc.

◆ row_view_is_valid()

bool operations_research::SetCoverModel::row_view_is_valid ( ) const

inline

Returns true if rows_ and columns_ represent the same problem.

Definition at line 180 of file set_cover_model.h.

◆ rows()

const SparseRowView & operations_research::SetCoverModel::rows ( ) const

inline

Row view of the set covering problem.

Definition at line 174 of file set_cover_model.h.

◆ SetName()

void operations_research::SetCoverModel::SetName ( const absl::string_view name )

inline

Definition at line 77 of file set_cover_model.h.

◆ SetSubsetCost() [1/2]

void operations_research::SetCoverModel::SetSubsetCost	(	BaseInt	subset,
		Cost	cost )

Sets 'cost' to an already existing 'subset'. This will CHECK-fail if cost is infinite or a NaN.

Todo: (user): refine the logic for is_unicost_ and is_unicost_valid_. NOMUTANTS – this is a performance optimization.

Definition at line 271 of file set_cover_model.cc.

◆ SetSubsetCost() [2/2]

void operations_research::SetCoverModel::SetSubsetCost	(	SubsetIndex	subset,
		Cost	cost )

Definition at line 288 of file set_cover_model.cc.

◆ SortElementsInSubsets()

void operations_research::SetCoverModel::SortElementsInSubsets ( )

Sorts the elements in each subset. Should be called before exporting the model to a proto.

std::sort(columns_[subset].begin(), columns_[subset].end());

Definition at line 328 of file set_cover_model.cc.

◆ subset_costs()

const SubsetCostVector & operations_research::SetCoverModel::subset_costs ( ) const

inline

Vector of costs for each subset.

Definition at line 151 of file set_cover_model.h.

◆ SubsetRange()

util_intops::StrongIntRange< SubsetIndex > operations_research::SetCoverModel::SubsetRange ( ) const

inline

Access to the ranges of subsets and elements.

Definition at line 183 of file set_cover_model.h.

◆ ToString()

std::string operations_research::SetCoverModel::ToString ( absl::string_view sep ) const

Returns a string representation of the model, using the given separator.

Definition at line 566 of file set_cover_model.cc.

◆ ToVerboseString()

std::string operations_research::SetCoverModel::ToVerboseString ( absl::string_view sep ) const

Returns a verbose string representation of the model, using the given separator.

Definition at line 558 of file set_cover_model.cc.

The documentation for this class was generated from the following files:

ortools/set_cover/set_cover_model.h
ortools/set_cover/set_cover_model.cc

Classes

Public Member Functions

Static Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ SetCoverModel()

Member Function Documentation

◆ AddElementToLastSubset() [1/2]

◆ AddElementToLastSubset() [2/2]

◆ AddElementToSubset() [1/2]

◆ AddElementToSubset() [2/2]

◆ AddEmptySubset()

◆ all_subsets()

◆ columns()

◆ compute_sparse_row_view_using_slices_duration()

◆ ComputeColumnDeciles()

◆ ComputeColumnDeltaSizeStats()

◆ ComputeColumnStats()

◆ ComputeCostStats()

◆ ComputeFeasibility()

◆ ComputeNumSingletonColumns()

◆ ComputeNumSingletonRows()

◆ ComputeRowDeciles()

◆ ComputeRowDeltaSizeStats()

◆ ComputeRowStats()

◆ ComputeSliceIndices()

◆ ComputeSparseRowViewSlice()

◆ ComputeSparseRowViewUsingSlices()

◆ create_sparse_row_view_duration()

◆ CreateSparseRowView()

◆ CutSparseRowViewInSlices()

◆ ElementRange()

◆ ExportModelAsProto()

◆ FillRate()

◆ GenerateRandomModelFrom()

◆ generation_duration()

◆ ImportModelFromProto()

◆ is_unicost()

◆ IsEmpty()

◆ name()

◆ num_elements()

◆ num_nonzeros()

◆ num_subsets()

◆ ReduceSparseRowViewSlices()

◆ ReserveNumElementsInSubset()

◆ ResizeNumSubsets() [1/2]

◆ ResizeNumSubsets() [2/2]

◆ row_view_is_valid()

◆ rows()

◆ SetName()

◆ SetSubsetCost() [1/2]

◆ SetSubsetCost() [2/2]

◆ SortElementsInSubsets()

◆ subset_costs()

◆ SubsetRange()

◆ ToString()

◆ ToVerboseString()