--— Finds a neighbor of the assignment passed --— More...

Inheritance diagram for operations_research::FindOneNeighbor:

Public Member Functions
	FindOneNeighbor (Assignment assignment, IntVar objective, SolutionPool pool, LocalSearchOperator ls_operator, DecisionBuilder sub_decision_builder, const RegularLimit limit, LocalSearchFilterManager *filter_manager)

	~FindOneNeighbor () override

Decision *	Next (Solver *solver) override

std::string	DebugString () const override
	-------— Decision Builder -------—

Public Member Functions inherited from operations_research::DecisionBuilder
	DecisionBuilder ()

	DecisionBuilder (const DecisionBuilder &)=delete
	This type is neither copyable nor movable.

DecisionBuilder &	operator= (const DecisionBuilder &)=delete

	~DecisionBuilder () override

virtual void	AppendMonitors (Solver solver, std::vector< SearchMonitor > *extras)

virtual void	Accept (ModelVisitor *visitor) const

void	set_name (absl::string_view name)

std::string	GetName () const

Public Member Functions inherited from operations_research::BaseObject
	BaseObject ()

	BaseObject (const BaseObject &)=delete
	This type is neither copyable nor movable.

BaseObject &	operator= (const BaseObject &)=delete

virtual	~BaseObject ()

Detailed Description

--— Finds a neighbor of the assignment passed --—

Definition at line 4763 of file local_search.cc.

Constructor & Destructor Documentation

◆ FindOneNeighbor()

operations_research::FindOneNeighbor::FindOneNeighbor	(	Assignment *	assignment,
		IntVar *	objective,
		SolutionPool *	pool,
		LocalSearchOperator *	ls_operator,
		DecisionBuilder *	sub_decision_builder,
		const RegularLimit *	limit,
		LocalSearchFilterManager *	filter_manager )

reference_assignment_ is used to keep track of the last assignment on which operators were started, assignment_ corresponding to the last successful neighbor. last_synchronized_assignment_ keeps track of the last assignment on which filters were synchronized and is used to compute the filter_assignment_delta_ when synchronizing again.

If limit is nullptr, default limit is 1 solution

Todo: (user): Support skipping neighborhood checks for limits accepting more than one solution (e.g. best accept). For now re-enabling systematic checks.

Todo: (user): Support skipping neighborhood checks with LNS (at least on the non-LNS operators).

Definition at line 4803 of file local_search.cc.

◆ ~FindOneNeighbor()

operations_research::FindOneNeighbor::~FindOneNeighbor ( )

inlineoverride

Definition at line 4770 of file local_search.cc.

Member Function Documentation

◆ DebugString()

std::string operations_research::FindOneNeighbor::DebugString ( ) const

inlineoverridevirtual

-------— Decision Builder -------—

Reimplemented from operations_research::DecisionBuilder.

Definition at line 4772 of file local_search.cc.

◆ Next()

Decision * operations_research::FindOneNeighbor::Next ( Solver * s )

overridevirtual

This is the main method of the decision builder class. It must return a decision (an instance of the class Decision). If it returns nullptr, this means that the decision builder has finished its work.

Only called on the first call to Next(), reference_assignment_ has not been synced with assignment_ yet

Keeping the code in case a performance problem forces us to use the old code with a zero test on pool_. reference_assignment_->CopyIntersection(assignment_);

Another assignment is needed to apply the delta

Todo: (user) : SyncNeed(assignment_) ?

All filters must be called for incrementality reasons. Empty deltas must also be sent to incremental filters; can be needed to resync filters on non-incremental (empty) moves.

Todo: (user): Don't call both if no filter is incremental and one of them returned false.

LNS deltas need to be restored

Advancing local search to the current solution without checking.

Todo: (user): support the case were limit_ accepts more than one solution (e.g. best accept).

Note: SynchronizeAll() sets neighbor_found_ to false, force it back to true when skipping checks.

Filtering is not perfect, disabling fast local search and resynchronizing with the last checked solution.

Todo: (user): Restore state of local search operators to make sure we are exploring neighbors in the same order. This can affect the local optimum found.

Reset the last synchronized assignment in case it's no longer up to date or we fail below.

In case the last checked assignment isn't the current one, restore it to make sure the solver knows about it, especially if this is the end of the search.

Todo: (user): Compare assignments in addition to their cost.

If restoring fails this means filtering is not perfect and the solver will consider the last checked assignment.

Keeping the code in case a performance problem forces us to use the old code with a zero test on pool_. reference_assignment_->CopyIntersection(assignment_);

NOTE(user): The last synchronized assignment must be reset here to guarantee filters will be properly synched in case we re-solve using an assignment that wasn't the last accepted and synchronized assignment.

Implements operations_research::DecisionBuilder.

Definition at line 4853 of file local_search.cc.

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

ortools/constraint_solver/local_search.cc