Tag Archives: optimization

dynamic programming day

Eric Dubois, one of my PhD students, interned at the RAND Corporation this summer. He gave a presentation about his internship to my lab.

I learned that dynamic programming is still of great importance at RAND. Richard Bellman introduced dynamic programming in 1953 while working at RAND. He spent most of his career at RAND, and his many contributions to dynamic programming are still cherished. You can download his 1954 RAND Report “The Theory of Dynamic Programming.” Every summer, RAND employees celebrate dynamic programming’s anniversary with cake.

I would love to celebrate dynamic programming with cake and with the cake eating problem (optimal depletion of an uncertain stock).

Note: the cake eating problem can be solved with dynamic programming.

The RAND Corporation began to provide analysis for the Air Force after World War II. Soon thereafter RAND branched into nuclear deterrence. A (fake) RAND analysis on nuclear deterrence is mentioned in Dr. Strangelove or: How I Learned to Stop Worrying and Love the Bomb.
The Dr. Strangelove character is based on RAND scientist Herman Kahn.

dividing up a large class into discussion sections using integer programming

I am team teaching a freshman course on engineering grand challenges with five other instructors. Each of the six instructors teaches a “theme” (mine is about systems, critical infrastructure, and logistics) to a subgroup of students. We must partition the students into six themes twice, since we repeat our themes in the second half of the semester with another group of students (we call these modules). To facilitate the assignments, students can submit a rank ordering of their top four choices. I was asked to use optimization to make the pairings. I thought about manually making the matches, but I could see that it would be a lot of work to redo the matchings if someone wanted to make some changes later on. So I put together a quick optimization model to do the work for me.

Here are the constraints:

  • Theme class sizes must be between 21 and 24 students
  • Each student should get one of their top two choices (this is not guaranteed)
  • Every student needs to be assigned to a theme in each module
  • Every student needs to be assigned to different themes across the two modules
  • Two groups of students are in first year interest groups (FIGs) and should all be assigned to the same first theme, regardless of preferences. This is a hard-but-flexible constraint (is that a thing?). These students needed to be assigned to the same theme, but I could choose any theme for them.

I had about two days to make the assignments and possibly field some requests to change the assignments. Integer programming was appealing because it would allow me to quickly make changes to the assignments and do a “what if” analysis. I could quickly see that it was going to be impossible to fill some of the themes based on student preferences. Luckily, some students did not submit preferences, so I could use these students to “pad” the assignments while maintaining a good solution. The objective function captures the quality of the assignments based on student preferences, so I would always have a feasible solution. I assigned weights for each student-theme pair as the objective function coefficients. I assigned the first choice theme a weight of 8, the second choice theme a weight of 4, a third choice theme a weight of 2, and a fourth choice theme a weight of 1. I assigned all other student-theme pairs a weight of zero. The goal was to mostly assign students to first and second preferred choices, so I chose weights that would “encourage” this. After solving the model I could easily check to see how many students were assigned to one of their top two matches (we promise to do this, if its possible).

The FIGs was a bit tricky. This constraint made it hard to eyeball a good solution and motivated the use of integer programming. I wanted to be able to manually test out different theme assignments for the FIGs and possibly have the flexibility to change the assignments really quickly if one of the instructors did or did not want a FIG. I manually selected themes for the FIG students by fixing variables and then optimized the assignment of everyone else. I could have treated the FIG assignments as a decision instead of an input.

Here are the parameters:

  • N = 138 students
  • T = 6 themes
  • M = 2 modules
  • w_{nt}: preference weight for student n and theme t (either 0, 1, 2, 4, or 8).

Here are the binary decision variables:

  • x_{ntm}: 1 if student n is assigned to theme t in module m.

The integer programming model is as follows.

maximize \sum_{n,t,m} w_{nt} x_{ntm}

subject to

21 \le \sum_n x_{ntm} \le 24, t=1,...,T,\ m=1,2

x_{nt1} + x_{nt2} \le 1, n=1,...,N, t=1,...,T

\sum_t x_{ntm} = 1,\ i=1,...,N,\ m=1,2

x_{ntm} \in \{0,1\}, n=1,...,N,\ t=1,...,T,\ m=1,2

The objective function maximizes the value of the assignments. The first constraint sets class sizes between 21 and 24. The second constraint ensures that a student is not assigned to the same theme across both modules. The third constraint ensures that each student is assigned to one of the themes in both modules. I do not require the model to assign students to one of their top two choices, and therefore, a feasible solution is always easy to find. However, I checked afterward to see if students got what they wanted (according to my results, they did!). What isn’t in this model is fixed variables associated with FIG student assignments, but that is straightforward to change.

