Hello all: I want to implement the following constraint in my linear programing model:

If A=B then C=1

Else C=0

I have been looking around and there are similar problems but nobody has been helpful to address the 'non equal to' condition.

Thank you in advance.

asked 27 Sep '14, 17:45

Chicago's gravatar image

Chicago
335
accept rate: 0%


As I understand the question, you want \(c\) to be binary, and \(c=1\) if and only if \(A=B\).

I will make a couple of assumptions:

  1. There is a (large) positive \(M\) such that \(|A-B|\le M\) for every feasible \( (A,B) \).
  2. There is a (small) positive \(\epsilon\) such that whenever \(A\neq B\), we can assume there is a solution satisfying \( |A-B| \ge \epsilon\).

Here's the formulation:

\[ \begin{align} A &\le B + My - \epsilon z \\ B &\le A + Mz - \epsilon y \\ c+y+z&=1 \\ c,y,z &\in \{0,1\} \end{align} \]

Now, if \(c=1\), then \(y=z=0\). In this case, the constraints reduce to \( A \le B\) and \(B \le A\), so \(A=B\).

Otherwise, \(c=0\). Then \(y+z=1\). There are two cases. In the first case, \(y=1,z=0\). Then the constraints reduce to \(A \le B + M\), which is always satisfied, and \(B \le A-\epsilon\), which implies \(B < A\). In the second case, \(y=0,z=1\). The analysis in this case is similar and implies \(A < B\). So if \(c=0\), then \(A \neq B\).

You can also reduce the number of variables by replacing all occurrences of \(z\) by \(1-c-y\). But, the MIP solver will probably do this anyway.

link

answered 27 Sep '14, 19:46

Austin%20Buchanan's gravatar image

Austin Buchanan
1.3k313
accept rate: 42%

edited 29 Sep '14, 13:09

Thank you so much! This was indeed helpful! Kudos!

(27 Sep '14, 21:55) Chicago

I would suggest the usage of an indicator constraint. I had a similar problem which is when @Florian suggested the usage of an indicator constraint. More information could be found in the cplex docs. You can find the syntax for the appropriate language over there. link text Thanks to Florian

link

answered 16 Oct '14, 05:17

crypto's gravatar image

crypto
6727
accept rate: 0%

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:

×28
×14
×6
×1

Asked: 27 Sep '14, 17:45

Seen: 2,069 times

Last updated: 16 Oct '14, 05:17

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