Topic
  • 14 replies
  • Latest Post - ‏2013-02-18T07:48:34Z by SystemAdmin
SystemAdmin
SystemAdmin
7929 Posts

Pinned topic Incorrect l,Q,r with CPLEX in Matlab

‏2013-02-13T07:53:11Z |
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');
Updated on 2013-02-18T07:48:34Z at 2013-02-18T07:48:34Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incorrect l,Q,r with CPLEX in Matlab

    ‏2013-02-13T08:34:51Z  
    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.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incorrect l,Q,r with CPLEX in Matlab

    ‏2013-02-13T08:38:55Z  
    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.
    CPLEX 12.5 + Matlab 2009 are used.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incorrect l,Q,r with CPLEX in Matlab

    ‏2013-02-13T08:56:48Z  
    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.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incorrect l,Q,r with CPLEX in Matlab

    ‏2013-02-14T11:34:39Z  
    Your problem does not represent convex quadratic inequalities and objective, hence it cannot be solved using CPLEX.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incorrect l,Q,r with CPLEX in Matlab

    ‏2013-02-14T12:25:18Z  
    Your problem does not represent convex quadratic inequalities and objective, hence it cannot be solved using CPLEX.
    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);
    
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incorrect l,Q,r with CPLEX in Matlab

    ‏2013-02-14T12:26:10Z  
    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.

    <pre class="jive-pre"> 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); </pre>
    I meant x1 is bounded by 100/6.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incorrect l,Q,r with CPLEX in Matlab

    ‏2013-02-16T00:18:35Z  
    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.

    <pre class="jive-pre"> 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); </pre>
    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.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incorrect l,Q,r with CPLEX in Matlab

    ‏2013-02-16T00:51:51Z  
    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.
    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.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incorrect l,Q,r with CPLEX in Matlab

    ‏2013-02-16T01:05:50Z  
    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.
    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
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incorrect l,Q,r with CPLEX in Matlab

    ‏2013-02-16T08:08:26Z  
    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
    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)
    
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incorrect l,Q,r with CPLEX in Matlab

    ‏2013-02-16T08:27:59Z  
    No, the solution x1=2, x6=1, x9=50 is not a feasible solution with objective 38. Check it!

    <pre class="jive-pre"> x = [2 0 0 0 0 1 0 0 50] '; 0.5*x '*H*x </pre>

    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

    <pre class="jive-pre"> 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) </pre>

    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

    <pre class="jive-pre"> 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) </pre>
    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.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incorrect l,Q,r with CPLEX in Matlab

    ‏2013-02-16T10:02:28Z  
    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.
    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.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incorrect l,Q,r with CPLEX in Matlab

    ‏2013-02-17T08:31:08Z  
    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.
    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.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Incorrect l,Q,r with CPLEX in Matlab

    ‏2013-02-18T07:48:34Z  
    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.
    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.