operations_research::bop Namespace Reference

Detailed Description

BopAdaptiveLNSOptimizer

Neighborhood generators.

Classes
class	AdaptiveParameterValue
class	AssignmentAndConstraintFeasibilityMaintainer
class	BacktrackableIntegerSet
class	BopAdaptiveLNSOptimizer
class	BopCompleteLNSOptimizer
struct	BopConstraintTerm
class	BopOptimizerBase
class	BopOptimizerMethod
struct	BopOptimizerMethodDefaultTypeInternal
class	BopParameters
struct	BopParametersDefaultTypeInternal
class	BopRandomFirstSolutionGenerator
class	BopSolution
class	BopSolver
	Solver of Boolean Optimization Problems based on Local Search. More...
class	BopSolverOptimizerSet
struct	BopSolverOptimizerSetDefaultTypeInternal
class	ConstraintBasedNeighborhood
class	GlopParameters
class	GuidedSatFirstSolutionGenerator
class	IntegralSolver
struct	LearnedInfo
class	LinearBooleanConstraint
class	LinearBooleanProblem
class	LinearObjective
class	LinearProgram
class	LinearRelaxation
class	LocalSearchAssignmentIterator
class	LocalSearchOptimizer
class	LPDecomposer
class	LubyAdaptiveParameterValue
class	NeighborhoodGenerator
class	NonOrderedSetHasher
class	ObjectiveBasedNeighborhood
class	OneFlipConstraintRepairer
class	OptimizerSelector
class	PortfolioOptimizer
class	ProblemState
class	RelationGraphBasedNeighborhood
class	SatCoreBasedOptimizer
class	SatWrapper
class	SparseColumn
class	SparseMatrix

Typedefs
typedef util_intops::StrongVector< SparseIndex, BopConstraintTerm >	BopConstraintTerms
typedef StrictITIVector< ColIndex, Fractional >	DenseRow
	Row-vector types. Row-vector types are indexed by a column index.
typedef StrictITIVector< ColIndex, Fractional >	DenseRow
	Row-vector types. Row-vector types are indexed by a column index.
typedef StrictITIVector< ColIndex, Fractional >	DenseRow
	Row-vector types. Row-vector types are indexed by a column index.
typedef StrictITIVector< ColIndex, Fractional >	DenseRow
	Row-vector types. Row-vector types are indexed by a column index.
typedef double	Fractional

Enumerations
enum class	BopSolveStatus {   OPTIMAL_SOLUTION_FOUND , FEASIBLE_SOLUTION_FOUND , NO_SOLUTION_FOUND , INFEASIBLE_PROBLEM ,   INVALID_PROBLEM }
	Status of the solve of Bop. More...
enum	BopOptimizerMethod_OptimizerType : int {   BopOptimizerMethod_OptimizerType_SAT_CORE_BASED = 0 , BopOptimizerMethod_OptimizerType_SAT_LINEAR_SEARCH = 15 , BopOptimizerMethod_OptimizerType_LINEAR_RELAXATION = 1 , BopOptimizerMethod_OptimizerType_LOCAL_SEARCH = 2 ,   BopOptimizerMethod_OptimizerType_RANDOM_FIRST_SOLUTION = 3 , BopOptimizerMethod_OptimizerType_RANDOM_CONSTRAINT_LNS = 4 , BopOptimizerMethod_OptimizerType_RANDOM_VARIABLE_LNS = 5 , BopOptimizerMethod_OptimizerType_COMPLETE_LNS = 7 ,   BopOptimizerMethod_OptimizerType_LP_FIRST_SOLUTION = 8 , BopOptimizerMethod_OptimizerType_OBJECTIVE_FIRST_SOLUTION = 9 , BopOptimizerMethod_OptimizerType_USER_GUIDED_FIRST_SOLUTION = 14 , BopOptimizerMethod_OptimizerType_RANDOM_CONSTRAINT_LNS_GUIDED_BY_LP = 11 ,   BopOptimizerMethod_OptimizerType_RANDOM_VARIABLE_LNS_GUIDED_BY_LP = 12 , BopOptimizerMethod_OptimizerType_RELATION_GRAPH_LNS = 16 , BopOptimizerMethod_OptimizerType_RELATION_GRAPH_LNS_GUIDED_BY_LP = 17 }
enum	BopParameters_ThreadSynchronizationType : int { BopParameters_ThreadSynchronizationType_NO_SYNCHRONIZATION = 0 , BopParameters_ThreadSynchronizationType_SYNCHRONIZE_ALL = 1 , BopParameters_ThreadSynchronizationType_SYNCHRONIZE_ON_RIGHT = 2 }

