1
2

Hi all,

Take the non-linear inequality:

z >= C + Axy

where z is continuous, C contains a bunch of linear stuff, A is a real variable, and x and y are binary variables.

I've been having headaches over how to linearize this for a few days, or at least to prove it is not possible. Any input is appreciated.

asked 30 Nov '13, 19:25

LC%20Coelho's gravatar image

LC Coelho
8816
accept rate: 100%


First, replace the \(xy\) term with a new variable \( w:=xy\) using this idea. Then you can replace the term \(Aw \), e.g., using this idea, assuming that \(A\) is bounded.

link

answered 30 Nov '13, 20:39

Austin%20Buchanan's gravatar image

Austin Buchanan
1.3k313
accept rate: 42%

edited 30 Nov '13, 20:40

This does not work because one assumes that the original constraint is an equality. In my case, it is a >=.

(30 Nov '13, 20:42) LC Coelho
2

It should work. Let your constraint be z>=C+v where you enforce v=Aw as the second link suggests.

(30 Nov '13, 20:46) Austin Buchanan

I'll give it another try tomorrow morning and I'll come back here later. Thanks Austin.

(30 Nov '13, 21:43) LC Coelho
1

@LC Coelho: If you follow your own advice, things should go just fine ;-) [...depending on how you define \(z\) – if it's a continuous variable, then an additional \(z \geq 0\) – as in the formulation suggested by @Austin – is required.]

(01 Dec '13, 05:23) fbahr ♦

Thanks Austin and Fbahr, you were both right. I was trying to rewrite everything at once. By adding several steps and intermediate variables those tips really work.

(01 Dec '13, 22:57) LC Coelho
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:

×231
×79
×65
×16

Asked: 30 Nov '13, 19:25

Seen: 4,770 times

Last updated: 01 Dec '13, 22:57

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