operations_research::sat::InclusionDetector< Storage > Class Template Reference

#include <inclusion.h>

Public Member Functions
	InclusionDetector (const Storage &storage)
void	Reset ()
	Resets the class to an empty state.
void	AddPotentialSubset (int index)
void	AddPotentialSuperset (int index)
void	AddPotentialSet (int index)
void	SetWorkLimit (uint64_t work_limit)
void	DetectInclusions (const std::function< void(int subset, int superset)> &process)
std::vector< bool >	IsInSuperset () const
void	StopProcessingCurrentSubset ()
void	StopProcessingCurrentSuperset ()
void	Stop ()
void	IncreaseWorkDone (uint64_t increase)
int	num_potential_subsets () const
	Stats.
int	num_potential_supersets () const
uint64_t	work_done () const

Detailed Description

template<class Storage>
class operations_research::sat::InclusionDetector< Storage >

An helper class to process many sets of integer in [0, n] and detects all the set included in each others. This is a common operations in presolve, and while it can be slow the algorithm used here is pretty efficient in practice.

The algorithm is based on the SAT preprocessing algorithm to detect clauses that subsumes others. It uses a one-watcher scheme where each subset candidate has only one element watched. To identify all potential subset of a superset, one need to inspect the watch list for all element of the superset candidate.

The number n will be detected automatically but we allocate various vector of size n, so avoid having large integer values in your sets.

All set contents will be accessed via storage_[index]. This can be used with a vector<vector<>> or our CompactVectorVector that we use in a few place. But it can also be anything that support:

• storage_.size()
• range iteration over storage_[index]
• storage_[index].size()

Definition at line 54 of file inclusion.h.

Constructor & Destructor Documentation

InclusionDetector()

template<class Storage >

operations_research::sat::InclusionDetector< Storage >::InclusionDetector ( const Storage & storage )

inlineexplicit

Definition at line 56 of file inclusion.h.

Member Function Documentation

AddPotentialSet()

template<typename Storage >

void operations_research::sat::InclusionDetector< Storage >::AddPotentialSet ( int index )

inline

Definition at line 170 of file inclusion.h.

AddPotentialSubset()

template<typename Storage >

void operations_research::sat::InclusionDetector< Storage >::AddPotentialSubset ( int index )

inline

Adds a candidate set to consider for the next DetectInclusions() call. The argument is an index that will only be used via storage_[index] to get the content of the candidate set.

Note

set with no element are just ignored and will never be returned as part of an inclusion.

Definition at line 182 of file inclusion.h.

AddPotentialSuperset()

template<typename Storage >

void operations_research::sat::InclusionDetector< Storage >::AddPotentialSuperset ( int index )

inline

Definition at line 193 of file inclusion.h.

DetectInclusions()

template<typename Storage >

void operations_research::sat::InclusionDetector< Storage >::DetectInclusions ( const std::function< void(int subset, int superset)> & process )

inline

Finds all subset included in a superset and call "process" on each of the detected inclusion. The std::function argument corresponds to indices passed to the Add*() calls.

The order of detection will be by increasing superset size. For superset with the same size, the order will be deterministic but not specified. And similarly, for a given superset, the order of the included subsets is deterministic but not specified.

Note

only the candidate marked as such can be a subset/superset. For the candidate than can be both and are duplicates (i.e. same set), only one pair will be returned. We will also never return identity inclusion and we always have subset != superset.

No need to do any work in these cases.

Temp data must be ready to use.

Main algo.

Compute the signature and also resize vector if needed. We want a signature that is order invariant and is compatible with inclusion.

Bitset should be cleared.

Find any subset included in current superset.

We make a copy because process() might alter the content of the storage when it returns "stop_with_current_superset_" and we need to clean is_in_superset_ properly.

Todo

(user): Alternatively, we could clean is_in_superset_ in the call to StopProcessingCurrentSuperset() and force client to call it before altering the superset content.

Quick check with signature.

Long check with bitset.

Remove from the watcher list.

Cleanup.

Add new subset candidate to the watchers.

Tricky: If this was also a superset and has been removed, we don't want to watch it!

Choose to watch the one with smallest list.

Stop also performs some cleanup.

Definition at line 206 of file inclusion.h.

IncreaseWorkDone()

template<class Storage >

void operations_research::sat::InclusionDetector< Storage >::IncreaseWorkDone ( uint64_t increase )

inline

The algorithm here can detect many small set included in a big set while only scanning the superset once. So if we do scan the superset in the process function, we can do a lot more work. This is here to reuse the deterministic limit mechanism.

Definition at line 120 of file inclusion.h.

IsInSuperset()

template<class Storage >

std::vector< bool > operations_research::sat::InclusionDetector< Storage >::IsInSuperset ( ) const

inline

Function that should only be used from within "process()". Returns the bitset corresponsing to the elements of the current superset passed to the process() function.

Definition at line 102 of file inclusion.h.

num_potential_subsets()

template<class Storage >

int operations_research::sat::InclusionDetector< Storage >::num_potential_subsets ( ) const

inline

Stats.

Definition at line 123 of file inclusion.h.

num_potential_supersets()

template<class Storage >

int operations_research::sat::InclusionDetector< Storage >::num_potential_supersets ( ) const

inline

Definition at line 124 of file inclusion.h.

Reset()

template<class Storage >

void operations_research::sat::InclusionDetector< Storage >::Reset ( )

inline

Resets the class to an empty state.

Definition at line 59 of file inclusion.h.

SetWorkLimit()

template<class Storage >

void operations_research::sat::InclusionDetector< Storage >::SetWorkLimit ( uint64_t work_limit )

inline

By default we will detect all inclusions. It is possible to make sure we don't do more than O(work_limit) operations and eventually abort early by setting this. Note that we don't reset it on Reset().

This is needed, because for m candidates of size n, we can have O(m ^ 2) inclusions, each requiring O(n) work to check.

Definition at line 81 of file inclusion.h.

Stop()

template<class Storage >

void operations_research::sat::InclusionDetector< Storage >::Stop ( )

inline

Definition at line 109 of file inclusion.h.

StopProcessingCurrentSubset()

template<class Storage >

void operations_research::sat::InclusionDetector< Storage >::StopProcessingCurrentSubset ( )

inline

Function that should only be used from within "process()". Stop will abort the current search. The other two will cause the corresponding candidate set to never appear in any future inclusion.

Definition at line 107 of file inclusion.h.

StopProcessingCurrentSuperset()

template<class Storage >

void operations_research::sat::InclusionDetector< Storage >::StopProcessingCurrentSuperset ( )

inline

Definition at line 108 of file inclusion.h.

work_done()

template<class Storage >

uint64_t operations_research::sat::InclusionDetector< Storage >::work_done ( ) const

inline

Definition at line 125 of file inclusion.h.

---

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

• ortools/sat/inclusion.h