Class PolyLCP

• Defined in File poly_lcp.h

Inheritance Relationships

Base Type

• public MathOpt::LCP (Class LCP)

Class Documentation

class PolyLCP : public MathOpt::LCP

Inheritor Class to handle the polyhedral aspects of the LCP class, and support algorithms. It mainly approximates the MathOpt::LCP feasible region with polyhedra. Each polyhedron is encoded with a {-1, 0, 1 2} scheme, which is used through the class.

There are three different usages for this class. Consider an encoding vector \( \bar{e} \) with a number of elements equal to LCP::nC.

• An inner approximation scheme, where the MathOpt::LCP is approximated by a union of polyhedra from the inside. For a given complementarity \( i \in [nC] \) , each polyhedron either fixes the complementarity to zero (e.g., \( z_i = 0 \) ) with an encoding \( \bar{e}_i=1 \) , or the corresponding variable to zero (e.g., \( x_i = 0 \) ) with an encoding \( \bar{e}_i=-1 \) . An encoding of \( \bar{e}_i=-0 \) is not allowed in the polyhedron. However, the methods in this class will generate children polyhedron having either \( \bar{e}_i=-1 \) or \( \bar{e}_i=+1 \)

• A full approximation scheme, which basically inner-approximate all the polyhedra. The starting encoding is \( \bar{e}=0 \) generates all the child polyhedra.

• An outer approximation scheme, where the MathOpt::LCP is approximated by a union of polyhedra from the outside. In contrast with the inner and full enumeration, here we allow a complementarity to be not enforced (not included in the model). In this sense, an encoding \( \bar{e}_i=2 \) means that the complementarity is not present in the current polyhedron.

