Expressing conditional constraints as linear constraints

 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 10●1●2●6 accept rate: 0% fbahr ♦ 4.6k●7●16

 5 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. answered 12 Oct '12, 00:43 yeesian 846●2●10 accept rate: 3%
 5 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. answered 12 Oct '12, 01:58 jfpuget 2.5k●3●10 accept rate: 8%
 toggle preview community wiki

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

Asked: 11 Oct '12, 23:27

Seen: 23,882 times

Last updated: 26 Sep '13, 06:16

Related questions

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