4
1

Dear OR experts!

I am trying to solve an integer optimization problem where the goal and constraints are all linear, except for the following constraints:

if x_i = x_j = 1, then y_i + C <= y_j or y_j + C <= y_i

if x_i = c_i = 1, then z_i <= a

if x_i = d_i = 1, then z_i <= b

where c_i and d_i are binary constants, a and b are real constants, y_i and z_i are a real variables, and \x_i is a binary variables (0 or 1). Also, none of these are negative.

My question is whether there is a trick to express these conditional constraints as linear constraints. For instance, I could remove the "if" part and say replace "if x_i = d_i = 1, then z_i <= b" with the following constraint:

x_i*d_i*z_i <= b

but the problem is that this is no longer linear! (since x_i and y_i are multiplied which are both variables) I feel like there should be a clever way of rewriting these simple conditional equalities as linear constraints. Any advice, tricks, suggestions?

Many thanks in advance!

Sina

asked 11 Oct '12, 23:27

sina's gravatar image

sina
10126
accept rate: 0%

edited 26 Sep '13, 06:16

fbahr's gravatar image

fbahr ♦
4.6k716


Here's one way of writing it:

if x_i = x_j = 1, then y_i + C <= y_j or y_j + C <= y_i:

x_i + x_j - 1 <=  b1
y_i + C - y_j <= (C + 1) * b2
C - y_i <= C * b3
b1 + b2 + b3 <= 2
b1, b2, b3 binary

if x_i = c_i = 1, then z_i <= a:

x_i + c_i - 1 <= b4
z_i - a <= M * (1 - b4)
b4 binary

if x_i = d_i = 1, then z_i <= b:

x_i + d_i - 1 <= b5
z_i - b <= M * (1 - b5)
b5 binary

(explanation below)


1) There is a general method of converting if-then constraints, eg.

if f(x) > 0, then g(x) >= 0

into an equivalent form, such as

f(x) <= My
-g(x) <= M(1-y)
y binary

2) You have an either-or constraint too (a special case of K-out-of-N), which can be expressed in a linear form too. Eg.

either f(x) <= 0
or g(x) <= 0

can be converted into

f(x) <= My
g(x) <= M(1-y)
y binary

3) However, you have nested an either-or, in your if-then constraint, like

if A, then B or C

It'll be better to break it up into:

(not A) or B or C

See also: a quick reference in an earlier thread on integer programming tricks.

link

answered 12 Oct '12, 00:43

yeesian's gravatar image

yeesian
846210
accept rate: 3%

edited 12 Oct '12, 01:03

We have introduced indicator variables in CPLEX for precisely this need.

Using big M approach, as explained by @yeesian is theoretically correct, but it may lead to numerical instability. The trick is to use the smallest possible M in all these additional constraints. It is our experience that keeping the logic form helps as it uses the smallest possible M at the time you need it.

link

answered 12 Oct '12, 01:58

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

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
×65
×21

Asked: 11 Oct '12, 23:27

Seen: 23,882 times

Last updated: 26 Sep '13, 06:16

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