Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Protected Attributes | List of all members
operations_research::sat::NeighborhoodGenerator Class Referenceabstract

Base class for a CpModelProto neighborhood generator. More...

#include <cp_model_lns.h>

Inheritance diagram for operations_research::sat::NeighborhoodGenerator:
operations_research::sat::ArcGraphNeighborhoodGenerator operations_research::sat::ConstraintGraphNeighborhoodGenerator operations_research::sat::DecompositionGraphNeighborhoodGenerator operations_research::sat::LocalBranchingLpBasedNeighborhoodGenerator operations_research::sat::RandomIntervalSchedulingNeighborhoodGenerator operations_research::sat::RandomPrecedenceSchedulingNeighborhoodGenerator operations_research::sat::RandomPrecedencesPackingNeighborhoodGenerator operations_research::sat::RandomRectanglesPackingNeighborhoodGenerator operations_research::sat::RectanglesPackingRelaxOneNeighborhoodGenerator operations_research::sat::RectanglesPackingRelaxTwoNeighborhoodsGenerator operations_research::sat::RelaxRandomConstraintsGenerator operations_research::sat::RelaxRandomVariablesGenerator operations_research::sat::RelaxationInducedNeighborhoodGenerator operations_research::sat::RoutingFullPathNeighborhoodGenerator operations_research::sat::RoutingPathNeighborhoodGenerator operations_research::sat::RoutingRandomNeighborhoodGenerator operations_research::sat::SchedulingResourceWindowsNeighborhoodGenerator operations_research::sat::SchedulingTimeWindowNeighborhoodGenerator operations_research::sat::SlicePackingNeighborhoodGenerator operations_research::sat::VariableGraphNeighborhoodGenerator

Classes

struct  SolveData
 Adds solve data about one "solved" neighborhood. More...
 

Public Types

using ActiveRectangle = NeighborhoodGeneratorHelper::ActiveRectangle
 

Public Member Functions

 NeighborhoodGenerator (absl::string_view name, NeighborhoodGeneratorHelper const *helper)
 
virtual ~NeighborhoodGenerator ()=default
 
virtual Neighborhood Generate (const CpSolverResponse &initial_solution, SolveData &data, absl::BitGenRef random)=0
 
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.
 

Protected Attributes

const std::string name_
 
const NeighborhoodGeneratorHelper & helper_
 
absl::Mutex generator_mutex_
 
double deterministic_limit_ = 0.1
 

Detailed Description

Base class for a CpModelProto neighborhood generator.

Definition at line 375 of file cp_model_lns.h.

Member Typedef Documentation

◆ ActiveRectangle

using operations_research::sat::NeighborhoodGenerator::ActiveRectangle = NeighborhoodGeneratorHelper::ActiveRectangle

Definition at line 386 of file cp_model_lns.h.

Constructor & Destructor Documentation

◆ NeighborhoodGenerator()

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

Definition at line 377 of file cp_model_lns.h.

◆ ~NeighborhoodGenerator()

virtual operations_research::sat::NeighborhoodGenerator::~NeighborhoodGenerator ( )
virtualdefault

Member Function Documentation

◆ AddSolveData()

void operations_research::sat::NeighborhoodGenerator::AddSolveData ( SolveData data)
inline

Definition at line 459 of file cp_model_lns.h.

◆ deterministic_limit()

double operations_research::sat::NeighborhoodGenerator::deterministic_limit ( ) const
inline

The current time limit that the sub-solve should use on this generator.

Definition at line 505 of file cp_model_lns.h.

◆ difficulty()

double operations_research::sat::NeighborhoodGenerator::difficulty ( ) const
inline

The current difficulty of this generator.

Definition at line 499 of file cp_model_lns.h.

◆ Generate()

virtual Neighborhood operations_research::sat::NeighborhoodGenerator::Generate ( const CpSolverResponse & initial_solution,
SolveData & data,
absl::BitGenRef random )
pure virtual

Generates a "local" subproblem for the given seed.

The data,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.

Implemented in operations_research::sat::ArcGraphNeighborhoodGenerator, operations_research::sat::ConstraintGraphNeighborhoodGenerator, operations_research::sat::DecompositionGraphNeighborhoodGenerator, operations_research::sat::LocalBranchingLpBasedNeighborhoodGenerator, operations_research::sat::RandomIntervalSchedulingNeighborhoodGenerator, operations_research::sat::RandomPrecedenceSchedulingNeighborhoodGenerator, operations_research::sat::RandomPrecedencesPackingNeighborhoodGenerator, operations_research::sat::RandomRectanglesPackingNeighborhoodGenerator, operations_research::sat::RectanglesPackingRelaxOneNeighborhoodGenerator, operations_research::sat::RectanglesPackingRelaxTwoNeighborhoodsGenerator, operations_research::sat::RelaxationInducedNeighborhoodGenerator, operations_research::sat::RelaxRandomConstraintsGenerator, operations_research::sat::RelaxRandomVariablesGenerator, operations_research::sat::RoutingFullPathNeighborhoodGenerator, operations_research::sat::RoutingPathNeighborhoodGenerator, operations_research::sat::RoutingRandomNeighborhoodGenerator, operations_research::sat::SchedulingResourceWindowsNeighborhoodGenerator, operations_research::sat::SchedulingTimeWindowNeighborhoodGenerator, operations_research::sat::SlicePackingNeighborhoodGenerator, and operations_research::sat::VariableGraphNeighborhoodGenerator.