Any encoding \( \bar{e} \) can be transformed to a single integer with the methods PolyLCP::vecToNum, and its inverse PolyLCP::numToVec. As for these two methods, their parameter innerApproximation controls whether the encoding is for the inner or full approaches (true), or for the outer approximation (false. In the class, the function replicate this behavior with their input parameters innerApproximation. The encodings used in such methods are then conformed to the above rationale. Finally, the fields may prepend Inner_ or _Outer depending on whether they are useful for one approach or the other.

Public Functions

inline PolyLCP(GRBEnv *env, const Game::NashGame &N)

A constructor given the Nash Game. It initializes unprocessed field members and the polyhedra objects in MathOpt::LCP.

Parameters

• env – The Gurobi pointer to the environment

• N – The Nash Game

inline unsigned long int getNumTheoreticalPoly() const noexcept

Getter (read-only) for the field PolyLCP::Inner_MaxPoly.

inline bool getFeasOuterApp() const

Getter (read-only) for the field PolyLCP::Outer_FeasibleApproximation.

inline std::array<std::set<unsigned long int>, 2> getAllPolyhedra() const

Gets the CurrentPoly object.

Returns

PolyLCP::CurrentPoly

void clearPolyhedra(bool inner)

Getter (read-only) for the field PolyLCP::CurrentPoly.

unsigned long convNumPoly(bool innerApproximation) const

Returns the number of polyhedra in the current approximation for the LCP feasible region.

Parameters

innerApproximation – True whenever the result is related to the inner-full approximation

Returns

The number of polyhedra

std::vector<short int> solEncode(const arma::vec &z, const arma::vec &x) const

Given variable values and equation values, encodes it in 0/+1/-1 format and returns it.

Parameters

• z – The equation values

• x – The variable values

Returns

an vector with the encoding {-1,0,1}

std::vector<short int> solEncode(const arma::vec &x) const

Given a point, it returns an encoding of {-1,0,1} associated with the polyhedron containing it.

Warning

The encoding cannot contain 2s!

Parameters

x – is the given point

Returns

an vector with the encoding {-1,0,1}

unsigned int convPolyPosition(const unsigned long int i, bool innerApproximation) const

Returns the position of polyhedron i’s variables in the current approximation for the LCP feasible region.

Parameters

• innerApproximation – True whenever the result is related to the inner-full approximation

• i – The polyhedron index.

Returns

The polyhedron’s variables positions

unsigned int convPolyWeight(const unsigned long int i, bool innerApproximation) const

Returns the position of the variable related to the convex weight of the i -th polyhedron.

Parameters

• i – The polyhedron index

• innerApproximation – True whenever the result is related to the inner-full approximation

Returns

The weight’s position

unsigned int addAPoly(unsigned long int nPoly = 1, Data::LCP::PolyhedraStrategy method = Data::LCP::PolyhedraStrategy::Sequential)

Adds a number nPoly of polyhedra to the current inner-full approximation, given a method of selection.

Warning

Suitable only for inner-full approximation

Parameters

• nPoly – The number of polyhedra

• method – The Data::LCP::PolyhedraStrategy method

Returns

The number of added polyhedra

bool addThePoly(const unsigned long int &decimalEncoding, bool innerApproximation)

Given a decimal encoding, adds the polyhedron to the relative approximation.

Parameters

• decimalEncoding – The encoding of the polyhedron

• innerApproximation – True if the encoding is an inner-full one, and the polyhedron should be added to the inner-full approximation

Returns

True if the polyhedron is added

bool checkPolyFeas(const unsigned long int &decimalEncoding, bool innerApproximation)

Given a decimal encoding, it checks whether the associated polyhedron is feasible or not.

Parameters

• decimalEncoding – The decimal encoding, either inner-full or outer

• innerApproximation – True if the encoding is inner-full. False otherwise

Returns

True if the polyhedron is feasible

bool checkPolyFeas(const std::vector<short int> &encoding, bool innerApproximation)

Given an encoding, it checks whether the associated polyhedron is feasible or not.

Parameters

• encoding – The encoding of the polyhedron

• innerApproximation – True if the encoding is inner-full. False otherwise

Returns

True if the polyhedron is feasible

bool addPolyFromX(const arma::vec &x, bool innerApproximation)

Given a feasible point, checks if the polyhedron containing it is already part of the approximation. If not, it adds it to the feasible region.

Warning

So far, only for the innerApproximation

Parameters

• x – The feasible point

• innerApproximation – True if the point is added to the inner-full approximation

Returns

True if the point is added.

unsigned int exactFullEnumeration(bool feasibilityCheck = true)

Fully enumerates the inner-full encoding of the LCP feasible region, namely by testing (at most) \(2^n\) polyhedra.

Parameters

feasibilityCheck – True if polyhedra should be tested for feasibility before getting added

Returns

The number of added polyhedra

std::string feasabilityDetailString() const

Returns a string containing the inner-full and outer approximation currently in place for the object.

Returns

A string detail

bool outerApproximate(const std::vector<bool> &encoding, bool clear = true)

Given a vector of active complementarities, outer approximates the MathOpt::LCP by computing the polyhedra where only the indicated complementarities are enforced.

Parameters

• encoding – A vector of the size of MathOpt::nC where true indicates that the complementarity is enforced, and false not.

• clear – True if the previous polyhedra and approximation is cleared before adding the new one

Returns

True if at least one polyhedron is feasible

inline unsigned int getFeasiblePolyhedra() const

Gets the size of LCP::FeasiblePoly (0) for inner-approximated polyhedra.

Returns

The size ofLCP::FeasiblePoly at (0)

std::vector<short> numToVec(unsigned long number, const unsigned long nCompl, bool inner)

This function transform the encoding associated to number, given a number of complementarities in nCompl, into a vector encoding. If inner is true, valid entries for binary are in {-1,1}, and in {-1,1,2} otherwise. The reverse of this function is given by MathOpt::PolyLCP::numToVec.

Parameters

• number – The decimal encoding

• nCompl – The number of complementarities, also the length of the final vector encoding

• inner – True if the encoding is an inner-full one

Returns

The vector encoding

unsigned long vecToNum(std::vector<short> binary, bool inner)

This function converts the vector encoding of binary to an unsigned long int. The parameter inner controls whether the encoding is the one of the inner approximation or the outer approximation. If inner is true, valid entries for binary are in {-1,1} and in {-1,1,2} otherwise. The reverse of this function is given by MathOpt::PolyLCP::numToVec.

Parameters

• binary – The vector encoding

• inner – True if the encoding is an inner-full one

Returns

The decimal encoding

Public Members

long int RandomSeed = {-1}

Theseed for random operations.

Private Functions

inline void initializeSizes()

Initializes the counter of polyhedra for the inner approximation, and the maximum number of them.

bool addPolyFromEncoding(const std::vector<short int> &encoding, bool innerApproximation = true, bool checkFeas = false, bool custom = false, spmat_Vec *customA = {}, vec_Vec *customb = {})

Given a vector encoding for a given polyhedron, it adds it to one of the approximations in the PolyLCP. If innerApproximation is true, then the encoding is an inner-full approximation one, and the polyhedron may go in the associated objects. Otherwise, the encoding is an outer approximation one, and goes as well in the relative object.

Warning

Use PolyLCP::addPoliesFromEncoding for multiple polyhedra

Parameters

• encoding – An inner-full or outer encoding. If custom is true, the polyhedron is added to a custom object passed to the method

• innerApproximation – True if the encoding is an inner-full one, false otherwise

• checkFeas – True if the method should check for the feasibility before adding

• custom – True if the polyhedron should be added to the custom object

• customA – Custom polyhedra LHS

• customb – Custom polyhedra RHS

Returns

True if the operation was performed correctly. False if the polyhedron is infeasible or was not added

unsigned int addPoliesFromEncoding(const std::vector<short> &encoding, bool innerApproximation = true, bool checkFeas = false, bool custom = false, spmat_Vec *customA = {}, vec_Vec *customb = {})

Given a vector encoding for some given polyhedra, it adds them to one of the approximations in the PolyLCP. If innerApproximation is true, then the encoding is an inner-full approximation one, and the polyhedron may go in the associated objects. Otherwise, the encoding is an outer approximation one, and goes as well in the relative object. Note that this method may add multiple polyhedra, and allows the encoding 0 in both inner-full and outer cases. When a 0 is detected in a given position, children polyhedra with either -1 or +1 are recursively added.

Warning

Use PolyLCP::addPolyFromEncoding for a single polyhedron

Parameters

• encoding – An inner-full or outer encoding. If custom is true, the polyhedron is added to a custom object passed to the method

• innerApproximation – True if the encoding is an inner-full one, false otherwise

• checkFeas – True if the method should check for the feasibility before adding

• custom – True if the polyhedron should be added to the custom object

• customA – Custom polyhedra LHS

• customb – Custom polyhedra RHS

Returns

A positive int for the number of added polyhedra. False if the polyhedron is infeasible or was not added

unsigned long int getNextPoly(Data::LCP::PolyhedraStrategy method)

Returns the inner-full decimal encoding of a given polyhedron that is neither known to be infeasible, nor already in the inner-full approximation.

Warning

meant to be used for inner approximation only.

Parameters

method – Data::LCP::PolyhedraStrategy strategy for selecting the polyhedron

Returns

The inner-full decimal encoding of the polyhedron

Private Members

bool Outer_FeasibleApproximation = false

True when the current outer approximation in CurrentPoly[1] is feasible.

unsigned int Inner_SequentialPolyCounter = {0}

A sequential counter for the polyhedra (integer) encoding that the inner approximation considered. Useful in PolyLCP::getNextPoly

long int Inner_ReverseSequentialPolyCounter = {0}

An inverse-sequential counter for the polyhedra (integer) encoding that the inner approximation considered. Useful in PolyLCP::getNextPoly

std::array<std::set<unsigned long int>, 2> CurrentPoly = {}

The current polyhedra in the (approximated) feasible region. The first element of the array is for inner-full approaches, while the second is for the outer approximation. Each element is the decimal encoding associated to the polyhedron, given the approach (inner-full/outer).

std::array<std::set<unsigned long int>, 2> FeasiblePoly = {}

The current known feasible polyhedra for the (approximated) feasible region. The first element of the array is for inner-full approaches, while the second is for the outer approximation. Each element is the decimal encoding associated to the polyhedron, given the approach (inner-full/outer).

std::array<std::set<unsigned long int>, 2> InfeasiblePoly = {}

The current known infeasible polyhedra for the (approximated) feasible region. The first element of the array is for inner-full approaches, while the second is for the outer approximation. Each element is the decimal encoding associated to the polyhedron, given the approach (inner-full/outer).

unsigned long int Inner_MaxPoly = {0}

The maximum number of polyhedra for the inner approximation of full enumartion