MathOpt

namespace MathOpt

This namespace contains the definition of the support structures for the mathematical optimization.

Typedefs

typedef struct MathOpt::QP_Objective QP_objective

struct to handle the objective params of MP_Param and inheritors

Refer QP_Param class for what Q, C and c,d mean.

typedef struct MathOpt::QP_Constraints QP_constraints

struct to handle the constraint params of MP_Param and inheritors

Refer QP_Param class for what A, B and b mean.

Functions

unsigned int convexHull(const std::vector<arma::sp_mat*> *Ai, const std::vector<arma::vec*> *bi, arma::sp_mat &A, arma::vec &b, const arma::sp_mat &Acom = {}, const arma::vec &bcom = {})

Computes the convex hull of a finite union of polyhedra where each polyhedra \(P_i\) is of the form.

\[\begin{split}\begin{eqnarray} A^ix &\leq& b^i\\ x &\geq& 0 \end{eqnarray}\end{split}\]

. It uses Balas’ approach to compute the convex hull.

Parameters

Ai – Inequality constraints LHSs that define polyhedra whose convex hull is to be found
bi – Inequality constraints RHSs that define polyhedra whose convex hull is to be found
A – Pointer to store the output of the convex hull LHS
b – Pointer to store the output of the convex hull RHS
Acom – Any common constraints to all the polyhedra - lhs.
bcom – Any common constraints to ALL the polyhedra - RHS.

Returns

void compConvSize(arma::sp_mat &A, unsigned int nFinCons, unsigned int nFinVar, const std::vector<arma::sp_mat*> *Ai, const std::vector<arma::vec*> *bi, const arma::sp_mat &Acom, const arma::vec &bcom)

Generates the matrix “A” in MathOpt::convexHull using batch insertion constructors. Motivation behind this: Response from armadillo:-https://gitlab.com/conradsnicta/armadillo-code/issues/111.

Parameters

A – The output matrix a
nFinCons – Number of rows in final matrix A
nFinVar – Number of columns in the final matrix A
Ai – Input inequality constraints LHSs defining the polyhedra whose convex hull is to be found
bi – Input inequality RHSs defining the polyhedra whose convex hull is to be found
Acom – LHS of the common constraints for all polyhedra
bcom – RHS of the common constraints for all polyhedra

void getDualMembershipLP(std::unique_ptr<GRBModel> &convexModel, unsigned int &numV, const arma::sp_mat &V, unsigned int &numR, const arma::sp_mat &R, const arma::vec &vertex, bool containsOrigin)

Given a vector R of rays, and V or vertices, builds a model in ConvexModel that certifies whether vertex belongs to the convex-hull generated by V and R. In case numV and/or numR are specified, it just updates the model in ConvexModel with the missing vertices and rays. The model is always normalized.

Parameters

convexModel – The pointer to the model
numV – The number of vertices in the model
V – The matrix containing vertices (as rows)
numR – The number of rays in the model
R – The matrix containing rays (as rows)
vertex – The vertex to separate
containsOrigin – True if the origin is a feasible vertex

void getPrimalMembershipLP(std::unique_ptr<GRBModel> &convexModel, unsigned int &numV, const arma::sp_mat &V, unsigned int &numR, const arma::sp_mat &R, const arma::vec &vertex, bool containsOrigin)

Given a vector R of rays, and V or vertices, builds a model in ConvexModel that certifies whether vertex belongs to the convex-hull generated by V and R. In case numV and/or numR are specified, it just updates the model in ConvexModel with the missing vertices and rays. The model is always normalized. From Chvátal, V., Cook, W. and Espinoza, D., 2013. Local cuts for mixed-integer programming. Mathematical Programming Computation, 5(2), pp.171-200.

Parameters

convexModel – The pointer to the model
numV – The number of vertices in the model
V – The matrix containing vertices (as rows)
numR – The number of rays in the model
R – The matrix containing rays (as rows)
vertex – The vertex to separate
containsOrigin – True if the origin is a feasible vertex

void print(const perps &C) noexcept

std::ostream &operator<<(std::ostream &os, const IP_Param &I)

Return a stream containing a stream with the description of the problem.

Parameters

os – Output stream
I – The IP_Param object

Returns

An std::ostream with the description

std::ostream &operator<<(std::ostream &os, const QP_Param &Q)

Return a stream containing a stream with the description of the problem.

Parameters

os – Output stream
Q – The QP_Param object

Returns

An std::ostream with the description

class LCP

#include <lcp.h>

This class manages and solves linear complementarity problems (LCPs). Let \(M\) be a matrix, \(q\) a vector with as many elements as the number of rows of \(M\). The associated LCP problem is to find.

\[ z=Mx+q \qquad x^\top z = 0 \]

Possibly, there can be additional side constraints in the form of

\[ Ax \leq b\]

This class has is the base class of MathOpt::PolyLCP, which manages the polyhedral aspect of the problem.

Subclassed by MathOpt::PolyLCP

Public Functions

LCP() = delete: No default constructor.

inline explicit LCP(GRBEnv *e)

A base constructor that does not initialize most of objects. This is useful when loading from a file

Parameters: e – The Gurobi environment

LCP(GRBEnv *env, arma::sp_mat &M, arma::vec &q, unsigned long int leadStart, unsigned leadEnd, arma::sp_mat &A, arma::vec &b)

A constructor for LCPs where some variables are subject to complementarities. This is useful, for instance, for Stackelberg games.

Parameters

env – The Gurobi environment pointer
M – The M matrix for the LCP
q – The q vector for the LCP
leadStart – Starting location of not-complementary variables
leadEnd – Ending location of not-complementary variables
A – Additional constraints matrix LHS
b – Additional constraints RHS

LCP(GRBEnv *env, arma::sp_mat &M, arma::vec &q, perps &Compl, arma::sp_mat &A, arma::vec &b)

A standard constructor for an LCP.

Parameters

env – The Gurobi environment pointer
M – The M matrix for the LCP
q – The q vector for the LCP
Compl – The complementarity pairs <Equation, Variable>
A – Additional constraints matrix LHS
b – Additional constraints RHS

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

Constructor given a Game::NashGame.

Given a NashGame, computes the KKT of the lower levels, and makes the appropriate LCP object. This constructor is the most suited for high-level usage.

Parameters

env – The Gurobi environment pointer
N – The Game::NashGame

~LCP() = default: Destructor - to delete the objects created with new operator

inline arma::sp_mat getM() const

Read-only access to LCP::M.

Returns: LCP::M

inline arma::vec getq() const

Read-only access to LCP::q.

Returns: LCP::q

inline unsigned long int getNumberLeader() const: Read-only access to LCP::NumberLeader.

inline const unsigned long int getLStart() const

Read-only access to LCP::LeadStart.

Returns: LCP::LeadStart

inline const arma::sp_mat getA() const

Read-only access to LCP::A.

Returns: LCP::A

inline const arma::vec getb() const

Read-only access to LCP::b.

Returns: LCP::b

inline const unsigned long int getLEnd() const

Read-only access to LCP::LeadEnd.

Returns: LCP::LeadEnd

inline perps getCompl() const

Read-only access to LCP::Compl.

Returns: LCP::Compl

inline unsigned long int getNumCols() const

Read-only access to LCP::nC.

Returns: LCP::nC

inline unsigned long int getNumRows() const

Read-only access to LCP::nR.

Returns: LCP::nR

inline bool hasCommonConstraints() const

bool extractSols(GRBModel *model, arma::vec &z, arma::vec &x, bool extractZ = false) const

A method to check whether LCP::A has any non-zero, namely any constraints.

Extracts variable and equation values from a solved Gurobi model.

Parameters

model – The Gurobi Model that was solved
z – Output variable for Z equation values
x – Output variable for X variable values
extractZ – Should the method extract Z values or not

Returns

true if the model was solved. False otherwise.

ZEROStatus solve(Data::LCP::Algorithms algo, arma::vec &xSol, arma::vec &zSol, double timeLimit, unsigned long int threads, double &objective, unsigned long int solLimit = 1)

This method is the generic wrapper to solve the LCP.

Parameters

algo – The Data::LCP::Algorithms used to solve the LCP
xSol – The resulting solution for z, if any. If the vector is filled, it will be seeded as a warmstart if Data::LCP::Algorithms::MIP
zSol – The resulting solution for z, if any. If the vector is filled, it will be seeded as a warmstart if Data::LCP::Algorithms::MIP
timeLimit – A double time limit
threads – The absolute number of threads in case algo is Data::LCP::Algorithms::MIP
solLimit – The number of solutions in the pool for if algo is Data::LCP::Algorithms::MIP
cutOff – Bounds the optima solution to be >= than a given threshold. Used if different from -GRB_INFINITY. As output, the object will be filled with the incumbent optimal value

Returns

A ZEROStatus for the problem

std::unique_ptr<GRBModel> LCPasMIP(bool solve = false, double timeLimit = -1, unsigned long int threads = 1, unsigned long int solLimit = 1)

Solves the LCP as a Mixed-Integer Program. Note that the returned model is either a MIP or a MINLP, depending on the class’ LCP::PureMIP boolean switch. In the first case, complementarities are modeled through SOS1 or indicator constraints. Otherwise, there is bi-linear term for each complementarity.

Parameters

solve – Determines whether the returned model is already solved or not
timeLimit – Sets the timeLimit for the MIP solver
threads – Sets the number of threads
solLimit – Sets the number of solutions in the pool

Returns

