Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | List of all members
operations_research::math_opt::AtomicConstraintStorage< ConstraintData > Class Template Reference

#include <atomic_constraint_storage.h>

Classes

struct  Diff
 

Public Types

using IdType = typename ConstraintData::IdType
 
using ProtoType = typename ConstraintData::ProtoType
 
using UpdatesProtoType = typename ConstraintData::UpdatesProtoType
 

Public Member Functions

IdType AddConstraint (ConstraintData constraint)
 Add a single constraint to the storage.
 
void AddConstraints (const google::protobuf::Map< int64_t, ProtoType > &constraints)
 
template<typename DiffIter >
void Delete (IdType id, const iterator_range< DiffIter > &diffs)
 Delete a single constraint.
 
void DeleteVariable (VariableId variable_id)
 Delete a single variable from each constraint in the storage.
 
int64_t size () const
 
IdType next_id () const
 The smallest ID which is valid for a new constraint.
 
void ensure_next_id_at_least (const IdType minimum)
 Sets the next variable id to be the maximum of next_id() and minimum.
 
bool contains (const IdType id) const
 Returns true if this id has been created and not yet deleted.
 
const absl::flat_hash_set< IdType > & RelatedConstraints (const VariableId variable_id) const
 
std::vector< IdType > Constraints () const
 The ids in use (not deleted). The order is not defined.
 
std::vector< IdType > SortedConstraints () const
 
google::protobuf::Map< int64_t, ProtoType > Proto () const
 Returns a proto representation of the constraint class.
 
const ConstraintData & data (const IdType id) const
 
bool diff_is_empty (const Diff &diff) const
 
ConstraintData::UpdatesProtoType Update (const Diff &diff) const
 Return a proto representation of the current update.
 
void AdvanceCheckpointInDiff (Diff &diff) const
 Updates the checkpoint and clears all stored changes in diff.
 

Detailed Description

template<typename ConstraintData>
class operations_research::math_opt::AtomicConstraintStorage< ConstraintData >

Storage for a "mapped" constraint type whose only supported updates are constraint addition, and variable or constraint deletion.

The constraints are "atomic" in the sense that they can be added or deleted individually, but direct data updates (e.g., to coefficients) are not permitted. Note that they are not strictly immutable, though, as variable deletions may have side effects (e.g., a constraint considers a deleted variable as implicitly fixed to zero).

Implementers of new constraint families should provide a conforming ConstraintData definition, along with a template specialization of AtomicConstraintTraits (defined below). These should likely be placed in math_opt/constraints/$new_constraint_family/storage.h.

The ConstraintData parameter should refer to a class to represent a single constraint in memory. It must satisfy a duck-typed interface:

  • A IdType alias to the (strong int) ID type for the constraint class.
  • A ProtoType alias to the proto message for a single constraint.
  • An UpdatesProtoType alias to the proto message for updates for the given constraint type, as represented by two fields:

A member function to return all variables involved in the constraint: std::vector<VariableId> RelatedVariables() const;

  • A member function to delete a variable from the constraint: void DeleteVariable(VariableId var);
  • A member function that returns a proto representation of the constraint: ProtoType Proto() const;
  • A static member function that initializes a constraint from its proto representation: static ConstraintData FromProto(const ProtoType& in_proto);

The setter functions all accept a DiffIter, which must be an iterator over non-const references to AtomicConstraintStorage<ConstraintData>::Diff. These functions will modify the diff objects.

Definition at line 70 of file atomic_constraint_storage.h.

Member Typedef Documentation

◆ IdType

template<typename ConstraintData >
using operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::IdType = typename ConstraintData::IdType

Definition at line 72 of file atomic_constraint_storage.h.

◆ ProtoType

template<typename ConstraintData >
using operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::ProtoType = typename ConstraintData::ProtoType

Definition at line 73 of file atomic_constraint_storage.h.

◆ UpdatesProtoType

template<typename ConstraintData >
using operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::UpdatesProtoType = typename ConstraintData::UpdatesProtoType

Definition at line 74 of file atomic_constraint_storage.h.

Member Function Documentation

◆ AddConstraint()

template<typename ConstraintData >
AtomicConstraintStorage< ConstraintData >::IdType operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::AddConstraint ( ConstraintData constraint)

