Dear All:

I am trying to develop equivalent linear constraints for the following if then condition:

if z=m then x=1, otherwise x=0; where z is an integer variable, x is a binary variables & m is a parameter.

Any suggestion is highly appreciated.

Thanks.

Noor

asked 30 Jan '15, 22:46

noorbuet's gravatar image

noorbuet
112
accept rate: 0%

Thanks all. I need to both maximize and minimize my objective function.

(31 Jan '15, 17:47) noorbuet

Assume that \(L\le z \le U\). Let \(y_1\) and \(y_2\) be new binary variables, and consider the constraints \[z \le (m-1)y_{1}+mx+Uy_{2}\] \[z \ge Ly_{1}+mx+(m+1)y_{2}\] \[x+y_{1}+y_{2} = 1.\] I think that does what was requested.

link

answered 31 Jan '15, 17:11

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k513
accept rate: 19%

edited 31 Jan '15, 17:16

Dear Professor Rubin: In my case, the lower bound for z is 0, and in that case the above set of constraints are not serving the purpose. Could please give more advise on this. Thanks.

(03 Feb '15, 21:18) noorbuet

Update: I have made the followoing changes, and seems working now: z+1<=my1+(m+1)x+Uy2 z+1>=y1+(m+1)x+(m+2)y2 x+y1+y2=1

(03 Feb '15, 23:11) noorbuet
1

Your changes do not allow z to take the value U. If you replace U with (U+1) to fix this, your formulation is equivalent with Paul Rubins answer. I do not see why it would fail if L=0 (or when L < 0).

(04 Feb '15, 08:42) optimizer

It would be great to know if you are going to minimize or maximize \(x\) and \(z\). In any case, you can construct so-called "Big-M" constraints of the form

\(\text{M} (1 - x) \ge z - m\)

\(\text{M} (1 - x) \ge m - z\)

to force x to be zero if z and m are different (M is a large enough number, derived from the constraints of z). These kinds of constraints are usually bad for Branch&X solving methods because the LP relaxation is poor.

link

answered 31 Jan '15, 04:09

JF%20Meier's gravatar image

JF Meier
22329
accept rate: 11%

edited 31 Jan '15, 04:45

fbahr's gravatar image

fbahr ♦
4.6k716

1

It is worth noting that these constraints enforce only one half of the requested implication. Maybe that is all @noorbuet really wanted, but these constraints do allow \(z=m\) with \(x=0\).

(31 Jan '15, 07:46) Rob Pratt

Yes. I hoped that noorbuet would point out the maximizing/minimizing direction to make it easier to provide sensible constraints.

(31 Jan '15, 13:03) JF Meier
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:

×6
×2
×1

Asked: 30 Jan '15, 22:46

Seen: 910 times

Last updated: 04 Feb '15, 08:42

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