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.

BaseInt	num_elements () const

BaseInt	num_subsets () const

ssize_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	CreateSparseRowView ()
	Creates the sparse ("dual") representation of the problem.

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

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< ssize_t >	ComputeRowDeciles () const
	Computes deciles on rows and returns a vector of deciles.

std::vector< ssize_t >	ComputeColumnDeciles () const
	Computes deciles on columns and returns a vector of deciles.

Detailed Description

Main class for describing a weighted set-covering problem.

Definition at line 122 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 125 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 51 of file set_cover_model.cc.

◆ AddElementToLastSubset() [2/2]

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

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

◆ AddElementToSubset() [2/2]

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

Definition at line 89 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 40 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 176 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 154 of file set_cover_model.h.

◆ ComputeColumnDeciles()

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

Computes deciles on columns and returns a vector of deciles.

Definition at line 286 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 268 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 252 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 142 of file set_cover_model.cc.

◆ ComputeRowDeciles()

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

Computes deciles on rows and returns a vector of deciles.

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

◆ CreateSparseRowView()

void operations_research::SetCoverModel::CreateSparseRowView ( )

Creates the sparse ("dual") representation of the problem.

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

Definition at line 117 of file set_cover_model.cc.

◆ ElementRange()

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

inline

Definition at line 170 of file set_cover_model.h.

◆ ExportModelAsProto()

SetCoverProto operations_research::SetCoverModel::ExportModelAsProto ( )

Returns the model as a SetCoverProto. The function is not const because the element indices in the columns need to be sorted for the representation as a protobuf to be canonical.

Definition at line 172 of file set_cover_model.cc.

◆ FillRate()

double operations_research::SetCoverModel::FillRate ( ) const

inline

Definition at line 146 of file set_cover_model.h.

◆ ImportModelFromProto()

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

Imports the model from a SetCoverProto.

Definition at line 185 of file set_cover_model.cc.

◆ 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 137 of file set_cover_model.h.

◆ num_nonzeros()

ssize_t operations_research::SetCoverModel::num_nonzeros ( ) const

inline

Current number of nonzeros in the matrix.

Definition at line 144 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 141 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 106 of file set_cover_model.cc.

◆ ReserveNumElementsInSubset() [2/2]

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

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

◆ ReserveNumSubsets() [2/2]

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

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

◆ SetSubsetCost() [2/2]

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

Definition at line 74 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 166 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

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

◆ ComputeColumnStats()

◆ ComputeCostStats()

◆ ComputeFeasibility()

◆ ComputeRowDeciles()

◆ ComputeRowStats()

◆ CreateSparseRowView()

◆ ElementRange()

◆ ExportModelAsProto()

◆ FillRate()

◆ ImportModelFromProto()

◆ 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]

◆ subset_costs()

◆ SubsetRange()