Saturday, October 9, 2010

Binary Variables and Quadratic Terms

Generally speaking, if $x$ and $y$ are variables in a mathematical program, and you want to deal with their product $z=x y$, you will end up having a quadratic problem (which may create problems with convexity if the quadratic terms appear in constraints). There is a special case, though, when at least one of $x$ and $y$ is binary, and when the other variable is bounded. Under those assumptions, the product can be linearized.

Let $x$ be binary and let $L\le y \le U$ where $L$ and $U$ are bounds known in advance. Introduce a new variable $z$. (Programming note: Regardless of whether $y$ is real-valued, integer-valued or binary, $z$ can be treated as real-valued.) Add the following four constraints: \begin{eqnarray*} z & \le & Ux \\ z & \ge & Lx \\ z & \le & y - L(1-x) \\ z & \ge & y - U(1-x). \end{eqnarray*}
Consider first the case $x=0$, which means the product $z = x y$ should be $0$. The first pair of inequalities says $0 \le z \le 0$, forcing $z=0$. The second pair of inequalities says $y-U \le z \le y - L$, and $z=0$ satisfies those inequalities.

Now consider the case $x=1$, so that the product should be $z = y$. The first pair of inequalities becomes $L \le z \le U$, which is satisfied by $z = y$. The second pair says $y \le z \le y$, forcing $z= y$ as desired.

