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

#include <set_cover_model.h>

Classes
struct	Stats

Public Member Functions
	SetCoverModel ()
	Constructs an empty weighted set-covering problem.

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

const SubsetCostVector &	subset_costs () const
	Vector of costs for each subset.

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.

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 ()

bool	ComputeFeasibility () const

void	ReserveNumSubsets (BaseInt num_subsets)
	Reserves num_subsets columns in the model.

void	ReserveNumSubsets (SubsetIndex num_subsets)

void	ReserveNumElementsInSubset (BaseInt num_elements, BaseInt subset)
	Reserves num_elements rows in the column indexed by subset.

void	ReserveNumElementsInSubset (ElementIndex num_elements, SubsetIndex subset)

SetCoverProto	ExportModelAsProto () const

void	ImportModelFromProto (const SetCoverProto &message)
	Imports the model from a SetCoverProto.

Stats	ComputeCostStats ()
	Computes basic statistics on costs and returns a Stats structure.

Stats	ComputeRowStats ()
	Computes basic statistics on rows and returns a Stats structure.

Stats	ComputeColumnStats ()
	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 104 of file set_cover_model.h.

Constructor & Destructor Documentation

◆ SetCoverModel()

operations_research::SetCoverModel::SetCoverModel ( )

inline

Constructs an empty weighted set-covering problem.

Definition at line 107 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 251 of file set_cover_model.cc.

◆ AddElementToLastSubset() [2/2]

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

Definition at line 260 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 282 of file set_cover_model.cc.

◆ AddElementToSubset() [2/2]

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

Definition at line 296 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.

Definition at line 239 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 187 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 165 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 559 of file set_cover_model.cc.

◆ ComputeColumnDeltaSizeStats()

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

Definition at line 575 of file set_cover_model.cc.

◆ ComputeColumnStats()

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

Computes basic statistics on columns and returns a Stats structure.

Definition at line 541 of file set_cover_model.cc.

◆ ComputeCostStats()

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

Computes basic statistics on costs and returns a Stats structure.

Definition at line 525 of file set_cover_model.cc.

◆ ComputeFeasibility()

bool operations_research::SetCoverModel::ComputeFeasibility ( ) const

Returns true if the problem is feasible, i.e. if the subsets cover all the elements.

Definition at line 365 of file set_cover_model.cc.

◆ ComputeRowDeciles()

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

Computes deciles on rows and returns a vector of deciles.

Definition at line 549 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 588 of file set_cover_model.cc.

◆ ComputeRowStats()

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

Computes basic statistics on rows and returns a Stats structure.

Definition at line 531 of file set_cover_model.cc.

◆ CreateSparseRowView()

void operations_research::SetCoverModel::CreateSparseRowView ( )

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

Sort the columns. It's not super-critical to improve performance here as this needs to be done only once.

Definition at line 334 of file set_cover_model.cc.

◆ ElementRange()

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

inline

Definition at line 181 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.

std::sort(column.begin(), column.end());

Definition at line 395 of file set_cover_model.cc.

◆ FillRate()

double operations_research::SetCoverModel::FillRate ( ) const

inline

Definition at line 157 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 86 of file set_cover_model.cc.

◆ ImportModelFromProto()

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

Imports the model from a SetCoverProto.

Definition at line 416 of file set_cover_model.cc.

◆ 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 144 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 148 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 155 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 152 of file set_cover_model.h.

◆ ReserveNumElementsInSubset() [1/2]

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

Reserves num_elements rows in the column indexed by subset.

Definition at line 314 of file set_cover_model.cc.

◆ ReserveNumElementsInSubset() [2/2]

void operations_research::SetCoverModel::ReserveNumElementsInSubset	(	ElementIndex	num_elements,
		SubsetIndex	subset )

Definition at line 320 of file set_cover_model.cc.

◆ ReserveNumSubsets() [1/2]

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

Reserves num_subsets columns in the model.

Definition at line 302 of file set_cover_model.cc.

◆ ReserveNumSubsets() [2/2]

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

Definition at line 309 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 174 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 168 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.

Definition at line 264 of file set_cover_model.cc.

◆ SetSubsetCost() [2/2]

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

Definition at line 278 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 325 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 162 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 177 of file set_cover_model.h.

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

ortools/algorithms/set_cover_model.h
ortools/algorithms/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()

◆ ComputeColumnDeciles()

◆ ComputeColumnDeltaSizeStats()

◆ ComputeColumnStats()

◆ ComputeCostStats()

◆ ComputeFeasibility()

◆ ComputeRowDeciles()

◆ ComputeRowDeltaSizeStats()

◆ ComputeRowStats()

◆ CreateSparseRowView()

◆ ElementRange()

◆ ExportModelAsProto()

◆ FillRate()

◆ GenerateRandomModelFrom()

◆ ImportModelFromProto()

◆ IsEmpty()

◆ num_elements()

◆ num_nonzeros()

◆ num_subsets()

◆ ReserveNumElementsInSubset() [1/2]

◆ ReserveNumElementsInSubset() [2/2]

◆ ReserveNumSubsets() [1/2]

◆ ReserveNumSubsets() [2/2]

◆ row_view_is_valid()

◆ rows()

◆ SetSubsetCost() [1/2]

◆ SetSubsetCost() [2/2]

◆ SortElementsInSubsets()

◆ subset_costs()

◆ SubsetRange()