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.

3 Comments

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:

WordPress.com Logo

You are commenting using your WordPress.com 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