The unique pointer to the model

std::unique_ptr<GRBModel> LCPasMILP(const arma::sp_mat &C, const arma::vec &c, const arma::vec &x_minus_i, bool solve = false)

This method returns an unique pointer to the Gurobi model where the objective is the one of a specific player. In particular, given by the parameter C, c, x_minus_i are fixed and then the objective is linear (MILP).

Warning

If LCP::PureMIP is false, then the model has a linear objective and bi-linear constraints. Hence, is not a MILP

Parameters

C – The interaction term for a given player
c – The linear term for a given player
x_minus_i – The strategies of other players
solve – True if the returned model is solved

Returns

The unique pointer to the model

std::unique_ptr<GRBModel> LCPasMIQP(const arma::sp_mat &Q, const arma::sp_mat &C, const arma::vec &c, const arma::vec &x_minus_i, bool solve = false)

This method returns an unique pointer to the Gurobi model where the objective is the one of a specific player. In particular, given by the parameter C, c, x_minus_i are fixed and then the objective is quadratic (MIQP)

Warning

If LCP::PureMIP is false, then the model has a quadratic objective and bi-linear constraints

Parameters

Q – The quadratic term for a given player
C – The interaction term for a given player
c – The linear term for a given player
x_minus_i – The strategies of other players
solve – True if the returned model is solved

Returns

The unique pointer to the model

ZEROStatus solvePATH(double timelimit, arma::vec &x, arma::vec &z, bool verbose = true)

Solves the LCP with Solvers::PATH.

Parameters

timelimit – A double time limit on the solving process
z – The resulting solution for z, if any
x – The resulting solution for x, if any
verbose – True if PATH will be verbose

Returns

The ZEROStatus of the model

void save(const std::string &filename, bool erase = true) const

Saves the LCP into a file.

Parameters

filename – The filename
erase – Whether the file should be cleaned or not

long int load(const std::string &filename, long int pos = 0)

This method load the LCP object from a file.

Parameters

filename – The filename
pos – The position of the LCP in the file

Returns

The position after the LCP in the file

virtual void makeQP(MathOpt::QP_Objective &QP_obj, MathOpt::QP_Param &QP)

This method create the convex-hull of the feasible (approximated) region for the LCP, and puts it into a MathOpt::QP_Param object. In addition, it transform the given input objective function by adding additional zero elements to it, to fit the number of variables in the quadratic program.

Parameters

QP_obj – The input/output MathOpt::QP_Param objective
QP – The output MathOpt::QP_Param

void addCustomCuts(const arma::sp_mat &A, const arma::vec &b)

Adds custom cuts defined in the input to the LCP::A and LCP::b objects.

Parameters

A_in – The LHS of the added cuts
b_in – The RHS of the added cuts note This method does not check whether such cuts are already in the LCP.

bool containsCut(const arma::vec &LHS, const double RHS, double tol = 1e-5)

Given the cut, the method checks whether there is already one (up to a numerical tolerance) in the LCP.

Parameters

A_in – The LHS of the cut
b_in – The RHS of the cut
tol – The numerical tolerance

Returns

True if the cut is already present, false otherwise.

arma::vec zFromX(const arma::vec &x)

Given a value for the variables, it returns the values of z.

Parameters: x – The x-values vector
Returns: The z-values vector

void processBounds(): Processes the bounds of BoundsX and removes any complementarity that is useless (e.g., variable is fixed). After processing, it calls back LCP::defConst to re-initializes the private attributes.

bool setMIPLinearObjective(const arma::vec &c)

Given the linear vector x c, sets the linear objective for the MIP reformulation of the LCP.

Parameters: c – Linear vector for the primal variables
Returns: True if successful

bool setMIPQuadraticObjective(const arma::vec &c, const arma::sp_mat &Q)

Given the linear vector and quadratic matrix c and Q, sets the quadratic objective for the MIP reformulation of the LCP.

Parameters

c – Linear vector for the primal variables
Q – Square matrix for the primal variables

Returns

True if successful

bool setMIPFeasibilityObjective()

Public Members

double Eps = {1e-6}: The threshold for optimality and feasability tolerances.

Protected Functions

void defConst(GRBEnv *env)

Assigns default values to the class’ LCP attributes.

Internal member that can be called from multiple constructors to assign default values to some attributes of the class.

Parameters: env – The Gurobi environment pointer

void makeRelaxed()

Makes a Gurobi object that relaxes complementarity constraints in the LCP.

The field LCP::RelaxedModel stores the relaxed version of the problem

void setMIPObjective(GRBModel &convexModel)

Given the MIP model in MIP, sets the objective according to the one given by MathOpt::LCP::setMIPQuadraticObjective or MathOpt::LCP::setMIPLinearObjective.

Parameters: MIP – The MIP model

std::unique_ptr<GRBModel> getMIP(bool indicators = false)

Gets the MIP model associated with the LCP, where complementarities are modeled with with SOS-1 constraints if indicators is false, with indicator constraints otherwise.

Parameters: indicators – If true, SOS-1 formulation will be used for each complementarity. Otherwise, indicator constraints will be used
Returns: The Gurobi pointer to the model

std::unique_ptr<GRBModel> getMINLP()

Gets the MINLP model associated with the LCP, where complementarities are modeled with bi-linear terms.

Returns: The Gurobi pointer to the model

unsigned long int convexHull(arma::sp_mat &A, arma::vec &b)

Computes the convex hull of the feasible region of the LCP.

Parameters

A – The output convex-hull LHS
b – The output convex-hull RHS

Returns

The number of polyhedra in the approximation

Protected Attributes

GRBEnv *Env = {}: A pointer to the Gurobi Env.

unsigned int ObjType = 0: Type of the objective for MIP/MINLP. 0 is feasibility, 1 linear, 2 quadratic.

arma::vec c_Obj: The linear objective for the LCP in case of MIP/MINLP.

arma::sp_mat Q_Obj: The quadratic objective matrix Q for the LCP in case of MIP/MINLP.

bool MadeObjective = false: True if the objective has been updated.

arma::sp_mat M: The matrix M in \(Mx+q\) that defines the LCP.

arma::vec q: The vector q in \(Mx+q\) that defines the LCP.

perps Compl: Compl dictates which equation (row in M) is complementary to which variable (column in M). The object is in a <Eqn, Var> form.

unsigned long int LeadStart = {1}: Starting leader location.

unsigned long int LeadEnd = {0}: Ending leader location.

unsigned long int NumberLeader = {0}: Number of leaders.

bool PureMIP = true: True if the LCP is modelled via a pure MIP with SOS1 (or indicator) constraints. Otherwise, a MINLP introduces a bilinear term for each complementarity.

arma::sp_mat A = {}: The additional constraint matrix A to the problem, in the form \(Ax \leq b\).

arma::vec b = {}: The additional constraint RHSs b to the problem, in the form \(Ax \leq b\).

bool MadeRlxdModel = {false}: True if a relaxed model has been already initialized.

unsigned long int nR = {}: The number of rows in the matrix M.

unsigned long int nC = {}: The number of columns in the matrix M.

VariableBounds BoundsX: Stores non-trivial upper and lower bounds on x variables in as a tuple (j,k) where j the lower bound, and k the upper bound. Usually, j is initialized to 0, while k to -1 (meaning inactive upepr bound)

GRBModel RelaxedModel: A Gurobi model without complementarities.

std::unique_ptr<spmat_Vec> Ai: A pointer to matrices containing the LHSs of a description (either exact or approximated) of the LCP’s feasible region

std::unique_ptr<vec_Vec> bi: A pointer to vectors containing the RHSs of a description (either exact or approximated) of the LCP’s feasible region

class PolyLCP : public MathOpt::LCP

#include <poly_lcp.h>

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

struct QP_Objective

#include <mathopt.h>

struct to handle the objective params of MP_Param and inheritors

Refer QP_Param class for what Q, C and c,d mean.

Public Members

arma::sp_mat Q

arma::sp_mat C

arma::vec d

arma::vec c

struct QP_Constraints

#include <mathopt.h>

struct to handle the constraint params of MP_Param and inheritors

Refer QP_Param class for what A, B and b mean.

Public Members

arma::sp_mat A

arma::sp_mat B

arma::vec b

class IP_Param : public MathOpt::MP_Param

#include <ip_param.h>

This class handles parametrized integer programs, and inherits from MP_Param. A parametrized Integer Program is defined as as.

\[ \min_y c^Ty + (Cx)^T y + d^T x \]

Subject to

\[\begin{split}\begin{eqnarray} By &\leq& b \\ y &\geq& 0 \\ y_i &\in& &\mathbb{Z}& &\forall& i &\in& I \end{eqnarray}\end{split}\]

Where the shape of C is \(Ny \times numParams\).

Public Functions

inline explicit IP_Param(GRBEnv *env = nullptr)

A constructor initializing only the size. Everything else is empty (can be updated later)

Parameters: env – The pointer to the Gurobi environment

IP_Param(const arma::sp_mat &C_in, const arma::sp_mat &B_in, const arma::vec &b_in, const arma::vec &c_in, const arma::vec &d_in, const arma::vec &integers_in, const VariableBounds &Bounds_in, GRBEnv *env_in)

Alternative constructor.

Parameters

C_in – The objective C matrix
B_in – The constraint matrix
b_in – The constraint RHS
c_in – The objective c vector
d_in – The objective c vector
integers_in – The indexes of integer variables
Bounds_in – The input bounds
env_in – A pointer to the Gurobi environment

