Originally posted by: SystemAdmin

Hello,

I tried to run a simple quadratic MIP problem with CPLEX in Matlab. However, I met the following error,

??? Error using ==> cplexmiqcp at 782
Error: incorrect l,Q,r.

Error in ==> Untitled at 22
x, fval, exitflag, output = cplexmiqcp (H, [ ], Aineq, bineq, [ ], [ ],...

Would anyone please help me fix the code as attached or tell me where the error comes from?

Thanks very much.

H = zeros(9,9);
for j=1:1:8
H(j,9) = 0.5 * 1;
H(9,j) = H(j,9);
end

Aineq = 1 2 3 4 5 6 7 8 9;
bineq = 1000;

l = 0 0 0 0 0 0 0 0 0;
Q = zeros(9,9);
Q(9,:)= 1 1 1 1 1 1 1 1 0;
r = -1 * 10;

lb = 0 0 0 0 0 0 0 0 0';
ub = inf inf inf inf inf inf inf inf 10';
ctype = 'IIIIIIIIC';
options = cplexoptimset;

x, fval, exitflag, output = cplexmiqcp (H, [ ], Aineq, bineq, [ ], [ ],...
l, Q, r, [ ], [ ], [ ], lb, ub, ctype, [ ], options);

fprintf ('\nSolution status = %s\n', output.cplexstatusstring);
fprintf ('Solution value = %f\n', fval);
disp ('Values =');
disp (x');
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I have read some posts in the forum and change my code as follows, but the problem is still there.

The problem is like this
Minimize
0.0258 x1 x9 + 0.022 x2 x9 + 0.0458 x3 x9 + 0.0616 x4 x9 + 0.0552 x5 x9 + 0.1956 x6 x9
+ 0.3238 x7 x9 + 0.9362 x8 x9

Subject to
6 x1 + 7 x2 + 12 x3 + 15 x4 + 15 x5 + 30 x6 + 39 x7 + 107 x8 + 0 x9 <= 100
0.0478 x1 x9 + 0.0357 x2 x9 + 0.0587 x3 x9 + 0.0948 x4 x9 + 0.1166 x5 x9 +
0.4812 x6 x9 + 0.8421 x7 x9 + 1.8286 x8 x9 >= 100

Bounds
x1 >= 0
x2 >= 0
x3 >= 0
x4 >= 0
x5 >= 0
x6 >= 0
x7 >= 0
x8 >= 0
50 >= x9 >= 0

Generals
x1 x2 x3 x4 x5 x6 x7 x8

End
\{code\}
f = 0 0 0 0 0 0 0 0 0;
H = [0 0 0 0 0 0 0 0 0.0129
0 0 0 0 0 0 0 0 0.011
0 0 0 0 0 0 0 0 0.0229
0 0 0 0 0 0 0 0 0.0308
0 0 0 0 0 0 0 0 0.0276
0 0 0 0 0 0 0 0 0.0978
0 0 0 0 0 0 0 0 0.1619
0 0 0 0 0 0 0 0 0.04681
0.0129 0.011 0.0229 0.0308 0.0276 0.0978 0.1619 0.4681 0];

Aineq = 6 7 12 15 15 30 39 107 0';
bineq = 100;

% both Q and r multiply (-1) to reverse >= as <=
l = 0 0 0 0 0 0 0 0 0';
Q = [0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
-0.0478 -0.0357 -0.0587 -0.0948 -0.1166 -0.4812 -0.8421 -1.8286 0];
r = -100;

lb = 0 0 0 0 0 0 0 0 0';
ub = inf inf inf inf inf inf inf inf 50';
ctype = 'IIIIIIIIC';
options = cplexoptimset;

x, fval, exitflag, output = cplexmiqcp (H, f, Aineq, bineq, [ ], [ ],...
l, Q, r, [ ], [ ], [ ], lb, ub, ctype, [ ], options);

\{code\}

I am very new to CPLEX, so I have two questions.
(1) Is this kind of problem as mentioned above fit CPLEX?
(2) Why does the code give me the following error and how could I fix it?
??? Error using ==> cplexmiqcp at 782
CPLEX Error 5002: Q in %s is not positive semi-definite.

Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

CPLEX 12.5 + Matlab 2009 are used.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I have read some posts in the forum and change my code as follows, but the problem is still there.

The problem is like this
Minimize
0.0258 x1 x9 + 0.022 x2 x9 + 0.0458 x3 x9 + 0.0616 x4 x9 + 0.0552 x5 x9 + 0.1956 x6 x9
+ 0.3238 x7 x9 + 0.9362 x8 x9

Subject to
6 x1 + 7 x2 + 12 x3 + 15 x4 + 15 x5 + 30 x6 + 39 x7 + 107 x8 + 0 x9 <= 100
0.0478 x1 x9 + 0.0357 x2 x9 + 0.0587 x3 x9 + 0.0948 x4 x9 + 0.1166 x5 x9 +
0.4812 x6 x9 + 0.8421 x7 x9 + 1.8286 x8 x9 >= 100

Bounds
x1 >= 0
x2 >= 0
x3 >= 0
x4 >= 0
x5 >= 0
x6 >= 0
x7 >= 0
x8 >= 0
50 >= x9 >= 0

Generals
x1 x2 x3 x4 x5 x6 x7 x8

End

code
f = 0 0 0 0 0 0 0 0 0;
H = [0 0 0 0 0 0 0 0 0.0129
0 0 0 0 0 0 0 0 0.011
0 0 0 0 0 0 0 0 0.0229
0 0 0 0 0 0 0 0 0.0308
0 0 0 0 0 0 0 0 0.0276
0 0 0 0 0 0 0 0 0.0978
0 0 0 0 0 0 0 0 0.1619
0 0 0 0 0 0 0 0 0.04681
0.0129 0.011 0.0229 0.0308 0.0276 0.0978 0.1619 0.4681 0];

Aineq = 6 7 12 15 15 30 39 107 0';
bineq = 100;

% both Q and r multiply (-1) to reverse >= as <=
l = 0 0 0 0 0 0 0 0 0';
Q = [0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
-0.0478 -0.0357 -0.0587 -0.0948 -0.1166 -0.4812 -0.8421 -1.8286 0];
r = -100;

lb = 0 0 0 0 0 0 0 0 0';
ub = inf inf inf inf inf inf inf inf 50';
ctype = 'IIIIIIIIC';
options = cplexoptimset;

x, fval, exitflag, output = cplexmiqcp (H, f, Aineq, bineq, [ ], [ ],...
l, Q, r, [ ], [ ], [ ], lb, ub, ctype, [ ], options);

[/code]

I am very new to CPLEX, so I have two questions.
(1) Is this kind of problem as mentioned above fit CPLEX?
(2) Why does the code give me the following error and how could I fix it?
??? Error using ==> cplexmiqcp at 782
CPLEX Error 5002: Q in %s is not positive semi-definite.

Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Your problem does not represent convex quadratic inequalities and objective, hence it cannot be solved using CPLEX.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I should add: Since the only nonconvex complication comes from multiplications of integers, and multiplication of integers and a continuous, the model can be linearized to a MILP.

One way to do that is to represent each integer variable as a binary expansion, and then model the binary products, and the continuous-binary products. It leads to a pretty large MILP, and the numerical details are beyond a response here.

The MATLAB Toolbox YALMIP which interfaces CPLEX has some functionality to do it for you automatically, so here is some code. Note that I manually create the binary expansions. To create these, bounds on the integer variables are required, but they are easily derived for your model, since your linear constraint immediately gives upper bounds on all 8 variables. For instance, x1 is bounded by 100/12, i.e., 16. Hence, it can be represented using a binary expansion with 5 binaries. Other variables have lower bounds, but the code below is lazy and uses the same bound for all variables.

The solution fails though, the problem is infeasible. Maybe I copy-pasted something incorrectly from your description.

sdpvar x9 x1 = 2.^(0:4)*binvar(5,1); x2 = 2.^(0:4)*binvar(5,1); x3 = 2.^(0:4)*binvar(5,1); x4 = 2.^(0:4)*binvar(5,1); x5 = 2.^(0:4)*binvar(5,1); x6 = 2.^(0:4)*binvar(5,1); x7 = 2.^(0:4)*binvar(5,1); x8 = 2.^(0:4)*binvar(5,1);   Objective = 0.0258*x1*x9+0.022*x2*x9+0.0458*x3*x9+0.0616*x4*x9+0.0552*x5*x9+0.1956*x6*x9+0.3238*x7*x9+0.9362*x8*x9; Nasty = 0.0478*x1*x9+0.0357*x2*x9+0.0587*x3*x9+0.0948*x4*x9+0.1166*x5*x9+0.4812*x6*x9+0.8421*x7*x9+1.8286*x8*x9; Linear = 6*x1+7*x2+12*x3+15*x4+15*x5+30*x6+39*x7+107*x8<=100; Bounds = [x1 >= 0,x2 >= 0,x3 >= 0,x4 >= 0,x5 >= 0,x6 >= 0,x7 >= 0,x8 >= 0,50 >= x9 >= 0];   [linearObjective,Cuts1] = binmodel(Objective,Bounds); [linearNasty,Cuts2] = binmodel(Nasty,Bounds);   CompleteModel = [Cuts1,Cuts2,Bounds,Linear,linearNasty>=100]; solvesdp(CompleteModel,linearObjective);

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I meant x1 is bounded by 100/6.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, you are right, the problem cannot be solved by CPLEX since the Q is not positive semi-definite.

Thanks very much for providing the alternate solution.

I installed the CPLEX 12.5 in the Matlab 2009; however, I could not find the YALMIP interface in Matlab. So I have no chance to try the method by myself. Do I need to install something else to get the YALMIP?

The only concern to me in your code is

<
Nasty = 0.0478*x1*x9+0.0357*x2*x9+0.0587*x3*x9+0.0948*x4*x9+0.1166*x5*x9+0.4812*x6*x9+0.8421*x7*x9+1.8286*x8*x9;
>

The Nasty should >= 100 in my original code. I do not know whether this would affect the final results or not.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I have found the YALMIP in your website, and installed it well.

It is really a useful tool and I saw the paper has been cited over 1000+ times.

However it is hard for me to find an example about how to convert my problem into a MIP problem with YALMIP. Would you please kindly provide the website or manuals which could provide me more detail information? Also, would you also please suggest one or two literature (papers), which give a brief introduction about how to linearize a nonconvex problem to a MIP, to help me basically understand the theory of this conversion method?

Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I am pretty sure that the problem should have an answer. Since if X9 = 50, then I could solve the problem with CPLEX and get the answer as

x1 = 2 and x6 = 1 with Obj = 34.814
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

No, the solution x1=2, x6=1, x9=50 is not a feasible solution with objective 38. Check it!

x = [2 0 0 0 0 1 0 0 50]
'; 0.5*x
'*H*x

Far from 38 (and the solution does not satisfy the constraint)

The term Nasty is constrained in my model. It is initially defined as a nonlinear expression, linearized, and then the constraint linearNasty>=0 is used.

To see that the problem remains infeasible when x9 is fixed

x9 = 50; intvar x1 x2 x3 x4 x5 x6 x7 x8 Objective = 0.0258*x1*x9+0.022*x2*x9+0.0458*x3*x9+0.0616*x4*x9+0.0552*x5*x9+0.1956*x6*x9+0.3238*x7*x9+0.9362*x8*x9; notNasty = 0.0478*x1*x9+0.0357*x2*x9+0.0587*x3*x9+0.0948*x4*x9+0.1166*x5*x9+0.4812*x6*x9+0.8421*x7*x9+1.8286*x8*x9; Linear = 6*x1+7*x2+12*x3+15*x4+15*x5+30*x6+39*x7+107*x8<=100; Bounds = [x1 >= 0,x2 >= 0,x3 >= 0,x4 >= 0,x5 >= 0,x6 >= 0,x7 >= 0,x8 >= 0]; solvesdp([Linear, notNasty >= 100, Bounds],Objective)

You probably have a typo in some numerical value. Check them again and compare with what you have reported here (and I have copied from you)

The largest possible value the quadratic term can be constrained by from below when x9 is fixed to 50 is 92.4, which you can compute as follows

x9 = 50; sdpvar t intvar x1 x2 x3 x4 x5 x6 x7 x8 Objective = 0.0258*x1*x9+0.022*x2*x9+0.0458*x3*x9+0.0616*x4*x9+0.0552*x5*x9+0.1956*x6*x9+0.3238*x7*x9+0.9362*x8*x9; notNasty = 0.0478*x1*x9+0.0357*x2*x9+0.0587*x3*x9+0.0948*x4*x9+0.1166*x5*x9+0.4812*x6*x9+0.8421*x7*x9+1.8286*x8*x9; Linear = 6*x1+7*x2+12*x3+15*x4+15*x5+30*x6+39*x7+107*x8<=100; Bounds = [x1 >= 0,x2 >= 0,x3 >= 0,x4 >= 0,x5 >= 0,x6 >= 0,x7 >= 0,x8 >= 0]; solvesdp([Linear, notNasty >= t, Bounds],-t)

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, you are right. The x1=2, x6=1 and obj = 34.816 is for the following objective with x9 = 177

Obj = 0.0222 x1 x9 + 0.0189 x2 x9 + 0.0408 x3 x9 + 0.0532 x4 x9 + 0.0461 x5 x9 + 0.1523 x6 x9 + 0.2557 x7 x9 + 0.7721 x8 x9
A more general formulation is with bounds as 177 >= x9 >= 0

Would you talk about more how to use YALMIP to convert my problem and why dose it work?

Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Basically, after modelling each integer as a sum of binaries, everything boils down to multiplications of binaries. Hence, your question is: How can I write multipölication of two binary variables as a linear operator.

Consider binaries x and y, and the product x*y. Replace each x*y with a new binary variables z. Now you simply have to add constraints such that z = x*y

Clearly

z <= x
z <= y

must be added. If either x or y is zero, then the product is zero, thus z must be zero. Now add

z >= x+y-1

This completes the model. Right!

Now do this for all binary products. You get a large list of new variables and constraints, but everything is linear. You don't want to do this manually, hence YALMIP helps you with that.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks very much for your clarification.

Would you please tell me what is the name of this conversion theory if there is one? And would you also please recommend a paper or two which discuss this topic?

I am also wondering how to use YALMIP to convert the problem, what commands should I use?

Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The reformulation is so basic that I don't know any particular name or so. It is a standard linearization procedure.

To do it in YALMIP, you do exactly as I wrote above, i.e., binmodel performs this.
#CPLEXOptimizers
#DecisionOptimization