Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
local_search.cc File Reference
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <memory>
#include <optional>
#include <random>
#include <string>
#include <utility>
#include <vector>
#include "absl/algorithm/container.h"
#include "absl/container/flat_hash_map.h"
#include "absl/container/flat_hash_set.h"
#include "absl/flags/flag.h"
#include "absl/log/check.h"
#include "absl/random/distributions.h"
#include "absl/random/random.h"
#include "absl/strings/str_cat.h"
#include "absl/strings/str_format.h"
#include "absl/strings/string_view.h"
#include "absl/time/time.h"
#include "absl/types/span.h"
#include "ortools/base/iterator_adaptors.h"
#include "ortools/base/logging.h"
#include "ortools/base/map_util.h"
#include "ortools/base/strong_int.h"
#include "ortools/base/strong_vector.h"
#include "ortools/base/timer.h"
#include "ortools/base/types.h"
#include "ortools/constraint_solver/constraint_solver.h"
#include "ortools/constraint_solver/constraint_solveri.h"
#include "ortools/graph/hamiltonian_path.h"
#include "ortools/util/bitset.h"
#include "ortools/util/saturated_arithmetic.h"

Go to the source code of this file.

Classes

class  operations_research::TwoOpt< ignore_path_vars >
 --— 2Opt --— More...
 
class  operations_research::Relocate< ignore_path_vars >
 --— Relocate --— More...
 
class  operations_research::Exchange< ignore_path_vars >
 --— Exchange --— More...
 
class  operations_research::Cross< ignore_path_vars >
 --— Cross --— More...
 
class  operations_research::BaseInactiveNodeToPathOperator< ignore_path_vars >
 
class  operations_research::MakeActiveOperator< ignore_path_vars >
 --— MakeActiveOperator --— More...
 
class  operations_research::RelocateAndMakeActiveOperator< ignore_path_vars >
 -— RelocateAndMakeActiveOperator --— More...
 
class  operations_research::ExchangeAndMakeActiveOperator< ignore_path_vars >
 --— ExchangeAndMakeActiveOperator --— More...
 
class  operations_research::ExchangePathStartEndsAndMakeActiveOperator< ignore_path_vars >
 --— ExchangePathEndsAndMakeActiveOperator --— More...
 
class  operations_research::MakeActiveAndRelocateOperator< ignore_path_vars >
 --— MakeActiveAndRelocate --— More...
 
class  operations_research::MakeInactiveOperator< ignore_path_vars >
 --— MakeInactiveOperator --— More...
 
class  operations_research::RelocateAndMakeInactiveOperator< ignore_path_vars >
 --— RelocateAndMakeInactiveOperator --— More...
 
class  operations_research::MakeChainInactiveOperator< ignore_path_vars >
 --— MakeChainInactiveOperator --— More...
 
class  operations_research::SwapActiveOperator< ignore_path_vars >
 --— SwapActiveOperator --— More...
 
class  operations_research::SwapActiveChainOperator< ignore_path_vars >
 --— SwapActiveChainOperator --— More...
 
class  operations_research::ExtendedSwapActiveOperator< ignore_path_vars >
 --— ExtendedSwapActiveOperator --— More...
 
class  operations_research::TSPOpt< ignore_path_vars >
 --— TSP-based operators --— More...
 
class  operations_research::TSPLns< ignore_path_vars >
 
class  operations_research::NearestNeighbors< ignore_path_vars >
 --— Lin-Kernighan --— More...
 
class  operations_research::LinKernighan< ignore_path_vars >
 
class  operations_research::PathLns< ignore_path_vars >
 --— Path-based Large Neighborhood Search --— More...
 
class  operations_research::NeighborhoodLimit
 --— Limit the number of neighborhoods explored --— More...
 
class  operations_research::LocalSearchProfiler
 --— LocalSearchProfiler --— More...
 
class  operations_research::FindOneNeighbor
 --— Finds a neighbor of the assignment passed --— More...
 
class  operations_research::LocalSearchPhaseParameters
 -------— Local Search Phase Parameters -------— More...
 
class  operations_research::LocalSearch
 --— Local search decision builder --— More...
 
class  operations_research::DefaultSolutionPool
 

Namespaces

namespace  operations_research
 In SWIG mode, we don't want anything besides these top-level includes.
 

Typedefs

using operations_research::NeighborAccessor
 --— Path-based Operators --—
 
using operations_research::VariableDomainId = LocalSearchState::VariableDomainId
 
using operations_research::NodeId = SubDagComputer::NodeId
 