inline arma::vec getIntegers() const: Read-only getter to IP_Param::Integers.

virtual bool finalize() override

This method creates the (mixed)-integer program for the game, where the objective omits the bilinear part. The flag Finalized in the object is then set to true.

Returns: True if checks are completed

IP_Param &setBounds(const VariableBounds &boundIn): Inheritor constructor for the class.

bool addConstraints(const arma::sp_mat &A_in, const arma::vec &b_in)

Adds a constraints to the IP_Param. It stores a description of the new cut \( A_{in} x \leq b_{in}\) of A_in (and RHS b_in) in B and b, respectively.

Parameters

A_in – The vector of LHS
b_in – The RHS value

Returns

true if the constraint has been added This works also when the IP_Param is Finalized.

Returns

True if the constraint is added

IP_Param(const IP_Param &ipg) = default

A copy constructor from anoter IP_Param.

Parameters: ipg – The model to be copied

MathOpt::IP_Param &set(const arma::sp_mat &C_in, const arma::sp_mat &B_in, const arma::vec &b_in, const arma::vec &c_in, const arma::vec &d_in, const arma::vec &integers_in, const VariableBounds &Bounds_in)

A setter method with copy arguments.

Parameters

C_in – Bi-linear term for x-y in the objective
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
b_in – Vector of RHS in the constraints
d_in – Vector of linear terms for x in the objective
integers_in – A vector containing the indexes of integer variables
Bounds_in – Variable bounds

Returns

A pointer to this

IP_Param &set(arma::sp_mat &&C_in, arma::sp_mat &&B_in, arma::vec &&b_in, arma::vec &&c_in, arma::vec &&d_in, arma::vec &&integers_in, VariableBounds &&Bounds_in)

A move constructor.

Parameters

C_in – Bi-linear term for x-y in the objective
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
b_in – Vector of RHS in the constraints
d_in – Vector of linear terms for x in the objective
integers_in – A vector containing the indexes of integer variables
Bounds_in – Variable bounds

Returns

A pointer to this

bool operator==(const IP_Param &IPG2) const

Compares two IP_param objects.

Parameters: IPG2 – The second IP_Param
Returns: True if the objects are identical

virtual double computeObjective(const arma::vec &y, const arma::vec &x, bool checkFeas = true, double tol = 1e-6) const override

Computes \((Cx)^Ty + c^Ty + d^Tx \) given the input values y and x. checkFeas if true, checks if the given \((x,y)\) satisfies the constraints of the problem, namely \(Ax + By \leq b\).

Parameters

y – The values for the variables y
x – The values for the parameters x
checkFeas – True if feasibility should be checked
tol – A numerical tolerance for the feasibility

Returns

A double value for the objective

virtual void save(const std::string &filename, bool append) const override

A save method for the IP_Param.

Parameters

filename – The filename
append – If true, the file will be appended

long load(const std::string &filename, long pos = 0) override

Loads the IP_Param from a file.

Warning

Call MP_Param(GRBEnv *env) before loading Example usage:

int main()
{
        GRBEnv Env;
        MathOpt::IP_Param ip(&Env);
        ip.load("./dat/q1data.dat");
        std::cout<<ip<<'\n';
        return 0;
}

Parameters

filename – The filename
pos – The position of the IP_Param in the file

Returns

The position after the IP_Param

void updateModelObjective(const arma::vec &x)

This method updates the model objective in IP_Param::IPModel by setting x to x.

Parameters: x – The parametrized values of x

virtual std::unique_ptr<GRBModel> solveFixed(arma::vec x, bool solve = false) override

Given a value for the parameters \(x\) in the definition of IP_Param, returns a pointer to the parameterized MIP program . Note that the method.

Parameters

x – The parametrized values of x
solve – If the returned model is solved

Returns

a pointer to a copy of the model. In this way, valid cuts and cut pools are kept each time the method is invoked. In terms of game theory, this can be viewed as the best response for a set of decisions by other players.

Returns

A pointer to the Gurobi model

std::unique_ptr<GRBModel> getIPModel(const arma::vec &x, bool relax = false)

Given a value for the parameters \(x\) in the definition of IP_Param, returns a pointer to the parameterized MIP program . Note that the method.

Parameters

x – The values for the parametrized x
relax – True if the model relaxes integrality requirements

Returns

a pointer to a copy of the model. In this way, valid cuts and cut pools are kept each time the method is invoked. If relax is true, then the model is the linear relaxation of the MIP.

Returns

A pointer to the Gurobi model

virtual unsigned int KKT(arma::sp_mat &M, arma::sp_mat &N, arma::vec &q) const override

Writes the KKT condition of the relaxation of the parameterized IP. As per the convention, y is the decision variable for the IP and that is parameterized in x. The KKT conditions are \(0 \leq y \perp My + Nx + q \geq 0\).

Parameters

M – The output M term
N – The output N term
q – The output q term

Returns

An int containing the rows of M

virtual bool isFeasible(const arma::vec &y, const arma::vec &x, double tol) const override

Given a parameter value x, and variables values y, returns true whenever the point is feasible for the program. This method overrides the MathOpt::MP_Param to manage integral requirements.

Parameters

y – The variables’ values
x – The parameters’ values
tol – A numerical tolerance

Returns

True if the point is feasible

void presolve()

Presolved the IP model and replaces the object in the class with the (possibly) simplified model. Note: this should be used with care. First, it can mess the sizes of the variables/constraints. Second, it may be resource consuming.

Todo:: currently disabled. check the method

Private Functions

MP_Param &set(const arma::sp_mat &Q_in, const arma::sp_mat &C_in, const arma::sp_mat &A_in, const arma::sp_mat &B_in, const arma::vec &c_in, const arma::vec &b_in, const arma::vec &d_in)

Constructor to set the data, while keeping the input objects intact.

Parameters

Q_in – Quadratic term for y in the objective
C_in – Bi-linear term for x-y in the objective
A_in – Matrix of constraints for the parameters x
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
d_in – Vector of linear terms for x in the objective
b_in – Vector of RHS in the constraints

Returns

A pointer to this

MP_Param &set(arma::sp_mat &&Q_in, arma::sp_mat &&C_in, arma::sp_mat &&A_in, arma::sp_mat &&B_in, arma::vec &&c_in, arma::vec &&b_in, arma::vec &&d_in)

Constructor to set the data through std::move.

Warning

The input data may be corrupted after

Parameters

Q_in – Quadratic term for y in the objective
C_in – Bi-linear term for x-y in the objective
A_in – Matrix of constraints for the parameters x
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
d_in – Vector of linear terms for x in the objective
b_in – Vector of RHS in the constraints

Returns

A pointer to this

MP_Param &set(const QP_Objective &obj, const QP_Constraints &cons)

A copy constructor given a QP_Objective and QP_Constraints.

Parameters

obj – The objective
cons – The constraints object

Returns

A pointer to this

MP_Param &set(QP_Objective &&obj, QP_Constraints &&cons)

A move constructor given a QP_Objective and QP_Constraints.

Warning

The input data may be corrupted after

Parameters

obj – The objective
cons – The constraints object

Returns

A pointer to this

Private Members

GRBModel IPModel: Stores the IP model associated with the object.

arma::vec Integers: Stores the indexes of integer variables.

bool Finalized = {false}: True if the model has been made and constraints cannot be changed.

class MP_Param

#include <mp_param.h>

This class handles parameterized mathematical programs (MP) Their form is the one of.

\[ \min_y \frac{1}{2}y^TQy + c^Ty + (Cx)^T y + d^Tx \]

Subject to

\[\begin{split}\begin{eqnarray} Ax + By &\leq& b \\ y &\geq& 0 \end{eqnarray}\end{split}\]

Subclassed by MathOpt::IP_Param, MathOpt::QP_Param

Public Functions

inline MP_Param(GRBEnv *env = nullptr)

Default constructor.

Parameters: env – The pointer to the Gurobi environment

MP_Param(const MP_Param &M) = default

Default copy constructor.

Parameters: M – The origin object Default copy constructor

inline arma::sp_mat getQ() const: Read-only access to the private variable Q.

inline arma::sp_mat getC() const: Read-only access to the private variable C.

arma::sp_mat getA(bool bounds = true) const

Read-only access to the private variable A.

Returns the matrix A.

Parameters: bounds – True if one needs to include the bounds in the matrix A
Returns: A const object with A

arma::sp_mat getB(bool bounds = true) const

Read-only access to the private variable B.

Returns the matrix B.

Parameters: bounds – True if one needs to include the bounds in the matrix B
Returns: A const object with B

inline arma::vec getc() const: Read-only access to the private variable c.

inline arma::vec getd() const: Read-only access to the private variable d.

arma::vec getb(bool bounds = true) const

Read-only access to the private variable b.

Returns the vector b.

Parameters: bounds – True if one needs to include the bounds in the vector b
Returns: A const object with b

inline unsigned int getNumParams() const: Read-only access to the private variable numParams.

inline unsigned int getNumVars() const: Read-only access to the private variable numVars.

inline VariableBounds getBounds() const: Read-only access to the Bounds.

inline MP_Param &setQ(const arma::sp_mat &Q_in): Set the private variable Q.

inline MP_Param &setC(const arma::sp_mat &C_in): Set the private variable C.

inline MP_Param &setA(const arma::sp_mat &A_in): Set the private variable A.

inline MP_Param &setB(const arma::sp_mat &B_in): Set the private variable B.

