Class LCP

Inheritance Relationships

Derived Type

Class Documentation

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

LCP::M

inline arma::vec getq() const

Read-only access to LCP::q.

Returns

LCP::q

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