Modeling Logical Conditions

circuitBinary variables are extensively used in integer programming (IP) models to represent yes/no decisions (“Should we open a new restaurant in Coconut Grove?”), and logical conditions (“If it rains tomorrow, I will not go to the beach.”). Most people are familiar with the project selection problem in which each variable Xi is equal to 1 if project “i” is selected, and it’s equal to zero otherwise. To model the condition “if project 1 is selected, then project 2 must also be selected” one can write “X1 ≤ X2”, and “if project 2 is selected, project 3 must not be selected” becomes “X2 + X3 ≤ 1”. Even students who are learning about integer programming for the first time are usually capable of coming up with those two constraints after a few minutes (or hours). A little bit of trial-and-error typically gets you there.

What if the logical condition is a tad more complicated? For instance:

If it rains tomorrow or the Heat defeat the Spurs and grandma doesn’t come to visit on the weekend, then I’ll either go to South Beach and not drink a mojito or I’ll fly to Vegas.

I’m sure it only took you about 7 seconds to figure out that the corresponding IP model is

w + q – x ≥ 0

z + w + q ≥ y

1 + q ≥ x + p

y + p – q – z ≤ 1

This assumes that the binary variables x, y, z, w, p, q are assigned the following meanings: x = whether it rains; y = whether Heat defeat Spurs; z = whether grandma comes to visit, etc.

My students always ask me if there’s a more systematic way to come up with the linear constraints other than trial-and-error or memorization of a few simple cases. This led me to write a 4-page handout on the topic. More recently, I searched around for a while (OK, I confess that my search wasn’t very extensive) and found two references: an article on INFORMS Transactions on Education and H. P. Williams’s book. It turns out that Williams (section 9.2) does an excellent job explaining the process (if only I had known that two years ago…).

I hope this handout can still be helpful to someone out there (instead of just sitting in my hard drive). As always, your comments and feedback are welcome.


Filed under Integer Programming, Modeling, Teaching

3 responses to “Modeling Logical Conditions

  1. Pingback: Using Airline Miles to Buy Magazines: a Hidden Deeper Lesson « O.R. by the Beach

  2. Geoffrey Anderson

    Oh my goodness, how I love your paper on modeling logical conditions. This translation work comes up all the time when I design integer programming models. My catalog of recipes was incomplete and hard to develop. Your paper totally answers everything, and it was so clear and easy to read that I was able understand the whole thing in one sitting, and this is from a person with just an undergrad degree. I can’t thank you enough. The standard OR textbooks for undergrad or intro OR really should include this material from your little paper … It’s come up in practically every IP model I can recall working on. Your clarity of writing is phenomenal. Thank you so much. About me…I am a software engineer with a BA in math who likes to build linear math models for optimization on the side. I loved my OR courses. Hillier and Lieberman really must get in contact with you for their textbook update. Cheers!

  3. orbythebeach

    Geoffrey: Thank you for the comment. I’m very happy to hear that you found the handout useful.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s