Hi, as in the previous question (https://www.or-exchange.org/questions/6760/expressing-conditional-constraints-as-linear-constraints) I have to write some conditional constraints as linear. These are my constraints:

  1. if A == k1 then B == k2

  2. if A <= k1 then B <= k2

  3. if (A <= k1 and k2 <= B <= k3) then C >= k4

where A, B and C are integer variables, and k1, k2, k3 and k4 are integer constants.

Could you help me? Thanks in advance.

asked 05 Jun '13, 13:47

tonecho's gravatar image

tonecho
314
accept rate: 0%

edited 05 Jun '13, 13:56

fbahr's gravatar image

fbahr ♦
4.6k716


A good paper has been published on this subject by Plastria (2002).

link

answered 05 Jun '13, 14:05

mrtncou's gravatar image

mrtncou
15319
accept rate: 0%

Austin, the script you postet should help a lot to solve the 3 cases and Martins paper reference helps to get deeper insights.

But let's face one of the cases, case 2 "if A <= k1 then B <= k2" as an example:

Let M1, M2 be two big-M constants (very big numbers), epsilon a very small constant and x a binary variable. Then the binary expression "if A <= k1 then B <= k2" can be described with 2 constraints:

(1): k1 - A + epsilon <= M1*x

(2): B - k2 <= M2*(1-x)

Validation: If k1 >= A, then k1 - A + epsilon > 0 ==> x = 1 to not violate (1).

And if we insert x = 1 in (2): B - k2 <= M2*(1-1) = 0 ==> B <= k2, which was asked.

The other 2 cases can be solved analogous. @tonecho: Good luck and post your solutions.

edit: hint added: a==b <==> a <= b AND a >= b @Paul: Thanks for clearing it up, I missed that the values are integer.

link

answered 05 Jun '13, 16:33

Christian%20Rathjen's gravatar image

Christian Ra...
112
accept rate: 0%

edited 23 Nov '13, 10:01

fbahr's gravatar image

fbahr ♦
4.6k716

1

A, B and C are integer valued (as are the k constants) according to @tonecho, so the epsilon is not really necessary. Either B <= k2 or B >= k2 + 1.

(05 Jun '13, 16:56) Paul Rubin ♦♦

ONE. if A == k1 then B == k2

1a) A - k1 * b11 - M * ( 1-b11 ) <= 0

1b) A - k1 * b11 >= 0

1c) b12 - b11 >= 0

1d) B - k2 * b12 - M * ( 1-b12 ) <= 0

1e) B - k2 * b12 >= 0

b11, b12 are binary variables (restricted to 1/0 values) and should be maximized

M is a constant (very large number)


TWO. if A <= k1 then B <= k2

2a) k1 * b21 + M * ( 1-b21 ) - A >= 0

2b) b22 - b21 >= 0

2c) k2 * b22 + M * ( 1-b22 ) - B >= 0

b21, b22 are binary variables (restricted to 1/0 values) and should be maximized

M is a constant (very large number)


THREE. if (A <= k1 and k2 <= B <= k3) then C >= k4

3a) A - k1 * b30 - M * ( 1-b30 ) <= 0

3b) k2 * b30 - B <= 0

3c) B - k3 * b30 - M * ( 1-b30 ) <= 0

3d) b31 - b30 >= 0

3e) C - k4 * b31 >= 0

b30, b31 are binary variables (restricted to 1/0 values) and should be maximized

M is a constant (very large number)


Regards from Lima, Perú

link

answered 06 Jun '13, 09:14

CAREDURO's gravatar image

CAREDURO
112
accept rate: 0%

edited 06 Jun '13, 15:41

fbahr's gravatar image

fbahr ♦
4.6k716

Thank you!!!

(27 Jun '13, 07:00) tonecho
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:

×231
×71
×21

Asked: 05 Jun '13, 13:47

Seen: 1,853 times

Last updated: 23 Nov '13, 10:01

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