Google OR-Tools v9.15
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/base/nullability.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 >
class  operations_research::Relocate< ignore_path_vars >
class  operations_research::Exchange< ignore_path_vars >
class  operations_research::Cross< ignore_path_vars >
class  operations_research::BaseInactiveNodeToPathOperator< ignore_path_vars >
class  operations_research::MakeActiveOperator< ignore_path_vars >
class  operations_research::RelocateAndMakeActiveOperator< ignore_path_vars >
class  operations_research::ExchangeAndMakeActiveOperator< ignore_path_vars >
class  operations_research::ExchangePathStartEndsAndMakeActiveOperator< ignore_path_vars >
class  operations_research::MakeActiveAndRelocateOperator< ignore_path_vars >
class  operations_research::MakeInactiveOperator< ignore_path_vars >
class  operations_research::RelocateAndMakeInactiveOperator< ignore_path_vars >
class  operations_research::MakeChainInactiveOperator< ignore_path_vars >
class  operations_research::SwapActiveOperator< ignore_path_vars >
class  operations_research::SwapActiveChainOperator< ignore_path_vars >
class  operations_research::ExtendedSwapActiveOperator< ignore_path_vars >
class  operations_research::TSPOpt< ignore_path_vars >
class  operations_research::TSPLns< ignore_path_vars >
class  operations_research::NearestNeighbors< ignore_path_vars >
class  operations_research::LinKernighan< ignore_path_vars >
class  operations_research::PathLns< ignore_path_vars >
class  operations_research::NeighborhoodLimit
class  operations_research::LocalSearchProfiler
class  operations_research::FindOneNeighbor
class  operations_research::LocalSearchPhaseParameters
class  operations_research::LocalSearch
class  operations_research::DefaultSolutionPool

Namespaces

namespace  operations_research
 OR-Tools root namespace.

Typedefs

using operations_research::NeighborAccessor
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::ContinueAtLocalOptimum (Search *search)
bool operations_research::AcceptDelta (Search *search, Assignment *delta, Assignment *deltadelta)
void operations_research::AcceptNeighbor (Search *search)
void operations_research::AcceptUncheckedNeighbor (Search *search)
LocalSearchOperator * operations_research::MakeTwoOpt (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
 --— 2Opt --—
LocalSearchOperator * operations_research::MakeRelocate (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr, int64_t chain_length=1LL, bool single_path=false, const std::string &name="Relocate")
 --— Relocate --—
LocalSearchOperator * operations_research::MakeExchange (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
 --— Exchange --—
LocalSearchOperator * operations_research::MakeCross (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
 --— Cross --—
LocalSearchOperator * operations_research::MakeActive (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
 --— MakeActive --—
LocalSearchOperator * operations_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 --—
LocalSearchOperator * operations_research::ExchangeAndMakeActive (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
LocalSearchOperator * operations_research::ExchangePathStartEndsAndMakeActive (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
LocalSearchOperator * operations_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 --—
LocalSearchOperator * operations_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 --—
LocalSearchOperator * operations_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 --—
LocalSearchOperator * operations_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 --—
LocalSearchOperator * operations_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 --—
LocalSearchOperator * operations_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 --—
LocalSearchOperator * operations_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 --—
LocalSearchOperator * operations_research::MakeTSPOpt (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int chain_length)
 --— TSP-based operators --—
LocalSearchOperator * operations_research::MakeTSPLns (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int tsp_size)
LocalSearchOperator * operations_research::MakeLinKernighan (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, const Solver::IndexEvaluator3 &evaluator, bool topt)
 --— Lin-Kernighan --—
LocalSearchOperator * operations_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)
LocalSearchProfiler * operations_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."  )

◆ 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."  )