operations_research::sat::DecompositionGraphNeighborhoodGenerator Class Reference

#include <cp_model_lns.h>

Inheritance diagram for operations_research::sat::DecompositionGraphNeighborhoodGenerator:

Public Member Functions
	DecompositionGraphNeighborhoodGenerator (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

The idea here is to try to generate a random neighborhood incrementally in such a way that we have at various point a "minimum connection" in term of constraints or variable to the outside world.

This is inspired by what would be a good neighborhood if one where to use a tree decomposition of the constraint-variable graph with small treewidth.

Todo

(user): Doing the full heuristic treewidth decomposition is probably better because when we grow the current neighborhood, just using local connection to the current candidate is probably not enough to orient the search towards a good final neighborhood.

Definition at line 579 of file cp_model_lns.h.

Constructor & Destructor Documentation

DecompositionGraphNeighborhoodGenerator()

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

inlineexplicit

Definition at line 581 of file cp_model_lns.h.

Member Function Documentation

Generate()

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

finalvirtual

Generates a "local" subproblem for the given seed.

The difficulty will be in [0, 1] and is related to the asked neighborhood size (and thus local problem difficulty). A difficulty of 0.0 means empty neighborhood and a difficulty of 1.0 means the full problem. The algorithm should try to generate a neighborhood according to this difficulty which will be dynamically adjusted depending on whether or not we can solve the subproblem in a given time limit.

The given initial_solution should contain a feasible solution to the initial CpModelProto given to this class. Any solution to the returned CPModelProto should also be valid solution to the same initial model.

This function should be thread-safe.

Note(user): The algo is slower than the other graph generator, so we might not want to lock the graph for so long? it is just a reader lock though.

We will grow this incrementally. Index in the graph are first variables then constraints.

We will process var/constraint node by minimum "score".

Initialize elements.

We start by a random active variable.

Note

while num_vars contains all variables, all the fixed variable will have no associated constraint, so we don't want to start from a random variable.

Todo

(user): Does starting by a constraint make sense too?

Pop max-degree from queue and update.

Just for logging.

When the score is zero, we don't need to update anything since the frontier does not grow.

Note

while it might looks bad, the overall complexity of this is in O(num_edge) since we scan each index once and each newly connected vertex once.

The score is exactly the frontier increase in size. This is the same as the min-degree heuristic for the elimination order. Except we only consider connected nodes.

Just for logging.

Implements operations_research::sat::NeighborhoodGenerator.

Definition at line 1558 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