In the previous tutorial, we introduced the LCP problem. Here we give a brief overview of
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:
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.
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
- 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.
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.
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
LeadEnd in the constructor,
1 as below.
GRBEnv env; LCP lcp = LCP(&env, M, q, 1, 1, A, b);
// 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.
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::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.