operations_research::sat::VariableGraphNeighborhoodGenerator Class Reference

#include <cp_model_lns.h>

Inheritance diagram for operations_research::sat::VariableGraphNeighborhoodGenerator:

Public Member Functions
	VariableGraphNeighborhoodGenerator (NeighborhoodGeneratorHelper const *helper, absl::string_view name)
Neighborhood	Generate (const CpSolverResponse &initial_solution, double difficulty, absl::BitGenRef random) final
Public Member Functions inherited from operations_research::sat::NeighborhoodGenerator
	NeighborhoodGenerator (absl::string_view name, NeighborhoodGeneratorHelper const *helper)
virtual	~NeighborhoodGenerator ()=default
virtual bool	ReadyToGenerate () const
	Returns true if the neighborhood generator can generate a neighborhood.
double	GetUCBScore (int64_t total_num_calls) const
void	AddSolveData (SolveData data)
double	Synchronize ()
std::string	name () const
	Returns a short description of the generator.
int64_t	num_calls () const
	Number of times this generator was called.
int64_t	num_fully_solved_calls () const
	Number of time the neighborhood was fully solved (OPTIMAL/INFEASIBLE).
int64_t	num_improving_calls () const
	Out of num_calls(), how many improved the given solution.
int64_t	num_consecutive_non_improving_calls () const
double	difficulty () const
	The current difficulty of this generator.
double	deterministic_limit () const
	The current time limit that the sub-solve should use on this generator.

Additional Inherited Members
Protected Attributes inherited from operations_research::sat::NeighborhoodGenerator
const std::string	name_
const NeighborhoodGeneratorHelper &	helper_
absl::Mutex	generator_mutex_

Detailed Description

Pick a random subset of variables that are constructed by a BFS in the variable <-> constraint graph. That is, pick a random variable, then all the variable connected by some constraint to the first one, and so on. The variable of the last "level" are selected randomly.

Note

in the presence of connected component, this works correctly already.

Definition at line 535 of file cp_model_lns.h.

Constructor & Destructor Documentation

VariableGraphNeighborhoodGenerator()

operations_research::sat::VariableGraphNeighborhoodGenerator::VariableGraphNeighborhoodGenerator ( NeighborhoodGeneratorHelper const * helper, absl::string_view name )

inlineexplicit

Definition at line 537 of file cp_model_lns.h.

Member Function Documentation

Generate()

Neighborhood operations_research::sat::VariableGraphNeighborhoodGenerator::Generate ( const CpSolverResponse & initial_solution, double difficulty, absl::BitGenRef random )

finalvirtual

Note

even if difficulty means full neighborhood, we go through the generation process to never get out of a connected components.

It is important complexity wise to never scan a constraint twice!

The number of active variables can decrease asynchronously. We read the exact number while locked.

Collect all the variables that appears in the same constraints as visited_variables[i].

We always randomize to change the partial subgraph explored afterwards.

Implements operations_research::sat::NeighborhoodGenerator.

Definition at line 1335 of file cp_model_lns.cc.

---

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

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