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.

## Saturday, October 9, 2010

#### 173 comments:

**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.**

Subscribe to:
Post Comments (Atom)

Really solve my problems. THX!!!

ReplyDeleteGreat! thanks.

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

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

DeleteThanks. It helps solve my problem.

ReplyDeleteso 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.

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

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

DeleteFor 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$.

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

ReplyDeleteRegards

You're welcome.

DeleteRespected Sir

Deletewhat happens if we have a product of an unbounded continuous and a binary variable.

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

ReplyDeleteJust 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.

ReplyDeleteGreat 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?

ReplyDeleteThanks for broadening my understanding

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:

Deletemin {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.

This comment has been removed by a blog administrator.

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

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

thanks

As far as I know, you cannot.

DeleteIf 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.

DeleteThank you very much Paul Rubin. Excellent explanation and helpful.

ReplyDeletehello to you Paul, im impressed with your promtness on replying. can i ask too?

ReplyDeletei 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...

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

ReplyDeleteThe 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.

DeleteHello 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

ReplyDeletesorry just notice small mistake z<=1 and z>=0

DeleteIs 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.

DeleteAt 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.

Hello,

ReplyDeletei 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}

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.

DeleteI want to linearize this constraint:

ReplyDeletec1*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?

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.

DeleteDear Paul,

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

Just change $y$ to $2y$ in what I posted.

DeleteDear Paul,

ReplyDeleteif 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

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.

DeleteDear Paul,

ReplyDeleteThank 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

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.

DeleteI'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.

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

DeleteThis helped me to solve my problem. Thanks!

ReplyDeleteAgain really helpfull!

ReplyDeleteA 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! :)

You could make the following substitutions: \begin{eqnarray*}

Deletey_{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$).

Thanks, this solved my problem!

DeleteDear Paul,

ReplyDeleteI 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

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).

DeleteThank you Paul for your valuable help.

ReplyDeleteI 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!

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)$.

DeleteIf 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)$.

Great!!! Thank you so much Paul.

ReplyDeleteHi Paul, this is exactly what i was looking for. Thank you so much.

ReplyDeleteWould you also happen to have a source to this methodology?

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.)

DeleteThanks Paul for such a fast reply.

DeleteI 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.

Thanks for sharing the Glover citation.

DeleteThis comment has been removed by the author.

ReplyDeleteYour 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.

DeleteIf 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.

HI Paul,

Deletethanks 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?

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.

DeleteOK. Thanks. Managed to solve it. Unfortunately it´s very time consuming.

DeleteHello Paul,

ReplyDeleteRegarding 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.

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".

DeleteIf 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$.

Hello Paul,

ReplyDeleteI'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

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.

DeleteHi Paul and thanks for the solution.

ReplyDeleteThe 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];

}

z[j][c] is added due to your recommendation

DeleteI'm afraid you misunderstood a couple of things:

Delete(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).

This comment has been removed by a blog administrator.

DeleteThis comment has been removed by a blog administrator.

DeleteThat solved my problem. Thank you so much!!

ReplyDeleteDo you have any reference to cite?

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

DeleteThank you so much :)

DeleteThis comment has been removed by the author.

ReplyDeleteThis comment has been removed by a blog administrator.

ReplyDeleteThank you very much Mr. Rubin. This was very helpful to me.

ReplyDeleteIn 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.

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.

DeleteThank 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.

DeleteHi Paul,

ReplyDeletein 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

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).

DeleteOk, 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.

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

Deletez>=C1*rd;

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

Thaks!

Dear Paul.

ReplyDeleteTanks 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!

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).

DeleteIf $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).

Hello Paul,

ReplyDeleteI 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

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.

DeleteSorry,

ReplyDeleteI 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

$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.

DeleteThank 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?

DeleteSorry, 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.)

DeleteDear 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.

ReplyDeleteI know of no way to linearize it without first bounding $y$.

DeleteThanks alot sir Paul Rubin

DeleteThis comment has been removed by a blog administrator.

ReplyDeleteHi 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!!

ReplyDeleteIf $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. ;-)

DeleteGreat. Thanks Paul.

DeleteHi 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 :)

ReplyDeleteAssuming 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.

DeleteThanks a lot! Paul :)

DeleteHi Paul,

ReplyDeleteI 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?

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.

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

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.

DeleteHello Paul,

ReplyDeleteI 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

The right hand side simplifies to something not containing X1.

DeleteHi Paul

ReplyDeletethanks 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

Romas,

DeleteThe 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.

Very good. I much appreciate it, Paul.

DeleteRomas

Hi Paul,

ReplyDeleteI 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

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.

DeleteThis comment has been removed by a blog administrator.

ReplyDeleteThis comment has been removed by the author.

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

DeleteSorry for typo on your name Paul

DeleteReposted

DeleteDear 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;

Dejene,

DeleteYes, 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.

Hi Paul,

ReplyDeleteI 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?

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.

DeleteThank you very much Paul.

DeleteI 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.

ReplyDelete{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];

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.

Deletethank you very much.

DeleteHello Mr. Rubin,

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

Thank you.

Sorry, I have no clue what you are asking.

Deletei have two linear decision variable

ReplyDeletei would like to know how to linearize

x[i][j][n] * y[j][k][n]

to be exact,

ReplyDeletei am solving a mathematical model:

subject to

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

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.

DeleteHi Paul,

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

Thanks

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

DeleteHi Paul,

ReplyDeleteIs 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,

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

DeleteIf 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).

Deleteb_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.

ReplyDeleteIt 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$.

DeleteThis comment has been removed by a blog administrator.

ReplyDeletehello Paul Rubin

ReplyDeletei 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

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

Deletethe 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.

This comment has been removed by a blog administrator.

ReplyDeleteSorry, 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.

DeleteHi Paul,

ReplyDeleteMany 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!

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.

DeleteDear Paul,

DeleteMany 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.

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.

DeleteHi Paul, I am wondering is there any way linearize the following equality constraint?

ReplyDeletez == x*(x-y);

where, x and y are continuous decision variables.

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

DeleteHi Paul,

ReplyDeleteI 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?

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

ReplyDeleteSecond 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.

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.

ReplyDeleteComing 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.

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.

Delete2. 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).

Thanks for your reply. I got you point but still some confusion..

DeleteSo 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?

Sorry I missed a b in the last eq:

DeleteSOC_min_SW*b <=SOC(t)*b <= SOC_max_SW*b

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

DeleteThanks for reply! One more last question, how do we define this constraint using "CVX"?

DeleteI have no idea.

DeleteHi Paul!

DeleteI 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

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

DeleteDear Rubin,

ReplyDeleteI 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

Sorry, your question is off topic.

DeleteHi Paul

DeleteIf 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?

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$?

DeleteThank you Paul for you response.

DeleteI 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.

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.

DeleteDear Paul,

ReplyDeleteHope 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

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.

DeleteThank you very much Paul for the reply.

DeleteI 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

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.

DeleteThank you very much Paul, that's exactly I was looking for.

Deleteyou saved my life!!!!

ReplyDeleteThank you!!!

:-)

DeleteHi 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?

ReplyDeleteSorry! 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.

DeleteDear Paul,

ReplyDeleteyou 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

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

DeleteDear Paul,

ReplyDeleteHopefully, 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

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.

DeleteDear 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 :)

DeleteHello Paul

ReplyDeleteyou 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

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$.

DeleteDear Paul Sir,

ReplyDeleteCan 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.

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