Functions
std::ostream &	operator<< (std::ostream &os, BopOptimizerBase::Status status)
	DEFINE_STRONG_INDEX_TYPE (OptimizerIndex)
const OptimizerIndex	kInvalidOptimizerIndex (-1)
	DEFINE_STRONG_INDEX_TYPE (ConstraintIndex)
	DEFINE_STRONG_INDEX_TYPE (EntryIndex)
	DEFINE_STRONG_INDEX_TYPE (SearchIndex)
	DEFINE_STRONG_INDEX_TYPE (TermIndex)
	DEFINE_STRONG_INDEX_TYPE (VariableIndex)
	DEFINE_STRONG_INT64_TYPE (SolverTimeStamp)
std::string	GetSolveStatusString (BopSolveStatus status)
std::ostream &	operator<< (std::ostream &os, BopSolveStatus status)
	DEFINE_STRONG_INDEX_TYPE (SparseIndex)
BopOptimizerBase::Status	LoadStateProblemToSatSolver (const ProblemState &problem_state, sat::SatSolver *sat_solver)
void	ExtractLearnedInfoFromSatSolver (sat::SatSolver *solver, LearnedInfo *info)
void	SatAssignmentToBopSolution (const sat::VariablesAssignment &assignment, BopSolution *solution)
const ::google::protobuf::EnumDescriptor *PROTOBUF_NONNULL	BopOptimizerMethod_OptimizerType_descriptor ()
const ::google::protobuf::EnumDescriptor *PROTOBUF_NONNULL	BopParameters_ThreadSynchronizationType_descriptor ()
bool	BopOptimizerMethod_OptimizerType_IsValid (int value)
template<typename T>
const ::std::string &	BopOptimizerMethod_OptimizerType_Name (T value)
template<>
const ::std::string &	BopOptimizerMethod_OptimizerType_Name (BopOptimizerMethod_OptimizerType value)
bool	BopOptimizerMethod_OptimizerType_Parse (::absl::string_view name, BopOptimizerMethod_OptimizerType *PROTOBUF_NONNULL value)
bool	BopParameters_ThreadSynchronizationType_IsValid (int value)
template<typename T>
const ::std::string &	BopParameters_ThreadSynchronizationType_Name (T value)
template<>
const ::std::string &	BopParameters_ThreadSynchronizationType_Name (BopParameters_ThreadSynchronizationType value)
bool	BopParameters_ThreadSynchronizationType_Parse (::absl::string_view name, BopParameters_ThreadSynchronizationType *PROTOBUF_NONNULL value)

