Class OuterTree

Nested Relationships

Nested Types

Class Documentation

class Algorithms::EPEC::OuterTree

This class manages the outer approximation tree.

Public Functions

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

Adds a vertex to OuterTree::V.

  • vertex – The vector containing the vertex

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


True if the vertex was added

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

Adds a ray to OuterTree::R.


ray – The vector containing the ray

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

A getter method for the nodes in the tree.


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.

  • 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.

  • idComp – The branching id for the complementarity

  • t – The pointer to the node


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 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.


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.

  • 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.

  • 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.


The number of unsuitable branching candidates

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.


friend class OuterTree