## Monday, May 29, 2017

### If This and That Then Whatever

I was asked a question that reduced to the following: if $x$, $y$ and $z$ are all binary variables, how do we handle (in an integer programming model) the requirement "if $x=1$ and $y=1$ then $z=1$"? In the absence of any constraints on $z$ when the antecedent is not true, this is very easy: add the constraint $$z \ge x + y - 1.$$Verification (by substituting all possible combinations of 0 and 1 for the variables) is left to the reader as an exercise.

I thought I had covered this in a previous post, but looking back it appears that it never came up (at least in this form). This might be my shortest post ever. :-)

1. Another useful exercise is to derive this constraint by rewriting the logical implication $x \wedge y \rightarrow z$ in conjunctive normal form.

1. Rob: I agree. In fact, I was thinking that there was probably a "cheat sheet" somewhere that showed conversion of basic logical expressions (conjunction, disjunction, negation, implication) into constraints on binary variables. You wouldn't happen to have a link to one, would you?

2. Table 1 here:
http://cepac.cheme.cmu.edu/pasilectures/grossmann/RamanRellogicCACE.pdf

3. Another reference I have used in the past is Ch 3 of the XPRESS LP/MIP book, available at: http://www.maths.ed.ac.uk/hall/Xpress/FICO_Docs/Xpress-booka4.pdf

1. Thanks for pointing that chapter out, Samik! I really liked the XPRESS book back when I used it (I shudder to think how long ago), and it's good to know that it's still out there.

Due to recent spamming, comments are being moderated. If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on Mathematics Stack Exchange.