Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Classes | 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::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 Member Functions

 NeighborhoodGenerator (absl::string_view name, NeighborhoodGeneratorHelper const *helper)
 
virtual ~NeighborhoodGenerator ()=default
 
virtual Neighborhood Generate (const CpSolverResponse &initial_solution, double difficulty, 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_
 

Detailed Description

Base class for a CpModelProto neighborhood generator.

Definition at line 352 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 354 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 426 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 472 of file cp_model_lns.h.

◆ difficulty()

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

The current difficulty of this generator.

Definition at line 466 of file cp_model_lns.h.

◆ Generate()

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

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.

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::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 1174 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 437 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 440 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 460 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 446 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 452 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 1170 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 1181 of file cp_model_lns.cc.

Member Data Documentation

◆ generator_mutex_

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

Definition at line 480 of file cp_model_lns.h.

◆ helper_

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

Definition at line 479 of file cp_model_lns.h.

◆ name_

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

Definition at line 478 of file cp_model_lns.h.

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