using operations_research::ArcId = SubDagComputer::ArcId
 

Functions

 ABSL_FLAG (int, cp_local_search_sync_frequency, 16, "Frequency of checks for better solutions in the solution pool.")
 
 ABSL_FLAG (int, cp_local_search_tsp_opt_size, 13, "Size of TSPs solved in the TSPOpt operator.")
 
 ABSL_FLAG (int, cp_local_search_tsp_lns_size, 10, "Size of TSPs solved in the TSPLns operator.")
 
bool operations_research::LocalOptimumReached (Search *search)
 Returns true if a local optimum has been reached and cannot be improved.
 
bool operations_research::AcceptDelta (Search *search, Assignment *delta, Assignment *deltadelta)
 
void operations_research::AcceptNeighbor (Search *search)
 Notifies the search that a neighbor has been accepted by local search.
 
void operations_research::AcceptUncheckedNeighbor (Search *search)
 
LocalSearchOperatoroperations_research::MakeTwoOpt (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, NeighborAccessor get_incoming_neighbors, NeighborAccessor get_outgoing_neighbors)
 
LocalSearchOperatoroperations_research::MakeRelocate (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, NeighborAccessor get_incoming_neighbors, NeighborAccessor get_outgoing_neighbors, int64_t chain_length, bool single_path, const std::string &name)
 
LocalSearchOperatoroperations_research::MakeExchange (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, NeighborAccessor get_incoming_neighbors, NeighborAccessor get_outgoing_neighbors)
 
LocalSearchOperatoroperations_research::MakeCross (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, NeighborAccessor get_incoming_neighbors, NeighborAccessor get_outgoing_neighbors)
 
LocalSearchOperatoroperations_research::MakeActive (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, NeighborAccessor get_incoming_neighbors, NeighborAccessor get_outgoing_neighbors)
 
LocalSearchOperatoroperations_research::RelocateAndMakeActive (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
 -— RelocateAndMakeActive --—
 
LocalSearchOperatoroperations_research::ExchangeAndMakeActive (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
 --— ExchangeAndMakeActive --—
 
LocalSearchOperatoroperations_research::ExchangePathStartEndsAndMakeActive (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
 --— ExchangePathEndsAndMakeActive --—
 
LocalSearchOperatoroperations_research::MakeActiveAndRelocate (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
 --— MakeActiveAndRelocate --—
 
LocalSearchOperatoroperations_research::MakeInactive (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
 --— MakeInactive --—
 
LocalSearchOperatoroperations_research::RelocateAndMakeInactive (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
 --— RelocateAndMakeInactive --—
 
LocalSearchOperatoroperations_research::MakeChainInactive (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
 --— MakeChainInactive --—
 
LocalSearchOperatoroperations_research::MakeSwapActive (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
 --— SwapActive --—
 
LocalSearchOperatoroperations_research::MakeSwapActiveChain (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, int max_chain_size)
 --— SwapActiveChain --—
 
LocalSearchOperatoroperations_research::MakeExtendedSwapActive (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
 --— ExtendedSwapActive --—
 
LocalSearchOperatoroperations_research::MakeTSPOpt (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int chain_length)
 --— TSP-based operators --—
 
LocalSearchOperatoroperations_research::MakeTSPLns (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int tsp_size)
 
LocalSearchOperatoroperations_research::MakeLinKernighan (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, const Solver::IndexEvaluator3 &evaluator, bool topt)
 --— Lin-Kernighan --—
 
LocalSearchOperatoroperations_research::MakePathLns (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, int number_of_chunks, int chunk_size, bool unactive_fragments)
 --— Path-based Large Neighborhood Search --—
 
void operations_research::InstallLocalSearchProfiler (LocalSearchProfiler *monitor)
 
LocalSearchProfileroperations_research::BuildLocalSearchProfiler (Solver *solver)
 
void operations_research::DeleteLocalSearchProfiler (LocalSearchProfiler *monitor)
 

Function Documentation

◆ ABSL_FLAG() [1/3]

ABSL_FLAG ( int ,
cp_local_search_sync_frequency ,
16 ,
"Frequency of checks for better solutions in the solution pool."  )

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

◆ ABSL_FLAG() [2/3]

ABSL_FLAG ( int ,
cp_local_search_tsp_lns_size ,
10 ,
"Size of TSPs solved in the TSPLns operator."  )

◆ ABSL_FLAG() [3/3]

ABSL_FLAG ( int ,
cp_local_search_tsp_opt_size ,
13 ,
"Size of TSPs solved in the TSPOpt operator."  )