The model was easy to set up except for setting the weights w_{nt} based on student preferences. This information came from a survey we conducted on the course management system. Downloading the data in a spreadsheet did not give us a flat file, so it took some extra parsing to get the right data. We would have needed to parse the survey data even if we made the assignments manually, so this was unavoidable. I would have liked to ensure diversity in teams somehow, but I did not have the data for this. Next time.

All in all, this was fun, and I would recommend the use of integer programming. It took me longer to write this post than to set up and solve the integer program to assign students to themes 🙂



how to seat guests at a wedding

How to optimally seat people at a wedding.

SAS started an operations research blog [Link]. Matthew Galati’s first entry is how to optimally seat people at a wedding given assignment preferences. He provides a model that maximizes the total happiness of his guests. His blog post has code, data, and a pictures of a quirky family member or two. It’s a great post worth checking out.

I’ve written about optimization for weddings before. I blogged about a paper entitled “Finding an Optimal Seating Chart” in the Annals of Improbable Research by Meghan L. Bellows and J. D. Luc Peterson shows how to use integer programming to optimally seat guests at a wedding [blog post & paper]. The reader comments to this post are really interesting – many people have used a similar modeling approach.

Geoffrey De Smet provided a link to a wedding planner on github.

Related posts:

help Santa solve this bin packing problem

Kaggle is sponsoring a non-denominational Christmas optimization contest to help Santa solve a 3-dimensional bin packing problem [Link].

This year we’re attacking the classic bin packing problem with a twist: cram all the gifts into his sleigh, but in the order they need to be delivered! MathWorks is sponsoring the $10,000 prizes — with $4000 going to both the holder of the top spot, and also the highest-ranked team using 100% MATLAB/MathWorks as their tool. The final $2000 is the Rudolph Prize: Rudolph, won’t you lead-our-board tonight? No word yet on whether the prize pool will include an optimally-stuffed reindeer.

The problem seeks to find an optimal ordering of Christmas presents in a single 3-dimensional bin. Packages have a size in each of the three dimensions, and they can be rotated to fit into the bin. The objective is to minimize the highest placed present in the bin. The contest ends at 11:59 pm, Sunday 26 January 2014 UTC.

Santa packs a bin full of presents

is integer programming the best tool in the OR/MS toolkit?

A tweet from Marco Luebbecke contained a provocative quote from George Nemhauser’s plenary talk at the EURO-INFORMS Joint International Meeting:

This needs more discussion than 140 characters. Integer programming is truly an amazing tool for optimally solving problems that are theoretically difficult to solve. It would be hard for me to come up with reasons for why IP would not be the most important tool. What do you think?

are squirrels optimizers or satisficers?

Last month, I had the pleasure of meeting Yakov Ben-Haim and talking with him at length about info-gap decision theory. He used an example of squirrels foraging for nuts to illustrate the types of problems for which info-gap decision theory models are useful.

A squirrel needs calories to survive, and nuts provide the perfect source of calories. The squirrel has a decision to make: where should the squirrel go to forage for nuts? Different foraging locations have different potentials for nut payoffs. They also have risks (not enough food). Foraging in a new location may carry highly uncertain risks that are impossible for the squirrel to estimate (being hit by a car, eaten by a wolf, etc.)

The squirrel has two options: the squirrel can hunt in the usual area where he can obtain n nuts with certainty or he can try a new location where he has a probability P of obtaining N nuts (with N > n) and a probability (1-P) of obtaining zero nuts. Let’s say that N and P are wild guesses.

Let’s say that the squirrel is an optimizer and decides to build a decision tree to maximize the number of nuts he can collect. Using basic decision analysis, he devices that he should choose the new location if PN>n.

The squirrel's decision tree. Squirrels don't really make decision trees, do they?

If the squirrel needs to collect n nuts to survive, then maximizing is nuts (pun intended. Sorry!) Staying with the status quo guarantees survival, even if P and N are large. The payoff for the new location may be greater, but there is a 1-P chance that the squirrel would starve.  The traditional decision tree is not robust to the squirrel’s desire to survive (neither is darting in front of cars on the highway, but I digress).

On the other hand, if the squirrel needs to collect N nuts to survive, then staying with the status quo guarantees the squirrel’s demise.  The new location is worth a look no matter how risky.

