#include <set_cover_invariant.h>

Public Types
enum class	ConsistencyLevel { kInconsistent = 0 , kCostAndCoverage , kFreeAndUncovered , kRedundancy }

Public Member Functions
	SetCoverInvariant (SetCoverModel *m)

void	Initialize ()

void	Clear ()
	Clears the invariant. Also called by Initialize.

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 have led to the current solution.

void	ClearTrace ()
	Clears the trace.

void	ClearRemovabilityInformation ()
	Clear the removability information.

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

const std::vector< SubsetIndex > &	newly_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 (ConsistencyLevel consistency) const
	Checks the consistency of the invariant at the given consistency level.

void	Recompute (ConsistencyLevel target_consistency)
	Recomputes the invariant to the given consistency level.

bool	ComputeIsRedundant (SubsetIndex subset) const

BaseInt	ComputeNumFreeElements (SubsetIndex subset) const
	Computes the number of free (uncovered) elements in the given subset.

void	SelectNoUpdate (SubsetIndex subset)

void	Flip (SubsetIndex subset, ConsistencyLevel consistency)

void	Select (SubsetIndex subset, ConsistencyLevel consistency)

void	Deselect (SubsetIndex subset, ConsistencyLevel consistency)

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 66 of file set_cover_invariant.h.

Member Enumeration Documentation

◆ ConsistencyLevel

enum class operations_research::SetCoverInvariant::ConsistencyLevel

strong

The consistency level of the invariant. The values denote the level of consistency of the invariant. There is an order between the levels, and the invariant is consistent at level k if it is consistent at all levels lower than k. The consistency level that is the most natural is to use kFreeAndUncovered, since it enables to implement most heuristics. kCostAndCoverage is used by LazyElementDegree, a fast greedy heuristic. kRedundancy is used for GuidedLocalSearch, because knowing whether a subset is redundant incrementally is faster than recomputing the information over and over again. Below, the quantities that are maintained at each level are listed.

Enumerator
kInconsistent
kCostAndCoverage
kFreeAndUncovered
kRedundancy

Definition at line 79 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 88 of file set_cover_invariant.h.

Member Function Documentation

◆ CheckConsistency()

bool operations_research::SetCoverInvariant::CheckConsistency ( ConsistencyLevel consistency ) const

Checks the consistency of the invariant at the given consistency level.

Definition at line 69 of file set_cover_invariant.cc.

◆ Clear()

void operations_research::SetCoverInvariant::Clear ( )

Clears the invariant. Also called by Initialize.

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

Definition at line 40 of file set_cover_invariant.cc.

◆ ClearRemovabilityInformation()

void operations_research::SetCoverInvariant::ClearRemovabilityInformation ( )

inline

Clear the removability information.

Definition at line 141 of file set_cover_invariant.h.

◆ ClearTrace()

void operations_research::SetCoverInvariant::ClearTrace ( )

inline

Clears the trace.

Definition at line 138 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 250 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 185 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 273 of file set_cover_invariant.cc.

◆ ComputeNumFreeElements()

BaseInt operations_research::SetCoverInvariant::ComputeNumFreeElements ( SubsetIndex subset ) const

Computes the number of free (uncovered) elements in the given subset.

Definition at line 293 of file set_cover_invariant.cc.

◆ const_model()

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

inline

Definition at line 100 of file set_cover_invariant.h.

◆ cost()

Cost operations_research::SetCoverInvariant::cost ( ) const

inline

Returns the cost of current solution.

Definition at line 103 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 123 of file set_cover_invariant.h.

◆ Deselect()

void operations_research::SetCoverInvariant::Deselect	(	SubsetIndex	subset,
		ConsistencyLevel	consistency )

Excludes subset from the solution by setting is_selected_[subset] to false and incrementally updating the invariant to the given consistency level.

If already selected, then num_free_elements == 0.

Fast path for kCostAndCoverage.

Update coverage. Notice the asymmetry with Select where coverage is incremented after being tested.

element is no longer covered.

element will be no longer overcovered.

There is one element of impacted_subset which is not overcovered. impacted_subset has just become non-removable.

Since subset is now deselected, there is no need nor meaning in adding it a list of removable or non-removable subsets. This is a dissymmetry with Select.

Definition at line 373 of file set_cover_invariant.cc.

◆ ExportSolutionAsProto()

SetCoverSolutionResponse operations_research::SetCoverInvariant::ExportSolutionAsProto ( ) const

Returns the current solution as a proto.

Definition at line 430 of file set_cover_invariant.cc.

◆ Flip()

void operations_research::SetCoverInvariant::Flip	(	SubsetIndex	subset,
		ConsistencyLevel	consistency )

Flips is_selected_[subset] to its negation, by calling Select or Deselect depending on value. Updates the invariant incrementally to the given consistency level.

Definition at line 303 of file set_cover_invariant.cc.

◆ ImportSolutionFromProto()

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

Imports the solution from a proto.

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

Definition at line 34 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 132 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 109 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 103 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 98 of file set_cover_invariant.h.

◆ newly_non_removable_subsets()

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

inline

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

Definition at line 152 of file set_cover_invariant.h.

◆ newly_removable_subsets()

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

inline

Returns the subsets that become removable after the last update.

Definition at line 147 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 119 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 113 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 106 of file set_cover_invariant.h.

◆ Recompute()

void operations_research::SetCoverInvariant::Recompute ( ConsistencyLevel target_consistency )

Recomputes the invariant to the given consistency level.

Definition at line 124 of file set_cover_invariant.cc.

◆ Select()

void operations_research::SetCoverInvariant::Select	(	SubsetIndex	subset,
		ConsistencyLevel	consistency )

Includes subset in the solution by setting is_selected_[subset] to true and incrementally updating the invariant to the given consistency level.

Fast path for kCostAndCoverage.

element will be newly covered.

element will be newly overcovered.

All the elements in impacted_subset are now overcovered, so it is removable. Note that this happens only when the last element of impacted_subset becomes overcovered.

Update coverage. Notice the asymmetry with Deselect where coverage is decremented before being tested. This allows to have more symmetrical code for conditions.

Definition at line 312 of file set_cover_invariant.cc.

◆ SelectNoUpdate()

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

Includes subset in the solution by setting is_selected_[subset] to true without updating the invariant. Only updates the cost and the coverage.

Todo: (user): Merge with Select. Introduce consistency levels and maybe split the invariant into three.

◆ trace()

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

inline

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

Definition at line 135 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 Types

Public Member Functions

Detailed Description

Member Enumeration Documentation

◆ ConsistencyLevel

Constructor & Destructor Documentation

◆ SetCoverInvariant()

Member Function Documentation

◆ CheckConsistency()

◆ Clear()

◆ ClearRemovabilityInformation()

◆ ClearTrace()

◆ CompressTrace()

◆ ComputeCoverageInFocus()

◆ ComputeIsRedundant()

◆ ComputeNumFreeElements()

◆ const_model()

◆ cost()

◆ coverage()

◆ Deselect()

◆ ExportSolutionAsProto()

◆ Flip()

◆ ImportSolutionFromProto()

◆ Initialize()

◆ is_redundant()

◆ is_selected()

◆ LoadSolution()

◆ model()

◆ newly_non_removable_subsets()

◆ newly_removable_subsets()

◆ num_coverage_le_1_elements()

◆ num_free_elements()

◆ num_uncovered_elements()

◆ Recompute()

◆ Select()

◆ SelectNoUpdate()

◆ trace()