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 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 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$
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 &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

• integers_in – The indexes of integer variables

• Bounds_in – The input bounds

• env_in – A pointer to the Gurobi environment

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)
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 &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

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

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

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)

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

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)

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

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 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
~LCP() = default

Destructor - to delete the objects created with new operator

inline arma::sp_mat getM() const

Read-only access to LCP::M.

Returns
inline arma::vec getq() const

Read-only access to LCP::q.

Returns
inline const unsigned long int getLStart() const

Read-only access to LCP::LeadStart.

Returns
inline const arma::sp_mat getA() const

Read-only access to LCP::A.

Returns
inline const arma::vec getb() const

Read-only access to LCP::b.

Returns
inline const unsigned long int getLEnd() const

Read-only access to LCP::LeadEnd.

Returns
inline perps getCompl() const

Read-only access to LCP::Compl.

Returns
inline unsigned long int getNumCols() const

Read-only access to LCP::nC.

Returns
inline unsigned long int getNumRows() const

Read-only access to LCP::nR.

Returns
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 MIPWorkers, 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

• MIPWorkers – The absolute number of MIP Workers 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 MIPWorkers = 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

• MIPWorkers – Sets the number of concurrent MIPWorkers

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

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

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

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)

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

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)

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

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 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 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 std::array<std::set<unsigned long int>, 2> getAllPolyhedra() const

Gets the CurrentPoly object.

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

methodData::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_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
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 mean.

Public Members

arma::sp_mat Q
arma::sp_mat C
arma::vec c
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$
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, 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) 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

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

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 MathOpt::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$
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

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

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

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)

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

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)

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

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 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 MathOpt::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$
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, 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) 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

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

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 MathOpt::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$
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 &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

• integers_in – The indexes of integer variables

• Bounds_in – The input bounds

• env_in – A pointer to the Gurobi environment

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)
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 &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

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

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

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)

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

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)

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

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 MathOpt::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
~LCP() = default

Destructor - to delete the objects created with new operator

inline arma::sp_mat getM() const

Read-only access to LCP::M.

Returns
inline arma::vec getq() const

Read-only access to LCP::q.

Returns
inline const unsigned long int getLStart() const

Read-only access to LCP::LeadStart.

Returns
inline const arma::sp_mat getA() const

Read-only access to LCP::A.

Returns
inline const arma::vec getb() const

Read-only access to LCP::b.

Returns
inline const unsigned long int getLEnd() const

Read-only access to LCP::LeadEnd.

Returns
inline perps getCompl() const

Read-only access to LCP::Compl.

Returns
inline unsigned long int getNumCols() const

Read-only access to LCP::nC.

Returns
inline unsigned long int getNumRows() const

Read-only access to LCP::nR.

Returns
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 MIPWorkers, 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

• MIPWorkers – The absolute number of MIP Workers 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 MIPWorkers = 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

• MIPWorkers – Sets the number of concurrent MIPWorkers

• 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
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 MathOpt::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 std::array<std::set<unsigned long int>, 2> getAllPolyhedra() const

Gets the CurrentPoly object.

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

methodData::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