Detailed Description

Contains pre-computed information about a given CpModelProto that is meant to be used to generate LNS neighborhood. This class can be shared between more than one generator in order to reduce memory usage.

Note: its implement the SubSolver interface to be able to Synchronize() the bounds of the base problem with the external world.

Definition at line 107 of file cp_model_lns.h.

#include <cp_model_lns.h>

Inheritance diagram for operations_research::sat::NeighborhoodGeneratorHelper:

Classes
struct	ActiveRectangle

Public Member Functions
	NeighborhoodGeneratorHelper (CpModelProto const model_proto, SatParameters const parameters, SharedResponseManager shared_response, ModelSharedTimeLimit global_time_limit, SharedBoundsManager *shared_bounds=nullptr)
bool	TaskIsAvailable () override
	SubSolver interface.
std::function< void()>	GenerateTask (int64_t) override
void	Synchronize () override
int	NumVariables () const
Neighborhood	FixGivenVariables (const CpSolverResponse &base_solution, const Bitset64< int > &variables_to_fix) const
Neighborhood	RelaxGivenVariables (const CpSolverResponse &initial_solution, absl::Span< const int > relaxed_variables) const
Neighborhood	FixAllVariables (const CpSolverResponse &initial_solution) const
Neighborhood	FullNeighborhood () const
	Returns a neighborhood that correspond to the full problem.
Neighborhood	NoNeighborhood () const
void	AddSolutionHinting (const CpSolverResponse &initial_solution, CpModelProto *model_proto) const
bool	IsActive (int var) const ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_)
std::vector< int >	ActiveVariables () const
	Returns the list of "active" variables.
int	NumActiveVariables () const
std::vector< int >	ActiveObjectiveVariables () const
bool	DifficultyMeansFullNeighborhood (double difficulty) const
const std::vector< int > &	ActiveVariablesWhileHoldingLock () const ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_)
std::vector< int >	ActiveObjectiveVariablesWhileHoldingLock () const ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_)
std::vector< int >	ImprovableObjectiveVariablesWhileHoldingLock (const CpSolverResponse &initial_solution) const ABSL_LOCKS_EXCLUDED(domain_mutex_)
const CompactVectorVector< int, int > &	ConstraintToVar () const ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_)
const CompactVectorVector< int, int > &	VarToConstraint () const ABSL_SHARED_LOCKS_REQUIRED(graph_mutex_)
absl::Span< const int >	TypeToConstraints (ConstraintProto::ConstraintCase type) const
	Returns all the constraints indices of a given type.
std::vector< int >	KeepActiveIntervals (absl::Span< const int > unfiltered_intervals, const CpSolverResponse &initial_solution) const
std::vector< int >	GetActiveIntervals (const CpSolverResponse &initial_solution) const
std::vector< ActiveRectangle >	GetActiveRectangles (const CpSolverResponse &initial_solution) const
std::vector< std::vector< int > >	GetUniqueIntervalSets () const
std::vector< std::vector< int > >	GetRoutingPathBooleanVariables (const CpSolverResponse &initial_solution) const
std::vector< std::pair< int, int > >	GetSchedulingPrecedences (const absl::flat_hash_set< int > &ignored_intervals, const CpSolverResponse &initial_solution, absl::BitGenRef random) const
CpModelProto	UpdatedModelProtoCopy () const
	Returns a copy of the problem proto with updated domains.
const CpModelProto &	ModelProto () const
const SatParameters &	Parameters () const
const SharedResponseManager &	shared_response () const
Public Member Functions inherited from operations_research::sat::SubSolver
	SubSolver (absl::string_view name, SubsolverType type)
virtual	~SubSolver ()=default
virtual bool	IsDone ()
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

Public Attributes
absl::Mutex	graph_mutex_

Additional Inherited Members
Public Types inherited from operations_research::sat::SubSolver
enum	SubsolverType { FULL_PROBLEM , FIRST_SOLUTION , INCOMPLETE , HELPER }

Constructor & Destructor Documentation

◆ NeighborhoodGeneratorHelper()

operations_research::sat::NeighborhoodGeneratorHelper::NeighborhoodGeneratorHelper	(	CpModelProto const *	model_proto,
		SatParameters const *	parameters,
		SharedResponseManager *	shared_response,
		ModelSharedTimeLimit *	global_time_limit,
		SharedBoundsManager *	shared_bounds = nullptr )

Initialize proto memory.

