Class LCP

Defined in File lcp.h

Inheritance Relationships

Derived Type

public MathOpt::PolyLCP (Class PolyLCP)

Class Documentation

class LCP

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

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

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

\[ Ax \leq b\]

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

Subclassed by MathOpt::PolyLCP

Public Functions

LCP() = delete: No default constructor.

inline explicit LCP(GRBEnv *e)

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

Parameters: e – The Gurobi environment

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

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

Parameters

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

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

A standard constructor for an LCP.

Parameters

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

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

Constructor given a Game::NashGame.

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

Parameters

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

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

inline arma::sp_mat getM() const

Read-only access to LCP::M.

Returns: LCP::M

inline arma::vec getq() const

Read-only access to LCP::q.

Returns: LCP::q

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

inline const unsigned long int getLStart() const

Read-only access to LCP::LeadStart.

Returns: LCP::LeadStart

inline const arma::sp_mat getA() const

Read-only access to LCP::A.

Returns: LCP::A

inline const arma::vec getb() const

Read-only access to LCP::b.

Returns: LCP::b

inline const unsigned long int getLEnd() const

Read-only access to LCP::LeadEnd.

Returns: LCP::LeadEnd

inline perps getCompl() const

Read-only access to LCP::Compl.

Returns: LCP::Compl

inline unsigned long int getNumCols() const

Read-only access to LCP::nC.

Returns: LCP::nC

inline unsigned long int getNumRows() const

Read-only access to LCP::nR.

Returns: LCP::nR

inline bool hasCommonConstraints() const

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

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

Extracts variable and equation values from a solved Gurobi model.

Parameters

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

Returns

true if the model was solved. False otherwise.

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

This method is the generic wrapper to solve the LCP.

Parameters

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

Returns

A ZEROStatus for the problem

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

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

Parameters

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

Returns

The unique pointer to the model

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

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

Warning

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

Parameters

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

Returns

The unique pointer to the model

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

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

Warning

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

Parameters

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

Returns

The unique pointer to the model

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

Solves the LCP with Solvers::PATH.

Parameters

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

Returns

The ZEROStatus of the model

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

Saves the LCP into a file.

Parameters

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

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

This method load the LCP object from a file.

Parameters

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

Returns

The position after the LCP in the file

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

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

Parameters

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

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

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

Parameters

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

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

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

Parameters

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

Returns

True if the cut is already present, false otherwise.

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

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

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

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

bool setMIPLinearObjective(const arma::vec &c)

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

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

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

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

Parameters

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

Returns

True if successful

bool setMIPFeasibilityObjective()

Public Members

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

Protected Functions

void defConst(GRBEnv *env)

Assigns default values to the class’ LCP attributes.

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

Parameters: env – The Gurobi environment pointer

void makeRelaxed()

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

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

void setMIPObjective(GRBModel &convexModel)

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

Parameters: MIP – The MIP model

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

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

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

std::unique_ptr<GRBModel> getMINLP()

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

Returns: The Gurobi pointer to the model

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

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

Parameters

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

Returns

The number of polyhedra in the approximation

Protected Attributes

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

GRBModel RelaxedModel: A Gurobi model without complementarities.

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

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