I have a quadratic equality constraint as below. \(x\) is a binary variable, \(z,y,w,v\) are real variables, the rest are constants.

\(z = yx - Ayx - Byx - Cyx + Dwx + Evx + Fx + G(1-x)\)

I try to refer to link text to solve the quadratic constraint, but since there are 4 real variables, I need some idea how to linearize the quadratic constraint... Would appreciate any suggestion or new method.

Well, I did something like this... probably introducing three new quadratic equality constraints will be neat?

\( \begin{align} z \leq & \overline{y} x- A\overline{y} x- B\overline{y} x- C\overline{y} x + D\overline{w} x + E\overline{v} x + Fx + G(1-x)\\ z \geq & \underline{y}x- A\underline{y} x- B\underline{y} x- C\underline{y} x + D\underline{w} x + E\underline{v} x + Fx + G(1-x)\\ z \leq & [y-\underline{y}(1-x)]- [A(y-\underline{y}(1-x))]- [B(y-\underline{y}(1-x))]- [C(y-\underline{y}(1-x))]\\ & + [D(w-\underline{w}(1-x))] + [E(v-\underline{v}(1-x))] + Fx + G(1-x)\\ z \geq & [y-\overline{y}(1-x)]- [A(y-\overline{y}(1-x))]- [B(y-\overline{y}(1-x))]- [C(y-\overline{y}(1-x))]\\ & + [D(w-\overline{w}(1-x))] + [E(v-\overline{v}(1-x))] + Fx + G(1-x) \end{align} \)

asked 14 Dec '13, 22:49

twfx's gravatar image

accept rate: 0%

edited 16 Dec '13, 14:02

fbahr's gravatar image

fbahr ♦

Every quadratic term of the constraint at hand consists of exactly one binary and one real(-valued) variable.

As the blog post points out:

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

Hence, you should be able to apply the provided reformulation "as-is".


answered 15 Dec '13, 05:22

fbahr's gravatar image

fbahr ♦
accept rate: 13%

edited 15 Dec '13, 16:23

PS: Start the reformulation by replacing \(yx\), \(wx\), and \(vx\) with real variables \(p,~q,~r\) respectively – which will make your equality constraint linear ...at the cost of introducing three new quadratic equality constraints, though. However, these three new constraints are actually good news, since they have the form \(p=yx,~q=wx,~r=vx\) – and that's where you can plug in the "template" discussed in @Paul Rubin's blog post.

(15 Dec '13, 06:12) fbahr ♦
Your answer
toggle preview

Follow this question

By Email:

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



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



Asked: 14 Dec '13, 22:49

Seen: 3,547 times

Last updated: 16 Dec '13, 14:02

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