Definition at line 73 of file cp_model_lns.cc.

Member Function Documentation

◆ ActiveObjectiveVariables()

std::vector< int > operations_research::sat::NeighborhoodGeneratorHelper::ActiveObjectiveVariables ( ) const

inline

Definition at line 169 of file cp_model_lns.h.

◆ ActiveObjectiveVariablesWhileHoldingLock()

std::vector< int > operations_research::sat::NeighborhoodGeneratorHelper::ActiveObjectiveVariablesWhileHoldingLock ( ) const

inline

Returns the vector of active objective variables. The graph_mutex_ must be locked before calling this method.

Definition at line 192 of file cp_model_lns.h.

◆ ActiveVariables()

std::vector< int > operations_research::sat::NeighborhoodGeneratorHelper::ActiveVariables ( ) const

inline

Returns the list of "active" variables.

Definition at line 157 of file cp_model_lns.h.

◆ ActiveVariablesWhileHoldingLock()

const std::vector< int > & operations_research::sat::NeighborhoodGeneratorHelper::ActiveVariablesWhileHoldingLock ( ) const

inline

Returns the vector of active variables. The graph_mutex_ must be locked before calling this method.

Definition at line 185 of file cp_model_lns.h.

◆ AddSolutionHinting()

void operations_research::sat::NeighborhoodGeneratorHelper::AddSolutionHinting	(	const CpSolverResponse &	initial_solution,
		CpModelProto *	model_proto ) const

Adds solution hinting to the neighborhood from the value of the initial solution.

Set the current solution as a hint.

Definition at line 1185 of file cp_model_lns.cc.

◆ ConstraintToVar()

const CompactVectorVector< int, int > & operations_research::sat::NeighborhoodGeneratorHelper::ConstraintToVar ( ) const

inline

Constraints <-> Variables graph. Important:

The constraint index is NOT related to the one in the cp_model.
Only non-constant var are listed in ConstraintToVar().

Definition at line 211 of file cp_model_lns.h.

◆ DifficultyMeansFullNeighborhood()

bool operations_research::sat::NeighborhoodGeneratorHelper::DifficultyMeansFullNeighborhood ( double difficulty ) const

inline

Definition at line 176 of file cp_model_lns.h.

◆ FixAllVariables()

Neighborhood operations_research::sat::NeighborhoodGeneratorHelper::FixAllVariables ( const CpSolverResponse & initial_solution ) const

Returns a trivial model by fixing all active variables to the initial solution values.

Definition at line 1217 of file cp_model_lns.cc.

◆ FixGivenVariables()

Neighborhood operations_research::sat::NeighborhoodGeneratorHelper::FixGivenVariables	(	const CpSolverResponse &	base_solution,
		const Bitset64< int > &	variables_to_fix ) const

Returns the LNS fragment where the given variables are fixed to the value they take in the given solution.

Todo: (user): Maybe relax all variables in the objective when the number is small or negligible compared to the number of variables.

Fill in neighborhood.delta all variable domains.

We only copy the name in debug mode.

Note the use of DomainInProtoContains() instead of ReadDomainFromProto() as the later is slower and allocate memory.

If under the updated domain, the base solution is no longer valid, We should probably regenerate this neighborhood. But for now we just do a best effort and take the closest value.

Fill some statistic fields and detect if we cover a full component.

Todo: (user): If there is just one component, we can skip some computation.

If the objective domain might cut the optimal solution, we cannot exploit the connected components. We compute this outside the mutex to avoid any deadlock risk.

Todo: (user): We could handle some complex domain (size > 2).

Todo: (user): force better objective? Note that this is already done when the hint above is successfully loaded (i.e. if it passes the presolve correctly) since the solver will try to find better solution than the current one.

Definition at line 1068 of file cp_model_lns.cc.

◆ FullNeighborhood()

Neighborhood operations_research::sat::NeighborhoodGeneratorHelper::FullNeighborhood ( ) const

Returns a neighborhood that correspond to the full problem.

Definition at line 419 of file cp_model_lns.cc.

◆ GenerateTask()

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

inlineoverridevirtual

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.

Implements operations_research::sat::SubSolver.

Definition at line 117 of file cp_model_lns.h.

◆ GetActiveIntervals()

std::vector< int > operations_research::sat::NeighborhoodGeneratorHelper::GetActiveIntervals ( const CpSolverResponse & initial_solution ) const

