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.

#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
void	ReportLowerBound (Cost lower_bound, bool is_cost_consistent)
Cost	cost () const
	Returns the cost of current solution.
Cost	CostOrLowerBound () const
bool	is_cost_consistent () const
Cost	LowerBound () const
	Returns the lower bound of the problem.
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.
BaseInt	ComputeCardinality () const
	Returns the cardinality of the solution in the invariant.
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.
void	LoadTraceAndCoverage (const std::vector< SetCoverDecision > &trace, const ElementToIntVector &coverage)
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.
bool	Select (SubsetIndex subset, ConsistencyLevel consistency)
bool	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.

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 80 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 89 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 74 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 42 of file set_cover_invariant.cc.

◆ ClearRemovabilityInformation()

void operations_research::SetCoverInvariant::ClearRemovabilityInformation ( )

inline

Clear the removability information.

Definition at line 178 of file set_cover_invariant.h.

◆ ClearTrace()

void operations_research::SetCoverInvariant::ClearTrace ( )

inline

Clears the trace.

Definition at line 162 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 291 of file set_cover_invariant.cc.

◆ ComputeCardinality()

BaseInt operations_research::SetCoverInvariant::ComputeCardinality ( ) const

inline

Returns the cardinality of the solution in the invariant.

Definition at line 165 of file set_cover_invariant.h.

◆ 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 224 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 314 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 334 of file set_cover_invariant.cc.

◆ const_model()

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

inline

Definition at line 101 of file set_cover_invariant.h.

◆ cost()

Cost operations_research::SetCoverInvariant::cost ( ) const

inline

Returns the cost of current solution.

Definition at line 112 of file set_cover_invariant.h.

◆ CostOrLowerBound()

Cost operations_research::SetCoverInvariant::CostOrLowerBound ( ) const

inline

Returns the cost of the current solution, or the lower bound if the solution is a relaxation.

For the time being we assume that we either have a feasible solution or a relaxation.

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

◆ Deselect()

bool 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. Returns false if the subset is already deselected.

NOMUTANTS – This is a short-circuit to avoid doing any work when the subset is already deselected.

If already selected, then num_free_elements == 0.

Fast path for kCostAndCoverage.

This is a dissymmetry with Select, and only maintained in consistency level kFreeAndUncovered and above.

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 410 of file set_cover_invariant.cc.

◆ ExportSolutionAsProto()

SetCoverSolutionResponse operations_research::SetCoverInvariant::ExportSolutionAsProto ( ) const

Returns the current solution as a proto.

Definition at line 473 of file set_cover_invariant.cc.

◆ ImportSolutionFromProto()

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

Imports the solution from a proto.

Definition at line 488 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 36 of file set_cover_invariant.cc.

◆ is_cost_consistent()

bool operations_research::SetCoverInvariant::is_cost_consistent ( ) const

inline

Returns true if the cost of the current solution is consistent with the solution.

Definition at line 124 of file set_cover_invariant.h.

◆ 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 156 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 133 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 109 of file set_cover_invariant.cc.

◆ LoadTraceAndCoverage()

void operations_research::SetCoverInvariant::LoadTraceAndCoverage	(	const std::vector< SetCoverDecision > &	trace,
		const ElementToIntVector &	coverage )

Loads the trace and the coverage. When both the trace and the coverage are loaded, the invariant is consistent at level kCostAndCoverage. It's also faster than to load a solution and recompute the cost and coverage. The trace and the coverage are expected to be consistent, otherwise the behavior is undefined (i.e. the invariant is not consistent, unless the code is run in DEBUG mode).

Definition at line 137 of file set_cover_invariant.cc.

◆ LowerBound()

Cost operations_research::SetCoverInvariant::LowerBound ( ) const

inline

Returns the lower bound of the problem.

Definition at line 127 of file set_cover_invariant.h.

◆ model()

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

inline

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

Definition at line 99 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 189 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 184 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 143 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 137 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 130 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 162 of file set_cover_invariant.cc.

◆ ReportLowerBound()

void operations_research::SetCoverInvariant::ReportLowerBound	(	Cost	lower_bound,
		bool	is_cost_consistent )

inline

Reports the lower bound of the problem. If is_cost_consistent is true, the lower bound is ignored and the cost is reported instead.

Definition at line 106 of file set_cover_invariant.h.

◆ Select()

bool 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. Returns false if the subset is already selected. This allows a programming style where Select is embedded in a DCHECK, or to write if (Select(subset, consistency)) { ... }, which is more readable than if (!is_selected_[subset]) { Select(subset, consistency); ... } The above is a good programming style for example to count how many elements were actually set.

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 344 of file set_cover_invariant.cc.

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

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

ortools/set_cover/set_cover_invariant.h
ortools/set_cover/set_cover_invariant.cc

Detailed Description

Public Types

Public Member Functions

Member Enumeration Documentation

◆ ConsistencyLevel

Constructor & Destructor Documentation

◆ SetCoverInvariant()

Member Function Documentation

◆ CheckConsistency()

◆ Clear()

◆ ClearRemovabilityInformation()

◆ ClearTrace()

◆ CompressTrace()

◆ ComputeCardinality()

◆ ComputeCoverageInFocus()

◆ ComputeIsRedundant()

◆ ComputeNumFreeElements()

◆ const_model()

◆ cost()

◆ CostOrLowerBound()

◆ coverage()

◆ Deselect()

◆ ExportSolutionAsProto()

◆ ImportSolutionFromProto()

◆ Initialize()

◆ is_cost_consistent()

◆ is_redundant()

◆ is_selected()

◆ LoadSolution()

◆ LoadTraceAndCoverage()

◆ LowerBound()

◆ model()

◆ newly_non_removable_subsets()

◆ newly_removable_subsets()

◆ num_coverage_le_1_elements()

◆ num_free_elements()

◆ num_uncovered_elements()

◆ Recompute()

◆ ReportLowerBound()

◆ Select()

◆ trace()