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.

192 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. 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
  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
    2. Thanks alot sir Paul Rubin

      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
  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
  59. Hi Paul,

    Many thanks for your post. I tried it with my model, however, it shows the "c0000005 EXCEPTION_ACCESS_VIOLATION" error.

    Do you have any clue what was wrong please?

    My relevant code as attached:

    forall(i in bType, e in legs, k in days, v in speeds)
    bulktotalprice[i][e][k][v]<=10000*sailingspeed[i][e][v];
    forall(i in bType, e in legs, k in days, v in speeds)
    bulktotalprice[i][e][k][v]>=0*sailingspeed[i][e][v];
    forall(i in bType, e in legs, k in days, v in speeds)
    bulktotalprice[i][e][k][v]>=ny[i][e][k]-10000*(1-sailingspeed[i][e][v]);
    forall(i in bType, e in legs, k in days, v in speeds)
    bulktotalprice[i][e][k][v]<=ny[i][e][k]-0*(1-sailingspeed[i][e][v]);

    bulktotalprice[i][e][k][v] is z, ny[i][e][k] is y and sailingspeed[i][e][v] is x. ny is an integer variable while sailingspeed is binary.

    The relevant expression in the constraint and objective function is:
    pen*(sum(i in bType, e in legs, j in (30*k-29 .. 30*k), v in speeds) bulktotalprice[i][e][maxl(0,j-db[i][e])][v]*conm[i][v]*dbm[i][e][v]);

    Many thanks!

    ReplyDelete
    Replies
    1. I can't say for sure, but my guess is that your c0000005 contains some combination of index values that result in either an index out of bounds or the program trying to access a variable that was never defined/initialized.

      Delete
    2. Dear Paul,

      Many thanks for your reply. I am currently overseas for a conference thus cannot provide detailed information. I would love to discuss in details upon my return I will consolidate the information I have and make my question clearer.

      Thank you for your valuable time in advance.

      Delete
    3. When you're back, I would suggest taking this to one of the help forums listed in the margin of this post. The comment stream on a blog is an awkward place for an extended discussion.

      Delete
  60. Hi Paul, I am wondering is there any way linearize the following equality constraint?

    z == x*(x-y);

    where, x and y are continuous decision variables.

    ReplyDelete
    Replies
    1. No. See my answer above to a comment from Nov. 25, 2014.

      Delete
  61. Hi Paul,
    I have a constraint as below
    Q = m*cp*t
    where m,t,q are continuous variables. My question is there any way to make above relation linear?
    Moreover, please also comment about two more thoughts, some one suggest me to use McCormick envelopes but this approximation not work well for my case, what do you think? 2nd saying is just my thoughts how about if I transform above constraint as below
    q = z*cp
    and define bounds of z as
    z.lo = m.lo*t.lo
    z.up = m.up*t.up
    and solve model and then recalculate value of t by using excel as
    t = z/t
    what you think about later technique?

    ReplyDelete
  62. First question: No, you cannot linearize that constraint. You can approximate it with piecewise linear constraints, but that's just an approximation, not exact.

    Second question: McCormick envelopes are the most common way to approximate a product like yours. Since they are just an approximation, they're not always useful. If it's not working well in your model, I'm not shocked, but it's still probably the thing I would try first.

    Third question: $t=z/t$ is a bit self-referential; did you mean $t=z/m$? Assuming so, if $t$ appears only in the equation for $Q$, this has a shot, but you could end up with $z/m$ violating one of the bounds on $t$ (if $t$ is bounded). If $t$ appears in other constraints, I don't see how this could work, because your model would be producing one value of $t$ and $t=z/m$ would be producing a different value.

    ReplyDelete
  63. This article was posted by you 7 years before in 2010. I have gone through all previous comments on this and you miraculously replied on every single query.. This is something fabulous commitment from you.
    Coming to my problem, I am working on a problem related to SOC evolution of an storage system, comprising several batteries. Problem involves multiplication of binary and continuous decision variables;
    SOC(t+1) = {SOC(t) + P(t)}*(1-b) + SOC_inc(t+1)*b
    SOC(t) has different limits for different values of "b"
    if b=1 --> SOC_min<=SOC(t)<=SOC_max if b=0 --> SOC_swmin<=SOC(t)<=SOC_swmax and p(t) is constrained as
    0<=p(t)<=P_max(t), similarly SOC_inc also has some upper and lower bounds.
    My worries are 1.is it possible to linearize such constraint which has different limits for different values of binary variable b. (Once again, b is a decision variable). 2. does CPLEX or any other solver has (e.g MOSEK) builtin capability to solve such problem? (I read in one of your previous comments CPLEX don't, but that's very old comment. Also, can you suggest any other solver to be used together with CPLEX in MATLAB to handle such constraint itself).
    3. Also can you help with "Lyapunov Optimization"? I have some questions about it too.. :P
    sorry for too many questions and thanks in advance.

    ReplyDelete
    Replies
    1. 1. Yes. Linearize each term separately. Suppose that we let z = SOC(t) * (1-b). Use the formula in the post (with SOC(t) replacing y and 1-b replacing x). If b = 1 (x = 0), the first two constraints force z = 0 and it does not matter what L and U are (so long as 0 is feasible in the third and fourth constraints). So you will most likely be safe using the bounds on SOC(t) when b = 0.

      2. I can't speak for other solvers, but CPLEX now does have indicator constraints (if ... then ...). In the Java API, look for IloModeler.ifThen().

      3. Sorry, I forgot what very little I knew about Lyapunov optimization some 40 or so years ago (lack of use).

      Delete
    2. Thanks for your reply. I got you point but still some confusion..
      So in that case if CPLEX allows using binary variable in the formulation then my problem should look something like this;
      If b = 0
      then
      SOC(t+1) = SOC(t) + P(t), where:{SOC_min <= SOC(t) <= SOC_max}
      otherwise
      SOC(t+1) = SOC_inc(t+1)
      Does above logic make sense in CPLEX? If yes then how do I include the bellow constraint to the problem;
      SOC_min_SW*b <=SOC(t) <= SOC_max_SW*b this constraint means, b can only be equal to 1, if this constraint is satisfied.
      How does the combination of above if--then.. and this constraint will look like in CPLEX?

      Delete
    3. Sorry I missed a b in the last eq:
      SOC_min_SW*b <=SOC(t)*b <= SOC_max_SW*b

      Delete
    4. Your latest version of the constraint would be "if b = 1 then SOC_min_SW <=SOC(t) <= SOC_max_SW".

      Delete
    5. Thanks for reply! One more last question, how do we define this constraint using "CVX"?

      Delete
    6. Hi Paul!
      I have a query related to linearization of product of continuous and binary variable at different times.

      My original constraint before linearization looks like this;

      for t = 1:T-1
      X(t+1) = X(t) - X(t)*b(t+1)
      end

      In above equation, X(t) is continuous and b(t+1) is binary. So to linearize the product, we let A = X(t)*b(t+1).
      Note that X(t) is the value of continuous variable at time (t) and b(t+1) is the value at time (t+1).
      My question is can we linearize the product of this kind of continuous and binary variables whose values are not of the same time interval?

      Thanks,
      Mohan

      Delete
    7. Yes, the time indices have absolutely nothing to do with whether you can linearize.

      Delete
  64. Dear Rubin,
    I hope you are doing great. Can you please help me in approximating following equation

    A/B = C
    All A,B & C are variables
    Bounds are as follow
    0<=A=<50
    0<=B=<50
    0<=C=<1

    ReplyDelete
    Replies
    1. Sorry, your question is off topic.

      Delete
    2. Hi Paul

      If we remove the variable and the constraints regarding the 'z' variable and add the following constraint

      x*L <= y <= x*U

      and deal with the 'y' variable in the objective function I think we end up with the same solution

      If x = 0 then y = 0 just like your solution where z = 0

      If x = 1 then L <= y <= U just like your solution where z = y and L <= z <= U

      What am I missing?

      Delete
    3. You are missing the product $xy$, which was the starting point for the post. Also, what happens if, in the original model, it is legitimate (perhaps optimal) for $y$ to be nonzero while $x = 0$?

      Delete
    4. Thank you Paul for you response.

      I totaly agree with your second comment.

      Regarding your first comment i want to ask the following. I think the product will be the same in both solutions.

      If x = 0 then y = 0 (in my solution) = x*y = z

      If x = 1 then y = x*y = z
      Am i correct?

      But i understand the reasoning behind your second comment. In my problem i have only the product x*y in the objective function. I think that what you say applies when you want to deal both with the product x*y and y in the objective function.

      Delete
    5. No, I don't assume $y$ and $xy$ both appear in the objective; I don't assume anything. In general, $y$ can appear in the _constraints_ by itself, in which case your approach would make a solution containing $x=0$ and $y=17$ infeasible, when in point of fact it might be feasible in the original problem. Example: $y$ is the cargo volume of a truck, $x$ is an indicator whether the driver is new (1) or not (0), and the objective totals cargoes assigned to new drivers (sums $xy$). Your approach would prevent experienced drivers from carrying cargo.

      Delete
  65. Dear Paul,

    Hope you doing great. I have a question, as per your article, multiplication of continuous and binary variables renders the problem to be quadratic. In my problem, continuous variable is an expression(not decision variable), the binary variable is decision variable. What do we call this kind of problem? Is it still quadratic and non-convex?
    Thanks,
    Mohan

    ReplyDelete
    Replies
    1. If the expression is a linear combination of decision variables, everything here applies. Just distribute multiplication by the binary variable across the expression. Otherwise, it's almost certainly not quadratic. It might or might not be convex, depending on the specifics of the expression.

      Delete
    2. Thank you very much Paul for the reply.
      I got another question, looks similar to what we are discussing here.
      I'm trying to include a constraint in my problem (to be solved by any convex optimization solver, e.g. CPLEX or CVX). Let {a1, a2, a3, ...,an} be a finite set of continuous variables. How to formulate a constraint using "big M" technique, which ensure all of these variables, in the same time interval, take either "positive or zero" or "negative or zero" values.

      sincerely,

      Mohan

      Delete
    3. The connection is rather tenuous, but in any event I answered it in a quick post today: https://orinanobworld.blogspot.com/2018/09/coordinating-variable-signs.html.

      Delete
    4. Thank you very much Paul, that's exactly I was looking for.

      Delete
  66. you saved my life!!!!
    Thank you!!!

    ReplyDelete
  67. Hi Paul, thanks for such a helpful post! Is this always/sometimes/usually better than big-m? Also, do you know if CPLEX uses this "under-the-hood" when implementing the indicator constraint class?

    ReplyDelete
    Replies
    1. Sorry! This question was sequestered in a moderation queue, and I somehow received no notification about it. To answer your first question, definitely "sometimes" and I suspect "usually" (but I have no empirical evidence to confirm that suspicion). As to the CPLEX indicator constraint, I don't know that they publish the mechanism. My impression is that at least sometimes it's a "big M" implementation, but it's possible that sometimes it is implemented in the branching logic. If done in the branching logic, I have no idea whether they also put in some linearization so that the indicator constraint impacts subproblem bounds. Implementing it purely in the branching logic would not touch the bounds other than in the subtree under the node where that branching occurred.

      Delete
  68. Dear Paul,
    you are explaining the Problem very good. This helps me a lot :)

    But how can I handle the same Problem but a Little Change:
    z <= xy

    Can you help me with that?

    Thanks
    Nico

    ReplyDelete
    Replies
    1. Simple: Keep the first and third constraints (the two $\le$ constraints) and drop the second and fourth constraints (the two $\ge$ constraints).

      Delete
  69. Dear Paul,

    Hopefully, I haven't missed the answer to my question somewhere in the post. My question is related to the case where all variables are continuous.

    I have a non-convex quadratic program of the form (c's are given positive numbers):

    min c_1*x_1 + c_2*x_2*x_4 - c_3*x_3*x_4
    s.t. Ax <= b,
    x >= 0

    Due to the fact that the problem is not convex, I'm not able to solve it with a convex solver. Is there a way to transform the problem (e.g. linearise the objective function) to get a MIP formulation.

    Thanks a lot in advance!
    Dirk

    ReplyDelete
    Replies
    1. I'm not all that familiar with non-convex optimization (I know enough to recognize it when I see it ... and run screaming in the opposite direction), but I don't think there's any way you can discretize the nonconvexity away.

      Delete
    2. Dear Paul, thanks a lot for your answer. It helps me already so far, that it makes sure that I'm not missing out a simple solution. Let's see how I will go with this :)

      Delete
  70. Hello Paul
    you are explaining the problem very good. This helps me a lot so thank you.

    But how can I handle the same Problem but a Little Change:
    Z=x^k(y) for k is a real number

    ReplyDelete
    Replies
    1. If $x$ is binary, $x^k = x$. If $x$ is continuous (and, presumably, $y$ is binary), then you are dealing with a nonlinear inequality constraint, which will make your problem harder to solve. You can still use what I wrote above, but my $y$ is your $x^k$, my $x$ is your $y$, and the bounds $L$ and $U$ apply to $x^k$.

      Delete
  71. Dear Paul Sir,
    Can you please help me?
    I am new to the CPLEX. I want to assign N jobs on M machines so as to maximize overall reliability. I face difficulty in implementing multiplication equation.
    Overall reliability is calculated by following equation:
    Rel = ∏ R(i,k)
    where i=(1 to N) and k=(1 to M)
    and R(i,k) - it is reliability of task i on processor k

    I am using Rel as float objective function which I have to maximize and binary decision variable x(i,k) which is 1 if job i is assigned to machine k, otherwise 0.
    I have some other constraints which take care that no two jobs will overlap on the same machine. I am comfortable in using them. But I am unable to do multiplication in the constraint as,
    R(i,k) * x(i,k) >= Rel; //where i=(1 to N) and k=(1 to M)

    Also, another concern is that if x(i,k) = 0 then it should not make overall reliability as zero.

    Rel and R(i,k) are float in the range of 0 to 1.

    Please help me. Thank you and appreciate your work, dedication for this blog.

    ReplyDelete
    Replies
    1. I'm guessing that the $R_{ik}$ are parameters, not variables, and that what you mean by overall reliability (to be maximized) is the product of those $R_{ik}$ for which $x_{ik} = 1$. In other words, $Rel=\prod_{i,k:x_{ik}=1}R_{ik}$. You can write this as $Rel=\prod_{i,k}R_{ik}^{x_{ik}}$, which looks even less linear but is a step in the right direction. Now take logs: $\log Rel=\sum_{i,k}\left(\log R_{ik}\right)x_{ik}$. Maximizing $\log Rel$ will maximize $Rel$, and you have a linear objective function.

      Delete
  72. Dear Paul,

    Many thanks for your post.

    I will like to ask if there's a way out for this situation. I have two binary variables dividing each other, in this form: x(i,j,k)/y(l,m), where i, j, k and l, m are the respective indices of x and y. I know that if y(l,m) = 0, then the result will be indeterminate, and the result will be x(i,j,k) if y(l,m) = 1. So this is my question: is there a way to linearize this division of binary variables, just as you explained for the multiplication case. Knowing fully well that I don't know the exact value of any of these variables (whether 0 or 1) before solving.

    Thank you Sir.

    ReplyDelete
    Replies
    1. A ratio of binary variables is not something that occurs "naturally" in models, by which I mean that you are probably using the wrong approach to capture whatever you intend. There are three possibilities. If the ratio $z=x/y$ must exist, you need to fix $y$ at 1 and set $z=x$. The second is that $z=x$ when $y=1$ and $z$ is unrestricted when $y=0$, i.e. $y=1\implies z=x$. The third is that you are trying to say $z=x$ when $y=1$ and $z$ is restricted in some other way when $y=0$ (for instance, $z=0$ when $y=0$). So, assuming the first option is not correct, you should look at the constraint $y=1\implies z=x$ and then consider whether you need an additional constraint on $z$ when $y=0$.

      Delete
  73. Hi Paul,

    Thank you for your post!

    My model is a scheduling problem where I am trying to output a weekly promotion calendar which maximizes profit subject to constraints. Each promotion type is represented by a binary variable where 1 indicates that promotion will be run and 0 if not.

    I have constraints which require promotions to be run in a particular order (eg: Promotion A needs to be followed by Promotion B greater than n number of times) and have represented this using the general formulation:

    Introducing indicator variables z(n), which indicate A(n) followed by B(n) where z = 1 => A*B = 1 (i.e. both A and B = 1)


    L < 0 < U
    z <= U*A
    z >= L*A
    z <= B - L*(1-A)
    z >= B - U*(1-A)

    sum(z(n)) >= number of promotions required

    Is there a general way to linearize conditions of length i, where;

    z = 1 => A*B*C...i = 1

    ReplyDelete
    Replies
    1. Yes, you can use an indicator to signal that a sequence of binary variables must all be 1. See "Modeling an On/Off Span" (https://orinanobworld.blogspot.com/2014/04/modeling-onoff-span.html).

      Delete
  74. Thank you Paul.

    If I understand correctly, these constraints will force Promotion A to always be followed by Promotion B and Promotion C?
    I would like to have it such that Promotion A can run standalone. But there will be at least n number of the sequence (Promo A, Promo B, Promo C). Let me know if I am missing something.

    Really appreciate your help.

    ReplyDelete
    Replies
    1. You create a binary indicator variable for each possible starting point of a sequence. If the variable is 1, you'll have a sequence (say, ABC) start there. If the indicator is zero, the solver is free to do something else at that point (such as run A by itself). To force at least a certain number of sequences, you sum the indicators and constrain that sum to be at least the required number of sequences.

      Delete
    2. Thanks Paul. Working on implementing the constraints as you described. Will let you know in case of any further questions.

      Delete
  75. Dear Paul,

    Thank you very much for the post. And your blog is so amazing.

    I am dealing with a an optimization problem, and have a term like:
    x*(A-Bx)*y
    where x is a continuous variable (x is bounded), y is a binary variable, A and B are parameters.

    I would like to ask if there is any way to linearize it?
    And more generally, could we linearize the term f(x)*y where f(x) is a non-linear function of bounded continuous variable x, while y is binary.

    Many thanks.

    ReplyDelete
  76. You're welcome. Thanks for the kind words.

    I'm assuming that $x$ and $y$ are scalar variables. Can you linearize $x(A-Bx)y$? No. You can approximate $x(A-Bx)$ with a piecewise linear function, multiply that by $y$ and linearize, but that is just an approximation.

    Depending on where the expression appears (constraint, objective or both), the sign of $B$, whether you are maximizing or minimizing, and what solver you are using, you may be able to handle the expression without approximation. A full treatment won't fit in a comment, due to the number of cases. You need a solver that handles quadratic inequality constraints. Basically, you split $Ax-Bx^2$ and $y$ using a surrogate variable $z$ and the same sort of inequalities in my post, and then hope that the sign of $B$ and the direction of the key inequalities results in a convex feasible region.

    As far as linearizing $f(x)\cdot y$, we're back to piecewise linear approximations.

    ReplyDelete
    Replies
    1. Thank you for your quick response. I really appreciate your help.

      If you don’t mind, could I ask you one more question? Specifically, the expression only appears in the objective function of a maximizing problem. B is positive, which means that x(A – Bx) is concave (down). Would it be any chance to linearize the expression x(A-Bx)y without approximation?

      Delete
  77. Yes, if your solver allows (convex) quadratic constraints. Maximize a new nonnegative variable $z$ subject to $Bx^2 - Ax + z + M_1 y \le M_1$ and $z \le M_2 y$ with $M_1$ and $M_2$ sufficiently large.

    ReplyDelete
    Replies
    1. That’s so helpful. I will work on it as your suggestions. Thank you very much!

      Delete
  78. Hi Paul,

    Thanks for the post and can I ask a question?
    I have many items with weight C and I want to put them into several boxes a, b, and c. then put the boxes onto different plane A or B. and the plane itself has carrier capacity.
    If I have two binary variable as x and y.
    when x_(1,a)=1 means to allocate item 1 to box a,
    y_(1,A) means to allocate item 1 to flight A.
    Only both x and y are 1, we will put the item into box and onto the plan. (We have to put the items into boxes before shipping with plane)
    x will be either 0 or 1, so is y (0 or 1) as the decision binary variable.
    C as the constants, e.g. weight of the item
    One of the constraints is like,

    C_1 * x_1a * y_1A + C_2 * x_2a * y_2A + .... + C_n * y_na * y_nA <= 800 (here 800 the airplane weight capacity)
    Similarly,
    C_1 * x_1a * y_1B + C_2 * x_2a * y_2B + .... + C_n * y_na * y_nB <= 1000
    How to linearise this one for xy?

    Thanks in advance,
    Tim

    ReplyDelete
    Replies
    1. Introduce a variable $z\in [0,1]$ for the product of $x$ and $y.$ (I'll let you add the subscripts.) add the constraints $z \le x,$, $z \le y$ and $z \ge x + y - 1.$ If either $x$ or $y$ is 0, $z$ has to be 0 thanks to the first two constraints. If they are both 1, $z$ has to be 1 thanks to the third constraint. You can declare $z$ as either a binary or a continuous variable; it works the same either way. Which one leads to faster solution is an empirical question.

      Delete
    2. Thanks a lot! I will work on the constaints with your suggestions. Meanwhile my objective functions are to balance the carrier loads in terms of percentage usage.
      e.g. plane A will carry the total loads as W_A with capacity 800, then the usage is (W_A/800). Plane B carry W_B as the loads with the capacity 1000, then the usage is (W_B/1000), Similarly, Plane C usage is (W_C/600). My aim is to make (W_A/800) = (W_B/1000) = (W_C/600) as close as possible. My thinking is to use the ratio for each of them but that is not linear, or use absolute value for the two each other differences. Is there any simpler methods to define the objective functions? Thanks in advance from Tim.

      Delete
    3. You could minimize the range (maximum usage minus minimum usage). To do that, introduce two new variables (call them x and y) with the constraints that every ration is greater than or equal to x and less than or equal to y, then set the objective to minimize y - x.

      Delete
    4. Thanks Paul, I was working on this. In the original post, I have x_1a to mean a binary variable x for item 1 to be assigned with box a. Also y_1A to mean the binary variable y for item 1 to be assigned onto flight A. For governance purpose, I have to introduce another binary variable p. e.g. p_aA to mean the policy for putting all items with group a onto flight A. where the policy is defined and given, so I can set p_aA = 1 to tell group_a is assigned to flight A, also p_aB=0 as the policy to forbid group_a onto flight B (possibly p_cA = 1 for group_c can be given to flight A also). Then my constraints and objectives can have the product of three binary (C_1 * x_1a * y_1A * p_aA + C_1 * x_1a * y_1C * p_aA + ... <= 800). C_1 * x_1a * y_1C * p_aA, this one is also funny as item 1 is assigned to group_a and a is valid for flight A but item 1 is assigned to flight C. Can you please help on some suggestions? Thanks in advance.

      Delete
    5. I suggest taking this to Operations Research Stack Exchange. There's a link to it in the right margin.

      Delete
    6. Thanks! I have worked out the problems with your hints!

      Delete

Due to intermittent spamming, comments are being moderated. 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 Operations Research Stack Exchange.