Returns the list of indices of active interval constraints according to the initial_solution and the parameter lns_focus_on_performed_intervals. If true, this method returns the list of performed intervals in the solution. If false, it returns all intervals of the model.

Definition at line 474 of file cp_model_lns.cc.

◆ GetActiveRectangles()

std::vector< NeighborhoodGeneratorHelper::ActiveRectangle > operations_research::sat::NeighborhoodGeneratorHelper::GetActiveRectangles ( const CpSolverResponse & initial_solution ) const

Definition at line 481 of file cp_model_lns.cc.

◆ GetRoutingPathBooleanVariables()

std::vector< std::vector< int > > operations_research::sat::NeighborhoodGeneratorHelper::GetRoutingPathBooleanVariables ( const CpSolverResponse & initial_solution ) const

Returns one sub-vector per circuit or per individual vehicle circuit in a routes constraints. Each circuit is non empty, and does not contain any self-looping arcs. Path are sorted, starting from the arc with the lowest tail index, and going in sequence up to the last arc before the circuit is closed. Each entry correspond to the Boolean variable of the arc literal on the circuit.

Collect arcs.

Skip unselected arcs.

Ignore self loops.

Unroll the path.

Collect route starts and arcs.

Skip unselected arcs.

Ignore self loops.

Unroll all routes.

Definition at line 982 of file cp_model_lns.cc.

◆ GetSchedulingPrecedences()

std::vector< std::pair< int, int > > operations_research::sat::NeighborhoodGeneratorHelper::GetSchedulingPrecedences	(	const absl::flat_hash_set< int > &	ignored_intervals,
		const CpSolverResponse &	initial_solution,
		absl::BitGenRef	random ) const

Returns all precedences extracted from the scheduling constraint and the initial solution. The precedences will be sorted by the natural order the pairs of integers.

Todo: (user): We could scan for model precedences and add them to the list of precedences. This could enable more simplifications in the transitive reduction phase.

Todo: (user): Reduce precedence graph

Definition at line 957 of file cp_model_lns.cc.

◆ GetUniqueIntervalSets()

std::vector< std::vector< int > > operations_research::sat::NeighborhoodGeneratorHelper::GetUniqueIntervalSets ( ) const

Returns the set of unique intervals list appearing in a no_overlap, cumulative, or as a dimension of a no_overlap_2d constraint.

Definition at line 515 of file cp_model_lns.cc.

◆ ImprovableObjectiveVariablesWhileHoldingLock()

std::vector< int > operations_research::sat::NeighborhoodGeneratorHelper::ImprovableObjectiveVariablesWhileHoldingLock ( const CpSolverResponse & initial_solution ) const

Returns the vector of objective variables that are not already at their best possible value. The graph_mutex_ must be locked before calling this method.

Definition at line 1334 of file cp_model_lns.cc.

◆ IsActive()

bool operations_research::sat::NeighborhoodGeneratorHelper::IsActive ( int var ) const

Indicates if the variable can be frozen. It happens if the variable is non constant, and if it is a decision variable, or if focus_on_decision_variables is false.

Definition at line 409 of file cp_model_lns.cc.

◆ KeepActiveIntervals()

std::vector< int > operations_research::sat::NeighborhoodGeneratorHelper::KeepActiveIntervals	(	absl::Span< const int >	unfiltered_intervals,
		const CpSolverResponse &	initial_solution ) const

Filters a vector of intervals against the initial_solution, and returns only the active intervals.

Definition at line 462 of file cp_model_lns.cc.

◆ ModelProto()

const CpModelProto & operations_research::sat::NeighborhoodGeneratorHelper::ModelProto ( ) const

inline

The initial problem.

Note: the domain of the variables are not updated here.

Definition at line 280 of file cp_model_lns.h.

◆ NoNeighborhood()

Neighborhood operations_research::sat::NeighborhoodGeneratorHelper::NoNeighborhood ( ) const

Returns a neighborhood that will just be skipped. It usually indicate that the generator failed to generated a neighborhood.

Definition at line 431 of file cp_model_lns.cc.

◆ NumActiveVariables()

int operations_research::sat::NeighborhoodGeneratorHelper::NumActiveVariables ( ) const

inline

Definition at line 164 of file cp_model_lns.h.

◆ NumVariables()

int operations_research::sat::NeighborhoodGeneratorHelper::NumVariables ( ) const

inline

Definition at line 122 of file cp_model_lns.h.

◆ Parameters()

