domino optimization art

Domino opt-art version of me

Domino opt-art version of me

I discovered a picture of me in my student lab – one of the students optimized me for a class project using dominos(!)  My second blog post ever was about Bob Bosch’s optimization art – see some of his domino art here. It’s worth revisiting opt art.

Bob Bosch wrote about his domino optimization models in Math Horizons, a trade journal from the Mathematical Association of America, and OR/MS Today. Bob also does other types of optimization art (TSP art, mosaic art, etc.). Let’s take a closer look at domino art.

The art is created by solving an integer programming model that finds the arrangement of dominos that is closest to the picture. When complete sets of dominoes are used, there are limited numbers of each type of tile/domino, and intelligently using each type of domino (a limited resource) by assigning it to the “right” part of the photo is the basis for the optimization model.

First, the photo of interest is divided into m x n squares. The goal is to fully use s sets of dominoes, where each set of dominoes contains 55 tiles. Therefore, the photo must be divided into squares such that is satisfies

mn=110s .

The photo must then be divided into a set P of adjacent pairs of squares to account for different domino orientations (i.e., laying a tile horizontally or vertically). Decision variable x_{dp} is 1 of we place domino d on the photo to cover pair and 0 otherwise. There is a parameter c_{dp} that captures the “cost” of placing domino d on the photo to cover pair based on the brightness of the photograph and the number of dots on the tiles. This then gives us an integer programming model that is an assignment problem variation:

dominoip

The objective function minimizes the deviation between the photo and the placement of the dominoes. The first set of constraints ensures that all dominoes are used. The second set of constraints ensures that each pair in the photo is covered by exactly one domino. Bob’s article in  Math Horizons has all the details on constructing the set P and computing the costs. There is no shortage of cool opt art photos of Bob’s creations – check out his stuff on twitter and his web site.

What do you think of my domino photo? I think it’s terrific, but I think I prefer the non-optimized version of me.


just write, damn it

I’ve had little time to write lately, so writing feels like a guilty pleasure when I have the time to do it. I am advising four PhD students who often ask me about the writing process. I’ve almost forgotten about how hard technical writing was for me back when I was in their shoes.

Roger Ebert’s memoir Life Itself  jarred my memory. This weekend, I was listening to the audiobook while working on on my yard. One passage about writing got my attention:

[Bill] Lyon watched as I ripped one sheet of copy paper after another out of my typewriter and finally gave me the most useful advice I have ever received as a writer: “One, don’t wait for inspiration, just start the damned thing. Two, once you begin, keep on until the end. How do you know how the story should begin until you find out where it’s going?” These rules saved me half a career’s worth of time and gained me a reputation as the fastest writer in town. I’m not faster. I spend less time not writing.

Part one is really great advice. I’m a firm believer in writing as you go. I’m not so sure about part two for students writing their first article or thesis. First, most of the time it is even feasible to write until you reach the end. Second, organization helps when writing a lengthy manuscript (lengthy here is relative to newspaper articles). It’s usually easier to write when you have an outline that lays out your ideas in a straightforward fashion. You should know where you’re going. But if organization paralyzes you, I recommend just starting the damned thing and reorganizing later. Students seem to struggle with writing sins of omission – the biggest mistake is not getting started. If you want to finish something, you need to start it first.

When searching for Roger Ebert’s comment on writing, I found similar advice from Matt Zoller Seitz about writing movie reviews on rogerebert.com:

Just write, damn it. I believe that ninety percent of writer’s block is not the fault of the writer. It’s the fault of the writer’s wrongheaded educational conditioning. We’re taught to write via a 20th century industrial model that’s boringly linear and predictable: What’s your topic sentence? What are your sections? What’s your conclusion? Nobody wants to read a piece that’s structured that way. Even if they did, the form would be more a hindrance than a help to the writing process, because it makes the writer settle on a thesis before he or she has had a chance to wade around in the ideas and inspect them. So to Hell with the outline. Just puke on the page, knowing that you can clean it up and make it structurally sound later. Your mind is a babbling lunatic. It’s Dennis Hopper, jumping all over the place, free associating, digressing, doubling back, exploding in profanity and absurdity and nonsense. Stop ordering it to calm down and speak clearly. Listen closely and take dictation. Be a stenographer for your subconscious. Then rewrite and

This isn’t quite the right advice for writing a thesis, but students should hear this. Students know they are supposed to organize. They seem less familiar with the idea of puking on the page, knowing that they can clean it up and make it structurally sound later. The latter approach is how I start almost all of my blog posts (most get cleaned up later).

How do you write?

 


the NFL football draft and the knapsack problem

