Hi all, I am trying to linearize Xy where X is binary variable and y is a semi-continuous variable. whenever X=0, M<=y<=2M (M is big M), if X=1 then 1<=y<=5. any hint to help me to linearize X*y would be appreciated.

Thank you Hesam

asked 22 Feb '13, 15:22

hesameivazy's gravatar image

hesameivazy
712
accept rate: 0%

1

If you want y between either 1 and 5 or M and 2M, depending on x, then y is not semicontinuous. A semicontinuous variable is either 0 or falls within a specified range (such as [1, 5]). So which do you mean?

(23 Feb '13, 16:23) Paul Rubin ♦

Another question: What is y representing and why does it make sense to have y between two effectively arbitrary large values in the one case? (I have to say, that sounds like the sort of logic puzzle that might come up in a homework problem on logical conditions in mixed integer programming class.)

(24 Feb '13, 17:29) Matthew Salt... ♦

Hi Paul, sorry I used a wrong term for y. y is not a semi-continuous variable, it is between either 1 and 5 or M and 2M, depending on x.

(25 Feb '13, 00:41) hesameivazy

@ Matthew Saltzman: X represents a binary variable deciding to/not to select an activity in a resource constrained project scheduling problem. y is the start time of one activity. If X=0, then y should be very large (it means that the activity would start at very much far from now, then no resource would be used by this activity in the project life time). that's why y is between M and 2M. Right now I think I have already linearized Xy. This is not a homework or part of a homework, it is part of my research to formulate an underground mine scheduling problem.

(25 Feb '13, 00:51) hesameivazy
1

Thanks for clarifying. It does seem that simply y >= M would serve the purpose of the first constraint, with any upper bound being arbitrary.

(25 Feb '13, 08:52) Matthew Salt... ♦

@ Matthew Saltzman: No problem. Yes any arbitrary upper bound more than M would work.

(25 Feb '13, 09:31) hesameivazy
showing 5 of 6 show 1 more comments

\(1 + (M-1)(1-x)\le y \le 5 + (2M-5)(1-x)\)

link

answered 25 Feb '13, 08:40

Paul%20Rubin's gravatar image

Paul Rubin ♦
10.5k412
accept rate: 17%

1

Or just 1 + M(1-x) <= y <= 5 + 2M(1-x) as M is arbitrary.

(25 Feb '13, 08:54) Matthew Salt... ♦
1

True. I decided to give the overly precise answer in case someone else stumbled on this and had a less arbitrary alternative interval in mind. Plus, this "M-1, M, what the heck" attitude is how we get such large budget deficits. :-)

(25 Feb '13, 08:58) Paul Rubin ♦

I write here what I have, I am not pretty sure if it is true, but it may give some idea to other people:

define WP=X*y.

Upper bound and lower bound of y are as follows:

UPPER BOUND =U= 2M(1-X)+5X
LOWER BOUND =L= M(1-X)+1X

Now:

X*[M(1-X)+1*X]≤WP≤X*[2M(1-X)+5*X]
y-(1-X)*[2M(1-X)+5X]≤WP≤y-(1-X)*[M(1-X)+1.X]

Since (1-X)*(1-X)=(1-X), (1-X)*X=0, and X*X=X, then above two equations are rearranged as follows:

1.X≤WP≤5.X
y-2M.(1-X)≤WP≤y-M.(1-X) (∀i=1…N)

(25 Feb '13, 09:47) hesameivazy
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:

×96
×40
×5

Asked: 22 Feb '13, 15:22

Seen: 758 times

Last updated: 25 Feb '13, 13:55

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