I had an escapist hobby that is captured in the history of this blog, making maze [link], and I need escape again. And now I have a 5-year-old User for the output! Cool things: the maze-making code from 7 years ago was pretty easy to get working again [links, links]; the scientific python ecosystem now has notebooks! [link]
[Photo of done mazes on paper.]
Comments Off on Python throw-back: making mazes again
Filed under combinatorial optimization
Playing around with that GIS optimization stuff was a chance for me to revisit some maze-making code I wrote a few years ago: https://healthyalgorithms.com/2011/01/07/piggies-and-mazes/ I wonder what age kids it will be good for.
Comments Off on Old Maze Making Code
Filed under combinatorial optimization
This is a fun movie. Nice motion graphics, and camera work. The sound design is good too, although I found the jazz in the background distracting. And I love this research area. I think some colleagues at CMU were starting to work on it right when I was leaving grad school. I’ll share it on healthy algorithms went I have some time to post things.
–Abie
From: Sommer Gentry
Sent: Monday, November 11, 2013 12:25 PM
To: abie
Subject: a movie link for Healthy Algorithms?
Dear Abraham,
I hope this email finds you well. I am enjoying your blog!
I am writing to let you know about a short documentary that features me and my husband and a nice mathematical modeling problem for helping people get kidney transplants. Its moving principle is to sell operations research to a lay audience by explaining the kidney exchange problem in great detail. It has some nice animations that describe the steps of modeling and solving an integer program, at a level for absolute beginners.
Maybe you’d find it interesting enough to put on your blog. In any case, thanks for checking it out.
best,
Sommer
Comments Off on Movie about a healthy algorithm for matching kidney transplants
Filed under combinatorial optimization
Is a SPARQL query computationally powerful enough to test (s,t)-connectivity? I don’t think so, but I don’t understand the mysterious PropertyPath, and even without it, I’m not sure. Tell me on Stack Overflow.
Filed under combinatorial optimization
Inspired by the recent 8F workshop, I’m trying to write up theory challenges arising from global health. And I’m trying to do it with less background research, because avoiding foolishness is a recipe for silence.
This is the what I called the “simplest open problem in DCP optimization” in a recent post about DCP (Disease Control Priorities), but with more reflection, I should temper that claim. I’m not sure it is the simplest. I’m not sure it is an open problem. And I’m pretty sure that if we solve it, the DCP optimizers will come back with something more complicated.
But it is a nice, clean problem to start with. I’m calling it “Fully Stochastic Knapsack”. It looks just like the plain, old knapsack problem:
The fully stochastic part is that everything that usually would be input data is now a probability distribution, and the parameters of the distribution are the input data.
This makes even deciding what to maximize a challenge. I was visiting the UW Industrial Engineering Dept yesterday, and Zelda Zabinsky pointed me to this nice INFORMS tutorial by Terry Rockafeller on “coherent approaches” to this.
Filed under combinatorial optimization, global health
(This is a post that I started a long time ago (Aug 10, 2010), but hung on to because it is only half-baked. But based on the philosophy that avoiding foolishness is a recipe for silence, I’m sending it out into the world. Coming next: the simplest useful open problem in DCP optimization.)
Acronyms are like candy in Global Health, and Operations Research is full of them, too. This post is a place for me to collect information about software available for solving the Mixed Integer Programming (MIP) problem that the Disease Control Priorities (DCP) project is going to put together.
DCP is a massive effort to quantify the cost-effectiveness of hundreds of health interventions across tens of “health platforms” (big hospitals, small clinics, pharmacies, etc). The output of this large, coordinated effort will be (as far as I’m concerned) a collection of giant matrices, that say, for different subsets of interventions across different platforms, (1) the cost of setting up the interventions, (2) the cost of operating the interventions, (3) the health gain from the interventions. Undoubtedly, there will be some quantification of the uncertainty in each of these quantities. Also, there is something called platform improvement, which can be thought of as a special type of intervention that makes a bunch of other interventions more effective on a certain platform. And there are a number of side-constraints; some interventions come together on certain platforms, some interventions are mutually exclusive, etc.
Some unknowns: (how) will the uncertainty in the entries of these matrices be quantified? Are the intervention choices all “yes/no” or do you choose how much you want of some of them, i.e a non-negative continuous variable?
This is the optimization that mixed integer programming was born for (except for the uncertainty, which takes us into less charted waters). So how we are going to do it, in theory, is just the sort of thing my OR classes focused on when I was in grad school. We didn’t talk much about how to do it in practice. Some of the hard-working students who sat in the business school and actually solved large integer programs would mutter about CPLEX once in a while at parties, but I didn’t pay it much heed.
Heed I must now pay. So I am collecting up the available MIP solvers here, and (eventually) evaluating them for my DCP optimization task. Got suggestions? I would love to hear them.
Filed under combinatorial optimization, global health
What people are saying now: Water shortage, food shortage, medical equiptment needed. What they are not saying as much anymore: Food, shelter, search and rescue.
(data details in previous post.)
Filed under combinatorial optimization, global health
When the earthquake devastated Haiti, Laura McLay asked if OR is helping with the relief efforts. I’ve been wondering the same thing, and I went to a “Crisis Camp” this weekend to see if there is anywhere I could plug in.
This Crisis Camp business is hard to describe, and I didn’t really know what I was getting into when I showed up, and it seems like most of the other participants didn’t either. But we all woke up for a 9 AM meeting on Saturday, and we all wanted to do something good for the people of Haiti.
This isn’t exactly something you can make an impact on in a day, and the only tangible result of my work was fixing a typo on a wiki, but I did learn a little bit about what is going on. One group of geographers did a quick course on Open Street Maps and was able to start helping in an effort to update the maps of Port-au-Prince, tagging blocked roads, collapsed buildings, etc.
I joined group that connected with an ongoing project to find hospitals outside Port-au-Prince and help them share information about available capacity with people who need medical attention. Like I said, I didn’t manage to help with this in a day, but I did learn about this Sahana project and their success in finding the lat and long of 100 hospitals in Haiti.
Another impressive data sharing tool that I a look at is Ushahidi, which I had heard about before, but never seen in action. This is a project that has a free SMS gateway for people in Haiti to use to report emergencies or share information. They translate messages into english and post them on the web with a CC-BY-SA license. I started looking at them yesterday, and they can be heartwrenching. Here is the breakdown by category, as of last night:
Does this inspire any operations research solutions? It makes me think of vehicle routing, if the earthquake damage tags in Open Street Maps show which roads are closed, that is:
I’m not sure if they do. (Red is map features with the tag earthquake:damage, but those are mostly IDP camps.)
Filed under combinatorial optimization, global health
I’m supposed to be doing the final edits on the journal version of this old paper of mine (jointly with Greg Sorkin and David Gamarnik), but I’ve thought of a way to procrastinate.
Instead of checking the proofs that the length of the shortest path in my weigthed width-2 strip is 
from pylab import *
from networkx import *
G = Graph()
for u, v in grid_2d_graph(100, 2).edges():
G.add_edge(u, v, weight=rand() < .5)
wt, p = bidirectional_dijkstra(G, (0,0), (99,1))
Filed under combinatorial optimization
I’m updating my CV, and that reminded me that I meant to promote this cool clustering technique that I was a little bit involved in, Clustering With Shallow Trees.
This goes way back to about half-way through my post-doc at MSR, when statistical physicist Riccardo Zecchina was visiting for a semester, and was teaching me about all of the “intractable” optimization problems that he can solve using his panoply of propagation algorithms. In particular, he was working on algorithms for certain types of steiner tree optimization, and he had discovered that adding an extra constraint on the depth of the tree didn’t make the problem harder. (All variants of the problem he considers are NP-hard, but some are NP-harder than others.) Continue reading
Filed under combinatorial optimization
Healthy Algorithms 