operations_research::sat::SharedTreeManager Class Reference

#include <work_assignment.h>

Public Member Functions
	SharedTreeManager (Model *model)
	SharedTreeManager (const SharedTreeManager &)=delete
int	NumWorkers () const
int	NumNodes () const ABSL_LOCKS_EXCLUDED(mu_)
bool	SyncTree (ProtoTrail &path) ABSL_LOCKS_EXCLUDED(mu_)
void	ReplaceTree (ProtoTrail &path)
	Assigns a path prefix that the worker should explore.
void	CloseTree (ProtoTrail &path, int level)
void	ProposeSplit (ProtoTrail &path, ProtoLiteral decision)
void	Restart ()

Detailed Description

Experimental thread-safe class for managing work assignments between workers. This API is intended to investigate Graeme Gange & Peter Stuckey's proposal "Scalable Parallelization of Learning Solvers". The core idea of this implementation is that workers can maintain several ProtoTrails, and periodically replace the "worst" one. With 1 assignment per worker, this leads to something very similar to Embarassingly Parallel Search.

Definition at line 176 of file work_assignment.h.

Constructor & Destructor Documentation

SharedTreeManager() [1/2]

operations_research::sat::SharedTreeManager::SharedTreeManager ( Model * model )

explicit

Create the root node with a fake literal.

Definition at line 210 of file work_assignment.cc.

SharedTreeManager() [2/2]

operations_research::sat::SharedTreeManager::SharedTreeManager ( const SharedTreeManager & )

delete

Member Function Documentation

CloseTree()

void operations_research::sat::SharedTreeManager::CloseTree	(	ProtoTrail &	path,
		int	level )

Asserts that the subtree in path up to level contains no improving solutions. Clears path.

Definition at line 515 of file work_assignment.cc.

NumNodes()

int operations_research::sat::SharedTreeManager::NumNodes

(

)

const

Definition at line 230 of file work_assignment.cc.

NumWorkers()

int operations_research::sat::SharedTreeManager::NumWorkers ( ) const

inline

Definition at line 181 of file work_assignment.h.

ProposeSplit()

void operations_research::sat::SharedTreeManager::ProposeSplit	(	ProtoTrail &	path,
		ProtoLiteral	decision )

Called by workers in order to split the shared tree. path may or may not be extended by one level, branching on decision.

Todo

(user): Need to write up the shape this creates. This rule will allow twice as many leaves in the preferred subtree.

Definition at line 278 of file work_assignment.cc.

ReplaceTree()

void operations_research::sat::SharedTreeManager::ReplaceTree

(

ProtoTrail &

path

)

Assigns a path prefix that the worker should explore.

Todo

(user): Investigate assigning a random leaf so workers can still improve shared tree bounds.

Definition at line 344 of file work_assignment.cc.

Restart()

void operations_research::sat::SharedTreeManager::Restart ( )

inline

Definition at line 200 of file work_assignment.h.

SyncTree()

bool operations_research::sat::SharedTreeManager::SyncTree

(

ProtoTrail &

path

)

Syncs the state of path with the shared search tree. Clears path and returns false if the assigned subtree is closed or a restart has invalidated the path.

We don't rely on these being empty, but we expect them to be.

Restart after processing updates - we might learn a new objective bound.

Sync lower bounds and implications from the shared tree to path.

Definition at line 235 of file work_assignment.cc.

---

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

• ortools/sat/work_assignment.h
• ortools/sat/work_assignment.cc