I have two equalities with variables \(X_1, X_2\) and parameters \(a_1, a_2\) both integer:

I) \(X_1 - a_1 = 0\)

II) \(X_2 - a_2 = 0\)

It is not allowed that both are true (true,true), however (true, false), (false,true) and (false,false) are valid. I want to have linear equations to model this logic and came up with:

\(X_1 - a_1 \ge 1 - M^+ \cdot \delta_1^+\)

\(a_1 - X_1 \ge 1 - M^- \cdot \delta_1^-\)

\(X_2 - a_2 \ge 1 - M^+ \cdot \delta_2^+\)

\(a_2 - X_2 \ge 1 - M^- \cdot \delta_2^-\)

\(\delta_1^+ + \delta_1^- + \delta_2^+ + \delta^-_2 \leq 3 \)

The delta variables are binary, the \(M \)'s are sufficiently large. I think it works, however it looks really complicated to me. Do you have better ideas to model this logic, i.e. with less (binary) variables?

Thanks in advance, Alex

asked 12 May '15, 09:46

Alex_K's gravatar image

accept rate: 0%

edited 12 May '15, 09:55

I think you can use something like this:

\(x_1 \geq a_1 - M.\delta_1 \)

\(x_1 \leq a_1 + M.\delta_1 \)

\(x_2 \geq a_2 - M.\delta_2 \)

\(x_2 \leq a_2 + M.\delta_2 \)

\(\delta_1 + \delta_2 \geq 1 \)

Delta variables being binaries.


answered 20 May '15, 18:02

eor's gravatar image

accept rate: 0%

edited 20 May '15, 18:02

I bid even less binaries. The sum of the variables must not equal the sum of the parameters, so let a single binary decide on which side the sum of variables should reside; this can be expressed with "big M" as you already tried.


answered 20 May '15, 18:19

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
accept rate: 16%

Thanks for the answers of the two of you!!!

I think the first logic works just fine. Marco, I had the same idea but I think with this kind of inequality you cut off feasible solutions. For example, assume \(a_1 = 3\) and \(a_2=4\) restricting the sum of the x variables to 7 would also not allow the solution \(x_1=4\), \(x_2=3\). Please correct me if I'm wrong.


answered 21 May '15, 02:18

Alex_K's gravatar image

accept rate: 0%

edited 21 May '15, 02:20

@eor: Thinking a bit more about your idea, I guess the following is still feasible - unfortunately:

\(a_1=3\) , \(a_2=4, x_1=3, x_2=4, M=10, \delta_1 = 1, \delta_2=1 \):

\(3 \geq 3 - M \cdot \delta_1 \Rightarrow 3 \geq -7 \)

\(3 \leq 3 + M \cdot \delta_1 \Rightarrow 3 \leq 13 \)

\(4 \geq 4 - M \cdot \delta_2 \Rightarrow 4 \geq -6\)

\(4 \leq 4 + M \cdot \delta_2 \Rightarrow 4 \leq 14\)


answered 21 May '15, 03:00

Alex_K's gravatar image

accept rate: 0%

edited 21 May '15, 03:05

These constraints only ensure that at the maximum one variable will be assigned to a_x, while the other varible will not be assigned to a_x and is free to take any value (including a_x). I think to ensure that the other variable don't take the value a_x you will need more constraints and binary variables.

(21 May '15, 13:24) eor
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: 12 May '15, 09:46

Seen: 1,139 times

Last updated: 21 May '15, 13:24

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