inline MP_Param &setc(const arma::vec &c_in): Set the private variable c.

inline MP_Param &setd(const arma::vec &d_in): Set the private variable d.

inline MP_Param &setb(const arma::vec &b_in): Set the private variable b.

inline MP_Param &setBounds(const VariableBounds &bounds_in)

Updates the bounds.

Parameters: bounds_in – The input bounds
Returns: A pointer to this Set the Bounds

virtual MP_Param &set(const arma::sp_mat &Q_in, const arma::sp_mat &C_in, const arma::sp_mat &A_in, const arma::sp_mat &B_in, const arma::vec &c_in, const arma::vec &b_in, const arma::vec &d_in)

Constructor to set the data, while keeping the input objects intact.

Parameters

Q_in – Quadratic term for y in the objective
C_in – Bi-linear term for x-y in the objective
A_in – Matrix of constraints for the parameters x
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
d_in – Vector of linear terms for x in the objective
b_in – Vector of RHS in the constraints

Returns

A pointer to this

virtual MP_Param &set(arma::sp_mat &&Q_in, arma::sp_mat &&C_in, arma::sp_mat &&A_in, arma::sp_mat &&B_in, arma::vec &&c_in, arma::vec &&b_in, arma::vec &&d_in)

Constructor to set the data through std::move.

Warning

The input data may be corrupted after

Parameters

Q_in – Quadratic term for y in the objective
C_in – Bi-linear term for x-y in the objective
A_in – Matrix of constraints for the parameters x
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
d_in – Vector of linear terms for x in the objective
b_in – Vector of RHS in the constraints

Returns

A pointer to this

virtual MP_Param &set(const QP_Objective &obj, const QP_Constraints &cons)

A copy constructor given a QP_Objective and QP_Constraints.

Parameters

obj – The objective
cons – The constraints object

Returns

A pointer to this

virtual MP_Param &set(QP_Objective &&obj, QP_Constraints &&cons)

A move constructor given a QP_Objective and QP_Constraints.

Warning

The input data may be corrupted after

Parameters

obj – The objective
cons – The constraints object

Returns

A pointer to this

virtual MP_Param &addDummy(unsigned int pars, unsigned int vars = 0, int position = -1)

Adds dummy variables to a parameterized mathematical program position dictates the position at which the parameters can be added.

Parameters

pars – Number of parameters to be added (e.g., MP_Param::numParams)
vars – Number of variables to be added (e.g., MP_Param::numVars)
position – The position at which the parameters should be added. -1 for adding at the end.

Returns

A pointer to the object

virtual void save(const std::string &filename, bool append) const

Writes a given parameterized Mathematical program to a set of files. Writes a given parameterized Mathematical program to a set of files. One file is written for each attribute namely.

To contrast see, MathOpt::MP_Param::save where all details are written to a single loadable file

Parameters

filename – The filename
append – True if the content is appended

virtual long int load(const std::string &filename, long int pos = 0)

Inverses the operation of MP_Param::save by loading the object from a file.

Warning

Call MP_Param(GRBEnv *env) before loading

Parameters

filename – The filename
pos – The position of the MP_Param in the file

Returns

The position after the MP_Param in the file

virtual unsigned int KKT(arma::sp_mat &M, arma::sp_mat &N, arma::vec &q) const = 0

A virtual method to take the KKT of the program, in a complementarity form.

Parameters

M – Output M matrix for variables
N – Output N matrix for parameters
q – Output q vector

Returns

The rows of M

virtual std::unique_ptr<GRBModel> solveFixed(const arma::vec x, bool solve = false) = 0

Returns the optimal Gurobi model where the paramers are fixed to x.

Parameters

x – The input parameters
solve – True if the model needs to be solved

Returns

The best response model

virtual double computeObjective(const arma::vec &y, const arma::vec &x, bool checkFeas = true, double tol = 1e-6) const

Computes \(\frac{1}{2} y^TQy + (Cx)^Ty + c^Ty\) given the input values y and x. checkFeas if true, checks if the given \((x,y)\) satisfies the constraints of the problem, namely \(Ax + By \leq b\).

Parameters

y – The values for the variables y
x – The values for the parameters x
checkFeasibility – True if feasibility should be checked
tol – A numerical tolerance for the feasibility

Returns

A double value for the objective

void forceDataCheck() const: Forces the datacheck on the object. Otherwise, it throws an error.

virtual bool isFeasible(const arma::vec &y, const arma::vec &x, double tol) const

Given a parameter value x, and variables values y, returns true whenever the point is feasible for the program.

Parameters

y – The variables’ values
x – The parameters’ values
tol – A numerical tolerance

Returns

True if the point is feasible

Protected Functions

unsigned int size()

Calculates numParams, numVars and numConstr Computes parameters in MP_Param:

Computes numVars as number of rows in MP_Param::Q
Computes numParams as number of columns in MP_Param::C
Computes numConstr as number of rows in MP_Param::b, i.e., the RHS of the constraints For proper working, MP_Param::dataCheck() has to be run after this.

Returns: numVars, Number of variables in the quadratic program, QP

bool dataCheck(bool forceSymmetry = true) const

Check that the data for the MP_Param class is valid Always works after calls to MP_Param::size().

Parameters: forceSymmetry –
Returns: True if data structures are correctly sized.

void detectBounds(): Detects explicit bounds stated in the MP_Param formulation, and stores them implicitly. This is useful when the formulation of the parametrized mathematical program is processed through other steps (e.g., KKT conditions, LCPs, etc…) since any bound constraint can possibly slow down the final problem solving.

void rewriteBounds(): Given the description of the object, renders the bounds explicitly. This method is useful when building the KKT conditions for the MP_Param. In particular, after bounds are detected and their respective rows are shedded by MP_Param::detectBounds, the explicit constraints should be added again.

Warning

The size of Bounds should be the future numVars.

virtual bool finalize()

Finalizes the MP_Param object. Can be overriden by inheritors.

Finalizes the MP_Param object, computing the object sizes and eventually shedding trivial bound constraints.

Returns: True if the object is Finalized and checks are passed.

Protected Attributes

arma::sp_mat Q: The Q matrix in the objective.

arma::sp_mat A: The A matrix for the parameters’ constraints.

arma::sp_mat B: The B matrix for the variables’ constraints.

arma::sp_mat C: The C matrix in the objective.

arma::sp_mat B_bounds: Implicit rows of B accounting for variables’ bounds.

arma::vec b_bounds: The implicit rows of b accounting for the variables’ bounds.

arma::vec c: The c vector in the objective.

arma::vec d: The d vector in the objective.

arma::vec b: The constraints’ RHS.

GRBEnv *Env: A pointer to the Gurobi environment.

VariableBounds Bounds: Bounds on the y variables.

unsigned int numParams: Number of x parameters.

unsigned int numVars: Number of y variables.

unsigned int numConstr: Number of constraints.

Private Members

double Eps = {1e-6}: A numerical tolerance.

class QP_Param : public MathOpt::MP_Param

#include <qp_param.h>

A class to handle parameterized quadratic programs (QP), defined as.

\[ \min_y \frac{1}{2}y^TQy + c^Ty + (Cx)^T y + d^T x \]

Subject to

\[\begin{split}\begin{eqnarray} Ax + By &\leq& b \\ y &\geq& 0 \end{eqnarray}\end{split}\]

The shape of C is \(numVars \times numParams\)

Public Functions

inline explicit QP_Param(GRBEnv *env = nullptr)

Standard void constructor.

Parameters: env – A pointer to the Gurobi environment

QP_Param(const arma::sp_mat &Q_in, const arma::sp_mat &C_in, const arma::sp_mat &A_in, const arma::sp_mat &B_in, const arma::vec &c_in, const arma::vec &b_in, const arma::vec &d_in, GRBEnv *env = nullptr)

Empty constructor initializing only the Gurobi environment.

Constructor to set the data with copies.

Set data at construct time

Warning

The input data may be corrupted after

Parameters

Q_in – Quadratic term for y in the objective
C_in – Bi-linear term for x-y in the objective
A_in – Matrix of constraints for the parameters x
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
b_in – Vector of RHS in the constraints
env – A Gurobi Environment pointer

Returns

A pointer to this

inline QP_Param(const QP_Param &Qu)

A copy constructor given a QP_Param.

Parameters: Qu – The copied model

virtual QP_Param &set(const arma::sp_mat &Q_in, const arma::sp_mat &C_in, const arma::sp_mat &A_in, const arma::sp_mat &B_in, const arma::vec &c_in, const arma::vec &b_in, const arma::vec &d_in) final

Constructor to set the data, while keeping the input objects intact.

Parameters

Q_in – Quadratic term for y in the objective
C_in – Bi-linear term for x-y in the objective
A_in – Matrix of constraints for the parameters x
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
b_in – Vector of RHS in the constraints
d_in – Vector of linear terms for x in the objective

Returns

A pointer to this

virtual QP_Param &set(arma::sp_mat &&Q_in, arma::sp_mat &&C_in, arma::sp_mat &&A_in, arma::sp_mat &&B_in, arma::vec &&c_in, arma::vec &&b_in, arma::vec &&d_in) final

Constructor to set the data through std::move.

Warning

The input data may be corrupted after

Parameters

Q_in – Quadratic term for y in the objective
C_in – Bi-linear term for x-y in the objective
A_in – Matrix of constraints for the parameters x
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
b_in – Vector of RHS in the constraints
d_in – Vector of linear terms for x in the objective

