LCPs

In the previous tutorial, we introduced the LCP problem. Here we give a brief overview of MathOpt::LCP. This class provides the essential tools to solve LCPs. Since the solution of LCPs are union of polyhedra, the inheritor class MathOpt::PolyLCP supports the polyhedral aspect of LCPs.

MathOpt::LCP handles problems in the following form:

\[ \begin{align}\begin{aligned}Ax + By \leq b\\0 \leq x \perp Mx + Ny + q \geq 0\end{aligned}\end{align} \]

However, we use a different notation. Instead of using y to refer to the variables that do not have matching complementary equations, we call all the variables as x and we keep track of the position of variables that are not complementary to any equation.

Note

The set of x’s indices that are not complementary to any equation should be a consecutive set of indices. For the sake of clarity, these components we refer to these as Leader vars components of x. - Suppose the leader vars components of x are not in x, in the remaining components, the first component should be complementary to the first row defined by @p M, the second component should be complementary to the second row defined by M and so on.

Note

For the sake of explaination, we assume that the lower bounds for the x variables is 0. However, ZERO handles arbitrary lower and upper bounds on these variables. In other words, it handles Mixed LCPs.

Modeling the problem

Now consider the following linear complementarity problem.

\[ \begin{align}\begin{aligned}x_1 + x_2 + x_3 \le 12\\0\le x_1 \perp x_4 - 1 \ge 0\\0\le x_2 \le 2\\0 \le x_3 \perp 2x_3 + x_5 \ge 0\\0 \le x_4 \perp -x_1 + x_2 + 10 \ge 0\\0 \le x_5 \perp x_2 - x_3 + 5 \ge 0\end{aligned}\end{align} \]

The variable \(x_2\) has no complementarity equation. This problem can be entered into the MathOpt::LCP class as follows.

// We have four complementarity equations and 5 variables.
arma::vec q(4); M.zeros();
arma::sp_mat M(4, 5);
// First equation
M(0, 3) = 1;
q(0) = -1;
// Second equation
M(1, 2) = 2;
M(1, 4)  = 1;
q(1) = 0;
// Third equation
M(2, 0) = -1;
M(2, 1) = 1;
q(2) = 10;
// Fourth equation
M(3, 1) = 1 ;
M(3, 2) = -1;
q(3) = 5;
// Other common constraints
arma::sp_mat A(2, 5); arma::vec b;
A.zeros();
// x_2 <= 2 constraint
A(0, 1) = 1;
b(0) = 2;
// x_1 + x_2 + x_3 <= 12 constraint
A(1, 0) = 1;
A(1, 1) = 1;
A(1, 2) = 1;
b(1) = 12;

Since the variable with no complementarity pair is \(x_2\) which is in position 1 (counting from 0) of the vector x, the arguments LeadStart and LeadEnd in the constructor, MathOpt::LCP::LCP() are 1 as below.

GRBEnv env;
LCP lcp = LCP(&env, M, q, 1, 1, A, b);

Computing solutions

This problem can be solved either with a MIP, a MINLP, or with PATH (Data::LCP::Algorithms). You refer MathOpt::LCP::solve() for various solution method.

// Solve using PATH
arma::vec x;
arma::vec z;
auto indModel = lcp.solve(Data::LCP::Algorithms::PATH,x,z,-1,1);

This LCP has multiple solutions. The solution set can be parameterized as below.

\[ \begin{align}\begin{aligned}x_1 &= 10 + t\\x_2 &= t\\x_3 &= 0\\x_4 &= 1\\x_5 &= 0\\\text{for}\;\; t \in [0, 1]\end{aligned}\end{align} \]

Utilities

Two functions MathOpt::LCP::LCPasMILP() and MathOpt::LCP::LCPasMIQP() allows to to optimize a linear objective function or a convex quadratic objective function over the set of solutions. Also, note that MathOpt::LCP::setMIPLinearObjective(), MathOpt::LCP::setMIPQuadraticObjective(), MathOpt::LCP::setMIPFeasibilityObjective() can change the objective function of the MIP model (if one is called for solving the LCP). In general, we recommend using:cpp:func:MathOpt::LCP::solve, which is a general method that delegates the solution to either one available solver.