or-tools/src/constraint_solver/local_search.cc File Reference

#include <string.h>
#include <algorithm>
#include "base/hash.h"
#include <iterator>
#include <set>
#include <string>
#include <utility>
#include <vector>
#include "base/callback.h"
#include "base/commandlineflags.h"
#include "base/integral_types.h"
#include "base/logging.h"
#include "base/macros.h"
#include "base/scoped_ptr.h"
#include "base/bitmap.h"
#include "base/concise_iterator.h"
#include "base/map-util.h"
#include "constraint_solver/constraint_solver.h"
#include "constraint_solver/constraint_solveri.h"
#include "graph/hamiltonian_path.h"
#include "base/random.h"

Go to the source code of this file.

Namespaces

namespace operations_research

Classes

class operations_research::FindOneNeighbor

Finds a neighbor of the assignment passed. More...

class operations_research::LocalSearchPhaseParameters

Local Search Phase Parameters. More...

Functions

DEFINE_int32 (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.

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

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

bool operations_research::LocalOptimumReached (Search *const search)

Utility methods to ensure the communication between local search and the search.

bool operations_research::AcceptDelta (Search *const search, Assignment *delta, Assignment *deltadelta)

Returns true if the search accepts the delta (actually checking this by calling AcceptDelta on the monitors of the search).

void operations_research::AcceptNeighbor (Search *const search)

Notifies the search that a neighbor has been accepted by local search.

int64 operations_research::CompoundOperatorNoRestart (int size, int active_index, int operator_index)

int64 operations_research::CompoundOperatorRestart (int active_index, int operator_index)

LSOperation * operations_research::OperationFromEnum (Solver::LocalSearchOperation op_enum)

Local search filter factory.

Function Documentation

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

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

DEFINE_int32	(	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.

Variable Documentation

const int active_operator_

Definition at line 1878 of file local_search.cc.

Assignment* assignment_

Definition at line 3115 of file local_search.cc.

int64* const cache_

Definition at line 2396 of file local_search.cc.

const int chain_length_

Definition at line 1023 of file local_search.cc.

const int chunk_size_

Definition at line 1775 of file local_search.cc.

std::vector<std::vector<int64> > cost_

Definition at line 1297 of file local_search.cc.

DecisionBuilder* const db_

Definition at line 3042 of file local_search.cc.

int64* const delta_cache_

Definition at line 2397 of file local_search.cc.

scoped_ptr<ResultCallback2<int64, int, int> > evaluator_

Definition at line 1299 of file local_search.cc.

Solver::LocalSearchFilterBound filter_enum_

Definition at line 2399 of file local_search.cc.

const std::vector<LocalSearchFilter*> filters_

Definition at line 3122 of file local_search.cc.

HamiltonianPathSolver<int64> hamiltonian_path_solver_

Definition at line 1298 of file local_search.cc.

bool has_started_

Definition at line 3123 of file local_search.cc.

int inactive_node_

Definition at line 1140 of file local_search.cc.

bool incremental_

Definition at line 2403 of file local_search.cc.

int64 index_

Definition at line 424 of file local_search.cc.

bool initialized_

Definition at line 1510 of file local_search.cc.

const int kNeighbors [static]

Definition at line 1614 of file local_search.cc.

int64 last_

Definition at line 958 of file local_search.cc.

int64 last_base_

Definition at line 957 of file local_search.cc.

SearchLimit* const limit_

Definition at line 1836 of file local_search.cc.

LocalSearchOperator* const ls_operator_

Definition at line 3117 of file local_search.cc.

hash_set<int64> marked_

Definition at line 1621 of file local_search.cc.

bool max_

Definition at line 2289 of file local_search.cc.

std::vector<SearchMonitor*> monitors_

Definition at line 3044 of file local_search.cc.

NearestNeighbors neighbors_

Definition at line 1506 of file local_search.cc.

int nested_decision_index_

Definition at line 3120 of file local_search.cc.

std::vector<NestedSolveDecision*> nested_decisions_

Definition at line 3119 of file local_search.cc.

int64 next_neighborhood_calls_

Definition at line 1837 of file local_search.cc.

int64 num_var_since_last_start_

Number of variables checked since the last call to OnStart().

Definition at line 564 of file local_search.cc.

const int number_of_chunks_

Definition at line 1774 of file local_search.cc.

const int number_of_variables_

Definition at line 425 of file local_search.cc.

const IntVar* const objective_

Definition at line 2398 of file local_search.cc.

int64 old_delta_value_

Definition at line 2402 of file local_search.cc.

int64 old_value_

Definition at line 2401 of file local_search.cc.

scoped_ptr<LSOperation> op_

Definition at line 2400 of file local_search.cc.

LocalSearchOperator* const operator_

Definition at line 1835 of file local_search.cc.

scoped_array<int> operator_indices_

Definition at line 1884 of file local_search.cc.

scoped_array<LocalSearchOperator*> operators_

Definition at line 1883 of file local_search.cc.

bool owner_

Definition at line 1619 of file local_search.cc.

const PathOperator& path_operator_

Definition at line 1508 of file local_search.cc.

SolutionPool* const pool_

Definition at line 3116 of file local_search.cc.

const int primary_vars_size_

Definition at line 2395 of file local_search.cc.

ACMRandom rand_

Definition at line 460 of file local_search.cc.

scoped_ptr<Assignment> reference_assignment_

Definition at line 3310 of file local_search.cc.

bool restore_

Definition at line 3043 of file local_search.cc.

int secondary_vars_offset_

Definition at line 2597 of file local_search.cc.

const bool single_path_

Definition at line 1024 of file local_search.cc.

const int size_

Definition at line 1509 of file local_search.cc.

int state_

Definition at line 3045 of file local_search.cc.

DecisionBuilder* const sub_decision_builder_

Definition at line 3118 of file local_search.cc.

const std::vector<int64> target_

Target values.

Definition at line 558 of file local_search.cc.

const bool topt_

Definition at line 1622 of file local_search.cc.

const int tsp_size_

Definition at line 1372 of file local_search.cc.

const bool unactive_fragments_

Definition at line 1776 of file local_search.cc.

int64 value_

Definition at line 2241 of file local_search.cc.

scoped_ptr<Solver::IndexEvaluator3> value_evaluator_

Definition at line 2543 of file local_search.cc.

std::set<int64> values_set_

Definition at line 2288 of file local_search.cc.

int64 variable_index_

Index of the next variable to try to restore.

Definition at line 561 of file local_search.cc.


Namespaces
namespace	operations_research
Classes
class	operations_research::FindOneNeighbor
	Finds a neighbor of the assignment passed. More...
class	operations_research::LocalSearchPhaseParameters
	Local Search Phase Parameters. More...
Functions
	DEFINE_int32 (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.
	DEFINE_int32 (cp_local_search_tsp_opt_size, 13,"Size of TSPs solved in the TSPOpt operator.")
	DEFINE_int32 (cp_local_search_tsp_lns_size, 10,"Size of TSPs solved in the TSPLns operator.")
bool	operations_research::LocalOptimumReached (Search *const search)
	Utility methods to ensure the communication between local search and the search.
bool	operations_research::AcceptDelta (Search const search, Assignment delta, Assignment *deltadelta)
	Returns true if the search accepts the delta (actually checking this by calling AcceptDelta on the monitors of the search).
void	operations_research::AcceptNeighbor (Search *const search)
	Notifies the search that a neighbor has been accepted by local search.
int64	operations_research::CompoundOperatorNoRestart (int size, int active_index, int operator_index)
int64	operations_research::CompoundOperatorRestart (int active_index, int operator_index)
LSOperation *	operations_research::OperationFromEnum (Solver::LocalSearchOperation op_enum)
	Local search filter factory.