operations_research::sat::SharedSolutionRepository< ValueType > Class Template Reference

#include <synchronization.h>

Classes
struct	Solution
	The solution format used by this class. More...

Public Member Functions
	SharedSolutionRepository (int num_solutions_to_keep, absl::string_view name="")
int	NumSolutions () const
Solution	GetSolution (int index) const
	Returns the solution i where i must be smaller than NumSolutions().
ValueType	GetVariableValueInSolution (int var_index, int solution_index) const
Solution	GetRandomBiasedSolution (absl::BitGenRef random) const
	Returns a random solution biased towards good solutions.
void	Add (const Solution &solution)
void	Synchronize ()
std::vector< std::string >	TableLineStats () const

Protected Member Functions
void	AddInternal (const Solution &solution) ABSL_EXCLUSIVE_LOCKS_REQUIRED(mutex_)
	Helper method for adding the solutions once the mutex is acquired.
int64_t num_added_	ABSL_GUARDED_BY (mutex_)=0
int64_t num_ignored_	ABSL_GUARDED_BY (mutex_)=0
int64_t num_queried_	ABSL_GUARDED_BY (mutex_)=0
int64_t num_synchronization_	ABSL_GUARDED_BY (mutex_)=0
std::vector< int > tmp_indices_	ABSL_GUARDED_BY (mutex_)
std::vector< Solution > solutions_	ABSL_GUARDED_BY (mutex_)
std::vector< Solution > new_solutions_	ABSL_GUARDED_BY (mutex_)

Protected Attributes
const std::string	name_
const int	num_solutions_to_keep_
absl::Mutex	mutex_

Detailed Description

template<typename ValueType>
class operations_research::sat::SharedSolutionRepository< ValueType >

Thread-safe. Keeps a set of n unique best solution found so far.

Todo

(user): Maybe add some criteria to only keep solution with an objective really close to the best solution.

Definition at line 56 of file synchronization.h.

Constructor & Destructor Documentation

SharedSolutionRepository()

template<typename ValueType >

operations_research::sat::SharedSolutionRepository< ValueType >::SharedSolutionRepository ( int num_solutions_to_keep, absl::string_view name = "" )

inlineexplicit

Definition at line 58 of file synchronization.h.

Member Function Documentation

ABSL_GUARDED_BY() [1/7]

template<typename ValueType >

std::vector< int > tmp_indices_ operations_research::sat::SharedSolutionRepository< ValueType >::ABSL_GUARDED_BY ( mutex_ )

mutableprotected

Our two solutions pools, the current one and the new one that will be merged into the current one on each Synchronize() calls.

ABSL_GUARDED_BY() [2/7]

template<typename ValueType >

std::vector< Solution > solutions_ operations_research::sat::SharedSolutionRepository< ValueType >::ABSL_GUARDED_BY ( mutex_ )

protected

ABSL_GUARDED_BY() [3/7]

template<typename ValueType >

std::vector< Solution > new_solutions_ operations_research::sat::SharedSolutionRepository< ValueType >::ABSL_GUARDED_BY ( mutex_ )

protected

ABSL_GUARDED_BY() [4/7]

template<typename ValueType >

int64_t num_added_ operations_research::sat::SharedSolutionRepository< ValueType >::ABSL_GUARDED_BY ( mutex_ )

protectedpure virtual

ABSL_GUARDED_BY() [5/7]

template<typename ValueType >

int64_t num_ignored_ operations_research::sat::SharedSolutionRepository< ValueType >::ABSL_GUARDED_BY ( mutex_ )

protectedpure virtual

ABSL_GUARDED_BY() [6/7]

template<typename ValueType >

int64_t num_queried_ operations_research::sat::SharedSolutionRepository< ValueType >::ABSL_GUARDED_BY ( mutex_ )

mutableprotectedpure virtual

ABSL_GUARDED_BY() [7/7]

template<typename ValueType >

int64_t num_synchronization_ operations_research::sat::SharedSolutionRepository< ValueType >::ABSL_GUARDED_BY ( mutex_ )

protectedpure virtual

Add()

template<typename ValueType >

void operations_research::sat::SharedSolutionRepository< ValueType >::Add

(

const Solution &

solution

)

Add a new solution. Note that it will not be added to the pool of solution right away. One must call Synchronize for this to happen.

Works in O(num_solutions_to_keep_).

Definition at line 683 of file synchronization.h.

AddInternal()

template<typename ValueType >

void operations_research::sat::SharedSolutionRepository< ValueType >::AddInternal ( const Solution & solution )

protected

Helper method for adding the solutions once the mutex is acquired.

Do not add identical solution.

Definition at line 690 of file synchronization.h.

GetRandomBiasedSolution()

template<typename ValueType >

SharedSolutionRepository< ValueType >::Solution operations_research::sat::SharedSolutionRepository< ValueType >::GetRandomBiasedSolution

(

absl::BitGenRef

random

)

const

Returns a random solution biased towards good solutions.

Todo

(user): Experiments on the best distribution.

As long as we have solution with the best objective that haven't been explored too much, we select one uniformly. Otherwise, we select a solution from the pool uniformly.

Note(user): Because of the increase of num_selected, this is dependent on the order of call. It should be fine for "determinism" because we do generate the task of a batch always in the same order.

Select all the best solution with a low enough selection count.

Definition at line 647 of file synchronization.h.

GetSolution()

template<typename ValueType >

SharedSolutionRepository< ValueType >::Solution operations_research::sat::SharedSolutionRepository< ValueType >::GetSolution

(

int

index

)

const

Returns the solution i where i must be smaller than NumSolutions().

Definition at line 631 of file synchronization.h.

GetVariableValueInSolution()

template<typename ValueType >

ValueType operations_research::sat::SharedSolutionRepository< ValueType >::GetVariableValueInSolution	(	int	var_index,
		int	solution_index ) const

Returns the variable value of variable 'var_index' from solution 'solution_index' where solution_index must be smaller than NumSolutions() and 'var_index' must be smaller than number of variables.

Definition at line 638 of file synchronization.h.

NumSolutions()

template<typename ValueType >

int operations_research::sat::SharedSolutionRepository< ValueType >::NumSolutions

(

)

const

Returns the number of current solution in the pool. This will never decrease.

Definition at line 624 of file synchronization.h.

Synchronize()

template<typename ValueType >

void operations_research::sat::SharedSolutionRepository< ValueType >::Synchronize

(

)

Updates the current pool of solution with the one recently added. Note that we use a stable ordering of solutions, so the final pool will be independent on the order of the calls to AddSolution() provided that the set of added solutions is the same.

Works in O(num_solutions_to_keep_).

We use a stable sort to keep the num_selected count for the already existing solutions.

Todo

(user): Introduce a notion of orthogonality to diversify the pool?

Definition at line 712 of file synchronization.h.

TableLineStats()

template<typename ValueType >

std::vector< std::string > operations_research::sat::SharedSolutionRepository< ValueType >::TableLineStats ( ) const

inline

Definition at line 122 of file synchronization.h.

Member Data Documentation

mutex_

template<typename ValueType >

absl::Mutex operations_research::sat::SharedSolutionRepository< ValueType >::mutex_

mutableprotected

Definition at line 137 of file synchronization.h.

name_

template<typename ValueType >

const std::string operations_research::sat::SharedSolutionRepository< ValueType >::name_

protected

Definition at line 134 of file synchronization.h.

num_solutions_to_keep_

template<typename ValueType >

const int operations_research::sat::SharedSolutionRepository< ValueType >::num_solutions_to_keep_

protected

Definition at line 135 of file synchronization.h.

---

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

• ortools/sat/synchronization.h