const SatParameters & operations_research::sat::NeighborhoodGeneratorHelper::Parameters ( ) const

inline

Definition at line 281 of file cp_model_lns.h.

◆ RelaxGivenVariables()

Neighborhood operations_research::sat::NeighborhoodGeneratorHelper::RelaxGivenVariables	(	const CpSolverResponse &	initial_solution,
		absl::Span< const int >	relaxed_variables ) const

Returns the LNS fragment which will relax all inactive variables and all variables in relaxed_variables.

Definition at line 1203 of file cp_model_lns.cc.

◆ shared_response()

const SharedResponseManager & operations_research::sat::NeighborhoodGeneratorHelper::shared_response ( ) const

inline

Definition at line 283 of file cp_model_lns.h.

◆ Synchronize()

void operations_research::sat::NeighborhoodGeneratorHelper::Synchronize ( )

overridevirtual

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.

This can mean two things: 1/ This variable is a normal one and the problem is UNSAT or 2/ This variable is optional, and its associated literal must be set to false.

Currently, we wait for any full solver to pick the crossing bounds and do the correct stuff on their own. We do not want to have empty domain in the proto as this would means INFEASIBLE. So we just ignore such bounds here.

Todo: (user): We could set the optional literal to false directly in the bound sharing manager. We do have to be careful that all the different solvers have the same optionality definition though.

Only trigger the computation if needed.

Implements operations_research::sat::SubSolver.

Definition at line 103 of file cp_model_lns.cc.

◆ TaskIsAvailable()

bool operations_research::sat::NeighborhoodGeneratorHelper::TaskIsAvailable ( )

inlineoverridevirtual

SubSolver interface.

Implements operations_research::sat::SubSolver.

Definition at line 116 of file cp_model_lns.h.

◆ TypeToConstraints()

absl::Span< const int > operations_research::sat::NeighborhoodGeneratorHelper::TypeToConstraints ( ConstraintProto::ConstraintCase type ) const

inline

Returns all the constraints indices of a given type.

Definition at line 221 of file cp_model_lns.h.

◆ UpdatedModelProtoCopy()

CpModelProto operations_research::sat::NeighborhoodGeneratorHelper::UpdatedModelProtoCopy ( ) const

Returns a copy of the problem proto with updated domains.

Definition at line 1229 of file cp_model_lns.cc.

◆ VarToConstraint()

const CompactVectorVector< int, int > & operations_research::sat::NeighborhoodGeneratorHelper::VarToConstraint ( ) const

inline

Definition at line 215 of file cp_model_lns.h.

Member Data Documentation

◆ graph_mutex_

absl::Mutex operations_research::sat::NeighborhoodGeneratorHelper::graph_mutex_

mutable

Todo: (user): Refactor the class to be thread-safe instead, it should be safer and more easily maintainable. Some complication with accessing the variable<->constraint graph efficiently though.

Note: This mutex needs to be public for thread annotations.

Definition at line 292 of file cp_model_lns.h.

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

ortools/sat/cp_model_lns.h
ortools/sat/cp_model_lns.cc

Detailed Description

Classes

Public Member Functions

Public Attributes

Additional Inherited Members

Constructor & Destructor Documentation

◆ NeighborhoodGeneratorHelper()

Member Function Documentation

◆ ActiveObjectiveVariables()

◆ ActiveObjectiveVariablesWhileHoldingLock()

◆ ActiveVariables()

◆ ActiveVariablesWhileHoldingLock()

◆ AddSolutionHinting()

◆ ConstraintToVar()

◆ DifficultyMeansFullNeighborhood()

◆ FixAllVariables()

◆ FixGivenVariables()

◆ FullNeighborhood()

◆ GenerateTask()

◆ GetActiveIntervals()

◆ GetActiveRectangles()

◆ GetRoutingPathBooleanVariables()

◆ GetSchedulingPrecedences()

◆ GetUniqueIntervalSets()

◆ ImprovableObjectiveVariablesWhileHoldingLock()

◆ IsActive()

◆ KeepActiveIntervals()

◆ ModelProto()

◆ NoNeighborhood()

◆ NumActiveVariables()

◆ NumVariables()

◆ Parameters()

◆ RelaxGivenVariables()

◆ shared_response()

◆ Synchronize()

◆ TaskIsAvailable()

◆ TypeToConstraints()

◆ UpdatedModelProtoCopy()

◆ VarToConstraint()

Member Data Documentation

◆ graph_mutex_