Variables
PROTOBUF_ATTRIBUTE_NO_DESTROY PROTOBUF_CONSTINIT OR_PROTO_DLL PROTOBUF_ATTRIBUTE_INIT_PRIORITY1 BopOptimizerMethodDefaultTypeInternal	_BopOptimizerMethod_default_instance_
PROTOBUF_ATTRIBUTE_NO_DESTROY PROTOBUF_CONSTINIT OR_PROTO_DLL PROTOBUF_ATTRIBUTE_INIT_PRIORITY1 BopSolverOptimizerSetDefaultTypeInternal	_BopSolverOptimizerSet_default_instance_
PROTOBUF_ATTRIBUTE_NO_DESTROY PROTOBUF_CONSTINIT OR_PROTO_DLL PROTOBUF_ATTRIBUTE_INIT_PRIORITY1 BopParametersDefaultTypeInternal	_BopParameters_default_instance_
PROTOBUF_CONSTINIT const uint32_t	BopOptimizerMethod_OptimizerType_internal_data_ []
PROTOBUF_CONSTINIT const uint32_t	BopParameters_ThreadSynchronizationType_internal_data_ []
PROTOBUF_CONSTINIT PROTOBUF_ATTRIBUTE_INIT_PRIORITY1 const::google::protobuf::internal::ClassDataFull	BopOptimizerMethod_class_data_
PROTOBUF_CONSTINIT PROTOBUF_ATTRIBUTE_INIT_PRIORITY1 const::google::protobuf::internal::ClassDataFull	BopSolverOptimizerSet_class_data_
PROTOBUF_CONSTINIT PROTOBUF_ATTRIBUTE_INIT_PRIORITY1 const::google::protobuf::internal::ClassDataFull	BopParameters_class_data_
constexpr BopOptimizerMethod_OptimizerType	BopOptimizerMethod_OptimizerType_OptimizerType_MIN
constexpr BopOptimizerMethod_OptimizerType	BopOptimizerMethod_OptimizerType_OptimizerType_MAX
constexpr int	BopOptimizerMethod_OptimizerType_OptimizerType_ARRAYSIZE = 17 + 1
constexpr BopParameters_ThreadSynchronizationType	BopParameters_ThreadSynchronizationType_ThreadSynchronizationType_MIN
constexpr BopParameters_ThreadSynchronizationType	BopParameters_ThreadSynchronizationType_ThreadSynchronizationType_MAX
constexpr int	BopParameters_ThreadSynchronizationType_ThreadSynchronizationType_ARRAYSIZE = 2 + 1
constexpr Fractional	kInfinity
	Infinity for type Fractional.

Typedef Documentation

BopConstraintTerms

typedef util_intops::StrongVector<SparseIndex, BopConstraintTerm> operations_research::bop::BopConstraintTerms

Definition at line 89 of file bop_types.h.

DenseRow [1/4]

typedef StrictITIVector<ColIndex, Fractional> operations_research::glop::DenseRow

Row-vector types. Row-vector types are indexed by a column index.

Row of fractional values.

Definition at line 351 of file lp_types.h.

DenseRow [2/4]

typedef StrictITIVector<ColIndex, Fractional> operations_research::glop::DenseRow

Row-vector types. Row-vector types are indexed by a column index.

Row of fractional values.

Definition at line 351 of file lp_types.h.

DenseRow [3/4]

typedef StrictITIVector<ColIndex, Fractional> operations_research::glop::DenseRow

Row-vector types. Row-vector types are indexed by a column index.

Row of fractional values.

Definition at line 351 of file lp_types.h.

DenseRow [4/4]

typedef StrictITIVector<ColIndex, Fractional> operations_research::glop::DenseRow

Row-vector types. Row-vector types are indexed by a column index.

Row of fractional values.

Definition at line 351 of file lp_types.h.

Fractional

typedef double operations_research::glop::Fractional