Returns

A pointer to this

virtual QP_Param &set(const QP_Objective &obj, const QP_Constraints &cons) final

A copy constructor given a QP_Objective and QP_Constraints.

Parameters

obj – The objective
cons – The constraints object

Returns

A pointer to this

virtual QP_Param &set(QP_Objective &&obj, QP_Constraints &&cons) final

A move constructor given a QP_Objective and QP_Constraints.

Warning

The input data may be corrupted after

Parameters

obj – The objective
cons – The constraints object

Returns

A pointer to this

bool operator==(const QP_Param &Q2) const

Compares two QP_param objects.

Parameters: Q2 – The second QP_Param
Returns: True if the objects are identical

virtual unsigned int KKT(arma::sp_mat &M, arma::sp_mat &N, arma::vec &q) const override

Writes the KKT condition of the parameterized QP. As per the convention, y is the decision variable for the QP and that is parameterized in x. The KKT conditions are \(0 \leq y \perp My + Nx + q \geq 0\).

Parameters

M – The output M term
N – The output N term
q – The output q term

Returns

An int containing the rows of M

virtual std::unique_ptr<GRBModel> solveFixed(arma::vec x, bool solve) override

Given a value for the parameters \(x\) in the definition of QP_Param, returns a pointer to the parameterized MIP program. Note that the method.

Parameters

x – The parametrized values of x
solve – If the returned model is solved

Returns

a pointer to a copy of the model. In this way, valid cuts and cut pools are kept each time the method is invoked. In terms of game theory, this can be viewed as the best response for a set of decisions by other players.

Returns

A pointer to the Gurobi model

virtual void save(const std::string &filename, bool append) const override

Writes a given parameterized QP to a set of files. Writes a given parameterized Mathematical program to a set of files. One file is written for each attribute namely.

To contrast see, MathOpt::QP_Param::save where all details are written to a single loadable file

Parameters

filename – The filename
append – True if the content is appended

virtual long int load(const std::string &filename, long int pos = 0) override

Inverses the operation of QP_Param::save by loading the object from a file.

Warning

Call MP_Param(GRBEnv *env) before loading

Parameters

filename – The filename
pos – The position of the QP_Param in the file

Returns

The position after the QP_Param in the file

Private Functions

void makeyQy(): Creates the quadratic term (in the y variables) and sets QP_Param::MadeyQy to true.

Private Members

GRBModel Model: Gurobi pointer to the QP model.

bool MadeyQy: True if the objective quadratic term has been generated.

MP_Param

class MP_Param

This class handles parameterized mathematical programs (MP) Their form is the one of.

\[ \min_y \frac{1}{2}y^TQy + c^Ty + (Cx)^T y + d^Tx \]

Subject to

\[\begin{split}\begin{eqnarray} Ax + By &\leq& b \\ y &\geq& 0 \end{eqnarray}\end{split}\]

Subclassed by MathOpt::IP_Param, MathOpt::QP_Param

Public Functions

inline MP_Param(GRBEnv *env = nullptr)

Default constructor.

Parameters: env – The pointer to the Gurobi environment

MP_Param(const MP_Param &M) = default

Default copy constructor.

Parameters: M – The origin object Default copy constructor

inline arma::sp_mat getQ() const: Read-only access to the private variable Q.

inline arma::sp_mat getC() const: Read-only access to the private variable C.

arma::sp_mat getA(bool bounds = true) const

Read-only access to the private variable A.

Returns the matrix A.

Parameters: bounds – True if one needs to include the bounds in the matrix A
Returns: A const object with A

arma::sp_mat getB(bool bounds = true) const

Read-only access to the private variable B.

Returns the matrix B.

Parameters: bounds – True if one needs to include the bounds in the matrix B
Returns: A const object with B

inline arma::vec getc() const: Read-only access to the private variable c.

inline arma::vec getd() const: Read-only access to the private variable d.

arma::vec getb(bool bounds = true) const

Read-only access to the private variable b.

Returns the vector b.

Parameters: bounds – True if one needs to include the bounds in the vector b
Returns: A const object with b

inline unsigned int getNumParams() const: Read-only access to the private variable numParams.

inline unsigned int getNumVars() const: Read-only access to the private variable numVars.

inline VariableBounds getBounds() const: Read-only access to the Bounds.

inline MP_Param &setQ(const arma::sp_mat &Q_in): Set the private variable Q.

inline MP_Param &setC(const arma::sp_mat &C_in): Set the private variable C.

inline MP_Param &setA(const arma::sp_mat &A_in): Set the private variable A.

inline MP_Param &setB(const arma::sp_mat &B_in): Set the private variable B.

inline MP_Param &setc(const arma::vec &c_in): Set the private variable c.

inline MP_Param &setd(const arma::vec &d_in): Set the private variable d.

inline MP_Param &setb(const arma::vec &b_in): Set the private variable b.

inline MP_Param &setBounds(const VariableBounds &bounds_in)

Updates the bounds.

Parameters: bounds_in – The input bounds
Returns: A pointer to this Set the Bounds

virtual MP_Param &set(const arma::sp_mat &Q_in, const arma::sp_mat &C_in, const arma::sp_mat &A_in, const arma::sp_mat &B_in, const arma::vec &c_in, const arma::vec &b_in, const arma::vec &d_in)

Constructor to set the data, while keeping the input objects intact.

Parameters

Q_in – Quadratic term for y in the objective
C_in – Bi-linear term for x-y in the objective
A_in – Matrix of constraints for the parameters x
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
d_in – Vector of linear terms for x in the objective
b_in – Vector of RHS in the constraints

Returns

A pointer to this

virtual MP_Param &set(arma::sp_mat &&Q_in, arma::sp_mat &&C_in, arma::sp_mat &&A_in, arma::sp_mat &&B_in, arma::vec &&c_in, arma::vec &&b_in, arma::vec &&d_in)

Constructor to set the data through std::move.

Warning

The input data may be corrupted after

Parameters

Q_in – Quadratic term for y in the objective
C_in – Bi-linear term for x-y in the objective
A_in – Matrix of constraints for the parameters x
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
d_in – Vector of linear terms for x in the objective
b_in – Vector of RHS in the constraints

Returns

A pointer to this

virtual MP_Param &set(const QP_Objective &obj, const QP_Constraints &cons)

A copy constructor given a QP_Objective and QP_Constraints.

Parameters

obj – The objective
cons – The constraints object

Returns

A pointer to this

virtual MP_Param &set(QP_Objective &&obj, QP_Constraints &&cons)

A move constructor given a QP_Objective and QP_Constraints.

Warning

The input data may be corrupted after

Parameters

obj – The objective
cons – The constraints object

Returns

A pointer to this

virtual MP_Param &addDummy(unsigned int pars, unsigned int vars = 0, int position = -1)

Adds dummy variables to a parameterized mathematical program position dictates the position at which the parameters can be added.

Parameters

pars – Number of parameters to be added (e.g., MP_Param::numParams)
vars – Number of variables to be added (e.g., MP_Param::numVars)
position – The position at which the parameters should be added. -1 for adding at the end.

Returns

A pointer to the object

virtual void save(const std::string &filename, bool append) const

Writes a given parameterized Mathematical program to a set of files. Writes a given parameterized Mathematical program to a set of files. One file is written for each attribute namely.

To contrast see, MathOpt::MP_Param::save where all details are written to a single loadable file

Parameters

filename – The filename
append – True if the content is appended

virtual long int load(const std::string &filename, long int pos = 0)

Inverses the operation of MP_Param::save by loading the object from a file.

Warning

Call MP_Param(GRBEnv *env) before loading

Parameters

filename – The filename
pos – The position of the MP_Param in the file

Returns

The position after the MP_Param in the file

virtual unsigned int KKT(arma::sp_mat &M, arma::sp_mat &N, arma::vec &q) const = 0

A virtual method to take the KKT of the program, in a complementarity form.

Parameters

M – Output M matrix for variables
N – Output N matrix for parameters
q – Output q vector

Returns

The rows of M

virtual std::unique_ptr<GRBModel> solveFixed(const arma::vec x, bool solve = false) = 0

Returns the optimal Gurobi model where the paramers are fixed to x.

Parameters

x – The input parameters
solve – True if the model needs to be solved

Returns

The best response model

virtual double computeObjective(const arma::vec &y, const arma::vec &x, bool checkFeas = true, double tol = 1e-6) const

Computes \(\frac{1}{2} y^TQy + (Cx)^Ty + c^Ty\) given the input values y and x. checkFeas if true, checks if the given \((x,y)\) satisfies the constraints of the problem, namely \(Ax + By \leq b\).

Parameters

y – The values for the variables y
x – The values for the parameters x
checkFeasibility – True if feasibility should be checked
tol – A numerical tolerance for the feasibility

Returns

A double value for the objective

void forceDataCheck() const: Forces the datacheck on the object. Otherwise, it throws an error.

virtual bool isFeasible(const arma::vec &y, const arma::vec &x, double tol) const

Given a parameter value x, and variables values y, returns true whenever the point is feasible for the program.

Parameters

y – The variables’ values
x – The parameters’ values
tol – A numerical tolerance

Returns

True if the point is feasible

Protected Functions

unsigned int size()

Calculates numParams, numVars and numConstr Computes parameters in MP_Param:

Computes numVars as number of rows in MP_Param::Q
Computes numParams as number of columns in MP_Param::C
Computes numConstr as number of rows in MP_Param::b, i.e., the RHS of the constraints For proper working, MP_Param::dataCheck() has to be run after this.

