MINP

[Alireza]

Dear Professor

I have a question about MINP problem. Please give me direction. Thank you very much.

In the NLP problem we can approximate the problem with some piece-wise linear cost functions and solve the problem with integer programming.

My question is that :

is this possible to approximate the Mixed-Integer Nonlinear cost function to some Mixed-Integer Piece-wise linear cost functions?

Please note that the integer variable is just 0 or 1

Best Regards

[Johan Löfberg]

of course, if you can approximate somethign using a pwa, that pwa can be used anyware

however, if you have a function described by a pwa, and the function involves an integer variable, you can just as well enumerate the possible function values

[Alireza]

Thank you very much johan

I have a another question about this.

How can obtain the piece-wise linear optimization formulation of a convex QP problem?

Best

Alireza

[Johan Löfberg]

Why would you even want that. Convex (MI)QP is essentially as simple as (MI)LP

Otherwise, x'*Qx is written as e'*e where e is a new variable satisfying e == R*x where R is a factor of Q. Now you have  sum of univariate quadratic terms which you can approximate one by one.

[Alireza]

thank you so much.

excuse me. What factorization do you propose ?

Best

[Johan Löfberg]

cholesky, svd-based, symmetric square-root or just what ever such that Q=R'*R

[Alireza]

Thank you very much professor.

As a last question would you please tell me where can I find an example which do the piece wise linearization and obtained new optimization form?

Best Regards

[Johan Löfberg]

https://yalmip.github.io/command/interp1/

https://yalmip.github.io/command/sos2/

[Alireza]

Dear Johan 

About what you said :  x'*Qx is written as e'*e where e is a new variable satisfying e == R*x where R is a factor of Q. Now you have  sum of univariate quadratic terms which you can approximate one by one.

What should I do to the binary variables in the MIQP problem?

Please consider the problem is :

X'QX + f'X

AX <= b

where X contains binary(x_1) and continuous(x_2) variables and Q is diagonal matrix. and f is [ 1 1]'

the cost function becomes: x_1^2 + x_2^2 + x_1 + x_2

now how can I do the approximation for the binary variable x_1^2?

Best Regards

[Johan Löfberg]

1. Again, why  do you want to approximate a convex quadratic objective. It's a MIQP, essentially as easy/hard as a MILP

2. If Q already is diagonal, it makes no sense to introduce a decomposition, as you already have a separable function

3. x_1^2 is trivial to rewrite (think!). If you want to do create a pwa approximation of f(x_2) = x_2^2, I already gave you the link 

[Alireza]

Dear Johan

1. Again, why  do you want to approximate a convex quadratic objective. It's a MIQP, essentially as easy/hard as a MILP

I want to do this since the MILP can solve FASTER than MIQP that is the motivation. Would you please introduce me what to do to solve the MIQP problem faster using interior point method and Branch and Bound algorithm? 

2. If Q already is diagonal, it makes no sense to introduce a decomposition, as you already have a separable function

I mean after Q factorization and obtaining the diagonal form

3. x_1^2 is trivial to rewrite (think!). If you want to do create a pwa approximation of f(x_2) = x_2^2, I already gave you the link 

I know how to rewrite the x_1^2 in the PWA form but my question is that: since x_1 is a binary variable is the method the same as the continuous variable?

Thank you VERY much 

Best Regards

[Johan Löfberg]

All main MILP solvers (cplex/gurobi/mosek/press) have MIQP solvers. Going from MILP to convex MIQP is a very small step, essentially same algorithms.

You notation is not consistent with our previously defined notation. If you original objective is x'*Q*x + f'*x where Q is unstructured, then you factorize and write as e'*e + f'*x with added constraint e = R*x. Now you have a sum of univariate quadratic function f(e_i) = e_i^2, and you apply pwa approximation on each of these.

But again, if x_1 is binary and you actually have the single term x_1^2 it makes no sense to use a pwa-approximation to model x_1^2 (well, it does but it's a trivially exact approximation)

[Alireza]

Dear Johan
Many thanks for the answers
But

I am trying to solve the MIQP problem in mpc and with embedded solvers. Therefore I need to solve the problem my self and I cant use the solvers such as CPLEX. this is the reason why I want to transform the MIQP to MILP.

The example which I write before is the sample and my main problem has a lot of binary variables. Do you suggest to do the approximation on the MIQP problem or on the relaxed QP problem in branch and bound algorithm?
Best Regards

[Johan Löfberg]

What I am saying is that if you have purely univariate quadratic terms of binary variables, you don't have to do any approximation (what is the relation between x and x^2 for a binary variable...)

(If you can write a MILP solver in an embedded language, you can write a MIQP solver)

[Alireza]

So without approximation how can transform the MIQP into MILP? Should I use x(binary) instead of x^2?
Thank you very much

[Johan Löfberg]

Not generally, but purely binary quadratic terms x^2 are trivially replaced with x

Generally, the factorization approach followed by sos2-based approximation of every term is what you'll have to do

[Alireza]

Thank you so much Johan

In general how much is the MILP solvers faster than MIQP solvers?

or clearly

is solving  MILP obtained from MIQP by approximation faster than original MIQP problem at all?

Best Regards and Many thanks