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 |

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:
if x_i = c_i = 1, then z_i <= a:
if x_i = d_i = 1, then z_i <= b:
(explanation below) 1) There is a general method of converting if-then constraints, eg.
into an equivalent form, such as
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.
can be converted into
3) However, you have nested an either-or, in your if-then constraint, like
It'll be better to break it up into:
See also: a quick reference in an earlier thread on integer programming tricks.
answered
yeesian |

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
jfpuget |