Google OR-Tools v9.15
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
constraint_solveri.h File Reference

Detailed Description

Collection of objects used to extend the Constraint Solver library.

This file contains a set of objects that simplifies writing extensions of the library.

The main objects that define extensions are:

  • BaseIntExpr, the base class of all expressions that are not variables.
  • SimpleRevFIFO, a reversible FIFO list with templatized values. A reversible data structure is a data structure that reverts its modifications when the search is going up in the search tree, usually after a failure occurs.
  • RevImmutableMultiMap, a reversible immutable multimap.
  • MakeConstraintDemon<n> and MakeDelayedConstraintDemon<n> to wrap methods of a constraint as a demon.
  • RevSwitch, a reversible flip-once switch.
  • SmallRevBitSet, RevBitSet, and RevBitMatrix: reversible 1D or 2D bitsets.
  • LocalSearchOperator, IntVarLocalSearchOperator, ChangeValue and PathOperator, to create new local search operators.
  • LocalSearchFilter and IntVarLocalSearchFilter, to create new local search filters.
  • BaseLns, to write Large Neighborhood Search operators.
  • SymmetryBreaker, to describe model symmetries that will be broken during search using the 'Symmetry Breaking During Search' framework see Gent, I. P., Harvey, W., & Kelsey, T. (2002). Groups and Constraints: Symmetry Breaking During Search. Principles and Practice of Constraint Programming CP2002 (Vol. 2470, pp. 415-430). Springer. Retrieved from http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.1442.

Then, there are some internal classes that are used throughout the solver and exposed in this file:

  • SearchLog, the root class of all periodic outputs during search.
  • ModelCache, A caching layer to avoid creating twice the same object.

Definition in file constraint_solveri.h.

#include <stdint.h>
#include <string.h>
#include <algorithm>
#include <functional>
#include <memory>
#include <string>
#include <tuple>
#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/log/check.h"
#include "absl/strings/str_cat.h"
#include "absl/strings/str_format.h"
#include "absl/time/time.h"
#include "absl/types/span.h"
#include "ortools/base/base_export.h"
#include "ortools/base/logging.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/util/bitset.h"
#include "ortools/util/tuple_set.h"

Go to the source code of this file.

Classes

class  operations_research::BaseIntExpr
class  operations_research::SimpleRevFIFO< T >
class  operations_research::SimpleRevFIFO< T >::Iterator
 This iterator is not stable with respect to deletion. More...
class  operations_research::RevImmutableMultiMap< K, V >
class  operations_research::RevSwitch
 A reversible switch that can switch once from false to true. More...
class  operations_research::SmallRevBitSet
class  operations_research::RevBitSet
class  operations_research::RevBitMatrix
 Matrix version of the RevBitSet class. More...
class  operations_research::CallMethod0< T >
 Demon proxy to a method on the constraint with no arguments. More...
class  operations_research::CallMethod1< T, P >
 Demon proxy to a method on the constraint with one argument. More...
class  operations_research::CallMethod2< T, P, Q >
 Demon proxy to a method on the constraint with two arguments. More...
class  operations_research::CallMethod3< T, P, Q, R >
 Demon proxy to a method on the constraint with three arguments. More...
class  operations_research::DelayedCallMethod0< T >
 Low-priority demon proxy to a method on the constraint with no arguments. More...
class  operations_research::DelayedCallMethod1< T, P >
 Low-priority demon proxy to a method on the constraint with one argument. More...
class  operations_research::DelayedCallMethod2< T, P, Q >
 Low-priority demon proxy to a method on the constraint with two arguments. More...
class  operations_research::LightIntFunctionElementCt< F >
class  operations_research::LightIntIntFunctionElementCt< F >
class  operations_research::LightIntIntIntFunctionElementCt< F >
class  operations_research::LocalSearchOperator
 The base class for all local search operators. More...
class  operations_research::LocalSearchOperatorState
class  operations_research::IntVarLocalSearchOperator
class  operations_research::BaseLns
 Here's a sample relaxing one variable at a time: More...
class  operations_research::ChangeValue
class  operations_research::AlternativeNodeIterator
class  operations_research::NodeNeighborIterator
class  operations_research::BaseNodeIterators< PathOperator >
class  operations_research::PathOperator< ignore_path_vars >
struct  operations_research::PathOperator< ignore_path_vars >::IterationParameters
 Set of parameters used to configure how the neighborhood is traversed. More...
struct  operations_research::PathOperator< ignore_path_vars >::Neighbor
class  operations_research::SubDagComputer
class  operations_research::LocalSearchState
struct  operations_research::LocalSearchState::DependencyGraph::Dependency
class  operations_research::LocalSearchState::Variable
class  operations_research::LocalSearchFilter
class  operations_research::LocalSearchFilterManager
struct  operations_research::LocalSearchFilterManager::FilterEvent
class  operations_research::IntVarLocalSearchFilter
class  operations_research::PropagationMonitor
class  operations_research::LocalSearchMonitor
class  operations_research::BooleanVar
class  operations_research::SymmetryBreaker
class  operations_research::SearchLog
class  operations_research::ModelCache
class  operations_research::ArgumentHolder
 Argument Holder: useful when visiting a model. More...
