Hi

I have this constraint in my model; X>=Z*Y, which X and Y are nonegative continues variables. It is appreciated if anybody could help me to express this constraint to linear form. Thanks in advance.

asked 24 Jan '16, 10:01

saeed's gravatar image

saeed
111
accept rate: 0%

retagged 03 Feb '16, 09:54

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26

Any hints on what Z is or shall we just kinda guess?

(24 Jan '16, 13:22) Mike Trick ♦♦

No, there isnot any condition on Z but Z>=0

(24 Jan '16, 13:36) saeed

Let V=Z*Y, then \(X\geq V\).

(24 Jan '16, 16:12) Slavko

There's no exact linearization that I've ever heard of. You can do a piecewise linear approximation, or you can do a McCormick relaxation (which is again an approximation). The latter requires both upper and lower bounds on both Y and Z.

If Z is binary (or at least integer) then you can do an exact linearization, at the cost of a size increase in the model (if Z is general integer).

link

answered 24 Jan '16, 16:21

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

thank you very much

(25 Jan '16, 05:21) saeed

Yes, pwl and McCormick are the first approximations/relaxations to try. Here are a few useful resources for more info on the latter.

  1. https://optimization.mccormick.northwestern.edu/index.php/Main_Page. This is the main page for the Northwestern University Process Optimization Open Textbook. This looks pretty useful in general. Just click on the link to McCormick envelopes (I think the mccormick in the URL refers to the McCormick School of Engineering).
  2. Pierre Bonami's slides from the 2014 ROADEF conference: http://ibm.co/1gtDdlj. Specifically see slide 39.
link

answered 02 Feb '16, 20:54

Ed%20Klotz's gravatar image

Ed Klotz
23623
accept rate: 11%

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

Asked: 24 Jan '16, 10:01

Seen: 705 times

Last updated: 03 Feb '16, 09:54

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