# Linear Complementarity problem using cplexmilp to solve.

1. Jan 27, 2012

### ndrake86

I am working on solving the linear complementarity problem, find vectors x,w such that w = Mx+q, x,w>=0 and w'x=0. Mathematically you can convert this problem into an equivalent mixed integer program and thus should be able to solve with cplexmilp. The format for the MILP is

max a
a, y, z
st
a<=(My)+aq<= 1-z
0<=y<=z
0<=a
z = 0 or 1

I have wrote the code the way I thought for a test problem in which I already know the solution and I get the null vector as a return which is not correct.

I am asking for help, if anyone has an idea please let me know

for syntax the M = 1 -1; 0 -1 q = -2 4'
which if I did my math correctly should lead to the following set of ineqalities

2x1-x2+x3 <=0
-4x1+x3<=0
-2x1+x2-x3+x4<=1
4x1-x3+x5<=1
x2+x4<=0
x3+x5<=0

with bounds

0<=x1<inf
0<=x2<inf
0<=x3<inf
0<=x4<1
0<=x5<1

here x4 and x5 are integers.

For consistency in notation

x1=a x2=y1 x3 =y2 x4 =z1 x5 =z2

This is my MATlab code to solve this problem
%%
%%
function LCP_test
try
f = -1 -1 -1 -1 -1' ;
Aineq = [2 -1 1 0 0; -4 0 1 0 0; -2 1 -1 1 0; 4 0 1 0 1; 0 1 0 1 0; ...
0 0 1 0 1];
bineq = 0; 0; 1; 1; 0; 0;
Aeq=[];
beq=[];
lb=0;0;0;0;0;
ub = inf; inf; inf; 1; 1;
ctype= 'CCCII';

options = cplexoptimset;
options.Diagnostics = 'on';

x, fval, exitflag, output = cplexmilp (f, Aineq, bineq, Aeq, beq,...
[ ], [ ], ], lb, ub, ctype, [, options);

fprintf ('\nSolution status = %s \n', output.cplexstatusstring);
fprintf ('Solution value = %f \n', fval);
disp ('Values =');
disp (x);
catch m
disp (m.message);
end
end
%%

please any help with this would be great.