operations_research::sat::SubSolver Class Reference

#include <subsolver.h>

Inheritance diagram for operations_research::sat::SubSolver:

Public Types
enum	SubsolverType { FULL_PROBLEM , FIRST_SOLUTION , INCOMPLETE , HELPER }

Public Member Functions
	SubSolver (absl::string_view name, SubsolverType type)
virtual	~SubSolver ()=default
virtual void	Synchronize ()=0
virtual bool	IsDone ()
virtual bool	TaskIsAvailable ()=0
virtual std::function< void()>	GenerateTask (int64_t task_id)=0
double	deterministic_time () const
std::string	name () const
	Returns the name of this SubSolver. Used in logs.
SubsolverType	type () const
	Returns the type of the subsolver.
void	AddTaskDuration (double duration_in_seconds)
void	NotifySelection ()
void	AddTaskDeterministicDuration (double deterministic_duration)
std::string	TimingInfo () const
std::string	DeterministicTimingInfo () const
double	GetSelectionScore (bool deterministic) const

Detailed Description

The API used for distributing work. Each subsolver can generate tasks and synchronize itself with the rest of the world.

Note

currently only the main thread interact with subsolvers. Only the tasks generated by GenerateTask() are executed in parallel in a threadpool.

Definition at line 44 of file subsolver.h.

Member Enumeration Documentation

SubsolverType

enum operations_research::sat::SubSolver::SubsolverType

Enumerator
FULL_PROBLEM
FIRST_SOLUTION
INCOMPLETE
HELPER

Definition at line 46 of file subsolver.h.

Constructor & Destructor Documentation

SubSolver()

operations_research::sat::SubSolver::SubSolver ( absl::string_view name, SubsolverType type )

inline

Definition at line 48 of file subsolver.h.

~SubSolver()

virtual operations_research::sat::SubSolver::~SubSolver ( )

virtualdefault

Member Function Documentation

AddTaskDeterministicDuration()

void operations_research::sat::SubSolver::AddTaskDeterministicDuration ( double deterministic_duration )

inline

This one need to be called by the Subclasses. Usually from Synchronize(), or from the task itself it we execute a single task at the same time.

Definition at line 114 of file subsolver.h.

AddTaskDuration()

void operations_research::sat::SubSolver::AddTaskDuration ( double duration_in_seconds )

inline

Note

this is protected by the global execution mutex and so it is called sequentially. Subclasses do not need to call this.

Definition at line 102 of file subsolver.h.

deterministic_time()

double operations_research::sat::SubSolver::deterministic_time ( ) const

inline

Returns the total deterministic time spend by the completed tasks before the last Synchronize() call.

Definition at line 92 of file subsolver.h.

DeterministicTimingInfo()

std::string operations_research::sat::SubSolver::DeterministicTimingInfo ( ) const

inline

Todo

(user): remove trailing "\n" from ValueAsString().

Definition at line 128 of file subsolver.h.

GenerateTask()

virtual std::function< void()> operations_research::sat::SubSolver::GenerateTask ( int64_t task_id )

pure virtual

Returns a task to run. The task_id is just an ever increasing counter that correspond to the number of total calls to GenerateTask().

Todo

(user): We could use a more complex selection logic and pass in the deterministic time limit this subtask should run for. Unclear at this stage.

This is only called by the main thread.

Implemented in operations_research::sat::FeasibilityJumpSolver, operations_research::sat::NeighborhoodGeneratorHelper, operations_research::sat::ObjectiveShavingSolver, operations_research::sat::SynchronizationPoint, and operations_research::sat::VariablesShavingSolver.

GetSelectionScore()

double operations_research::sat::SubSolver::GetSelectionScore ( bool deterministic ) const

inline

Returns a score used to compare which tasks to schedule next. We will schedule the LOWER score.

Tricky: Note that this will only be called sequentially. The deterministic time should only be used with the DeterministicLoop() because otherwise it can be updated at the same time as this is called.

If we have little data, we strongly limit the number of task in flight. This is needed if some LNS are stuck for a long time to not just only schedule this type at the beginning.

We assume a "minimum time per task" which will be our base etimation for the average running time of this task.

Definition at line 141 of file subsolver.h.

IsDone()

virtual bool operations_research::sat::SubSolver::IsDone ( )

inlinevirtual

Returns true if this SubSolver is done and its memory can be freed. Note that the *Loop(subsolvers) functions below takes a reference in order to be able to clear the memory of a SubSolver as soon as it is done. Once this is true, the subsolver in question will be deleted and never used again.

This is needed since some subsolve can be done before the overal Solve() is finished. This is the case for first solution subsolvers for instances.

This is only called by the main thread in a sequential fashion. Important: This is only called when there is currently no task from that SubSolver in flight.

Reimplemented in operations_research::sat::FeasibilityJumpSolver.

Definition at line 74 of file subsolver.h.

name()

std::string operations_research::sat::SubSolver::name ( ) const

inline

Returns the name of this SubSolver. Used in logs.

Definition at line 95 of file subsolver.h.

NotifySelection()

void operations_research::sat::SubSolver::NotifySelection ( )

inline

Note

this is protected by the global execution mutex and so it is called sequentially. Subclasses do not need to call this.

Definition at line 110 of file subsolver.h.

Synchronize()

virtual void operations_research::sat::SubSolver::Synchronize ( )

pure virtual

Synchronizes with the external world from this SubSolver point of view. Also incorporate the results of the latest completed tasks if any.

Note(user): The intended implementation for determinism is that tasks update asynchronously (and so non-deterministically) global "shared" classes, but this global state is incorporated by the Subsolver only when Synchronize() is called.

This is only called by the main thread in Subsolver creation order.

Implemented in operations_research::sat::FeasibilityJumpSolver, operations_research::sat::NeighborhoodGeneratorHelper, operations_research::sat::ObjectiveShavingSolver, operations_research::sat::SynchronizationPoint, and operations_research::sat::VariablesShavingSolver.

TaskIsAvailable()

virtual bool operations_research::sat::SubSolver::TaskIsAvailable ( )

pure virtual

Returns true iff GenerateTask() can be called. This is only called by the main thread in a sequential fashion.

Implemented in operations_research::sat::FeasibilityJumpSolver, operations_research::sat::NeighborhoodGeneratorHelper, operations_research::sat::ObjectiveShavingSolver, operations_research::sat::SynchronizationPoint, and operations_research::sat::VariablesShavingSolver.

TimingInfo()

std::string operations_research::sat::SubSolver::TimingInfo ( ) const

inline

Todo

(user): remove trailing "\n" from ValueAsString() or just build the table line directly.

Definition at line 120 of file subsolver.h.

type()

SubsolverType operations_research::sat::SubSolver::type ( ) const

inline

Returns the type of the subsolver.

Definition at line 98 of file subsolver.h.

---

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

• ortools/sat/subsolver.h