Originally posted by: EPED_Nicholas_Drake

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.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: John Cui

Here is what I get:

Tried aggregator 1 time.
MIP Presolve eliminated 6 rows and 5 columns.
All rows and columns eliminated.
Presolve time =    0.00 sec.
 
Solution status = integer optimal solution 
Solution value = 0.000000 
Values =
     0
     0
     0
     0
     0

You can see it is not null, what did you get?

John
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EPED_Nicholas_Drake

That is the same solution that I gather, sorry I should have been more specific when I explained the solution the O vector for this problem is called the Null solution, as in that is always a solution to the problem, I reworked the problem using another definition and retrieved an answer but it is also incorrect. Basically I believe that I am setting the problem up incorrect in converting from the LCP problem to the MIP. Once question that I do have is for ctype if x4 x5 can be either 0 or 1 should I set their ctype to B (binary). I think that I am missing how to set the problem up to as the MIP.

This is what I got when I re-worked the problem

max a
a, y, z
st
a<=(My)+aq<= z
0<=y<=1-z
0<=a
z = 0 or 1
e is the vector(array) of all ones.

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.

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 inequalities

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

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

%%%%%%%%%%%%%%%%%%%%%%%%%CODE%%%%%%%%%%%%%%%%%%%%%
function LCP_test2
try
f = -1 -1 -1 -1 -1' ;
Aineq = 2 -1 1 1 0; -4 0 1 0 1;
bineq = 0; 0;
Aeq=[];
beq=[];
lb=0;0;0;0;0;
ub = 1; 1; 1; 1; 1;
ctype= 'CCCBB';
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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%OUTPUT%%%%%%%%%%%%%%%%%
Tried aggregator 2 times.
MIP Presolve eliminated 0 rows and 1 columns.
Aggregator did 1 substitutions.
Reduced MIP has 1 rows, 3 columns, and 3 nonzeros.
Reduced MIP has 2 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec.
Clique table members: 1.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 2 threads.
Root relaxation solution time = -0.00 sec.

Nodes Cuts/
Node Left Objective IInf Best Integer Best Node ItCnt Gap

• 0+ 0 -1.8333 0 ---

0 0 -2.7500 1 -1.8333 -2.7500 0 50.00%

• 0+ 0 -2.6667 -2.7500 0 3.12%

0 0 cutoff -2.6667 0 0.00%

Root node processing (before b&c):
Real time = 0.01
Parallel b&c, 2 threads:
Real time = 0.00
Sync time (average) = 0.00
Wait time (average) = 0.00

---

Total (root+branch&cut) = 0.01 sec.

Solution status = integer optimal solution
Solution value = -2.666667
Values =
0.3333
1.0000
0.3333
0
1.0000
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Where I think I have a problem is in the bounds or setup of the problem

I really dont need to maximize x4 or x5 and since there always 1 or 0 I should be able to set to binary. See the problem I have is finding someone who can verify the conversion from LCP to MIP is correct; for arguments sake I know that x1=.25 x2 =.5 and x3=0.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: John Cui

1. x1, x2 and x3 less than 1 or less than inf? I saw they are less than inf in your formula, but you set their ub to 1 in your matlab code.
2. set B in ctype is ok for CPLEX.

John Cui
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EPED_Nicholas_Drake

I believe that i have the x2 and x3 bounds correct but for for x1 inf would be the correct value but i still get the same solution, which isnt correct still.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: John Cui

Sorry, I think I didn't catch your point.

Could you please summarize your questions again? For example, which kind feature in MATLAB connector you don't know how to use.

John Cui
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EPED_Nicholas_Drake

I think I am using the cplex function correct. It is casting the problem from the LCP to the MILP that I believe I am failing at. As far as I can tell, the bounds are now correct with x1<=inf all others being less than 1. I dont think there is anything more in terms of cplex that I need to have answered. Setting x4 x5 to ctype binary was helpful, being that they can only be 1 or 0.
Thank you for your help with explaining the cplex portion, I must now work on getting the conversion correct.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EPED_Nicholas_Drake

John,

I know that this might be a dead thread but I had one more question. How does Cplex handle mutliple soltions I know there is supposed to be multiple solutions for a problem. ( I know the answer before hand) how does cplex handle that, is there a way to gather multiple solutions into a pool so that further mathematical theory can be used to determine the global optimal solutions?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: John Cui

You can do it in CPLEX matlab interface.

But you may need to switch to Cplex class, when you solved a MIP model by Cplex class, then there is pool field in Cplex.Solution stucture.
And you can set CPLEX parameters to get more solutions. Please refer to solution pool doc here:

http://publib.boulder.ibm.com/infocenter/cosinfoc/v12r4/topic/ilog.odms.cplex.help/CPLEX/User_manual/topics/uss_solnpool_1.html
John Cui
#CPLEXOptimizers
#DecisionOptimization