Reformulate quadratic program to linear program

3 次查看（过去 30 天）

显示更早的评论

Kernel7364 2019-4-25

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/458527-reformulate-quadratic-program-to-linear-program

评论： Kernel7364 2019-4-28

采纳的回答： Matt J

I have a quadratic program:

minimize

want to have a linear program by substitution:

and after substitution I have the following constraints:

are binary integer values (just 0 or 1) and also my

should be binary as well.

I have no idea how to implement the new constraints.

Best regards !

采纳的回答

Matt J 2019-4-25

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/458527-reformulate-quadratic-program-to-linear-program#answer_372282

编辑：Matt J 2019-4-25

在 MATLAB Online 中打开

Organize x into an N-vector X=x(:) and organize q into an NxN matrix Q=reshape(q,[N,N]).

X=optimvar('X',[N,1],'Type','integer','LowerBound',0,'UpperBound',1);
Q=optimvar('Q',[N,N],'Type','integer','LowerBound',0,'UpperBound',1);

Now you can use the problem-based approach, expressing the constraints as follows:

    e=ones(N,1);
Constraint1= Q<=e*X.';
Constraint2= Q<=X*e.';
Constraint3= Q>=e*X.'+X*e.' - 1;

18 个评论
显示 16更早的评论隐藏 16更早的评论

Kernel7364 2019-4-25

在 MATLAB Online 中打开

Hey Matt,

thanks again for your help. It seems like you will rescue me today, but I am an absolut beginner in matlab and I always get some errors. That is my code:

Y = [7,3,10;5,0,12;10,6,1];
T= [0,2,4,6;2,0,3,5;4,3,0,7;6,5,7,0];
prob = optimproblem('ObjectiveSense','minimize')
X=optimvar('X',[size(Y,1)*size(T,1),1],'Type','integer','LowerBound',0,'UpperBound',1);
Q=optimvar('Q',[size(Y,1)*size(T,1),size(Y,1)*size(T,1)],'Type','integer','LowerBound',0,'UpperBound',1);
prob.Objective = X*M*X'
    e=ones(size(Y,1)*size(T,1),1);
prob.Constraints1= Q <= e*X.';
prob.Constraints2= Q <= X*e.';
prob.Constraints3= Q >= e*X.'+X*e.' - 1;
prob.Constraints4= A*X <= b;
prob.Constraints5= Aeq*X==beq;
sol = solve(prob)

But I always get this error

prob = 
  OptimizationProblem with properties:
       Description: ''
    ObjectiveSense: 'minimize'
         Variables: [0×0 struct] containing 0 OptimizationVariables
         Objective: [0×0 OptimizationExpression]
       Constraints: [0×0 struct] containing 0 OptimizationConstraints
  No problem defined.
Error using optim.internal.problemdef.MatrixOperator
Incorrect dimensions for matrix multiplication. Check that the number of columns in the first matrix matches the
number of rows in the second matrix. To perform elementwise multiplication, use '.*'.
Error in optim.internal.problemdef.Mtimes
Error in *
Error in Untitled3 (line 10)
prob.Objective = X*M*X'
 

I tried to use your tipps and the tipps from the link you gave me, but I dont get it.

Best regards !

Kernel7364 2019-4-25

在 MATLAB Online 中打开

I cant belive it, it is working !!!

Thank you very much !!

LP:                Optimal objective value is 0.000000.                                             
Cut Generation:    Applied 2 strong CG cuts,                                                        
                   and 2 zero-half cuts.                                                            
                   Lower bound is 0.000000.                                                         
Heuristics:        Found 1 solution using diving.                                                   
                   Upper bound is 150.000000.                                                       
                   Relative gap is 99.34%.                                                         
Heuristics:        Found 1 solution using rss.                                                      
                   Upper bound is 148.000000.                                                       
                   Relative gap is 99.33%.                                                         
Cut Generation:    Applied 42 implication cuts.                                                     
                   Lower bound is 126.000000.                                                       
                   Relative gap is 0.00%.                                                          
Optimal solution found.
Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value,
options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).
sol = 
  struct with fields:
    Q: [12×12 double]
    X: [12×1 double]

But why does it said that the Optimal objective value is 0.000000 ????

The solution is 126 and that what it also said. I also get the right vector X in sol. Everything is perfectly working.

And hopefully my last question: Why do I dont have to define

??????

Matt J 2019-4-28

编辑：Matt J 2019-4-28

What do you mean, "don't know"? I gave you 3 pieces of advice...

Kernel7364 2019-4-28

Sorry for the missunderstanding.

Your advice for the wrong solution makes sense and this helped me. After around 15 minutes the solver finished and the exitflag was -6 at first so I knew that there was a problem with it.

I am trying to find a way how to tell matlab that he please has to use CPLEX for my problem and not the solver in matlab itself. I just want a command for this but I am still looking. I know how to do it if I have a linear problem, then I have to call

cplexlp(f,A,b,Aeq,beq,lb,ub)

And Matlab uses cplex. But when i use the solve() function, I dont know how to tell matlab to solve it with Cplex.

请先登录，再进行评论。