In both of these scenarios, the squirrel isn’t really maximizing the subjective expected nuts that he can collect–he really wants to maximize the probability of meeting his nut threshold (the one that guarantees survival). This is a satisficing strategy (although not dissimilar from an optimizing strategy with a moving threshold). The satisficing strategy is a better bet for the squirrel than the optimization strategy in this decision context. The squirrel doesn’t always need to know the exact probabilistic information to make a good decision, as illustrated above.  In fact, he can have absolutely no idea what N and P would be to find an effective nut foraging strategy–even when there is severe uncertainty.

The idea of a squirrel building a decision tree is, of course, ludicrous. But it makes the point that what we should rethink our traditional optimization models so make sure they fit the real decision criteria on hand.  Info-gap decision theory thus focuses on satisfying a given acceptable level of what is traditionally considered the objective function value and instead optimizing robustness.  It also has philosophical implications for how one views certainty.

I’ve been looking more closely at robustness lately.  I won’t abandon my optimization models, but I will acknowledge that including robustness in certain scenarios leads to decisions that more accurately reflect the criteria at hand and decisions that could be counter-intuitive.

Yakov Ben-Haim can explain this much better than I can, so I’ll refer you to his blog about info-gap decision theory and his article about foragers in the American Naturalist if you want to learn more.

a course blog on discrete optimization

I decided to try an experiment this semester that involves possibly torturing a few grad students:  I proposed that the students in my grad-level course on discrete optimization would maintain a blog for course of the semester. Amazingly, the students in my class agreed to my little experiment!  I am happy to say that our blog, the not-so-cleverly titled Discrete Optimization Blog, has been live for two weeks now.

If you’re interested, please stop by and visit us.  Blog posts are due on Mondays at noon (from now until the first week in May).  You can read more about the blog assignment here. As far as I know, this is the first operations research course blog, and I think the students are doing a great job.

a Christmas brain teaser

When finding some math worksheets to occupy my six year old daughter on her day off of school, I discovered a Christmas brain teaser for elementary students (in pdf format):

Find a route [between twelve cities] for Santa to follow that is as short as possible. After you have found a route, compare it to others to see if they found a shorter route.

Of course, you will immediately recognize this as the TSP.  The “solution” is amusing:

Try to view this question as open-ended, or your student(s) might be working on it for days. …And if someone figures out the best answer to this question, please let me know and I’ll add it here.

Finding the optimal solution to a twelve city TSP is indeed pretty hard.  So hard, in fact, that the folks at math-drills.com couldn’t find the solution.  I have confidence that my readers can find the optimal solution in less than a day.  But please spend Christmas with your families enjoying holiday cheer.

Happy holidays!

robust Christmas shopping

I usually more or less finish my Christmas shopping before Black Friday, so I usually do not worry about optimal shopping strategies. I enjoyed reading about Aurelie Thiele’s latest paper on robust timing of markdowns.  Her blog post summarizes her new paper (she provides a link to the paper), where Aurelie and her collaborators propose a method for dynamically timing markdowns over a finite horizon using robust optimization models.

This got me thinking about how to reverse-engineer the process to get the best deals.  If you’re not willing to do Black Friday shopping (the getting up at 3am and waiting in long lines do not make up for the extra savings), then shopping for a few key items is like a stopping problem (e.g., the Secretary Problem), where a series of deals are offered (some at the same time, such as in the Sunday ads) and the consumer eventually decides to purchase exactly one item with a deadline of December 24.  When should I purchase the item?  I suppose it depends on how retailers adjust the prices from one time period to the next.

These are a few rules of thumb that I’ve learned (beware: no modeling or algorithms used here).  With a bad economy, I see no drawback to a wait and see approach, since sales continually improve and store coupons become available as shoppers stay home.  I have found that in the last three years or so, the pre-Christmas sales (not just Black Friday) are often better than the post-Christmas clearance sales.  So I stock up and do some personal shopping before the holidays.  However, the clearance sales become lucrative in February and insanely good in March (for clothes, at least).

How do you do your Christmas shopping?

Related posts:

Opt Art

Last month, Robert Bosch gave a fascinating talk on operations research and art here at Virginia Commonwealth University. His talk focused on showcasing how optimization, in particular, using entire sets of dominos to reconstruct paintings and images, such as the Mona Lisa and Marilyn Monroe. You can see his masterpieces at DominoArtwork. It was fascinating to see an illustration of how art connects to optimization.

Some links:
Bob’s OR/MS Today article
Images using knots
Science for kids article featuring Bob’s art