Returns: numVars, Number of variables in the quadratic program, QP

bool dataCheck(bool forceSymmetry = true) const

Check that the data for the MP_Param class is valid Always works after calls to MP_Param::size().

Parameters: forceSymmetry –
Returns: True if data structures are correctly sized.

void detectBounds(): Detects explicit bounds stated in the MP_Param formulation, and stores them implicitly. This is useful when the formulation of the parametrized mathematical program is processed through other steps (e.g., KKT conditions, LCPs, etc…) since any bound constraint can possibly slow down the final problem solving.

void rewriteBounds(): Given the description of the object, renders the bounds explicitly. This method is useful when building the KKT conditions for the MP_Param. In particular, after bounds are detected and their respective rows are shedded by MP_Param::detectBounds, the explicit constraints should be added again.

Warning

The size of Bounds should be the future numVars.

virtual bool finalize()

Finalizes the MP_Param object. Can be overriden by inheritors.

Finalizes the MP_Param object, computing the object sizes and eventually shedding trivial bound constraints.

Returns: True if the object is Finalized and checks are passed.

Protected Attributes

arma::sp_mat Q: The Q matrix in the objective.

arma::sp_mat A: The A matrix for the parameters’ constraints.

arma::sp_mat B: The B matrix for the variables’ constraints.

arma::sp_mat C: The C matrix in the objective.

arma::sp_mat B_bounds: Implicit rows of B accounting for variables’ bounds.

arma::vec b_bounds: The implicit rows of b accounting for the variables’ bounds.

arma::vec c: The c vector in the objective.

arma::vec d: The d vector in the objective.

arma::vec b: The constraints’ RHS.

GRBEnv *Env: A pointer to the Gurobi environment.

VariableBounds Bounds: Bounds on the y variables.

unsigned int numParams: Number of x parameters.

unsigned int numVars: Number of y variables.

unsigned int numConstr: Number of constraints.

Private Members

double Eps = {1e-6}: A numerical tolerance.

QP_Param

class QP_Param : public MathOpt::MP_Param

A class to handle parameterized quadratic programs (QP), defined as.

\[ \min_y \frac{1}{2}y^TQy + c^Ty + (Cx)^T y + d^T x \]

Subject to

\[\begin{split}\begin{eqnarray} Ax + By &\leq& b \\ y &\geq& 0 \end{eqnarray}\end{split}\]

The shape of C is \(numVars \times numParams\)

Public Functions

inline explicit QP_Param(GRBEnv *env = nullptr)

Standard void constructor.

Parameters: env – A pointer to the Gurobi environment

QP_Param(const arma::sp_mat &Q_in, const arma::sp_mat &C_in, const arma::sp_mat &A_in, const arma::sp_mat &B_in, const arma::vec &c_in, const arma::vec &b_in, const arma::vec &d_in, GRBEnv *env = nullptr)

Empty constructor initializing only the Gurobi environment.

Constructor to set the data with copies.

Set data at construct time

Warning

The input data may be corrupted after

Parameters

Q_in – Quadratic term for y in the objective
C_in – Bi-linear term for x-y in the objective
A_in – Matrix of constraints for the parameters x
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
b_in – Vector of RHS in the constraints
env – A Gurobi Environment pointer

Returns

A pointer to this

inline QP_Param(const QP_Param &Qu)

A copy constructor given a QP_Param.

Parameters: Qu – The copied model

virtual QP_Param &set(const arma::sp_mat &Q_in, const arma::sp_mat &C_in, const arma::sp_mat &A_in, const arma::sp_mat &B_in, const arma::vec &c_in, const arma::vec &b_in, const arma::vec &d_in) final

Constructor to set the data, while keeping the input objects intact.

Parameters

Q_in – Quadratic term for y in the objective
C_in – Bi-linear term for x-y in the objective
A_in – Matrix of constraints for the parameters x
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
b_in – Vector of RHS in the constraints
d_in – Vector of linear terms for x in the objective

Returns

A pointer to this

virtual QP_Param &set(arma::sp_mat &&Q_in, arma::sp_mat &&C_in, arma::sp_mat &&A_in, arma::sp_mat &&B_in, arma::vec &&c_in, arma::vec &&b_in, arma::vec &&d_in) final

Constructor to set the data through std::move.

Warning

The input data may be corrupted after

Parameters

Q_in – Quadratic term for y in the objective
C_in – Bi-linear term for x-y in the objective
A_in – Matrix of constraints for the parameters x
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
b_in – Vector of RHS in the constraints
d_in – Vector of linear terms for x in the objective

Returns

A pointer to this

virtual QP_Param &set(const QP_Objective &obj, const QP_Constraints &cons) final

A copy constructor given a QP_Objective and QP_Constraints.

Parameters

obj – The objective
cons – The constraints object

Returns

A pointer to this

virtual QP_Param &set(QP_Objective &&obj, QP_Constraints &&cons) final

A move constructor given a QP_Objective and QP_Constraints.

Warning

The input data may be corrupted after

Parameters

obj – The objective
cons – The constraints object

Returns

A pointer to this

bool operator==(const QP_Param &Q2) const

Compares two QP_param objects.

Parameters: Q2 – The second QP_Param
Returns: True if the objects are identical

virtual unsigned int KKT(arma::sp_mat &M, arma::sp_mat &N, arma::vec &q) const override

Writes the KKT condition of the parameterized QP. As per the convention, y is the decision variable for the QP and that is parameterized in x. The KKT conditions are \(0 \leq y \perp My + Nx + q \geq 0\).

Parameters

M – The output M term
N – The output N term
q – The output q term

Returns

An int containing the rows of M

virtual std::unique_ptr<GRBModel> solveFixed(arma::vec x, bool solve) override

Given a value for the parameters \(x\) in the definition of QP_Param, returns a pointer to the parameterized MIP program. Note that the method.

Parameters

x – The parametrized values of x
solve – If the returned model is solved

Returns

a pointer to a copy of the model. In this way, valid cuts and cut pools are kept each time the method is invoked. In terms of game theory, this can be viewed as the best response for a set of decisions by other players.

Returns

A pointer to the Gurobi model

virtual void save(const std::string &filename, bool append) const override

Writes a given parameterized QP to a set of files. Writes a given parameterized Mathematical program to a set of files. One file is written for each attribute namely.

To contrast see, MathOpt::QP_Param::save where all details are written to a single loadable file

Parameters

filename – The filename
append – True if the content is appended

virtual long int load(const std::string &filename, long int pos = 0) override

Inverses the operation of QP_Param::save by loading the object from a file.

Warning

Call MP_Param(GRBEnv *env) before loading

Parameters

filename – The filename
pos – The position of the QP_Param in the file

Returns

The position after the QP_Param in the file

Private Functions

void makeyQy(): Creates the quadratic term (in the y variables) and sets QP_Param::MadeyQy to true.

Private Members

GRBModel Model: Gurobi pointer to the QP model.

bool MadeyQy: True if the objective quadratic term has been generated.

IP_Param

class IP_Param : public MathOpt::MP_Param

This class handles parametrized integer programs, and inherits from MP_Param. A parametrized Integer Program is defined as as.

\[ \min_y c^Ty + (Cx)^T y + d^T x \]

Subject to

\[\begin{split}\begin{eqnarray} By &\leq& b \\ y &\geq& 0 \\ y_i &\in& &\mathbb{Z}& &\forall& i &\in& I \end{eqnarray}\end{split}\]

Where the shape of C is \(Ny \times numParams\).

Public Functions

inline explicit IP_Param(GRBEnv *env = nullptr)

A constructor initializing only the size. Everything else is empty (can be updated later)

Parameters: env – The pointer to the Gurobi environment

IP_Param(const arma::sp_mat &C_in, const arma::sp_mat &B_in, const arma::vec &b_in, const arma::vec &c_in, const arma::vec &d_in, const arma::vec &integers_in, const VariableBounds &Bounds_in, GRBEnv *env_in)

Alternative constructor.

Parameters

C_in – The objective C matrix
B_in – The constraint matrix
b_in – The constraint RHS
c_in – The objective c vector
d_in – The objective c vector
integers_in – The indexes of integer variables
Bounds_in – The input bounds
env_in – A pointer to the Gurobi environment

inline arma::vec getIntegers() const: Read-only getter to IP_Param::Integers.

virtual bool finalize() override

This method creates the (mixed)-integer program for the game, where the objective omits the bilinear part. The flag Finalized in the object is then set to true.

Returns: True if checks are completed

IP_Param &setBounds(const VariableBounds &boundIn): Inheritor constructor for the class.

bool addConstraints(const arma::sp_mat &A_in, const arma::vec &b_in)

Adds a constraints to the IP_Param. It stores a description of the new cut \( A_{in} x \leq b_{in}\) of A_in (and RHS b_in) in B and b, respectively.

Parameters

A_in – The vector of LHS
b_in – The RHS value

Returns

true if the constraint has been added This works also when the IP_Param is Finalized.

Returns

True if the constraint is added

IP_Param(const IP_Param &ipg) = default

A copy constructor from anoter IP_Param.

Parameters: ipg – The model to be copied

MathOpt::IP_Param &set(const arma::sp_mat &C_in, const arma::sp_mat &B_in, const arma::vec &b_in, const arma::vec &c_in, const arma::vec &d_in, const arma::vec &integers_in, const VariableBounds &Bounds_in)

