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

hesam%20eivazy's gravatar image

hesam eivazy
accept rate: 0%


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) hesam eivazy

@ 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) hesam eivazy

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) hesam eivazy
showing 5 of 6 show 1 more comments

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


answered 25 Feb '13, 08:40

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%


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

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

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:




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

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

(25 Feb '13, 09:47) hesam eivazy
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: 22 Feb '13, 15:22

Seen: 2,783 times

Last updated: 25 Feb '13, 13:55

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