MATLAB: Reformulate quadratic program to linear program

Question

I have a quadratic program:

minimize

want to have a linear program by substitution:

and after substitution I have the following constraints:

,

My 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 !

Answer 1

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;