132 comments:

  1. Really solve my problems. THX!!!

    ReplyDelete
  2. how to formulate y=1 whenever z1+z1=2. Z1, Z2, and y are binary variables.

    ReplyDelete
    Replies
    1. Have a look at this earlier post. I think you should be able to work out what you need from it.

      Delete
  3. Thanks. It helps solve my problem.

    ReplyDelete
  4. so it means that if x is either 0 or 1, then z = x*y would be either 0 or between the lower and upper bound of y.

    Am i missing something ? Can you give some practical use-case that make me understand its importance better ?

    ReplyDelete
    Replies
    1. $x=1$ does not just imply that $z$ is between the lower and upper bounds of $y$; it implies that $z=y$.

      For a physical example, suppose that $y$ is the production output of some process and $x$ is an indicator whether that output is loaded on a particular vehicle ($x=1$) or not ($x=0$). It follows that $z=xy$ is the amount loaded on the vehicle. Either $z=0$ or $z=y$.

      Delete
  5. Thanks for this great article Paul! It helped me to model a machine that can be operated in two modes (fast and slow).
    Regards

    ReplyDelete
    Replies
    1. Respected Sir
      what happens if we have a product of an unbounded continuous and a binary variable.

      Delete
  6. Hi Paul. Congratulations! It is an important topic. I have a similar problem: I would like to compute (x_ij )(y_j)=(w_i), such that, i and j are index. Moreover, w, y and w are binary variables. I dont know how to model a sulution similar to your strategy. Can you help-me? Thanks. Cristiano

    ReplyDelete
  7. Just set $U=1$ and $L=0$ in what I posted above. The inequality $Z\ge Lx=0$ becomes vacuous; the three remaining inequalities do what you want.

    ReplyDelete
  8. Great article. I was thinking whether to use cplex.prod() for z = x*y constriant. where x is binary. Probably new version cplex 12.6 handles it as your post?
    Thanks for broadening my understanding

    ReplyDelete
    Replies
    1. Thanks for the kind words. As for CPLEX 12.6, no, I don't think it will do the linearization for you. (Possibly the OPL interpreter will, although I doubt it, but the CPLEX programming APIs won't.) As a test, I coded and tried to solve the following small problem in Java:

      min {z : x*y + z >= 15; 0 <= y <= 10; z >= 0; x = 0 or 1}.

      As I expected, CPLEX crabbed at me that the "Q" matrix in constraint 1 was not positive semi-definite. That would not have happened had CPLEX linearized the constraint.

      Delete
  9. This comment has been removed by a blog administrator.

    ReplyDelete
  10. I have a function Z=(1+A*B)/ C where all A,B,C are continuous variables.

    How can we linearize this. ? 0<=A, 0<=B, 0<=C

    thanks

    ReplyDelete
    Replies
    1. As far as I know, you cannot.

      Delete
    2. If you manage to make one of A, B, C to be binary, i.e., A is binary, then you can achieve a quadratic form with the technique introduced here.

      Delete
  11. Thank you very much Paul Rubin. Excellent explanation and helpful.

    ReplyDelete
  12. hello to you Paul, im impressed with your promtness on replying. can i ask too?
    i have two binary variables x[i,j,k] and z[k]. Im sure the x[i,j,k] should appear in objective function but where should the z[k] be multiplied to x[i,j,k]? in both constraints or only in objective function? or constraints? many thanks...

    ReplyDelete
  13. I already have the linearization added in my constraints...and put z[k] only objective function...this is probably why my z's are zero so the objective function is zero...i must have put it somewhere in one of the constraints...? thanks

    ReplyDelete
    Replies
    1. The answer to your questions depends on your specific model, what x and z represent, etc. If you linearized by substituting a new variable (call it w[i,j,k]) for the product of x[i,j,k] and z[k], and if w appears in the objective, then both x and z are reflected in the objective value. If x incurs costs/generates profits/... and w is not in the objective function, then x probably should be.

      Delete
  14. Hello Paul I'm working on a quite complex model on opl and this article just make my day cause i didn't know what to do. However, i am not sure how i can formulate the last two constraints on my case. I need the product of z=x[jvt]*c[v][t] z and c are positive integers (including 0) x is a binary. So i need z<=1 and z<=0 but I am not sure for the last two tried some formulations on opl but doesn't seem to work. I hope that you can help me with that many thanks in advance

    ReplyDelete
    Replies
    1. sorry just notice small mistake z<=1 and z>=0

      Delete
    2. Is c bounded above by 1? If not, saying z = x*c and z <= 1 is going to force either c to be 0 or 1 or x to be 0.

      At any rate, just follow the recipe in the post, with c taking the place of y. Since y is nonnegative and can be zero, L = 0. You just need to figure out a valid upper bound U for c.

      Delete
  15. Hello,
    i want to linearise this function
    Min  4X1Y1+3X1Y2‐3X2Y2+2X1X2    
    sc.  x1-‐y2+x2y1  ≥  6  
    y1+y2  ≤10
     y1,  y2  ≥0  
    x1,x2  ∈  {0,1}  

    ReplyDelete
    Replies
    1. Since all your products contain at least one binary variable, you can. Introduce a new continuous variable for each product and apply the method described in the post to each of them.

      Delete
  16. I want to linearize this constraint:

    c1*log2(1+p1*h1)+c2*log2(1+p2*h2)<=Mx

    Here, c1 and c2 are binary integer variables, 0<= {p1, p2} <=3, M is a constant (M>0). h1 and h2 are known parameters (h1=10, h2=20); x is an variable.

    how can I linearize this?

    ReplyDelete
    Replies
    1. You cannot (due to the use of logarithms), but you can approximate it. See my post http://orinanobworld.blogspot.com/2014/11/linearize-that.html.

      Delete
  17. Dear Paul,

    If z=2xy, do I need to incorporate then in the formulations? If yes, then how?

    ReplyDelete
    Replies
    1. Just change $y$ to $2y$ in what I posted.

      Delete
  18. Dear Paul,

    if I have a two continuous variables (x1, x2) and I have the cross product of them (x1*x2) in an equality constraint ---> x3 - x1*x2 = 0.0 Can I lineraize (x1*x2) or at least approximate it?

    Thank you

    ReplyDelete
    Replies
    1. No, you cannot linearize it, and in fact it makes your feasible region nonconvex. If $x_1$ and $x_2$ are bounded (on both sides), you can approximate $x_3$ using McCormick envelopes. I'm on the road and don't have access to my bibliographic databases, but if you search "McCormick envelope" you should be able to track down the information, including the original paper (which I think dates back to the 1970s). Whether the approximation is accurate enough for your purposes is an empirical question.

      Delete
  19. Dear Paul,
    Thank you very much for your post; it helps in my current research which may lead to a paper. If it does, how should I credit (cite) the method here? Is it your original technique, and if yes, should I cite this post, or is there any other academic literature that I can cite (asking since books/papers are preferable to cite)?

    A

    ReplyDelete
    Replies
    1. You're quite welcome; glad it helped. Good luck with the paper! Regarding the technique, no, I'm not the source of it. It's been "common knowledge" (among those who know it, often by virtue of seeing it used in a paper) for some time. One reason I blog stuff like this is to get it into Google (and, hopefully, other search engines) so that people who need it can (hopefully) find it.

      I'm not sure what a good reference for this particular linearization would be. It's a special case of what is variously known as a McCormick {envelope | relaxation | linearization}. If you search one of those phrase, you should find McCormick's paper. McCormick's work is integral to global optimization, but my sense is that this specific linearization was in use in MIP models before McCormick's work came out (or at least before it was well known). I might be wrong, though.

      For what its worth, if I do this in a paper, I don't bother to cite it.

      Delete
    2. :-) Okay, thank you very much once again! And the endeavor to post this kind of stuff is awesome; highly appreciated!

      Delete
  20. This helped me to solve my problem. Thanks!

    ReplyDelete
  21. Again really helpfull!

    A question though:

    Say I have z = xPf, where x is binary, P is a binary matrix and f is continuous.

    I could substitute y = Pf and follow your structure (z = xy). Which would lead to a solution in terms of z, x and y.
    But how can I then obtain the solution in terms of f?

    Hope you can help! :)

    ReplyDelete
    Replies
    1. You could make the following substitutions: \begin{eqnarray*}
      y_{i} & = & \sum_{j}P_{ij}f_{j}\\
      z_{i} & = & x_{i}y_{i}\\
      z & = & \sum_{i}z_{i}
      \end{eqnarray*} Linearize each $z_i$ as above. Keep the equation defining $y$ in the model. The solver will provide values for $f$ as well as $x$, $y$ and $z$ (and the surrogate variables for the $z_i$).

      Delete
    2. Thanks, this solved my problem!

      Delete
  22. Dear Paul,

    I encounter the following error " QP Hessian is not positive semi-definite" even though I linearized the objective function. It works fine when I tried a small dataset. But I got this error when I tried a large dataset. What can I do?
    Thanks

    ReplyDelete
    Replies
    1. The fact that you only get the message on larger data sets suggests a bug in your code. Make sure you are assigning meaningful names to all variables and constraints, then run one of the cases where the error occurs and write the model to a .lp file. Open the .lp file in a text editor, make sure you are well supplied with coffee, and look for a product of two variables somewhere (objective or constraints).

      Delete
  23. Thank you Paul for your valuable help.

    I am dealing with a special case where my objective function looks like : ∑_t | ∑_i (x_i*y_i(t)) | with y_i(t) is known for all i and t. x_i is the binary decision variable. The non-linearity is introduced by the absolute value function |.|.

    So here is what I tried:
    New objective: ∑_t (Xplus(t)*Yplus(t)+Xmin(t)*Ymin(t))

    Constraints:
    Delta(t)=∑_i (x_i*y_i(t))
    Yplus(t)-Ymin(t)=Delta(t)
    M*(1-Xmin(t))>=Delta(t)+epsilon
    M*Xplus(t)>=Delta(t)+epsilon
    Xminus(t)+Xplus(t)<=1
    ∑_i x_i=N
    x_i binary

    So basically I tried to split my absolute value function and defined two indicators Xplus and Xmin to capture whether or not the term in the absolute value function is positive.

    But unfortunately I am still having this error: "QP Hessian is not positive semi-definite" with CPLEX 12.6. Paul, is there anything that can help me move forward? Thank you!

    ReplyDelete
    Replies
    1. How to handle this depends on whether you are minimizing or maximizing. Minimizing is the easier case. Introduce new variables $z_t$ and minimize their sum. Add as constraints that $z_t \ge Delta(t)$, $z_t \ge -Delta(t)$.

      If you are maximizing, you also need a new binary variable $w_t$ for each $t$, and you need an a priori upper bound $U_t$ for $|Delta(t)|$. In addition to what I said above, add $z_t \le Delta(t) + U_t w_t$ and $z_t \le -Delta(t) + U_t (1-w_t)$.

      Delete
  24. Great!!! Thank you so much Paul.

    ReplyDelete
  25. Hi Paul, this is exactly what i was looking for. Thank you so much.
    Would you also happen to have a source to this methodology?

    ReplyDelete
    Replies
    1. I think the origins are lost in the mists of time. :-) If you just want to cite a printed publication that explains it, it appears on page 164 of the fourth edition of "Model Building in Mathematical Programming" by H. Paul Williams. (You can never go wrong citing something by an author named Paul.)

      Delete
    2. Thanks Paul for such a fast reply.
      I just checked it. For those interested, it is in page 176 in the 5th edition of "Model Building in Mathematical Programming" by H. Paul Williams.
      I believe it is based on Glover, F. (1975). Improved linear integer programming formulations of nonlinear integer problems. Management Science, 22(4), 455-460.

      Delete
    3. Thanks for sharing the Glover citation.

      Delete
  26. This comment has been removed by the author.

    ReplyDelete
    Replies
    1. Your constraints guarantee that z[p][q] = 0 for all p and q (unless I = 1). Assuming I > 1, at least one of y1[p][1] and y1[p][2] must be zero, and so your second constraint will force z[p][q] <= 0 for one of those two values of i.

      If you are trying to use z to indicate whether p and q are assigned to the same i in PC, you need an additional continuous variable that I'll call w[p][q][i]. Replace z[p][q] with w[p][q][i] in all your constraints. Now enforce 0 <= z[p][q] <= sum(i in PC) w[p][q][i] for all p-q combinations.

      Delete
    2. HI Paul,
      thanks for your response. Sadly it did not work. As I commented the version above is only a part of the model. In the complete model I use 3 different decision variables(y1[p][i],y2[p][j], y3[p][k]). Now z has to indicate for all three chunks if p and q are in the same i in PC or j in FAL or k in CC. Do you have any idea how to model this?

      Delete
    3. Sorry, it's unclear what you are asking. The best advice I can give is to start with the logical condition for which you want z to be an indicator, write it in disjunctive normal form, and then attack each term separately (adding binary variables as needed) and build up to the final expression.

      Delete
    4. OK. Thanks. Managed to solve it. Unfortunately it´s very time consuming.

      Delete
  27. Hello Paul,

    Regarding to your solution, if U and L are introduced as very big constants, have you found problem in the solution? For example, variable x is introduced as a binary number, but in the solution (produced by cplex), it has floating-point value. I do not have any clue for explaining and overcoming the problem. if you have any suggestion, please let me know.
    Thanks you so much.

    ReplyDelete
    Replies
    1. In most solvers, all arithmetic (and hence the value of every variable, including binary variables) is double precision (possibly extended precision with certain settings). The solver has a tolerance parameter for how close a value needs to be to the nearest integer in order for it to qualify as a feasible solution. If the solver tells you that binary variable $x$ is 1, it may in fact be taking the double precision value 0.999...95 (how many nines depends on the tolerance setting), and the solver says "close enough to 1".

      If U and L are very large, they create at least two possible problems. The first is that, since they appear in the constraint coefficient matrix, they can lead to numerical instability (massive rounding errors). The second is that, even in the absence of numerical instability, you can get something like $x=0, \quad z = 27$ because, in actuality, $x=3.2e-7$ (which the solver feels is close enough to zero) but $U$ is so large that $3.2e-7 U$ is bigger than 27.

      So you want to use the smallest (in magnitude) values of $L$ and $U$ that you know to be valid bounds on $y$. If that does not solve the problem, you can try tightening the integrality tolerance parameter of the solver, but this may slow down the solver. CPLEX also has a numerical emphasis setting that tells it to be extra careful with rounding errors (again, at the price of slowing the solver). Those settings may help, but possibly not with grotesquely large $L$ and $U$.

      Delete
  28. Hello Paul,
    I'm doing some modeling using Gurobi, and I encounter a problem when I tried to set a quadratic constraint like this : cx - s*x = b, where is s and x are two continuous variables, and both c and b are constants. The gurobi said there is an error for Q is not psd. Is there any way to linearize (s*x) to make it solvable? Actually i also read your another article "Piecewise-linear Functions in Math Programs ", I also wonder if I can use it to solve my problem by transforming cx-s*x = b to s(x) = b/(c-x) , then use sos 2 to solve it ?

    Thank you !

    Thank you

    ReplyDelete
    Replies
    1. Quadratic equality constraints produce nonconvex feasible regions. You can look up "McCormick linearization" for an approximation to a quadratic term, but I'm not sure it will help much with an equality constraint.

      Delete
  29. Hi Paul and thanks for the solution.
    The problem is I still receive the error says Q is not positive semi-definite.

    int NbCW = ...; //number of central warehouses
    int NbLDC = ...;//number of local distribution centers
    int NbPOD = ...;//number of point of demands
    int NbCom = ...;//number of commodities
    int NbTrMod = ...;//number of transportation modes
    int LDCMAX = ...;//maximum number of ldcs
    int UPD1 = ...;
    int Fixed = ...;//cost for warehouse establishment



    // range CW = 1..NbCW;
    range LDC = 1..NbLDC;
    range POD = 1..NbPOD;
    range Com = 1..NbCom;
    range TrMod = 1..NbTrMod;

    float t[LDC][POD]=...;
    int D[LDC][POD]=...;
    int Sup[LDC][Com]=...;
    float Dem[POD][Com]=...;
    int SGlobal[Com] = ...;//total supply of each commodity
    int DCap[LDC][TrMod] = ...;
    float V[Com] = ...;//unit volume of each commodity
    int CapV[TrMod] = ...;//volume capacity of transportation mode m
    int LCap[LDC][TrMod] = ...;
    float DrvPrice[TrMod] = ...;//driver price $ per km

    float Dev[POD][Com]=...;
    float Priority[Com]=...;

    //variables
    dvar int+ Y[LDC][POD][TrMod];//transportation flow
    dvar boolean loc[LDC];
    dvar int+ UD[POD][Com];
    dvar int+ X[LDC][POD][Com][TrMod];//commodity flow
    dvar boolean supply[LDC][POD];
    dvar float+ z[POD][Com];

    dexpr int DeploymentCost = sum(i in LDC) Fixed * loc[i];
    dexpr float UnsatisfiedDemand = sum(i in LDC, j in POD, c in Com) D[i][j]*supply[i][j]*UD[j][c];

    minimize DeploymentCost + UnsatisfiedDemand;

    subject to {

    forall (m in TrMod, i in LDC, c in Com)
    ct1:
    sum(j in POD) X[i][j][c][m] * supply [i][j] <= Sup[i][c] * loc[i];

    forall (j in POD)
    ct2:
    sum(i in LDC) supply[i][j] == 1;

    forall (i in LDC, j in POD, c in Com)
    ct2a: (1==supply[i][j]) =>
    (sum(m in TrMod) X[i][j][c][m]== Dem[j][c] - UD[j][c]);

    forall (i in LDC, j in POD, c in Com)
    ct2b: (0==supply[i][j]) =>
    (0 == Dem[j][c] - UD[j][c]);

    forall (i in LDC, j in POD, c in Com)
    ct3:
    z[j][c]<= supply[i][j] * Dem[j][c];

    forall (j in POD, c in Com)
    ct4:
    z[j][c] <= UD [j][c];

    forall (i in LDC, j in POD, c in Com)
    ct5:
    UD[j][c] - Dem[j][c]*(1-supply[i][j]) <= z[j][c];

    forall (i in LDC, j in POD )
    ct6:
    supply[i][j] <= loc [i] ;


    forall (j in POD, c in Com)
    ct8:
    UD[j][c]<=Dem[j][c];
    }

    ReplyDelete
    Replies
    1. z[j][c] is added due to your recommendation

      Delete
    2. I'm afraid you misunderstood a couple of things:
      (a) z is intended to _replace_ the product of the binary and continuous variables, so you need to change your definition of UnsatisfiedDemand to contain z;
      (b) since z replaces supply[i][j]*UD[j][c], z should have three dimensions and three indices (i, j, c).

      Delete
    3. This comment has been removed by a blog administrator.

      Delete
    4. This comment has been removed by a blog administrator.

      Delete
  30. That solved my problem. Thank you so much!!

    Do you have any reference to cite?

    ReplyDelete
    Replies
    1. You're welcome. I don't have a specific source, but please see the comment posted 12/16/2014 above (and my response).

      Delete
  31. This comment has been removed by the author.

    ReplyDelete
  32. This comment has been removed by a blog administrator.

    ReplyDelete
  33. Thank you very much Mr. Rubin. This was very helpful to me.

    In my case I have a term: 1-X1.X2 (both X1 and X2 are binary variables) which is a part of a greater multi-objective function, the rest of the parts are linear, but to linearize the mentioned part I consider another binary variable named Y and used the above inequalities as below:

    set X1.X2=Y

    and the following 3 constraints should be added to the problem:
    Y<=X1
    Y<=X2
    Y>=X1+X2-1
    X1,X2,Y = {0 or 1}

    Is that correct? And to solve the problem with LINGO as Y is a binary, the term 0<=Y<=1 is also needed to be mentioned as the 4th constraint or just the above constraints are adequate?

    Thank you in advance for any help you can provide.

    ReplyDelete
    Replies
    1. This looks correct. I have not used LINGO, but chances are $Y$ is either nonnegative by default or you can declare it nonnegative, eliminating the need for $Y\ge 0$ as an explicit constraint. The first two constraints imply $Y\le 1$, so you do not need to specify that explicitly either. For that matter, as long as $X1$ and $X2$ are declared binary, you can make $Y$ a continuous variable; the first three constraints will limit it to the values 0 and 1.

      Delete
    2. Thank you again so much for replying. And also I have to admit that your blog is very helpful to me Mr. Rubin. Thanks a lot.

      Delete
  34. Hi Paul,

    in my case I have to model a non-linear function depending on the value of a float+ variable (rd) and a constant (RD).

    If rd <= RD,
    then f(rd)=C1*rd;
    If rd > RD,
    then f(rd)=C1*RD+C2*(rd-RD)

    where C1 and C2 are also constants. In this case 0 <= rd <= 230 and also one of the objectives of my project is minimize f(rd) (thus I guess that the lower boundary is not so important).

    Any help would be very helpful, thanks in advance.

    Iago

    ReplyDelete
    Replies
    1. This is not the relevant post for you. Your f() is piecewise linear. Type "piecewise" in the search box at the top left of the page and you'll find some potentially more useful posts. Whether you need a binary variable or not will boil down to whether f is convex (C2 > C1) or concave (C2 < C1).

      Delete
    2. Ok, I understand. In my case, C2>C1, so I guess I have a piecewise convex function. At least now I know exactly what I'm looking for. Thank you Paul, I appreciate it.

      Delete
    3. After looking into the post 'Piecewise-linear Functions in Math Programs' I came with the conclusion that my function would be:

      z>=C1*rd;
      z>=C1*RD+C2*(rd-RD);

      Thaks!

      Delete
  35. Dear Paul.
    Tanks for the solution. In my case, there are two binary variables which are x[s,t,k] and y[s,t,k].And my objective function is

    minimize sum([s,t,k]in Route1)(x[s,t,k]*k)*sum([s,t,k]in Route2 )(y[s,t,k]*k)

    I use OPL Cplex.How can I linearize this?
    Thanks!

    ReplyDelete
    Replies
    1. Each product $x_{s,t,k}\cdot y_{s',t',k'}$ can be linearized as described above, introducing a new variable $z_{s,t,k,s',t',k'}$. Your expression then reduces to $$\sum_{(s,t,k)\in \text{Route1}}\sum_{(s',t',k')\in \text{Route2}} (k\cdot k'\cdot z_{s,t,k,s',t',k'})$$(which admittedly is a bit messy).

      If $x$ and $y$ both belong to SOS1 sets (meaning exactly one of the $x$ variables and exactly one of the $y$ variables will take value 1, all others being zero), then there is an alternate linearization where $z$ is indexed by the value of $k\cdot k'$ (so one $z$ variable for each distinct value of that product).

      Delete
  36. Hello Paul,

    I have an expression x^2 * y/z where x,y and z are all binary variables. I was wondering if there is any way to linearize it?

    Thank you!
    Sepid

    ReplyDelete
    Replies
    1. That's easy. The expression is indeterminate if $z = 0$, so $z$ has to be 1. Since $x$ is binary, $x^2=x$, so we're now down to $x*y/1=x*y$, which is covered by the content of this post.

      Delete
  37. Sorry,

    I am revising my above post: I have an expression: x^2 * y/z where x,y are binary variables and z is an integer ( >=0). I was wondering if there is any way to linearize it?

    I have to mention that I already have another expression in my objective function as x* y which I replaced with another binary variable M. Also, z is itself a variable which is equal to the product of x and another integer variable (based on your advice in previous posts).


    Thank you!
    Sepid

    ReplyDelete
    Replies
    1. $x^2=x$ and $xy$, being the product of two binaries, linearizes easily. If $z$ can be 0 when $x=1$, you're screwed. If $z=0\implies x=0$, it can be done, but the only way I know is a bit painful. Enumerate all possible positive values of $z$ (which obviously requires that $z$ be bounded above). Let's call that set $\{\zeta_1,\dots,\zeta_K\}$. Create $K$ binary variables $w_1,\dots,w_K$ in an SOS1 ($\sum_{k=1}^K w_k = 1$). Let $v=xy$. Your expression can now be written $\sum_{k=1}^K (\zeta_k * v * w_k)$, which leaves you with linearizing all the $v * w_k$ terms.

      Delete
    2. Thank you for your response, Paul. I am not quite sure if I understood why you use K binary variables in SOS1. Could you please explain more?

      Delete
    3. Sorry, there was a typo. The last summation should be $\sum_{k=1}^K (1/\zeta_k * v * w_k)$. The $K$ binary variables tell you which value $z$ takes. (You also need a constraint $z=\sum_{k=1}^K \zeta_k * w_k$ to enforce this definition.)

      Delete
  38. Dear all I have z=x*y where x is a binary variable and y is continuous unbounded variable, I know how to linearize it if y is bounded can you help me that how i can linearize it if y is unbounded i.e 0<=y<=infinity.

    ReplyDelete
    Replies
    1. I know of no way to linearize it without first bounding $y$.

      Delete
  39. This comment has been removed by a blog administrator.

    ReplyDelete
  40. Hi Paul. Since we know we could linearize the product of two binaries, I wonder how we can linearize the product of more than two binaries. For example, if we have a constraint gamma <= xyz and x y z are binaries. Should we transform it to the form of gamma <= tz(tx or ty) or gamma <= t. I am more curious about the latter one. Thanks!!

    ReplyDelete
    Replies
    1. If $w=xyz$, the direct linearization would be $w\le x$, $w \le y$, $w \le z$, $w \ge x+y+z-2$. The inequalities you get from a two stage linearization (linearize the product of any two of $x, y, z$, then linearize the product of that product with the third variable) imply the four inequalities of the direct linearization, so the two stage result should be at least as tight as the direct result. Whether it's meaningfully tighter I don't know, but I'm pretty sure the two stage is no worse (and maybe better). That's if I did my algebra correctly, of course. ;-)

      Delete
  41. Hi Paul, if we can linearlize the product of the two variables, can we do that with the sum of product? For example, if we have Zi = sum (Xj*Yij), I am curious how the second pair of constraints that you suggest will look like. Thanks :)

    ReplyDelete
    Replies
    1. Assuming either $X$ or $Y$ is binary (as in https://www.or-exchange.org/questions/14101/formulate-the-non-linear-term-to-a-mixed-integer-linear-programming, which is apparently the same question), you linearize each term separately. Call the new product variables $W_{ij}$ (since you are using $Z_i$ for the summation. Now sum the $W$ variables.

      Delete
  42. Hi Paul,

    I am using CPLEX and receive the not convex answer.

    I have the following problem, where w3[k, m, t] is the binary variable. Vbtm, st, et, O are float variables and Z represents a large number. St and Et are values that are set at another point in the problem forumulation.

    forall(m in M, t in T, k in K)
    vbtm[m, t] - et[k, m, t] >= 0 - Z * w3[k, m, t];

    forall (m in M, t in T, k in K)
    st[k, m, t] - vbtm[m, t] <= Z * w3[k, m, t];

    forall (m in M, t in T, k in K, in Km)
    sum(k in K)(w3[k, m, t] * (et[k, m, t] - st[k, m, t])) * (b [m, t] + CO[m, t]) <= O[m, t];

    Do you have any idea how I could rewrite the following problem in order to solve it properbly?

    ReplyDelete
    Replies
    1. You did not specify the nature of b[] and CO[]. If either is a continuous variable, you cannot linearize the last constraint (the source of the error message). If they are both constants, linearize each term of the sum as explained in this post. If they are both binary (or a mix of a binary variable and a constant), linearize each term in the sum, then linearize the product of the surrogate variable for that term with the b+CO factor.

      If you have further questions, I recommend using one of the "Places to Ask Questions" listed in the right margin of the blog.

      Delete
    2. Thank you Paul. b[] and CO[] are both constants as they are are data known in advance. I will try to linearize the term as described by you. Thank you very much.

      Delete
  43. Hello Paul,
    I am trying to make this linear:

    A >= 1 +(X1 * B/ X1 * C)

    where A, X1 are variables
    X1 is a binary variable. it can be either 0 or 1.
    A is the variable which is the result of the equation.

    Please help me in making this linear

    ReplyDelete
    Replies
    1. The right hand side simplifies to something not containing X1.

      Delete
  44. Hi Paul

    thanks a lot. I found a similar solution on

    http://www.leandro-coelho.com/linearization-product-variables/

    and it looks a bit more cumbersome, i.e. 7 constraints as opposed to your 4. What do you make of it?

    Thanks
    Romas

    ReplyDelete
    Replies
    1. Romas,

      The first pair of inequalities in that section of Leandro's post are redundant but harmless. The upper and lower limits are both constants, so you are just imposing constant bounds on $z$. With most solvers, you can enter those as bounds rather than constraints (so they won't add rows to the constraint matrix). The information in the bounds might possibly make solution a bit more efficient, although I'm a bit doubtful it will help.

      The middle four inequalities are equivalent to what I gave above.

      Leandro's last inequality will be redundant in general. Unfortunately, it is incorrect in one pathological (?) case. Using my notation, if $L < 0 < U$, $|L| > U$, $y < -U$ and $x=0$, Leandro's last inequality will attempt to force $z \le y+U < 0$, which is inconsistent with the remaining inequalities (that force $z=0$). I doubt this case would ever arise in a "real life" problem, but as the last inequality is redundant at best and wrong at worst, it should be dropped.

      Delete
    2. Very good. I much appreciate it, Paul.

      Romas

      Delete
  45. Hi Paul,

    I am trying to make this linear:

    "forall (j in job) 2*z[j]-v[j]>=ss[j]" where z[j]==v[j]*ss[j] (for all j )

    I try to use your method but it doesn't work :'( I already have the same error : CPLEX Error 5002: 'q1' is not convex.
    The variables are difined as follow:
    v[j] is binary (j in 1..n) and ss[j] is a positive integer with a upper bound equal to "n" .

    So, I added those constraints as you explaint it

    forall (j in job) z[j]<= n*v[j];
    forall (j in job) z[j]>=0;
    forall (j in job) z[j]<= ss[j];
    forall (j in job) z[j]>= ss[j]-n*(1-v[j]);

    Coud you help me please ?

    Thank you

    Hanane


    ReplyDelete
    Replies
    1. Assuming that n is declared as a parameter and not as a variable, your constraints look correct to me. So perhaps 'q1' refers to a different part of your model.

      Delete
  46. This comment has been removed by a blog administrator.

    ReplyDelete
  47. This comment has been removed by the author.

    ReplyDelete
    Replies
    1. ... waiting for "Raul" to answer ...

      Delete
    2. Sorry for typo on your name Paul

      Delete
    3. Reposted
      Dear Paul,

      How I may linearize the following with the above concept.

      z=b1d1+...+bndn

      where bi are binary variables and di's are real variables. It is possible to compute upper bound and lower boud for each product.

      To give further explanation on the problem, the di's are line segments to approximate a convex curve. The line segments can be represented by di=mix+c, I want to select one of these line segments based on the value of x which is a function of some decision variable. The selected segment is used to evaluate the value of di which is used in a constraint for my optimization. I approached the problem by introducing a binary variable to select a given segment which is set to 1 when it is selected and set to 0 otherwise. This means I have an expression d=b1d1+...+bndn; b1+b2+..+bn=1;

      Delete
    4. Dejene,

      Yes, you can linearize each product. In this particular case, though, it may not be the most efficient approach. A piecewise linear expression can be expressed as a Type 2 Special Ordered Set (SOS2). See the portion of https://orinanobworld.blogspot.com/2010/10/piecewise-linear-functions-in-math.html devoted to SOS2. Many solvers have explicit SOS2 support, and in fact some (including CPLEX) have explicit support for piecewise linear functions.

      Delete
  48. Hi Paul,

    I have a mixed integer quadratic problem where i need to minimize the following function:

    F(w) = 0.5*w'*H*w - w'f
    s.t. L*v <= abs(w) <= U*v

    v: Nx1 binary variable
    w: Nx1 continuous variable
    L: lower bound
    U: upper bound
    H: NxN positive semidefinite covariance matrix
    f: Nx1 vector of expected returns

    Is there a way to remove the absolute value from the constraint?

    ReplyDelete
    Replies
    1. Yes. If $L=0$, it can be done with additional constraints but no new variables. if $L>0$, you'll need more binary variables (to distinguish between $w_i>0$ and $w_i<0$. See this post: https://orinanobworld.blogspot.com/2012/07/modeling-absolute-values.html.

      Delete
    2. Thank you very much Paul.

      Delete
  49. I have a MILP which has a not convex constraint. But as you said if one decision variable is binary there is no problem. But still this error appears : CPLEX Error 5002: q1 is not convex.

    {int} T= ...;
    {int} J=...;

    int f[T]=...;
    int r[T]=...;
    int d[J][T]=...;


    dvar boolean y[J][T];
    dvar boolean q[T];
    dvar int+ x[J][T];
    dvar int+ z[T0];
    dvar int+ theta[J][T];

    z[0] == 6;

    forall (t in T)
    z[t] == z[t-1] + sum(j in J)(x[j][t] - d[j][t])*y[j][t] - r[t]*q[t] - f[t];

    ReplyDelete
    Replies
    1. The error message is correct. What I said was that the product of a binary variable and a continuous (or general integer) variable can be linearized ... by you. You apparently have not done so. CPLEX will not do it for you.

      Delete
  50. Hello Mr. Rubin,

    Binary to continuous variables? But the constraint to be added must be linear. i.e x² = x or x(x-1)=0 linear.

    Thank you.

    ReplyDelete
    Replies
    1. Sorry, I have no clue what you are asking.

      Delete
  51. i have two linear decision variable
    i would like to know how to linearize
    x[i][j][n] * y[j][k][n]

    ReplyDelete
  52. to be exact,
    i am solving a mathematical model:


    subject to
    y[i][k][n] = x[i][k][n] + sum(x[i][j][n]*y[j][k][n])

    ReplyDelete
    Replies
    1. I don't know what a "linear decision variable" is, but if you mean that $x$ and $y$ are both continuous, then you cannot linearize the expression.

      Delete
  53. Hi Paul,

    If x is integer-valued and y is real-valued how can i deal with their product?

    Thanks

    ReplyDelete
    Replies
    1. https://orinanobworld.blogspot.com/2013/07/integer-variables-and-quadratic-terms.html

      Delete
  54. Hi Paul,
    Is it possible to piece wise linearize the following expression

    (SUM(b_i))^C1+C2*N; i=1,2,..N, b_i's are real numbers

    Thanks,


    ReplyDelete
    Replies
    1. Sorry b_i's are the product of binary and real number.

      Delete
    2. If b_i is the product of a binary variable and a real variable, no, you cannot linearize it. If it is the product of a binary variable and a real constant, then you can linearize for small N (by tabulating all possible values of the sum, which is impractical unless N is fairly small).

      Delete
  55. b_i=a_i*v_i; a_i's are real constants and v_i's are binary decision variables. In addition 0<=(SUM(b_i))^C1 <=1.0. I am thinking to piece-wise linearize the expression z=(SUM(b_i))^C1 using SOS2 and substitute z in the original expression. I don't if that makes sense.

    ReplyDelete
    Replies
    1. It doesn't make sense to me. A single SOS2 produces a piecewise linear function of a single variable. Your expression maps $\{0,1\}^N\rightarrow\Re$.

      Delete
  56. This comment has been removed by a blog administrator.

    ReplyDelete
  57. hello Paul Rubin
    i just want to understand how come a quadratic problem create problems with convexity?? i am totally agree with your solution and i understand it perefctly , but now i just want to figure out what's the relation between convexity and quadratic problem? and when we say that this function is convex and why we forced to linearise this product ?? thank you in advance

    ReplyDelete
    Replies
    1. They don't automatically create problems with convexity; it depends on the specific constraint. $g(x)\le0$ with $g$ convex, or $g(x)\ge0$ with $g$ concave, are fine as far as convexity is concerned. $g(x)\ge0$ with $g$ convex (or $g(x)\le0$ with $g$ concave) means the feasible region \_may\_ be nonconvex. For example, $x^{2}+y^{2}\ge1$ gives
      the exterior (and boundary) of the unit disk, clearly nonconvex.

      $g(x)=0$with $g$ strictly convex (or strictly concave) is always a problem. If $\hat{x}$ and $\tilde{x}$ are both feasible and $x=(\hat{x}+\tilde{x})/2$, strict convexity means $g(x)<(g(\hat{x})+g(\tilde{x}))/2=0$, violating
      the constraint.

      Delete
  58. This comment has been removed by a blog administrator.

    ReplyDelete
    Replies
    1. Sorry, but a blog is no place to be debugging a model (especially when lengthy output is involved). I suggest you post the question on one of the forums listed in the margin.

      Delete

If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on OR-Exchange.