A setter method with copy arguments.

Parameters

C_in – Bi-linear term for x-y in the objective
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
b_in – Vector of RHS in the constraints
d_in – Vector of linear terms for x in the objective
integers_in – A vector containing the indexes of integer variables
Bounds_in – Variable bounds

Returns

A pointer to this

IP_Param &set(arma::sp_mat &&C_in, arma::sp_mat &&B_in, arma::vec &&b_in, arma::vec &&c_in, arma::vec &&d_in, arma::vec &&integers_in, VariableBounds &&Bounds_in)

A move constructor.

Parameters

C_in – Bi-linear term for x-y in the objective
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
b_in – Vector of RHS in the constraints
d_in – Vector of linear terms for x in the objective
integers_in – A vector containing the indexes of integer variables
Bounds_in – Variable bounds

Returns

A pointer to this

bool operator==(const IP_Param &IPG2) const

Compares two IP_param objects.

Parameters: IPG2 – The second IP_Param
Returns: True if the objects are identical

virtual double computeObjective(const arma::vec &y, const arma::vec &x, bool checkFeas = true, double tol = 1e-6) const override

Computes \((Cx)^Ty + c^Ty + d^Tx \) given the input values y and x. checkFeas if true, checks if the given \((x,y)\) satisfies the constraints of the problem, namely \(Ax + By \leq b\).

Parameters

y – The values for the variables y
x – The values for the parameters x
checkFeas – True if feasibility should be checked
tol – A numerical tolerance for the feasibility

Returns

A double value for the objective

virtual void save(const std::string &filename, bool append) const override

A save method for the IP_Param.

Parameters

filename – The filename
append – If true, the file will be appended

long load(const std::string &filename, long pos = 0) override

Loads the IP_Param from a file.

Warning

Call MP_Param(GRBEnv *env) before loading Example usage:

int main()
{
        GRBEnv Env;
        MathOpt::IP_Param ip(&Env);
        ip.load("./dat/q1data.dat");
        std::cout<<ip<<'\n';
        return 0;
}

Parameters

filename – The filename
pos – The position of the IP_Param in the file

Returns

The position after the IP_Param

void updateModelObjective(const arma::vec &x)

This method updates the model objective in IP_Param::IPModel by setting x to x.

Parameters: x – The parametrized values of x

virtual std::unique_ptr<GRBModel> solveFixed(arma::vec x, bool solve = false) override

Given a value for the parameters \(x\) in the definition of IP_Param, returns a pointer to the parameterized MIP program . Note that the method.

Parameters

x – The parametrized values of x
solve – If the returned model is solved

Returns

a pointer to a copy of the model. In this way, valid cuts and cut pools are kept each time the method is invoked. In terms of game theory, this can be viewed as the best response for a set of decisions by other players.

Returns

A pointer to the Gurobi model

std::unique_ptr<GRBModel> getIPModel(const arma::vec &x, bool relax = false)

Given a value for the parameters \(x\) in the definition of IP_Param, returns a pointer to the parameterized MIP program . Note that the method.

Parameters

x – The values for the parametrized x
relax – True if the model relaxes integrality requirements

Returns

a pointer to a copy of the model. In this way, valid cuts and cut pools are kept each time the method is invoked. If relax is true, then the model is the linear relaxation of the MIP.

Returns

A pointer to the Gurobi model

virtual unsigned int KKT(arma::sp_mat &M, arma::sp_mat &N, arma::vec &q) const override

Writes the KKT condition of the relaxation of the parameterized IP. As per the convention, y is the decision variable for the IP and that is parameterized in x. The KKT conditions are \(0 \leq y \perp My + Nx + q \geq 0\).

Parameters

M – The output M term
N – The output N term
q – The output q term

Returns

An int containing the rows of M

virtual bool isFeasible(const arma::vec &y, const arma::vec &x, double tol) const override

Given a parameter value x, and variables values y, returns true whenever the point is feasible for the program. This method overrides the MathOpt::MP_Param to manage integral requirements.

Parameters

y – The variables’ values
x – The parameters’ values
tol – A numerical tolerance

Returns

True if the point is feasible

void presolve()

Presolved the IP model and replaces the object in the class with the (possibly) simplified model. Note: this should be used with care. First, it can mess the sizes of the variables/constraints. Second, it may be resource consuming.

Todo:: currently disabled. check the method

Private Functions

MP_Param &set(const arma::sp_mat &Q_in, const arma::sp_mat &C_in, const arma::sp_mat &A_in, const arma::sp_mat &B_in, const arma::vec &c_in, const arma::vec &b_in, const arma::vec &d_in)

Constructor to set the data, while keeping the input objects intact.

Parameters

Q_in – Quadratic term for y in the objective
C_in – Bi-linear term for x-y in the objective
A_in – Matrix of constraints for the parameters x
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
d_in – Vector of linear terms for x in the objective
b_in – Vector of RHS in the constraints

Returns

A pointer to this

MP_Param &set(arma::sp_mat &&Q_in, arma::sp_mat &&C_in, arma::sp_mat &&A_in, arma::sp_mat &&B_in, arma::vec &&c_in, arma::vec &&b_in, arma::vec &&d_in)

Constructor to set the data through std::move.

Warning

The input data may be corrupted after

Parameters

Q_in – Quadratic term for y in the objective
C_in – Bi-linear term for x-y in the objective
A_in – Matrix of constraints for the parameters x
B_in – Matrix of constraints for the variables y
c_in – Vector of linear terms for y in the objective
d_in – Vector of linear terms for x in the objective
b_in – Vector of RHS in the constraints

Returns

A pointer to this

MP_Param &set(const QP_Objective &obj, const QP_Constraints &cons)

A copy constructor given a QP_Objective and QP_Constraints.

Parameters

obj – The objective
cons – The constraints object

Returns

A pointer to this

MP_Param &set(QP_Objective &&obj, QP_Constraints &&cons)

A move constructor given a QP_Objective and QP_Constraints.

Warning

The input data may be corrupted after

Parameters

obj – The objective
cons – The constraints object

Returns

A pointer to this

Private Members

GRBModel IPModel: Stores the IP model associated with the object.

arma::vec Integers: Stores the indexes of integer variables.

bool Finalized = {false}: True if the model has been made and constraints cannot be changed.

LCP

class LCP

This class manages and solves linear complementarity problems (LCPs). Let \(M\) be a matrix, \(q\) a vector with as many elements as the number of rows of \(M\). The associated LCP problem is to find.

\[ z=Mx+q \qquad x^\top z = 0 \]

Possibly, there can be additional side constraints in the form of

\[ Ax \leq b\]

This class has is the base class of MathOpt::PolyLCP, which manages the polyhedral aspect of the problem.

Subclassed by MathOpt::PolyLCP

Public Functions

LCP() = delete: No default constructor.

inline explicit LCP(GRBEnv *e)

A base constructor that does not initialize most of objects. This is useful when loading from a file

Parameters: e – The Gurobi environment

LCP(GRBEnv *env, arma::sp_mat &M, arma::vec &q, unsigned long int leadStart, unsigned leadEnd, arma::sp_mat &A, arma::vec &b)

A constructor for LCPs where some variables are subject to complementarities. This is useful, for instance, for Stackelberg games.

Parameters

env – The Gurobi environment pointer
M – The M matrix for the LCP
q – The q vector for the LCP
leadStart – Starting location of not-complementary variables
leadEnd – Ending location of not-complementary variables
A – Additional constraints matrix LHS
b – Additional constraints RHS

LCP(GRBEnv *env, arma::sp_mat &M, arma::vec &q, perps &Compl, arma::sp_mat &A, arma::vec &b)

A standard constructor for an LCP.

Parameters

env – The Gurobi environment pointer
M – The M matrix for the LCP
q – The q vector for the LCP
Compl – The complementarity pairs <Equation, Variable>
A – Additional constraints matrix LHS
b – Additional constraints RHS

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

Constructor given a Game::NashGame.

Given a NashGame, computes the KKT of the lower levels, and makes the appropriate LCP object. This constructor is the most suited for high-level usage.

Parameters

env – The Gurobi environment pointer
N – The Game::NashGame

~LCP() = default: Destructor - to delete the objects created with new operator

inline arma::sp_mat getM() const

Read-only access to LCP::M.

Returns: LCP::M

inline arma::vec getq() const

Read-only access to LCP::q.

Returns: LCP::q

inline unsigned long int getNumberLeader() const: Read-only access to LCP::NumberLeader.

inline const unsigned long int getLStart() const

Read-only access to LCP::LeadStart.

Returns: LCP::LeadStart

inline const arma::sp_mat getA() const

Read-only access to LCP::A.

Returns: LCP::A

inline const arma::vec getb() const

Read-only access to LCP::b.

Returns: LCP::b

inline const unsigned long int getLEnd() const

Read-only access to LCP::LeadEnd.

Returns: LCP::LeadEnd

inline perps getCompl() const

Read-only access to LCP::Compl.

Returns: LCP::Compl

inline unsigned long int getNumCols() const

Read-only access to LCP::nC.

Returns: LCP::nC

inline unsigned long int getNumRows() const

Read-only access to LCP::nR.

Returns: LCP::nR

inline bool hasCommonConstraints() const

bool extractSols(GRBModel *model, arma::vec &z, arma::vec &x, bool extractZ = false) const

A method to check whether LCP::A has any non-zero, namely any constraints.

Extracts variable and equation values from a solved Gurobi model.

Parameters

