operations_research::sat::LocalBranchingLpBasedNeighborhoodGenerator Class Reference

#include <cp_model_lns.h>

Inheritance diagram for operations_research::sat::LocalBranchingLpBasedNeighborhoodGenerator:

Public Member Functions
	LocalBranchingLpBasedNeighborhoodGenerator (NeighborhoodGeneratorHelper const *helper, absl::string_view name, ModelSharedTimeLimit *const global_time_limit, SharedClasses *shared)
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

Solves a local branching LP and greedily picks a set of variables with the largest differences between the initial and local branching LP solutions, breaking ties uniformly at random.

This is based on Huang et al., "Local Branching Relaxation Heuristics for Integer Linear Programs", 2023.

Definition at line 627 of file cp_model_lns.h.

Constructor & Destructor Documentation

LocalBranchingLpBasedNeighborhoodGenerator()

operations_research::sat::LocalBranchingLpBasedNeighborhoodGenerator::LocalBranchingLpBasedNeighborhoodGenerator ( NeighborhoodGeneratorHelper const * helper, absl::string_view name, ModelSharedTimeLimit *const global_time_limit, SharedClasses * shared )

inline

Given that we spend time generating a good neighborhood it sounds reasonable to spend a bit more time solving it too.

Definition at line 630 of file cp_model_lns.h.

Member Function Documentation

Generate()

Neighborhood operations_research::sat::LocalBranchingLpBasedNeighborhoodGenerator::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.

Quick corner case in case the difficulty is too high. This is mainly useful when testing with only that kind of LNS to abort early on super-easy problems.

These are candidate for relaxation. The score will be filled later. Active variable not kept in candidate will be added to other_variables.

Our extra relaxation constraint will be: sums of distance to the respective bound smaller than a constant that depends on the difficulty.

For the "easy" part of the extra constraint, we either look only at the binary variables. Or we extend that to all variables at their bound.

We copy the model early to have access to reduced domains.

Todo

(user): that might not be the most efficient if we abort just below.

Loop over active variables.

With this option, we will create a bunch of Boolean variable and add the constraints : "bool==0 => var == value_in_base_solution".

Add it to the distance constraint.

Clear other_variables so that they are not added at the end.

Constrain the distance to the bounds.

Parameters to enable solving the LP only.

Parameters to attempt to speed up solve.

Parameters to limit time spent in the solve. The max number of iterations is relaxed from the default since we rely more on deterministic time.

Todo

(user): This is a lot longer than a normal LNS, so it might cause issue with the current round-robbin selection based on number of calls.

Tricky: we want the inner_objective_lower_bound in the response to be in term of the current problem, not the user facing one.

Dump?

Solve.

Todo

(user): Shall we pass the objective upper bound so we have more chance to fix variable via reduced cost fixing.

Todo

(user): Does the current solution can provide a warm-start for the LP?

Update dtime.

Analyze the status of this first "solve".

Todo

(user): If we run into this case, it also means that every other LNS that tries to more variable than here will never be able to improve.

In this case, we cannot improve on the base solution. We could try to find a different solution for diversity, but we do have other neighborhood for that. Lets abort early.

Compute differences between LP solution and initial solution, with a small random noise for tie breaking.

We likely didn't solve the LP at all, so lets not use this neighborhood.

Take the target_size variables with largest differences.

We will also relax all "other variables". We assume their values are likely tied to the other ones.

Lets the name reflect the type.

Todo

(user): Unfortunately like this we have a common difficulty for all variant, we should probably fix that.

Implements operations_research::sat::NeighborhoodGenerator.

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