Bilinear terms in equality constraints (non-convex MIQCP) xy=z?

  • 7 June 2019
  • 4 replies
  • 1074 views

Hi, I have a non convex MIQCP problem, where the non convexity is illustrated in bilinear constrains like :
x+yz=u where x,y,z,u are continuous variables, a general form of this topic is modeling or approaching the constraint : "xy=z" neither gurobi or cplex can handle it. I m wondering, should i use a non linear solver (like Baron)or is there a way to linearize the problem or to approach differently with gurobi or cplex ?
Thnaks for your answers.

This topic has been closed for comments

4 replies

Userlevel 4
Badge +4
As far as I know it is not possible to linearize the product of two continuous variables, except for some special cases (see, e.g., Chapter 7.7 in the AIMMS Optimization Modeling Guide). Therefore the only option is to use a nonlinear solver like Baron.
I m sorry Marcel, but i didn't understand the last method in the section 7.7 of the AIMMS optimization Modeling Guide, where we proceed with the transformation : u=x-y , v=x+y what kind of approximation are we using ?
can you explain how it's done please?

As for Baron, do you know how efficient it is? At matter fact, i have a problem where the number of continuous variables can reach 3000, with eventually 1000 complementarity constrains (but i think i can take them off).
Great appreciation for your help,
Saad
Userlevel 5
Badge +2
@sadofly

u=x-y , v=x+y what kind of approximation are we using ?


The approximation has been explained in section 7.6 of the same document. x1x2 has been represented as y1^2 - y^2 and y1^2 is a separable function. See page number 82 for the lambda-formulation
Userlevel 4
Badge +4
There are two approaches mentioned in the last part of Chapter 7.7 for handling a product of two continuous variables, namely

  1. converting into a separable form;
  2. replacing by a single variable.
The first method uses an approximation but I think it will not work very well if the product is used in an equality constraint. The second method is an exact method but only applies in special situations (namely the lower bound of both variables must be nonnegative and one of the variable can only be referenced in products with the other variable (and not in a linear term)).

The number of variables seems quite large for Baron. Can you share your project such that we can check whether there is a way to reformulate of solve it? If so, please add your project to a zip file. You can send it to our support by email if your project contains sensitive information.

Didn't find what you were looking for? Try searching on our documentation pages:

AIMMS Developer & PRO | AIMMS How-To | AIMMS SC Navigator