Class CutAndPlay

Inheritance Relationships

Base Type

Class Documentation

class CutAndPlay : public Algorithms::EPEC::PolyBase

This class is responsible for the Cut-and-Play Algorithm.

Public Functions

inline explicit CutAndPlay(GRBEnv *env, Game::EPEC *EPECObject)

Standard constructor.

Parameters

  • env – Pointer to the Gurobi environment

  • EPECObject – Pointer to the EPEC

CutAndPlay() = delete
inline double getTol() const

Read-Only getter for CutAndPlay::Tolerance.

inline void setTol(double tol)

Setter for CutAndPlay::Tolerance.

virtual void solve() override

Given the Game::EPEC instance, this method solves it through the outer approximation scheme.

void printCurrentApprox()

Prints a log message containing the encoding at the current outer approximation iteration.

virtual bool isSolved(double tol = 1e-4) override

Overrides Algorithms::EPEC::PolyBase::isSolved with a custom method.

Parameters

tol – Numerical tolerance. Currently not useful

Returns

True if the current outer approximation solution is feasible (then, it is solved)

bool isFeasible(bool &addedCuts)

Checks whether the current outer approximation equilibrium is feasible and solves the problem. Otherwise, it adds cuts or generate useful information for the next iterations.

Parameters

addedCuts – [out] is true if at least a cut has been added

Returns

bool isPureStrategy(double tol = 1e-4) const

Checks whether the current solution is a pure-strategy nash equilibrium.

Parameters

tol – A numerical tolerance. Currently not used

Returns

True if the strategy is a pure nash equilibrium

Public Static Functions

static void printBranchingLog(std::vector<int> vector)

Given the vector of branching candidates from Algorithms::EPEC::CutAndPlay::getNextBranchLocation, prints a sum up of them.

Parameters

vector – Output of Algorithms::EPEC::CutAndPlay::getNextBranchLocation

Protected Functions

void after()

Standard method for post-solve execution.

void updateMembership(const unsigned int &player, const arma::vec &xOfI)

Updates the membership linear-program in the relative Algorithms::EPEC::CutAndPlay::Trees for the player player.

Parameters

  • player – The player index

  • xOfI – The point for which the membership LP should be updated for

int hybridBranching(unsigned int player, OuterTree::Node *node)

Given player &#8212; containing the id of the player, returns the branching decision for that node given by a hybrid branching rule. In particular, the method return the complementarity id maximizing a combination of constraint violations and number of violated constraints. node contains the tree’s node. It isn’t const since a branching candidate can be pruned if infeasibility is detected. Note that if the problem is infeasible, namely one complementarity branching candidate results in an infeasible relaxation, then all branching candidates are removed from the list of branching candidates.

Parameters

  • player – The player id

  • node – The pointer to the incumbent OuterTree::Node

Returns

The branching candidate. -1 if none. -2 if infeasible.

int infeasibleBranching(unsigned int player, const OuterTree::Node *node)

Given player &#8212; containing the id of the player, returns the branching decision for that node, where the complementarity is the most (possibly) infeasible one (with both x and z positive). In particular, the method return the (positive) id of the complementarity equation if there is a feasible branching decision at node, and a negative value otherwise.

Parameters

  • player – The player id

  • node – The pointer to the incumbent OuterTree::Node

Returns

The branching candidate. Negative if none

int deviationBranching(unsigned int player, const OuterTree::Node *node)

Given player &#8212; containing the id of the player, returns the branching decision for that node, where the complementarity helps include the deviation. In particular, the method return the (positive) id of the complementarity equation if there is a feasible branching decision at node, and a negative value otherwise.

Parameters

  • player – The player id

  • node – The pointer to the incumbent OuterTree::Node

Returns

The branching candidate. Negative if none

std::unique_ptr<GRBModel> getFeasibilityQP(const unsigned int player, const arma::vec &x)

Given the player index player, gets a feasibility quadratic problem enforcing x to be in the feasible (approximated) region of the Game::EPEC::PlayersQP.

Parameters

  • player – The player index

  • x – The strategy for the player

Returns

A Gurobi pointer to the model

void addValueCut(unsigned int player, double RHS, const arma::vec &xMinusI)

Adds a value cut to player MathOpt::LCP.

Parameters

  • player – The index of the player

  • RHS – The RHS of the value cut

  • xMinusI – The strategies of the other players

bool equilibriumOracle(arma::vec &xOfI, arma::vec &x, unsigned int player, int budget, bool &addedCuts)

The main Equilibrium CutAndPlay loop. Given a player, a maximum number of iterations, a strategy and the other players strategy, it tries to determine if xOfI is feasible for player.

Parameters

  • xOfI – The incumbent strategy for player

  • x – The full solution vector

  • player – The player id

  • budget – A bound on the number of iteration

  • addedCuts – The number of added cuts

Returns

1 if feasible. 0 if infeasible. 2 if iteration limit was hit.

bool isFeasiblePure(const unsigned int player, const arma::vec &x)

Given the player index player, gets a feasibility quadratic problem enforcing x to be in the feasible region of the given player.

Parameters

  • player – The player index

  • x – The strategy for the player

Returns

A Gurobi pointer to the model

void originFeasibility(unsigned int player)

Gets the LCP for player player, and tries to see whether the origin is feasible. If the answer is yes, sets the corresponding object in the tree to true.

Parameters

player – The player’s id

Private Functions

std::vector<int> getNextBranchLocation(unsigned int player, OuterTree::Node *node)

Given player &#8212; containing the id of the player &#8212; and node containing a node, returns the branching decision for that node, with respect to the current node. In particular, the method return the (positive) id of the complementarity equation if there is a feasible branching decision at node, and a negative value otherwise.

Parameters

  • player – The player id

  • node – The pointer to the incumbent OuterTree::Node

Returns

A vector of 4 integers with the branching location given by the most Algorithms::EPEC::CutAndPlay::infeasibleBranching, Algorithms::EPEC::CutAndPlay::deviationBranching, Algorithms::EPEC::CutAndPlay::hybridBranching, and Algorithms::EPEC::CutAndPlay::getFirstBranchLocation, respectively. If an int is negative, there is no real candidate.

int getFirstBranchLocation(const unsigned int player, OuterTree::Node *node)

Given player &#8212; containing the id of the player, returns the branching decision for that node, with no complementarity condition enforced. In particular, the method return the (positive) id of the complementarity equation if there is a feasible branching decision at node, and a negative value otherwise.

Parameters

  • player – The player id

  • node – The pointer to the incumbent OuterTree::Node

Returns

The branching candidate. Negative if none

Private Members

std::vector<OuterTree*> Trees

The vector of pointer to OuterTree for each player.

std::vector<OuterTree::Node*> Incumbent

The incumbent nodes for each player.

bool Feasible = {false}

True if a feasible solution has been found.

double Tolerance = 3 * 1e-5

The numerical tolerance for the algorithm.