#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, 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_)

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 }

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.

Constructor & Destructor Documentation

◆ NeighborhoodGeneratorHelper()

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

Initialize proto memory.

Definition at line 72 of file cp_model_lns.cc.

Member Function Documentation

◆ ActiveObjectiveVariables()

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

inline

Definition at line 168 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 191 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 156 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 184 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 1172 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 202 of file cp_model_lns.h.

◆ DifficultyMeansFullNeighborhood()

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

inline

Definition at line 175 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 1204 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 1055 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 406 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 116 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 461 of file cp_model_lns.cc.

◆ GetActiveRectangles()

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

Definition at line 468 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 969 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 944 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 502 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 396 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 449 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 271 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 418 of file cp_model_lns.cc.

◆ NumActiveVariables()

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

inline

Definition at line 163 of file cp_model_lns.h.

◆ NumVariables()

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

inline

Definition at line 121 of file cp_model_lns.h.

◆ Parameters()

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

inline

Definition at line 272 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 1190 of file cp_model_lns.cc.

◆ shared_response()

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

inline

Definition at line 274 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 100 of file cp_model_lns.cc.

◆ TaskIsAvailable()

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

inlineoverridevirtual

SubSolver interface.

Implements operations_research::sat::SubSolver.

Definition at line 115 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 212 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 1216 of file cp_model_lns.cc.

◆ VarToConstraint()

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

inline

Definition at line 206 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 283 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

Classes

Public Member Functions

Public Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ NeighborhoodGeneratorHelper()

Member Function Documentation

◆ ActiveObjectiveVariables()

◆ ActiveObjectiveVariablesWhileHoldingLock()

◆ ActiveVariables()

◆ ActiveVariablesWhileHoldingLock()

◆ AddSolutionHinting()

◆ ConstraintToVar()

◆ DifficultyMeansFullNeighborhood()

◆ FixAllVariables()

◆ FixGivenVariables()

◆ FullNeighborhood()

◆ GenerateTask()

◆ GetActiveIntervals()

◆ GetActiveRectangles()

◆ GetRoutingPathBooleanVariables()

◆ GetSchedulingPrecedences()

◆ GetUniqueIntervalSets()

◆ IsActive()

◆ KeepActiveIntervals()

◆ ModelProto()

◆ NoNeighborhood()

◆ NumActiveVariables()

◆ NumVariables()

◆ Parameters()

◆ RelaxGivenVariables()

◆ shared_response()

◆ Synchronize()

◆ TaskIsAvailable()

◆ TypeToConstraints()

◆ UpdatedModelProtoCopy()

◆ VarToConstraint()

Member Data Documentation

◆ graph_mutex_