Class OuterTree

Nested Relationships

Nested Types

Class Documentation

class OuterTree

This class manages the outer approximation tree.

Public Functions

inline OuterTree(unsigned int encSize, GRBEnv *env)

Constructor of the Tree given the encoding size.

inline void resetFeasibility()

Reset the feasibility parameters for the tree.

inline bool getPure() const

Read-only getter for OuterTree::isPure.

inline void setFeasible()

Read-only getter for OuterTree::isFeasible.

inline void setPure()

Setter for OuterTree::isPure.

inline unsigned int getEncodingSize() const

Getter for the encoding size.

inline const arma::sp_mat *getV()

Getter for OuterTree::V.

inline const arma::sp_mat *getR()

Getter for OuterTree::R.

inline unsigned int getVertexCount() const

Getter for OuterTree::VertexCounter.

inline unsigned int getRayCount() const

Getter for OuterTree::RayCounter.

inline bool addVertex(const arma::vec &vertex, bool checkDuplicates)

Adds a vertex to OuterTree::V.

Parameters

  • vertex – The vector containing the vertex

  • checkDuplicates – True if the method has to check for duplicates

Returns

True if the vertex was added

inline void addRay(const arma::vec &ray)

Adds a ray to OuterTree::R.

Parameters

ray – The vector containing the ray

inline Node *getRoot()

Getter for the root node.

inline std::vector<Node> *getNodes()

A getter method for the nodes in the tree.

Returns

The pointer to the nodes in the tree

void denyBranchingLocation(Node &node, const unsigned int &location) const

If a complementarity equation location has proven to be infeasible or it isn’t a candidate for branching, this method prevents any further branching on it for the node node.

Parameters

  • node – The node pointer

  • location – The denied branching location

std::vector<long int> singleBranch(unsigned int idComp, Node &t)

Given the idComp and the parent node t, creates a single child by branching on idComp.

Parameters

  • idComp – The branching id for the complementarity

  • t – The pointer to the node

Returns

The node counter stored in a single-element vector

Protected Attributes

std::unique_ptr<GRBModel> MembershipLP

Stores the pointer to the MembershipLP associated to the tree.

std::unique_ptr<MathOpt::PolyLCP> OriginalLCP

Stores the original LCP. This object is separated from the working one to avoid bugs and numerical problems.

arma::sp_mat V = {}

Stores the known extreme vertices of the player’s feasible region. These are used to derive valid cuts, or certify that an equilibrium is inside (outside) the convex-hull of the feasible region.

arma::sp_mat R = {}

As in V, but instead of vertices, this object contains rays.

unsigned int VertexCounter = 0

The counter for node ids.

unsigned int RayCounter = 0

The counter for node ids.

bool containsOrigin = false

True if the origin is feasible.

Private Functions

inline unsigned int nextIdentifier()

Increments the node counter and get the id of the new node.

Private Members

Node Root = Node(0)

The root node of the tree.

unsigned int EncodingSize = 0

The size of the encoding, namely the number of complementarity equations.

unsigned int NodeCounter = 1

The counter for node ids.

std::vector<Node> Nodes = {}

Storage of nodes in the tree with the vertices in V

bool isPure = {false}

True if the strategy at the current node is a pure-strategy.

bool isFeasible{false}

True if the strategy at the current node is feasible for the original game.

struct Node

Public Functions

explicit Node(unsigned int encSize)

Constructor for the root node, given the encoding size, namely the number of complementarity equations.

Parameters

encSize – The number of complementarities

Node(Node &parent, unsigned int idComp, unsigned long int id)

Given the parent node address parent, the idComp to branch on, and the id, creates a new node.

Parameters

  • parent – The parent node

  • idComp – The id of the node

  • id – The The branching candidate

Node(Node &parent, std::vector<int> idComps, unsigned long int id)

Given the parent node address parent, the idsComp to branch on (containing all the complementarities ids), and the id, creates a new node.

Parameters

  • parent – The parent node pointer

  • idsComp – The vector of branching locations

  • id – The node id for the children

inline unsigned long int getCumulativeBranches() const

Returns the number of variables that cannot be candidate for the branching decisions, namely the ones on which a branching decision has already been taken, or for which the resulting child node is infeasible.

Returns

The number of unsuitable branching candidates

inline std::vector<bool> getEncoding() const

Getter method for the encoding.

inline std::vector<bool> getAllowedBranchings() const

Getter method for the allowed branchings.

Private Members

std::vector<unsigned int> IdComps

Contains the branching decisions taken at the node.

std::vector<bool> Encoding

An encoding of bool. True if the complementarity condition is included in the current node outer approximation, false otherwise.

std::vector<bool> AllowedBranchings

A vector where true means that the corresponding complementarity is a candidate for branching at the current node

unsigned long int Id

A long int giving the numerical identifier for the node.

Node *Parent = {}

A pointer to the parent node.

Friends

friend class OuterTree