I have an equality constraint like z(Ax-y)=0, where z>=0 ,and x is binary variable, and y is bounded variable Lx<=y<=Ux. How can it be linearized? Thanks in advance.

asked 07 Jul '15, 16:58

zun's gravatar image

zun
111
accept rate: 0%


If \(y_1\),\(y_2\) are binary and \(M\) is enough big then linear constraints are as follows.

\[\begin{cases} & -M\cdot y_1 & \leq z &\leq M\cdot y_1 \\ & -M\cdot y_2 & \leq A\cdot x - y &\leq M\cdot y_2 \\ & y_1+y_2 & \leq 1 & \end{cases}\]

link

answered 09 Jul '15, 03:08

Slavko's gravatar image

Slavko
20515
accept rate: 12%

edited 09 Jul '15, 03:10

That helps a great deal. Thanks for the answer.

(13 Jul '15, 16:36) zun
1

You welcome! So please accept my answer :-) .

(13 Jul '15, 17:25) Slavko

We create constraints that exlude the possibility that both are non-zero. We have two cases, x=0 or x=1.

If z is bounded by M it can be done by adding the constraint

z<=M(1-x)

If x=0 then we have no requirements on z, and as x=0 imply L0<=y<=U0 i.e. 0<=y<=0 and y=0, so Ax-y=0 and hence z(Ax-y)=0.

If x=1 we obtain z<=M(1-1)=0 so z=0 as we had z>=0. This also implies z(Ax-y)=0.

So if the constraint is included the equality constraint is satisfied.

link

answered 12 Aug '15, 07:22

RuneR's gravatar image

RuneR
192
accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×65
×37
×6
×6
×4

Asked: 07 Jul '15, 16:58

Seen: 895 times

Last updated: 12 Aug '15, 07:22

OR-Exchange! Your site for questions, answers, and announcements about operations research.