model – The Gurobi Model that was solved
z – Output variable for Z equation values
x – Output variable for X variable values
extractZ – Should the method extract Z values or not

Returns

true if the model was solved. False otherwise.

ZEROStatus solve(Data::LCP::Algorithms algo, arma::vec &xSol, arma::vec &zSol, double timeLimit, unsigned long int threads, double &objective, unsigned long int solLimit = 1)

This method is the generic wrapper to solve the LCP.

Parameters

algo – The Data::LCP::Algorithms used to solve the LCP
xSol – The resulting solution for z, if any. If the vector is filled, it will be seeded as a warmstart if Data::LCP::Algorithms::MIP
zSol – The resulting solution for z, if any. If the vector is filled, it will be seeded as a warmstart if Data::LCP::Algorithms::MIP
timeLimit – A double time limit
threads – The absolute number of threads in case algo is Data::LCP::Algorithms::MIP
solLimit – The number of solutions in the pool for if algo is Data::LCP::Algorithms::MIP
cutOff – Bounds the optima solution to be >= than a given threshold. Used if different from -GRB_INFINITY. As output, the object will be filled with the incumbent optimal value

Returns

A ZEROStatus for the problem

std::unique_ptr<GRBModel> LCPasMIP(bool solve = false, double timeLimit = -1, unsigned long int threads = 1, unsigned long int solLimit = 1)

Solves the LCP as a Mixed-Integer Program. Note that the returned model is either a MIP or a MINLP, depending on the class’ LCP::PureMIP boolean switch. In the first case, complementarities are modeled through SOS1 or indicator constraints. Otherwise, there is bi-linear term for each complementarity.

Parameters

solve – Determines whether the returned model is already solved or not
timeLimit – Sets the timeLimit for the MIP solver
threads – Sets the number of threads
solLimit – Sets the number of solutions in the pool

Returns

The unique pointer to the model

std::unique_ptr<GRBModel> LCPasMILP(const arma::sp_mat &C, const arma::vec &c, const arma::vec &x_minus_i, bool solve = false)

This method returns an unique pointer to the Gurobi model where the objective is the one of a specific player. In particular, given by the parameter C, c, x_minus_i are fixed and then the objective is linear (MILP).

Warning

If LCP::PureMIP is false, then the model has a linear objective and bi-linear constraints. Hence, is not a MILP

Parameters

C – The interaction term for a given player
c – The linear term for a given player
x_minus_i – The strategies of other players
solve – True if the returned model is solved

Returns

The unique pointer to the model

std::unique_ptr<GRBModel> LCPasMIQP(const arma::sp_mat &Q, const arma::sp_mat &C, const arma::vec &c, const arma::vec &x_minus_i, bool solve = false)

This method returns an unique pointer to the Gurobi model where the objective is the one of a specific player. In particular, given by the parameter C, c, x_minus_i are fixed and then the objective is quadratic (MIQP)

Warning

If LCP::PureMIP is false, then the model has a quadratic objective and bi-linear constraints

Parameters

Q – The quadratic term for a given player
C – The interaction term for a given player
c – The linear term for a given player
x_minus_i – The strategies of other players
solve – True if the returned model is solved

Returns

The unique pointer to the model

ZEROStatus solvePATH(double timelimit, arma::vec &x, arma::vec &z, bool verbose = true)

Solves the LCP with Solvers::PATH.

Parameters

timelimit – A double time limit on the solving process
z – The resulting solution for z, if any
x – The resulting solution for x, if any
verbose – True if PATH will be verbose

Returns

The ZEROStatus of the model

void save(const std::string &filename, bool erase = true) const

Saves the LCP into a file.

Parameters

filename – The filename
erase – Whether the file should be cleaned or not

long int load(const std::string &filename, long int pos = 0)

This method load the LCP object from a file.

Parameters

filename – The filename
pos – The position of the LCP in the file

Returns

The position after the LCP in the file

virtual void makeQP(MathOpt::QP_Objective &QP_obj, MathOpt::QP_Param &QP)

This method create the convex-hull of the feasible (approximated) region for the LCP, and puts it into a MathOpt::QP_Param object. In addition, it transform the given input objective function by adding additional zero elements to it, to fit the number of variables in the quadratic program.

Parameters

QP_obj – The input/output MathOpt::QP_Param objective
QP – The output MathOpt::QP_Param

void addCustomCuts(const arma::sp_mat &A, const arma::vec &b)

Adds custom cuts defined in the input to the LCP::A and LCP::b objects.

Parameters

A_in – The LHS of the added cuts
b_in – The RHS of the added cuts note This method does not check whether such cuts are already in the LCP.

bool containsCut(const arma::vec &LHS, const double RHS, double tol = 1e-5)

Given the cut, the method checks whether there is already one (up to a numerical tolerance) in the LCP.

Parameters

A_in – The LHS of the cut
b_in – The RHS of the cut
tol – The numerical tolerance

Returns

True if the cut is already present, false otherwise.

arma::vec zFromX(const arma::vec &x)

Given a value for the variables, it returns the values of z.

Parameters: x – The x-values vector
Returns: The z-values vector

void processBounds(): Processes the bounds of BoundsX and removes any complementarity that is useless (e.g., variable is fixed). After processing, it calls back LCP::defConst to re-initializes the private attributes.

bool setMIPLinearObjective(const arma::vec &c)

Given the linear vector x c, sets the linear objective for the MIP reformulation of the LCP.

Parameters: c – Linear vector for the primal variables
Returns: True if successful

bool setMIPQuadraticObjective(const arma::vec &c, const arma::sp_mat &Q)

Given the linear vector and quadratic matrix c and Q, sets the quadratic objective for the MIP reformulation of the LCP.

Parameters

c – Linear vector for the primal variables
Q – Square matrix for the primal variables

Returns

True if successful

bool setMIPFeasibilityObjective()

Public Members

double Eps = {1e-6}: The threshold for optimality and feasability tolerances.

Protected Functions

void defConst(GRBEnv *env)

Assigns default values to the class’ LCP attributes.

Internal member that can be called from multiple constructors to assign default values to some attributes of the class.

Parameters: env – The Gurobi environment pointer

void makeRelaxed()

Makes a Gurobi object that relaxes complementarity constraints in the LCP.

The field LCP::RelaxedModel stores the relaxed version of the problem

void setMIPObjective(GRBModel &convexModel)

Given the MIP model in MIP, sets the objective according to the one given by MathOpt::LCP::setMIPQuadraticObjective or MathOpt::LCP::setMIPLinearObjective.

Parameters: MIP – The MIP model

std::unique_ptr<GRBModel> getMIP(bool indicators = false)

Gets the MIP model associated with the LCP, where complementarities are modeled with with SOS-1 constraints if indicators is false, with indicator constraints otherwise.

Parameters: indicators – If true, SOS-1 formulation will be used for each complementarity. Otherwise, indicator constraints will be used
Returns: The Gurobi pointer to the model

std::unique_ptr<GRBModel> getMINLP()

Gets the MINLP model associated with the LCP, where complementarities are modeled with bi-linear terms.

Returns: The Gurobi pointer to the model

unsigned long int convexHull(arma::sp_mat &A, arma::vec &b)

Computes the convex hull of the feasible region of the LCP.

Parameters

A – The output convex-hull LHS
b – The output convex-hull RHS

Returns

The number of polyhedra in the approximation

Protected Attributes

GRBEnv *Env = {}: A pointer to the Gurobi Env.

unsigned int ObjType = 0: Type of the objective for MIP/MINLP. 0 is feasibility, 1 linear, 2 quadratic.

arma::vec c_Obj: The linear objective for the LCP in case of MIP/MINLP.

arma::sp_mat Q_Obj: The quadratic objective matrix Q for the LCP in case of MIP/MINLP.

bool MadeObjective = false: True if the objective has been updated.

arma::sp_mat M: The matrix M in \(Mx+q\) that defines the LCP.

arma::vec q: The vector q in \(Mx+q\) that defines the LCP.

perps Compl: Compl dictates which equation (row in M) is complementary to which variable (column in M). The object is in a <Eqn, Var> form.

unsigned long int LeadStart = {1}: Starting leader location.

unsigned long int LeadEnd = {0}: Ending leader location.

unsigned long int NumberLeader = {0}: Number of leaders.

bool PureMIP = true: True if the LCP is modelled via a pure MIP with SOS1 (or indicator) constraints. Otherwise, a MINLP introduces a bilinear term for each complementarity.

arma::sp_mat A = {}: The additional constraint matrix A to the problem, in the form \(Ax \leq b\).

arma::vec b = {}: The additional constraint RHSs b to the problem, in the form \(Ax \leq b\).

bool MadeRlxdModel = {false}: True if a relaxed model has been already initialized.

unsigned long int nR = {}: The number of rows in the matrix M.

unsigned long int nC = {}: The number of columns in the matrix M.

VariableBounds BoundsX: Stores non-trivial upper and lower bounds on x variables in as a tuple (j,k) where j the lower bound, and k the upper bound. Usually, j is initialized to 0, while k to -1 (meaning inactive upepr bound)

GRBModel RelaxedModel: A Gurobi model without complementarities.

std::unique_ptr<spmat_Vec> Ai: A pointer to matrices containing the LHSs of a description (either exact or approximated) of the LCP’s feasible region

std::unique_ptr<vec_Vec> bi: A pointer to vectors containing the RHSs of a description (either exact or approximated) of the LCP’s feasible region

PolyLCP

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