There are a lot of optimizers at the INFORMS meeting, so I suppose it should not be surprising that difficult problems get solved here. Nonetheless, I have seen a few results I would not have anticipated.
- The shortest path problem is well known to be easy, but I thought the longest path problem was NP-hard(ish). Yet my feet solved longest path problems every time I went to a session.
- One can reasonably approximate the volume of space occupied by a human with a cylinder. Sphere packing problems can be tricky, but at the WORMS networking event we easily found a maximal solution to the cylinder packing problem, using the attendee swarm metaheuristic. (This is a nature-inspired algorithm based on the innate ability of conference attendees to locate free food and beverages.)
- In recent years, both deterministic and stochastic methods have been applied to security problems. This includes finding the best places to hide something (a terrorist cell, surveillance equipment, the “nuclear football” during the current administration) and the best order to search places. The conference venue staff has apparently found an efficient way to solve the former. During coffee services in the main exhibit hall, they placed carts at four locations, with each cart containing three coffee urns plus hot water. In the morning, decaf was reasonably readily available, but in the afternoon only one urn out of 12 had decaf. (Why decaf was in greater supply in the morning is left to the reader as an exercise.) Probability theory says that a completely random search for the lone decaf urn in the afternoon should have a negative binomial distribution. A more plausible search strategy (search carts exhaustively, but in random order) would convolute a negative binomial (number of carts needing to be searched) with a conditional distribution for the number of urns on each cart needing to be checked (a degenerate distribution if it is the wrong cart, negative binomial on the correct cart). In actuallity, though, the venue staff figured out a way to position urns such that the decaf urn is always the 12th one checked. I’m pretty sure DOD is going to be interested in their process.