 |
Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
|
|
Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
|
#include <cp_model_lns.h>
Public Member Functions | |
| RoutingFullPathNeighborhoodGenerator (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 |
This routing based LNS generator aims at relaxing one full path, and make some room on the other paths to absorb the nodes of the relaxed path.
In order to do so, it will relax the first and the last arc of each path in the circuit or routes constraints. Then it will relax all arc literals in one random path. Then it will relax random arcs in the remaining paths until it reaches the given difficulty.
Definition at line 830 of file cp_model_lns.h.
|
inline |
Definition at line 832 of file cp_model_lns.h.
|
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.
Remove a corner case where all paths are empty.
Collect all unique variables.
Select target number of variables to relax.
Relax the start and end of each path to ease relocation.
Relax all variables, if possible, of one random path.
Relax more variables until the target is reached.
Compute the set of variables to fix.
Implements operations_research::sat::NeighborhoodGenerator.
Definition at line 2691 of file cp_model_lns.cc.
1.13.2