Add a single constraint to the storage.

Inlined implementations

Definition at line 192 of file atomic_constraint_storage.h.

◆ AddConstraints()

template<typename ConstraintData >
void operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::AddConstraints ( const google::protobuf::Map< int64_t, ProtoType > & constraints)

Adds a collection of constraints to the storage, from an "id-to-proto" map. The keys for the input map will be used as the associated IDs in storage.

Will CHECK-fail if any ID is less than next_id().

Definition at line 204 of file atomic_constraint_storage.h.

◆ AdvanceCheckpointInDiff()

template<typename ConstraintData >
void operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::AdvanceCheckpointInDiff ( Diff & diff) const

Updates the checkpoint and clears all stored changes in diff.

Definition at line 273 of file atomic_constraint_storage.h.

◆ Constraints()

template<typename ConstraintData >
std::vector< typename AtomicConstraintStorage< ConstraintData >::IdType > operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::Constraints ( ) const

The ids in use (not deleted). The order is not defined.

Definition at line 250 of file atomic_constraint_storage.h.

◆ contains()

template<typename ConstraintData >
bool operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::contains ( const IdType id) const
inline

Returns true if this id has been created and not yet deleted.

Definition at line 119 of file atomic_constraint_storage.h.

◆ data()

template<typename ConstraintData >
const ConstraintData & operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::data ( const IdType id) const
inline

Returns the underlying data for constraint id. Will crash if id is not present (i.e., if contains(id) returns false).

Definition at line 146 of file atomic_constraint_storage.h.

◆ Delete()

template<typename ConstraintData >
template<typename DiffIter >
void operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::Delete ( IdType id,
const iterator_range< DiffIter > & diffs )

Delete a single constraint.

if the constraint >= checkpoint_, we don't store any info.

Definition at line 218 of file atomic_constraint_storage.h.

◆ DeleteVariable()

template<typename ConstraintData >
void operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::DeleteVariable ( VariableId variable_id)

Delete a single variable from each constraint in the storage.

Definition at line 236 of file atomic_constraint_storage.h.

◆ diff_is_empty()

template<typename ConstraintData >
bool operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::diff_is_empty ( const Diff & diff) const
inline

Functions for working with Diff Returns true if there are no changes (tracked changes before the checkpoint or new constraints after the checkpoint).

Definition at line 267 of file atomic_constraint_storage.h.

◆ ensure_next_id_at_least()

template<typename ConstraintData >
void operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::ensure_next_id_at_least ( const IdType minimum)
inline

Sets the next variable id to be the maximum of next_id() and minimum.

Definition at line 114 of file atomic_constraint_storage.h.

◆ next_id()

template<typename ConstraintData >
IdType operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::next_id ( ) const
inline

The smallest ID which is valid for a new constraint.

Definition at line 111 of file atomic_constraint_storage.h.

◆ Proto()

template<typename ConstraintData >
google::protobuf::Map< int64_t, ProtoType > operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::Proto ( ) const
inline

Returns a proto representation of the constraint class.

Definition at line 136 of file atomic_constraint_storage.h.

◆ RelatedConstraints()

template<typename ConstraintData >
const absl::flat_hash_set< IdType > & operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::RelatedConstraints ( const VariableId variable_id) const
inline

Definition at line 121 of file atomic_constraint_storage.h.

◆ size()

template<typename ConstraintData >
int64_t operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::size ( ) const
inline

The number of constraints stored (includes everything created and not yet deleted).

Definition at line 108 of file atomic_constraint_storage.h.

◆ SortedConstraints()

template<typename ConstraintData >
std::vector< typename AtomicConstraintStorage< ConstraintData >::IdType > operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::SortedConstraints ( ) const

Returns a sorted vector of all existing (not deleted) constraints in the model.

Runs in O(n log(n)), where n is the number of constraints returned.

Definition at line 260 of file atomic_constraint_storage.h.

◆ Update()

template<typename ConstraintData >
ConstraintData::UpdatesProtoType operations_research::math_opt::AtomicConstraintStorage< ConstraintData >::Update ( const Diff & diff) const

Return a proto representation of the current update.

Definition at line 281 of file atomic_constraint_storage.h.

The documentation for this class was generated from the following file: