Hi Community,

I am new in this forum and I hope that I can help you as well as you can help me to solve my problems.

I have a quadratic program, where I want to minimize:

\(\displaystyle \sum_{i=1}^n \sum_{j=1}^n x_i x_j a_{i,j} \)

and every \(\displaystyle x_i \in \{0,1\}\)So all in all it is a quadratic problem of the form: minimize

\(\displaystyle x^T*A*x\)

where x is a vector and A a matrix. How can I bring that to a linear problem?

I had one idea to define another variable \(\displaystyle y_{i,j} := x_i * x_j\) and to make some new constraints like

\(\displaystyle y_{i,j} \geq 0 ,\\

y_{i,j} \leq x_i ,\\

y_{i,j} \leq x_j \)

But this is not complete and I have no idea whether this is working.

How can I define a linear problem of a quadratic problem?

Thank you very much for your help.

Best regards

Craig

I am new in this forum and I hope that I can help you as well as you can help me to solve my problems.

I have a quadratic program, where I want to minimize:

\(\displaystyle \sum_{i=1}^n \sum_{j=1}^n x_i x_j a_{i,j} \)

and every \(\displaystyle x_i \in \{0,1\}\)So all in all it is a quadratic problem of the form: minimize

\(\displaystyle x^T*A*x\)

where x is a vector and A a matrix. How can I bring that to a linear problem?

I had one idea to define another variable \(\displaystyle y_{i,j} := x_i * x_j\) and to make some new constraints like

\(\displaystyle y_{i,j} \geq 0 ,\\

y_{i,j} \leq x_i ,\\

y_{i,j} \leq x_j \)

But this is not complete and I have no idea whether this is working.

How can I define a linear problem of a quadratic problem?

Thank you very much for your help.

Best regards

Craig

Last edited by a moderator: