Originally posted by: Mambo12345

Good morning everyone,

i have a generall question about the transformation from a binary quadratic program to a linear. I know that

transforms the problem, but what exactly is the transformation ?
Is it the standard way:

y_ijkl := x_ik*x_jl with

y_{i,j,k,l}  <=  x_{i,k}, \\
y_{i,j,k,l}  <=  x_{j,l}, \\
y_{i,j,k,l}  >=  x_{i,k} + x_{j,l} - 1

I could not find something to this ? Does anyone have a description or a reference to the procedure of the linearization ?

Best regards and thank you very much !

Hi,

let me show you with OPL and you ll do the same with MATLAB

dvar boolean x;
 dvar boolean y;
 
 dvar boolean xy; // x times y
 
 subject to
 {
 // xy==x * y; // We can write that with CPO but not with CPLEX
 xy<=x;
 xy<=y;
 xy>=x+y-1;
 }

regards

Originally posted by: Mambo12345

Thank you very much for your quick answer !
I think that I did not explain my problem the right way.
When I use
cplex.param.preprocessing.qtolin = 1
Cplex does a linearization.
But what linearization ?
I dont have to do the transformation by my own but I would like to know how the transformation looks like ?
Is there a reference about this transformation ?
I know that the transformation I wrote is a guilty one but there are probably more options to linearize a quadratic program.
I hope that you know what I mean.

Best regards

Originally posted by: BoJensen

Just out of curiosity, what do you mean by a "guilty" constraint ?

Yes, the transformation is basically what you wrote. A new variable is introduced and some constraints are added to make sure that you have yij=xi*xj in any optimal solution. Depending on the sign of xi*xj in the objective some of the constraints you listed can be omitted since they will always be satisfied.

Originally posted by: Mambo12345

Thank you very much !
Do you also have a reference to that ? Any presentation, paper, link where I can show my chef that this is exactly the transformation ?
But it is very good to hear that I know the right transformation now. :)
Many thanks again !

No, sorry, there is no official document that states this is what CPLEX does. But you can always export the presolved model as LP file and look at that file. Then you can see exactly what CPLEX did.