In this week’s Advanced Football Analytics podcast, Brian Burke talked about the knapsack problem and the NFL draft [Link]. I enjoyed it. Brian has a blog post explaining the concept of the knapsack problem as it relates to the NFL draft here here. The idea is that the draft is a capital budgeting problem for each team, where the team’s salary cap space is the knapsack budget, the potential players are the items, the players’ salaries against the cap are the item weights, and the players’ values (hard to estimate!) are the item rewards. Additional constraints are needed to ensure that all the positions are covered, otherwise the optimal solution returned might be a team with only quarterbacks and running backs. Brian talks a bit about analytics and estimating value. I’ll let you listen to the podcast to get to all the details.

During the podcast, Brian gave OR a shout out and added a side note about how knapsack problems are useful for a bunch of real applications and can be very difficult to solve in the real world (thanks!). I appreciated this aside, since sometimes cute applications of OR on small problem instances give the impression that our tools are trivial and silly. The reality is that optimization algorithms are incredibly powerful and have allowed us to solve incredibly difficult optimization problems.

Optimization has gotten sub-optimal coverage in the press lately. My Wisconsin colleagues Michael Ferris and Stephen Wright wrote a defense of optimization in response to an obnoxious anti-optimization article in the New York Times Magazine (“A sucker is optimized every minute.” Really?). Bill CookNathan Brixius, and JF Puget wrote nice blog posts in response to coverage of a TSP road trip application that failed to touch on the bigger picture (TSP is useful for routing and gene sequencing, not just planning imaginary road trips!!). I didn’t write my own defense of optimization since Bill, Nathan, and JF did such a good job, but needless to say, I am with them (and with optimization) all the way. It’s frustrating when our field misses opportunities to market what we do.

If you enjoy podcasts, football, and analytics, I recommend the Advanced Football Analytics podcast that featured Virgil Carter, who published his groundbreaking football analytics research in Operations Research [Link].

Related posts:

 


tips for filling out a statistically sound bracket

Go Badgers!!

Here are a few things I do to fill out my bracket using analytics.

1. Let’s start with what not to do. I usually don’t put a whole lot of weight on a team’s record because strength of schedule matters. Likewise, I don’t put a whole lot of weight on bad ranking tools like RPI that do not do a good job of taking strength of schedule into account.

2. Instead of records, use sophisticated ranking tools. The seeding committee using some of these ranking tools to select the seeds, so the seeds themselves reflect strength of schedule and implicitly rank teams.  Here are a few ranking tools that use math modeling.

I like the LRMC (logistic regression Markov chain) method from some of my colleagues at Georgia Tech. Again: RPI bad, LRMC good.

3. Survival analysis quantifies how far each each team is likely to make it in the tournament. This doesn’t give you insight into team-to-team matchups per se, but you can think about the probability that Wisconsin making it to the Final Four reflecting an kind of average across the different teams a team might play during the tournament.

4. Look at the seeds. Only once did all four 1-seeds make the Final Four. It’s a tough road. Seeds matter a lot in the rounds of 64 and 32, not so much after that point. There will be upsets. Some seed match ups produce more upsets than others. The 7-10 and 5-12 match ups are usually good to keep an eye on.

4. Don’t ignore preseason rankings. The preseason rankings are educated guesses on who the best teams are before any games have been played. It may seem silly to consider preseason rankings at the end of the season after all games have been played (when we have much better information!) but the preseason rankings seem to reflect some of the intangibles that predict success in the tournament (a team’s raw talent or athleticism).

6.Math models are very useful, but they have their limits. Math models implicitly assume that the past is good for predicting the future. This is not usually a good assumption when a team has had any major changes, like injuries or suspensions. You can check out crowdsourcing data (who picked who in a matchup), expert opinion, and things like injury reports to make the final decision.

For more reading:


operations research improves school choice in Boston

Many cities allow families to choose elementary schools to address growing inequities in school instruction and performance. School choice lets families give a rank ordering of their preferred schools, and a lottery ultimately assigns students to schools. The result is that many students have to travel a long way to school, crazy bus schedules, and students on the same block who do not know each other because they go to different schools.

Peng Shi at MIT (with advisor Itai Ashlagi) won the 2013 Doing Good with Good OR Award held by INFORMS with his project entitled “Guiding school choice reform through novel applications of operations research” that addressed and improved Boston’s school choice model.  I am pleased to find that his paper based on this project is in press at Interfaces (see below).

The schools in Boston were divided into three zones, and every family could choose among the schools in their zone. Each zone was huge, so on any given block, students might be attending a dozen different schools. See a graphic in a Boston Globe report to see more about the problem.

