operations_research::AffineRelation Class Reference

#include <affine_relation.h>

Classes
struct	Relation

Public Member Functions
	AffineRelation ()
int	NumRelations () const
	Returns the number of relations added to the class and not ignored.
bool	TryAdd (int x, int y, int64_t coeff, int64_t offset)
bool	TryAdd (int x, int y, int64_t coeff, int64_t offset, bool allow_rep_x, bool allow_rep_y)
Relation	Get (int x) const
void	IgnoreFromClassSize (int x)
int	ClassSize (int x) const
	Returns the size of the class of x.

Detailed Description

Union-Find algorithm to maintain "representative" for relations of the form: x = coeff * y + offset, where "coeff" and "offset" are integers. The variable x and y are represented by non-negative integer indices. The idea is to express variables in affine relation using as little different variables as possible (the representatives).

IMPORTANT: If there are relations with std::abs(coeff) != 1, then some relations might be ignored. See TryAdd() for more details.

Todo

(user): it might be possible to do something fancier and drop less relations if all the affine relations are given before hand.

Definition at line 37 of file affine_relation.h.

Constructor & Destructor Documentation

AffineRelation()

operations_research::AffineRelation::AffineRelation ( )

inline

Definition at line 39 of file affine_relation.h.

Member Function Documentation

ClassSize()

int operations_research::AffineRelation::ClassSize ( int x ) const

inline

Returns the size of the class of x.

Definition at line 111 of file affine_relation.h.

Get()

AffineRelation::Relation operations_research::AffineRelation::Get ( int x ) const

inline

Definition at line 215 of file affine_relation.h.

IgnoreFromClassSize()

void operations_research::AffineRelation::IgnoreFromClassSize ( int x )

inline

Advanced usage. This is a bit hacky and will just decrease the class size of a variable without any extra checks. Use with care. In particular when this is called, then x should never be used anymore in any of the non const calls of this class.

Definition at line 97 of file affine_relation.h.

NumRelations()

int operations_research::AffineRelation::NumRelations ( ) const

inline

Returns the number of relations added to the class and not ignored.

Definition at line 42 of file affine_relation.h.

TryAdd() [1/2]

bool operations_research::AffineRelation::TryAdd ( int x, int y, int64_t coeff, int64_t offset )

inline

Adds the relation x = coeff * y + offset to the class. Returns true if it wasn't ignored.

This relation will only be taken into account if the representative of x and the one of y are different and if the relation can be transformed into a similar relation with integer coefficient between the two representatives.

That is, given that:

• x = coeff_x * representative_x + offset_x
• y = coeff_y * representative_y + offset_y we have: coeff_x * representative_x + offset_x = coeff * coeff_y * representative_y + coeff * offset_y + offset. Which can be simplified with the introduction of new variables to: coeff_x * representative_x = new_coeff * representative_y + new_offset. And we can merge the two if:
  • new_coeff and new_offset are divisible by coeff_x.
  • OR coeff_x and new_offset are divisible by new_coeff.

Checked preconditions: x >=0, y >= 0, coeff != 0 and x != y.

IMPORTANT: we do not check for integer overflow, but that could be added if it is needed.

Definition at line 168 of file affine_relation.h.

TryAdd() [2/2]

bool operations_research::AffineRelation::TryAdd ( int x, int y, int64_t coeff, int64_t offset, bool allow_rep_x, bool allow_rep_y )

inline

Same as TryAdd() with the option to disallow the use of a given representative.

Todo

(user): It should be possible to optimize this code block a bit, for instance depending on the magnitude of new_coeff vs coeff_x, we may already know that one of the two merge is not possible.

Definition at line 173 of file affine_relation.h.

---

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

• ortools/util/affine_relation.h