#include <set_cover_invariant.h>

Public Member Functions
	SetCoverInvariant (SetCoverModel *m)

void	Initialize ()

void	Clear ()

void	RecomputeInvariant ()
	Recomputes all the invariants for the current solution.

SetCoverModel *	model () const
	Returns the weighted set covering model to which the state applies.

const SetCoverModel *	const_model () const

Cost	cost () const
	Returns the cost of current solution.

BaseInt	num_uncovered_elements () const
	Returns the number of uncovered elements.

const SubsetBoolVector &	is_selected () const
	Returns the subset assignment vector.

const SubsetToIntVector &	num_free_elements () const

const SubsetToIntVector &	num_coverage_le_1_elements () const

const ElementToIntVector &	coverage () const
	Returns vector containing number of subsets covering each element.

ElementToIntVector	ComputeCoverageInFocus (absl::Span< const SubsetIndex > focus) const

const SubsetBoolVector &	is_redundant () const

const std::vector< SetCoverDecision > &	trace () const
	Returns the vector of the decisions which has led to the current solution.

void	ClearTrace ()
	Clears the trace.

void	ClearRemovabilityInformation ()
	Clear the removability information.

const std::vector< SubsetIndex > &	new_removable_subsets () const
	Returns the subsets that become removable after the last update.

const std::vector< SubsetIndex > &	new_non_removable_subsets () const
	Returns the subsets that become non removable after the last update.

void	CompressTrace ()

void	LoadSolution (const SubsetBoolVector &solution)
	Loads the solution and recomputes the data in the invariant.

bool	CheckConsistency () const

bool	ComputeIsRedundant (SubsetIndex subset) const

void	MakeFullyUpdated ()

void	Flip (SubsetIndex subset)

void	FlipAndFullyUpdate (SubsetIndex subset)

void	Select (SubsetIndex subset)

void	SelectAndFullyUpdate (SubsetIndex subset)

void	Deselect (SubsetIndex subset)

void	DeselectAndFullyUpdate (SubsetIndex subset)

SetCoverSolutionResponse	ExportSolutionAsProto () const
	Returns the current solution as a proto.

void	ImportSolutionFromProto (const SetCoverSolutionResponse &message)
	Imports the solution from a proto.

Detailed Description

SetCoverInvariant does the bookkeeping for a solution to the SetCoverModel passed as argument. The state of a SetCoverInvariant instance is uniquely defined by a SubsetBoolVector representing whether a subset is selected in the solution or not.

See https://cs.brown.edu/research/pubs/pdfs/1999/Michel-1999-LML.pdf for an explanation of the terminology.

A SetCoverInvariant is (relatively) small: is_selected_: a partial solution, vector of Booleans of size #subsets. From this, the following can be computed: coverage_ : number of times an element is covered; num_free_elements_: number of elements in a subset that are uncovered. num_non_overcovered_elements_: the number of elements of a subset that are covered 1 time or less (not overcovered) in the current solution; is_redundant_, whether a subset can be removed from the solution. is_redundant_[subset] == (num_non_overcovered_elements_[subet] == 0).

Definition at line 67 of file set_cover_invariant.h.

Constructor & Destructor Documentation

◆ SetCoverInvariant()

operations_research::SetCoverInvariant::SetCoverInvariant ( SetCoverModel * m )

inlineexplicit

Constructs an empty weighted set covering solver state. The model may not change after the invariant was built.

Definition at line 71 of file set_cover_invariant.h.

Member Function Documentation

◆ CheckConsistency()

bool operations_research::SetCoverInvariant::CheckConsistency ( ) const

Returns true if the data stored in the invariant is consistent. The body of the function will CHECK-fail the first time an inconsistency is encountered.

Definition at line 65 of file set_cover_invariant.cc.

◆ Clear()

void operations_research::SetCoverInvariant::Clear ( )

inline

Definition at line 77 of file set_cover_invariant.h.

◆ ClearRemovabilityInformation()

void operations_research::SetCoverInvariant::ClearRemovabilityInformation ( )

inline

Clear the removability information.

Definition at line 129 of file set_cover_invariant.h.

◆ ClearTrace()

void operations_research::SetCoverInvariant::ClearTrace ( )

inline

Clears the trace.

Definition at line 126 of file set_cover_invariant.h.

◆ CompressTrace()

void operations_research::SetCoverInvariant::CompressTrace ( )

Compresses the trace so that:

each subset appears only once,
there are only "positive" decisions. This trace is equivalent to the original trace in the sense that the cost and the covered elements are the same. This can be used to recover the solution by indices after local search.

As of 2024-05-14, this is as fast as "smarter" alternatives that try to avoid some memory writes by keeping track of already visited subsets. We also tried to use is_selected_ as a helper, which slowed down everything.

Definition at line 191 of file set_cover_invariant.cc.

◆ ComputeCoverageInFocus()

ElementToIntVector operations_research::SetCoverInvariant::ComputeCoverageInFocus ( absl::Span< const SubsetIndex > focus ) const

Returns a vector containing the number of subsets within focus covering each element. Subsets that are without focus are not considered.

Definition at line 125 of file set_cover_invariant.cc.

◆ ComputeIsRedundant()

bool operations_research::SetCoverInvariant::ComputeIsRedundant ( SubsetIndex subset ) const

Returns true if the subset is redundant within the current solution, i.e. when all its elements are already covered twice. Note that the set need not be selected for this to happen.

Todo: (user): Implement this using AVX-512?

Definition at line 214 of file set_cover_invariant.cc.

◆ const_model()

const SetCoverModel * operations_research::SetCoverInvariant::const_model ( ) const

inline

Definition at line 88 of file set_cover_invariant.h.

◆ cost()

Cost operations_research::SetCoverInvariant::cost ( ) const

inline

Returns the cost of current solution.

Definition at line 91 of file set_cover_invariant.h.

◆ coverage()

const ElementToIntVector & operations_research::SetCoverInvariant::coverage ( ) const

inline

Returns vector containing number of subsets covering each element.

Definition at line 111 of file set_cover_invariant.h.

◆ Deselect()

void operations_research::SetCoverInvariant::Deselect ( SubsetIndex subset )

inline

Excludes subset from the solution by setting is_selected_[subset] to false and incrementally updating the invariant. DeselectAndFullyUpdate also updates the invariant in a more thorough way as explained with FlipAndFullyUpdate.

Definition at line 191 of file set_cover_invariant.h.

◆ DeselectAndFullyUpdate()

void operations_research::SetCoverInvariant::DeselectAndFullyUpdate ( SubsetIndex subset )

inline

Definition at line 192 of file set_cover_invariant.h.

◆ ExportSolutionAsProto()

SetCoverSolutionResponse operations_research::SetCoverInvariant::ExportSolutionAsProto ( ) const

Returns the current solution as a proto.

Definition at line 362 of file set_cover_invariant.cc.

◆ Flip()

void operations_research::SetCoverInvariant::Flip ( SubsetIndex subset )

inline

Flips is_selected_[subset] to its negation, by calling Select or Deselect depending on value. Updates the invariant incrementally. FlipAndFullyUpdate performs a full incremental update of the invariant, including num_non_overcovered_elements_, is_redundant_, new_removable_subsets_, new_non_removable_subsets_. This is useful for some meta-heuristics.

Definition at line 177 of file set_cover_invariant.h.

◆ FlipAndFullyUpdate()

void operations_research::SetCoverInvariant::FlipAndFullyUpdate ( SubsetIndex subset )

inline

Definition at line 178 of file set_cover_invariant.h.

◆ ImportSolutionFromProto()

void operations_research::SetCoverInvariant::ImportSolutionFromProto ( const SetCoverSolutionResponse & message )

Imports the solution from a proto.

Definition at line 377 of file set_cover_invariant.cc.

◆ Initialize()

void operations_research::SetCoverInvariant::Initialize ( )

Initializes the solver once the data is set. The model cannot be changed afterwards.

Note: in many of the member functions, variables have "crypterse" names to avoid confusing them with member data. For example mrgnl_impcts is used to avoid confusion with num_free_elements_.

No need to reserve for trace_ and other vectors as extending with push_back is fast enough.

Definition at line 35 of file set_cover_invariant.cc.

◆ is_redundant()

const SubsetBoolVector & operations_research::SetCoverInvariant::is_redundant ( ) const

inline

Returns vector of Booleans telling whether each subset can be removed from the solution.

Definition at line 120 of file set_cover_invariant.h.

◆ is_selected()

const SubsetBoolVector & operations_research::SetCoverInvariant::is_selected ( ) const

inline

Returns the subset assignment vector.

Definition at line 97 of file set_cover_invariant.h.

◆ LoadSolution()

void operations_research::SetCoverInvariant::LoadSolution ( const SubsetBoolVector & solution )

Loads the solution and recomputes the data in the invariant.

Definition at line 85 of file set_cover_invariant.cc.

◆ MakeFullyUpdated()

void operations_research::SetCoverInvariant::MakeFullyUpdated ( )

Updates the invariant fully, so that is_redundant_ can be updated incrementally later with SelectAndFullyUpdate and DeselectSelectAndFullyUpdate.

Definition at line 99 of file set_cover_invariant.cc.

◆ model()

SetCoverModel * operations_research::SetCoverInvariant::model ( ) const

inline

Returns the weighted set covering model to which the state applies.

Definition at line 86 of file set_cover_invariant.h.

◆ new_non_removable_subsets()

const std::vector< SubsetIndex > & operations_research::SetCoverInvariant::new_non_removable_subsets ( ) const

inline

Returns the subsets that become non removable after the last update.

Definition at line 140 of file set_cover_invariant.h.

◆ new_removable_subsets()

const std::vector< SubsetIndex > & operations_research::SetCoverInvariant::new_removable_subsets ( ) const

inline

Returns the subsets that become removable after the last update.

Definition at line 135 of file set_cover_invariant.h.

◆ num_coverage_le_1_elements()

const SubsetToIntVector & operations_research::SetCoverInvariant::num_coverage_le_1_elements ( ) const

inline

Returns the vector of numbers of free or exactly covered elements for each subset.

Definition at line 107 of file set_cover_invariant.h.

◆ num_free_elements()

const SubsetToIntVector & operations_research::SetCoverInvariant::num_free_elements ( ) const

inline

Returns vector containing the number of elements in each subset that are not covered in the current solution.

Definition at line 101 of file set_cover_invariant.h.

◆ num_uncovered_elements()

BaseInt operations_research::SetCoverInvariant::num_uncovered_elements ( ) const

inline

Returns the number of uncovered elements.

Definition at line 94 of file set_cover_invariant.h.

◆ RecomputeInvariant()

void operations_research::SetCoverInvariant::RecomputeInvariant ( )

Recomputes all the invariants for the current solution.

Definition at line 90 of file set_cover_invariant.cc.

◆ Select()

void operations_research::SetCoverInvariant::Select ( SubsetIndex subset )

inline

Includes subset in the solution by setting is_selected_[subset] to true and incrementally updating the invariant. SelectAndFullyUpdate also updates the invariant in a more thorough way as explained with FlipAndFullyUpdate.

Definition at line 184 of file set_cover_invariant.h.

◆ SelectAndFullyUpdate()

void operations_research::SetCoverInvariant::SelectAndFullyUpdate ( SubsetIndex subset )

inline

Definition at line 185 of file set_cover_invariant.h.

◆ trace()

const std::vector< SetCoverDecision > & operations_research::SetCoverInvariant::trace ( ) const

inline

Returns the vector of the decisions which has led to the current solution.

Definition at line 123 of file set_cover_invariant.h.

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

ortools/algorithms/set_cover_invariant.h
ortools/algorithms/set_cover_invariant.cc

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ SetCoverInvariant()

Member Function Documentation

◆ CheckConsistency()

◆ Clear()

◆ ClearRemovabilityInformation()

◆ ClearTrace()

◆ CompressTrace()

◆ ComputeCoverageInFocus()

◆ ComputeIsRedundant()

◆ const_model()

◆ cost()

◆ coverage()

◆ Deselect()

◆ DeselectAndFullyUpdate()

◆ ExportSolutionAsProto()

◆ Flip()

◆ FlipAndFullyUpdate()

◆ ImportSolutionFromProto()

◆ Initialize()

◆ is_redundant()

◆ is_selected()

◆ LoadSolution()

◆ MakeFullyUpdated()

◆ model()

◆ new_non_removable_subsets()

◆ new_removable_subsets()

◆ num_coverage_le_1_elements()

◆ num_free_elements()

◆ num_uncovered_elements()

◆ RecomputeInvariant()

◆ Select()

◆ SelectAndFullyUpdate()

◆ trace()