Peng balanced equity with social problems introduced with the choice model by proposing a limited choice model. His plan was to let every family to choose among just a few schools: the best and the closest. Families could choose from the 2 closest in the top 25% of schools, the 4 closest in the top 50% of schools, and the 6 closest top 75% schools, the 3 closest “capacity schools,” and any school within a mile. There was generally a lot of overlap between these sets, so families had about 8 choices in total (a lot less than the original school choice model!). This gave all families good choices while managing some of the unintended consequences of a school choice system (busing and transportation, distant schools, neighbors who didn’t know each other).

The model itself was not obvious: there is no “textbook” way to model choice. Peng visited with the school board and iteratively adapted and changed his model to address concerns within the community.  This resulted in the model becoming simpler and more transparent to parents (most parents don’t know about linear programming!). The new model pairs above average schools with below average schools in a capacity-weighted way to make school pairs have comparable average qualities. This lets families choose from school partners, the closest four schools, and schools within a mile.

The school board voted to adopt his plan. Peng worked with the school district to come up with important outcomes to evaluate. The model itself uses linear programming to “ration” school seats probabilistically among students by minimizing the expected distance subject to constraints. To parameterize the model, he used a multinomial logit model to fit the data (with validation). He also ran a simulation with Gale-Shapley’s deferred acceptance algorithm as a proof of concept to ensure that the model would work.

See Peng Shi’s web site for more information. Some of his documentation is here.

I’ve been on the INFORMS Doing Good with Good OR Award committee for the past three years. This award honors and celebrates student research with societal impact. I love this committee – I get to learn about how students are making the world a better place through optimization. And these projects really do make a difference: all applications must submit a letter from the sponsor attesting to improvements. Submissions are due near the end of the semester (hint hint!)

Reference:

Guiding School-Choice Reform through Novel Applications of Operations Research by Peng Shi
Interfaces articles in advance
Permalink: http://dx.doi.org/10.1287/inte.2014.0781


land O links

Here are a few links for your weekend reading:

  1. I’ve used the Monty Hall Problem in class. I didn’t realize agreeing on the correct solution was so controversial.
  2. Leonard Nimoy’s portrayal of Spock “in many ways co-created, helped define geek/nerd personality and interests for millions of future geeks” So true.
  3. Sports analytics is great and all that, but there is a serious lack of data in women’s sports.
  4. Five class Atari games that totally stump google’s artificial intelligence algorithm (like Asteroids!)
  5. The math behind getting all that damn snow off your street.
  6. Han Solo shot first: the surprising significance of past tense, present tense, and Wikipedia.
  7. A sobering Los Angeles Times article about why women are leaving the tech industry in droves (hint: it’s a hostile work environment)

be a satisficer or use the secretary problem to find love!

I was surprised to read that a study recommends using a satisficing strategy to find a mate [Link to article, Michigan State press release]

The researchers studied the evolution of risk aversion and discovered that it is in the human nature to go for the safe bet when their stakes are high. For instance whether or not mate. This human nature is traced back to the earliest period of their evolution.

The study is computational (i.e., not a psychological study) and involves simulation that mimics the degree and range of risk-taking in human behavior. It suggests that we are satisficers, not optimizers* and that something like the secretary problem is not suitable for finding a mate/spouse [read Mike Trick’s counterpoint here].

In the secretary problem, the goal is to maximize the probability of finding the “best” secretary and its optimal solution by interviewing up to n secretaries, letting a few go, and then selecting the next secretary that is the “best” so far (totally how dating works, right?!) The secretary problem focuses on finding the best possible solution (only the best will do) but the optimal strategy may lead to a suboptimal secretary (good but not the best) or no secretary at all. In fact, the optimal strategy leaves a pretty big chance of finding no secretary, which will occur if the “best” overall is one of those candidates that we let go at the beginning. I have a figure below of the probability that a candidate is hired at all (it’s the blue line), and it’s way less than 1.0.

The probability of hiring a secretary/finding a spouse as a function of the number of candidates (n) simulated over 10,000 replications

The probability of hiring a secretary/finding a spouse and the probability of hiring the *best* secretary/choosing the right spouse as a function of the number of candidates (n) simulated over 10,000 replications

Do I think this satisficing advice is really worth taking? Well, I have three daughters and I’ll encourage them to optimize instead of satisfice.

Here are my other Valentine’s Day, secretary problem, and love posts from my blog archive:

Valentine’s day posts from the #orms blogosphere:

* Yes, I know that satisficing and optimizing are really the same thing, but I finding-the-absolute-best and not-walking-away-without-empty-handed are really two different objective functions.

Do you optimize or satisfice? What other OR models can be compared to finding a partner for life aside from the secretary problem?


Follow

Get every new post delivered to your Inbox.

Join 2,762 other followers