class  operations_research::ModelParser
 Model Parser. More...
class  operations_research::ArrayWithOffset< T >
class  operations_research::RevGrowingArray< T, C >
class  operations_research::RevIntSet< T >
class  operations_research::RevPartialSequence
 --— RevPartialSequence --— More...
class  operations_research::UnsortedNullableRevBitset

Namespaces

namespace  operations_research
 OR-Tools root namespace.

Enumerations

enum  operations_research::VarTypes {
  operations_research::UNSPECIFIED , operations_research::DOMAIN_INT_VAR , operations_research::BOOLEAN_VAR , operations_research::CONST_VAR ,
  operations_research::VAR_ADD_CST , operations_research::VAR_TIMES_CST , operations_research::CST_SUB_VAR , operations_research::OPP_VAR ,
  operations_research::TRACE_VAR
}

Functions

uint64_t operations_research::Hash1 (uint64_t value)
 Hash functions.
uint64_t operations_research::Hash1 (uint32_t value)
uint64_t operations_research::Hash1 (int64_t value)
uint64_t operations_research::Hash1 (int value)
uint64_t operations_research::Hash1 (void *const ptr)
template<class T>
uint64_t operations_research::Hash1 (const std::vector< T * > &ptrs)
uint64_t operations_research::Hash1 (const std::vector< int64_t > &ptrs)
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 --—
template<class T>
bool operations_research::IsArrayConstant (const std::vector< T > &values, const T &value)
template<class T>
bool operations_research::IsArrayBoolean (const std::vector< T > &values)
template<class T>
bool operations_research::AreAllOnes (const std::vector< T > &values)
template<class T>
bool operations_research::AreAllNull (const std::vector< T > &values)
template<class T>
bool operations_research::AreAllGreaterOrEqual (const std::vector< T > &values, const T &value)
template<class T>
bool operations_research::AreAllLessOrEqual (const std::vector< T > &values, const T &value)
template<class T>
bool operations_research::AreAllPositive (const std::vector< T > &values)
template<class T>
bool operations_research::AreAllNegative (const std::vector< T > &values)
template<class T>
bool operations_research::AreAllStrictlyPositive (const std::vector< T > &values)
template<class T>
bool operations_research::AreAllStrictlyNegative (const std::vector< T > &values)
template<class T>
bool operations_research::IsIncreasingContiguous (const std::vector< T > &values)
template<class T>
bool operations_research::IsIncreasing (const std::vector< T > &values)
template<class T>
bool operations_research::IsArrayInRange (const std::vector< IntVar * > &vars, T range_min, T range_max)
bool operations_research::AreAllBound (const std::vector< IntVar * > &vars)
bool operations_research::AreAllBooleans (const std::vector< IntVar * > &vars)
template<class T>
bool operations_research::AreAllBoundOrNull (const std::vector< IntVar * > &vars, const std::vector< T > &values)
bool operations_research::AreAllBoundTo (const std::vector< IntVar * > &vars, int64_t value)
 Returns true if all variables are assigned to 'value'.
int64_t operations_research::MaxVarArray (const std::vector< IntVar * > &vars)
int64_t operations_research::MinVarArray (const std::vector< IntVar * > &vars)
void operations_research::FillValues (const std::vector< IntVar * > &vars, std::vector< int64_t > *const values)
int64_t operations_research::PosIntDivUp (int64_t e, int64_t v)
int64_t operations_research::PosIntDivDown (int64_t e, int64_t v)
std::vector< int64_t > operations_research::ToInt64Vector (const std::vector< int > &input)
template<class T>
Demon * operations_research::MakeConstraintDemon0 (Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
template<class P>
std::string operations_research::ParameterDebugString (P param)
template<class P>
std::string operations_research::ParameterDebugString (P *param)
 Support limited to pointers to classes which define DebugString().
template<class T, class P>
Demon * operations_research::MakeConstraintDemon1 (Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
template<class T, class P, class Q>
Demon * operations_research::MakeConstraintDemon2 (Solver *const s, T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
template<class T, class P, class Q, class R>
Demon * operations_research::MakeConstraintDemon3 (Solver *const s, T *const ct, void(T::*method)(P, Q, R), const std::string &name, P param1, Q param2, R param3)
template<class T>
Demon * operations_research::MakeDelayedConstraintDemon0 (Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
template<class T, class P>
Demon * operations_research::MakeDelayedConstraintDemon1 (Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
template<class T, class P, class Q>
Demon * operations_research::MakeDelayedConstraintDemon2 (Solver *const s, T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)