◆ GetUCBScore()

double operations_research::sat::NeighborhoodGenerator::GetUCBScore ( int64_t total_num_calls) const

Uses UCB1 algorithm to compute the score (Multi armed bandit problem). Details are at https://lilianweng.github.io/lil-log/2018/01/23/the-multi-armed-bandit-problem-and-its-solutions.html. 'total_num_calls' should be the sum of calls across all generators part of the multi armed bandit problem. If the generator is called less than 10 times then the method returns infinity as score in order to get more data about the generator performance.

Definition at line 1230 of file cp_model_lns.cc.

◆ name()

std::string operations_research::sat::NeighborhoodGenerator::name ( ) const
inline

Returns a short description of the generator.

Definition at line 470 of file cp_model_lns.h.

◆ num_calls()

int64_t operations_research::sat::NeighborhoodGenerator::num_calls ( ) const
inline

Number of times this generator was called.

Definition at line 473 of file cp_model_lns.h.

◆ num_consecutive_non_improving_calls()

int64_t operations_research::sat::NeighborhoodGenerator::num_consecutive_non_improving_calls ( ) const
inline

Returns the number of the last calls to this generator that didn't improve the best solution. Note that this count improvement to the best known solution not the base one used to generate one neighborhood.

Definition at line 493 of file cp_model_lns.h.

◆ num_fully_solved_calls()

int64_t operations_research::sat::NeighborhoodGenerator::num_fully_solved_calls ( ) const
inline

Number of time the neighborhood was fully solved (OPTIMAL/INFEASIBLE).

Definition at line 479 of file cp_model_lns.h.

◆ num_improving_calls()

int64_t operations_research::sat::NeighborhoodGenerator::num_improving_calls ( ) const
inline

Out of num_calls(), how many improved the given solution.

Definition at line 485 of file cp_model_lns.h.

◆ ReadyToGenerate()

bool operations_research::sat::NeighborhoodGenerator::ReadyToGenerate ( ) const
virtual

Returns true if the neighborhood generator can generate a neighborhood.

Reimplemented in operations_research::sat::RelaxationInducedNeighborhoodGenerator.

Definition at line 1226 of file cp_model_lns.cc.

◆ Synchronize()

double operations_research::sat::NeighborhoodGenerator::Synchronize ( )

Process all the recently added solve data and update this generator score and difficulty. This returns the sum of the deterministic time of each SolveData.

To make the whole update process deterministic, we currently sort the SolveData.

This will be used to update the difficulty of this neighborhood.

INFEASIBLE or OPTIMAL means that we "fully solved" the local problem. If we didn't, then we cannot be sure that there is no improving solution in that neighborhood.

It seems to make more sense to compare the new objective to the base solution objective, not the best one. However this causes issue in the logic below because on some problems the neighborhood can always lead to a better "new objective" if the base solution wasn't the best one.

This might not be a final solution, but it does work ok for now.

Confusing: this one is however comparing to the base solution objective.

Todo
(user): Weight more recent data. degrade the current average to forget old learnings.

Update the difficulty.

Bump the time limit if we saw no better solution in the last few calls. This means that as the search progress, we likely spend more and more time trying to solve individual neighborhood.

Todo
(user): experiment with resetting the time limit if a solution is found.

We do not want the limit to go to high. Intuitively, the goal is to try out a lot of neighborhoods, not just spend a lot of time on a few.

Definition at line 1237 of file cp_model_lns.cc.

Member Data Documentation

◆ deterministic_limit_

double operations_research::sat::NeighborhoodGenerator::deterministic_limit_ = 0.1
protected

Definition at line 514 of file cp_model_lns.h.

◆ generator_mutex_

absl::Mutex operations_research::sat::NeighborhoodGenerator::generator_mutex_
mutableprotected

Definition at line 513 of file cp_model_lns.h.

◆ helper_

const NeighborhoodGeneratorHelper& operations_research::sat::NeighborhoodGenerator::helper_
protected

Definition at line 512 of file cp_model_lns.h.

◆ name_

const std::string operations_research::sat::NeighborhoodGenerator::name_
protected

Definition at line 511 of file cp_model_lns.h.

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