The type Fractional denotes the type of numbers on which the computations are performed. This is defined as double here, but it could as well be float, DoubleDouble, QuadDouble, or infinite-precision rationals. Floating-point representations are binary fractional numbers, thus the name. (See http://en.wikipedia.org/wiki/Fraction_(mathematics) .)

Definition at line 81 of file lp_types.h.

Enumeration Type Documentation

BopOptimizerMethod_OptimizerType

enum operations_research::bop::BopOptimizerMethod_OptimizerType : int

Enumerator
BopOptimizerMethod_OptimizerType_SAT_CORE_BASED
BopOptimizerMethod_OptimizerType_SAT_LINEAR_SEARCH
BopOptimizerMethod_OptimizerType_LINEAR_RELAXATION
BopOptimizerMethod_OptimizerType_LOCAL_SEARCH
BopOptimizerMethod_OptimizerType_RANDOM_FIRST_SOLUTION
BopOptimizerMethod_OptimizerType_RANDOM_CONSTRAINT_LNS
BopOptimizerMethod_OptimizerType_RANDOM_VARIABLE_LNS
BopOptimizerMethod_OptimizerType_COMPLETE_LNS
BopOptimizerMethod_OptimizerType_LP_FIRST_SOLUTION
BopOptimizerMethod_OptimizerType_OBJECTIVE_FIRST_SOLUTION
BopOptimizerMethod_OptimizerType_USER_GUIDED_FIRST_SOLUTION
BopOptimizerMethod_OptimizerType_RANDOM_CONSTRAINT_LNS_GUIDED_BY_LP
BopOptimizerMethod_OptimizerType_RANDOM_VARIABLE_LNS_GUIDED_BY_LP
BopOptimizerMethod_OptimizerType_RELATION_GRAPH_LNS
BopOptimizerMethod_OptimizerType_RELATION_GRAPH_LNS_GUIDED_BY_LP

Definition at line 89 of file bop_parameters.pb.h.

BopParameters_ThreadSynchronizationType

enum operations_research::bop::BopParameters_ThreadSynchronizationType : int

Enumerator
BopParameters_ThreadSynchronizationType_NO_SYNCHRONIZATION
BopParameters_ThreadSynchronizationType_SYNCHRONIZE_ALL
BopParameters_ThreadSynchronizationType_SYNCHRONIZE_ON_RIGHT

Definition at line 134 of file bop_parameters.pb.h.

BopSolveStatus

enum class operations_research::bop::BopSolveStatus

strong

Status of the solve of Bop.

Enumerator
OPTIMAL_SOLUTION_FOUND	The solver found the proven optimal solution.
FEASIBLE_SOLUTION_FOUND	The solver found a solution, but it is not proven to be the optimal solution.
NO_SOLUTION_FOUND	The solver didn't find any solution.
INFEASIBLE_PROBLEM	The problem is infeasible.
INVALID_PROBLEM	The problem is invalid.

Definition at line 34 of file bop_types.h.

Function Documentation

BopOptimizerMethod_OptimizerType_descriptor()

OR_PROTO_DLLconst::google::protobuf::EnumDescriptor *PROTOBUF_NONNULL operations_research::bop::BopOptimizerMethod_OptimizerType_descriptor

(

)

Definition at line 352 of file bop_parameters.pb.cc.

BopOptimizerMethod_OptimizerType_IsValid()

bool operations_research::bop::BopOptimizerMethod_OptimizerType_IsValid ( int value )

inline

Definition at line 112 of file bop_parameters.pb.h.

BopOptimizerMethod_OptimizerType_Name() [1/2]

template<>

const ::std::string & operations_research::bop::BopOptimizerMethod_OptimizerType_Name ( BopOptimizerMethod_OptimizerType value )

inline

Definition at line 125 of file bop_parameters.pb.h.

BopOptimizerMethod_OptimizerType_Name() [2/2]

template<typename T>

const ::std::string & operations_research::bop::BopOptimizerMethod_OptimizerType_Name

(

T

value

)

Definition at line 118 of file bop_parameters.pb.h.

BopOptimizerMethod_OptimizerType_Parse()

bool operations_research::bop::BopOptimizerMethod_OptimizerType_Parse ( ::absl::string_view name, BopOptimizerMethod_OptimizerType *PROTOBUF_NONNULL value )

inline

Definition at line 129 of file bop_parameters.pb.h.

BopParameters_ThreadSynchronizationType_descriptor()

OR_PROTO_DLLconst::google::protobuf::EnumDescriptor *PROTOBUF_NONNULL operations_research::bop::BopParameters_ThreadSynchronizationType_descriptor

(

)

Definition at line 358 of file bop_parameters.pb.cc.

BopParameters_ThreadSynchronizationType_IsValid()

bool operations_research::bop::BopParameters_ThreadSynchronizationType_IsValid ( int value )

inline

Definition at line 145 of file bop_parameters.pb.h.

BopParameters_ThreadSynchronizationType_Name() [1/2]

template<>

const ::std::string & operations_research::bop::BopParameters_ThreadSynchronizationType_Name ( BopParameters_ThreadSynchronizationType value )

inline

Definition at line 158 of file bop_parameters.pb.h.

BopParameters_ThreadSynchronizationType_Name() [2/2]

template<typename T>

const ::std::string & operations_research::bop::BopParameters_ThreadSynchronizationType_Name

(

T

value

)

Definition at line 151 of file bop_parameters.pb.h.

BopParameters_ThreadSynchronizationType_Parse()

bool operations_research::bop::BopParameters_ThreadSynchronizationType_Parse ( ::absl::string_view name, BopParameters_ThreadSynchronizationType *PROTOBUF_NONNULL value )

inline

Definition at line 162 of file bop_parameters.pb.h.

DEFINE_STRONG_INDEX_TYPE() [1/7]

operations_research::bop::DEFINE_STRONG_INDEX_TYPE

(

ConstraintIndex

)

DEFINE_STRONG_INDEX_TYPE() [2/7]

operations_research::bop::DEFINE_STRONG_INDEX_TYPE

(

EntryIndex

)

DEFINE_STRONG_INDEX_TYPE() [3/7]

operations_research::bop::DEFINE_STRONG_INDEX_TYPE

(

OptimizerIndex

)

DEFINE_STRONG_INDEX_TYPE() [4/7]

operations_research::bop::DEFINE_STRONG_INDEX_TYPE

(

SearchIndex

)

DEFINE_STRONG_INDEX_TYPE() [5/7]

operations_research::bop::DEFINE_STRONG_INDEX_TYPE

(

SparseIndex

)

Todo

(user): Remove.

DEFINE_STRONG_INDEX_TYPE() [6/7]

operations_research::bop::DEFINE_STRONG_INDEX_TYPE

(

TermIndex

)

DEFINE_STRONG_INDEX_TYPE() [7/7]

operations_research::bop::DEFINE_STRONG_INDEX_TYPE

(

VariableIndex

)

DEFINE_STRONG_INT64_TYPE()

operations_research::bop::DEFINE_STRONG_INT64_TYPE

(

SolverTimeStamp

)

ExtractLearnedInfoFromSatSolver()

void operations_research::bop::ExtractLearnedInfoFromSatSolver	(	sat::SatSolver *	solver,
		LearnedInfo *	info )

Extracts from the sat solver any new information about the problem. Note that the solver is not const because this function clears what is considered "new".

This should never be called if the problem is UNSAT.

Fixed variables.

Binary clauses.

Definition at line 109 of file bop_util.cc.

GetSolveStatusString()

std::string operations_research::bop::GetSolveStatusString ( BopSolveStatus status )

inline

Fallback. We don't use "default:" so the compiler will return an error if we forgot one enum case above.

Definition at line 52 of file bop_types.h.

kInvalidOptimizerIndex()

const OptimizerIndex operations_research::bop::kInvalidOptimizerIndex

(

-

1

)

LoadStateProblemToSatSolver()

BopOptimizerBase::Status operations_research::bop::LoadStateProblemToSatSolver	(	const ProblemState &	problem_state,
		sat::SatSolver *	sat_solver )

Loads the problem state into the sat_solver. If the problem has already been loaded in the sat_solver, fixed variables and objective bounds are updated. Returns the status of the load:

• CONTINUE: State problem successfully loaded.
• OPTIMAL_SOLUTION_FOUND: Solution is proved optimal. If a feasible solution exists, this load function imposes the solution to be strictly better. Then when SAT proves the problem is UNSAT, that actually means that the current solution is optimal.
• INFEASIBLE: The problem is proved to be infeasible.

  Note

  the sat_solver will be backtracked to the root level in order to add new constraints.

Definition at line 98 of file bop_util.cc.

operator<<() [1/2]

std::ostream & operations_research::bop::operator<< ( std::ostream & os, BopOptimizerBase::Status status )

inline

Definition at line 110 of file bop_base.h.

operator<<() [2/2]

std::ostream & operations_research::bop::operator<< ( std::ostream & os, BopSolveStatus status )

inline

Definition at line 69 of file bop_types.h.

SatAssignmentToBopSolution()

void operations_research::bop::SatAssignmentToBopSolution	(	const sat::VariablesAssignment &	assignment,
		BopSolution *	solution )

Only extract the variables of the initial problem.

Definition at line 132 of file bop_util.cc.

Variable Documentation

_BopOptimizerMethod_default_instance_

OR_PROTO_DLL BopOptimizerMethodDefaultTypeInternal operations_research::bop::_BopOptimizerMethod_default_instance_

Definition at line 53 of file bop_parameters.pb.cc.

_BopParameters_default_instance_

OR_PROTO_DLL BopParametersDefaultTypeInternal operations_research::bop::_BopParameters_default_instance_

Definition at line 141 of file bop_parameters.pb.cc.

_BopSolverOptimizerSet_default_instance_

OR_PROTO_DLL BopSolverOptimizerSetDefaultTypeInternal operations_research::bop::_BopSolverOptimizerSet_default_instance_

Definition at line 78 of file bop_parameters.pb.cc.

BopOptimizerMethod_class_data_

OR_PROTO_DLLconst::google::protobuf::internal::ClassDataFull operations_research::bop::BopOptimizerMethod_class_data_

Initial value:

=
        BopOptimizerMethod::InternalGenerateClassData_()

Definition at line 448 of file bop_parameters.pb.cc.

BopOptimizerMethod_OptimizerType_internal_data_

OR_PROTO_DLL const uint32_t operations_research::bop::BopOptimizerMethod_OptimizerType_internal_data_

Initial value:

= {
    393216u, 32u, 3950u, }

Definition at line 356 of file bop_parameters.pb.cc.

BopOptimizerMethod_OptimizerType_OptimizerType_ARRAYSIZE

int operations_research::bop::BopOptimizerMethod_OptimizerType_OptimizerType_ARRAYSIZE = 17 + 1

inlineconstexpr

Definition at line 115 of file bop_parameters.pb.h.

BopOptimizerMethod_OptimizerType_OptimizerType_MAX

BopOptimizerMethod_OptimizerType operations_research::bop::BopOptimizerMethod_OptimizerType_OptimizerType_MAX

inlineconstexpr

Initial value:

=
    static_cast<BopOptimizerMethod_OptimizerType>(17)

Definition at line 110 of file bop_parameters.pb.h.

BopOptimizerMethod_OptimizerType_OptimizerType_MIN

BopOptimizerMethod_OptimizerType operations_research::bop::BopOptimizerMethod_OptimizerType_OptimizerType_MIN

inlineconstexpr

Initial value:

=
    static_cast<BopOptimizerMethod_OptimizerType>(0)

Definition at line 108 of file bop_parameters.pb.h.

BopParameters_class_data_

OR_PROTO_DLLconst::google::protobuf::internal::ClassDataFull operations_research::bop::BopParameters_class_data_

Initial value:

=
        BopParameters::InternalGenerateClassData_()

Definition at line 1003 of file bop_parameters.pb.cc.

BopParameters_ThreadSynchronizationType_internal_data_

OR_PROTO_DLL const uint32_t operations_research::bop::BopParameters_ThreadSynchronizationType_internal_data_

Initial value:

= {
    196608u, 0u, }

Definition at line 362 of file bop_parameters.pb.cc.

BopParameters_ThreadSynchronizationType_ThreadSynchronizationType_ARRAYSIZE

int operations_research::bop::BopParameters_ThreadSynchronizationType_ThreadSynchronizationType_ARRAYSIZE = 2 + 1

inlineconstexpr

Definition at line 148 of file bop_parameters.pb.h.

BopParameters_ThreadSynchronizationType_ThreadSynchronizationType_MAX

BopParameters_ThreadSynchronizationType operations_research::bop::BopParameters_ThreadSynchronizationType_ThreadSynchronizationType_MAX

inlineconstexpr

Initial value:

=
    static_cast<BopParameters_ThreadSynchronizationType>(2)

Definition at line 143 of file bop_parameters.pb.h.

BopParameters_ThreadSynchronizationType_ThreadSynchronizationType_MIN

BopParameters_ThreadSynchronizationType operations_research::bop::BopParameters_ThreadSynchronizationType_ThreadSynchronizationType_MIN

inlineconstexpr

Initial value:

=
    static_cast<BopParameters_ThreadSynchronizationType>(0)

Definition at line 141 of file bop_parameters.pb.h.

BopSolverOptimizerSet_class_data_

OR_PROTO_DLLconst::google::protobuf::internal::ClassDataFull operations_research::bop::BopSolverOptimizerSet_class_data_

Initial value:

=
        BopSolverOptimizerSet::InternalGenerateClassData_()

Definition at line 701 of file bop_parameters.pb.cc.

kInfinity

Fractional operations_research::glop::kInfinity

constexpr

Infinity for type Fractional.

Definition at line 87 of file lp_types.h.