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

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

ReplyDeleteRob: 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?

DeleteTable 1 here:

ReplyDeletehttp://cepac.cheme.cmu.edu/pasilectures/grossmann/RamanRellogicCACE.pdf

Nice. Thanks.

DeleteAnother 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

ReplyDeleteThanks 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