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 200 of file work_assignment.h.

#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 ()

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 218 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 532 of file work_assignment.cc.

◆ NumNodes()

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

Definition at line 239 of file work_assignment.cc.

◆ NumWorkers()

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

inline

Definition at line 205 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 292 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 360 of file work_assignment.cc.

◆ Restart()

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

inline

Definition at line 224 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 244 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