Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Public Member Functions | List of all members
operations_research::sat::SharedBoundsManager Class Referenceabstract

#include <synchronization.h>

Public Member Functions

 SharedBoundsManager (const CpModelProto &model_proto)
 
void ReportPotentialNewBounds (const std::string &worker_name, absl::Span< const int > variables, absl::Span< const int64_t > new_lower_bounds, absl::Span< const int64_t > new_upper_bounds)
 
void FixVariablesFromPartialSolution (absl::Span< const int64_t > solution, absl::Span< const int > variables_to_fix)
 
int RegisterNewId ()
 
void GetChangedBounds (int id, std::vector< int > *variables, std::vector< int64_t > *new_lower_bounds, std::vector< int64_t > *new_upper_bounds)
 
void UpdateDomains (std::vector< Domain > *domains)
 
void Synchronize ()
 
void LogStatistics (SolverLogger *logger)
 
int NumBoundsExported (absl::string_view worker_name)
 
void LoadDebugSolution (absl::Span< const int64_t > solution)
 
void set_dump_prefix (absl::string_view dump_prefix)
 Debug only. Set dump prefix for solutions written to file.
 

Detailed Description

This class manages a pool of lower and upper bounds on a set of variables in a parallel context.

Definition at line 523 of file synchronization.h.

Constructor & Destructor Documentation

◆ SharedBoundsManager()

operations_research::sat::SharedBoundsManager::SharedBoundsManager ( const CpModelProto & model_proto)
explicit

Fill symmetry data.

Get orbits in term of IntegerVariable.

Fill orbits_.

Fill representative.

Definition at line 832 of file synchronization.cc.

Member Function Documentation

◆ FixVariablesFromPartialSolution()

void operations_research::sat::SharedBoundsManager::FixVariablesFromPartialSolution ( absl::Span< const int64_t > solution,
absl::Span< const int > variables_to_fix )

If we solved a small independent component of the full problem, then we can in most situation fix the solution on this subspace.

Note
because there can be more than one optimal solution on an independent subproblem, it is important to do that in a locked fashion, and reject future incompatible fixing.
this do not work with symmetries. And for now we don't call it when this is the case.
Todo
(user): Because we look at the non-synchronized and up to date bounds, this break determinism if two solution for the same subpart comes at the same time.

This function shouldn't be called if we has symmetry.

Abort if incompatible. Note that we only check the position that we are about to fix. This should be enough. Otherwise we might never accept any solution because the base LNS solution was not the same in some of the variables that we fixed here.

Fix the variables.

This is problematic as we might find a different partial solution. To allow for further investigation, we currently fix it to the debug solution instead.

Definition at line 970 of file synchronization.cc.

◆ GetChangedBounds()

void operations_research::sat::SharedBoundsManager::GetChangedBounds ( int id,
std::vector< int > * variables,
std::vector< int64_t > * new_lower_bounds,
std::vector< int64_t > * new_upper_bounds )

When called, returns the set of bounds improvements since the last time this method was called with the same id.

We need to report the bounds in a deterministic order as it is difficult to guarantee that nothing depend on the order in which the new bounds are processed.

Now that the mutex is released, we can add all symmetric version if any.

Note
alternatively we could do that in the client side, but the complexity will be the same, we will just save some memory that is usually just reused.

Definition at line 1050 of file synchronization.cc.

◆ LoadDebugSolution()

void operations_research::sat::SharedBoundsManager::LoadDebugSolution ( absl::Span< const int64_t > solution)
inline

If non-empty, we will check that all bounds update contains this solution.

Note
this might fail once we reach optimality and we might have wrong bounds, but if it fail before that it can help find bugs.

Definition at line 572 of file synchronization.h.

◆ LogStatistics()

void operations_research::sat::SharedBoundsManager::LogStatistics ( SolverLogger * logger)

Definition at line 1109 of file synchronization.cc.

◆ NumBoundsExported()

int operations_research::sat::SharedBoundsManager::NumBoundsExported ( absl::string_view worker_name)

Definition at line 1123 of file synchronization.cc.

◆ RegisterNewId()

int operations_research::sat::SharedBoundsManager::RegisterNewId ( )

Returns a new id to be used in GetChangedBounds(). This is just an ever increasing sequence starting from zero. Note that the class is not designed to have too many of these.

Definition at line 1032 of file synchronization.cc.

◆ ReportPotentialNewBounds()

void operations_research::sat::SharedBoundsManager::ReportPotentialNewBounds ( const std::string & worker_name,
absl::Span< const int > variables,
absl::Span< const int64_t > new_lower_bounds,
absl::Span< const int64_t > new_upper_bounds )

Reports a set of locally improved variable bounds to the shared bounds manager. The manager will compare these bounds changes against its global state, and incorporate the improving ones.

In the presence of symmetry we only update the representative.

We count -1 so that num_improvements + num_symmetric_improvements corresponds to the number of actual bound improvement.

Definition at line 890 of file synchronization.cc.

◆ set_dump_prefix()

void operations_research::sat::SharedBoundsManager::set_dump_prefix ( absl::string_view dump_prefix)
inline

Debug only. Set dump prefix for solutions written to file.

Definition at line 577 of file synchronization.h.

◆ Synchronize()

void operations_research::sat::SharedBoundsManager::Synchronize ( )

Publishes any new bounds so that GetChangedBounds() will reflect the latest state.

Definition at line 1018 of file synchronization.cc.

◆ UpdateDomains()

void operations_research::sat::SharedBoundsManager::UpdateDomains ( std::vector< Domain > * domains)

This should not be called too often as it lock the class for O(num_variables) time.

Definition at line 1100 of file synchronization.cc.

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