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. :-)

6 comments:

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

    ReplyDelete
    Replies
    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?

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

    ReplyDelete
  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

    ReplyDelete
    Replies
    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.

      Delete

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 OR-Exchange.