operations_research::sat::RectanglesPackingRelaxOneNeighborhoodGenerator Class Reference

#include <cp_model_lns.h>

Inheritance diagram for operations_research::sat::RectanglesPackingRelaxOneNeighborhoodGenerator:

Public Member Functions
	RectanglesPackingRelaxOneNeighborhoodGenerator (NeighborhoodGeneratorHelper const *helper, absl::string_view name)
Neighborhood	Generate (const CpSolverResponse &initial_solution, SolveData &data, 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
Public Types inherited from operations_research::sat::NeighborhoodGenerator
using	ActiveRectangle = NeighborhoodGeneratorHelper::ActiveRectangle
Protected Attributes inherited from operations_research::sat::NeighborhoodGenerator
const std::string	name_
const NeighborhoodGeneratorHelper &	helper_
absl::Mutex	generator_mutex_
double	deterministic_limit_ = 0.1

Detailed Description

Only make sense for problems with no_overlap_2d constraints. This selects one random rectangles and relax the closest rectangles to it.

Definition at line 745 of file cp_model_lns.h.

Constructor & Destructor Documentation

RectanglesPackingRelaxOneNeighborhoodGenerator()

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

inlineexplicit

Definition at line 748 of file cp_model_lns.h.

Member Function Documentation

Generate()

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

finalvirtual

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.

First pick one rectangle.

Now compute a neighborhood around that rectangle. In this neighborhood we prefer a "Square" region around the initial rectangle center rather than a circle.

Note

we only consider two rectangles as potential neighbors if they are part of the same no_overlap_2d constraint.

Heuristic: we relax a bit the bounding box in order to allow some movements, this is needed to not have a trivial neighborhood if we relax a single box for instance.

The call above add the relaxed variables to the neighborhood using the current bounds at level 0. For big problems, this might create a hard model with a large complicated landscape of fixed boxes with a lot of potential places to place the relaxed boxes. Therefore we update the domain so the boxes can only stay around the area we decided to relax.

Implements operations_research::sat::NeighborhoodGenerator.

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