Category Archives: combinatorial optimization

OR and Crisis Camp

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.)

1 Comment

Filed under combinatorial optimization, global health

ACO in Python: Shortest Paths in NetworkX

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 \frac{p^2(1+p)^2}{(3p^2+1)} n, I’ll make a quick blog post about verifying this claim numerically (in python with networkx). This also gives me a chance to try out the new networkx, which is currently version 1.0rc1. I think it has changed a bit since we last met.

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))

Continue reading

2 Comments

Filed under combinatorial optimization

Clustering with Shallow Trees

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

4 Comments

Filed under combinatorial optimization

Dense-Subset Break-the-Bank Challenge

I’m preparing for my first global travel for global health, but the net is paying attention to a paper that I think I’ll like, and I want to mention it briefly before I fly.

Computational Complexity and Information Asymmetry in Financial Products is 27 pages of serious TCS, but it is so obviously applicable that people outside of our particular ivory tower, and even outside of academia entirely are blogging and twittering about it, and even reading it!

Freedom to Tinker has a nice summary of this paper, if you want to know what it’s about in a hurry.

Mike Trick makes the salient observation that NP-hard doesn’t mean computers can’t do it. But the assumption that this paper is based on is not about worst-case complexity; it is, as it should be, based on an assumption about the average-case complexity of a particular optimization problem over a particular distribution.

As it turns out, this is an average-case combinatorial optimization problem that I know and love, the densest subgraph problem. My plan is to repeat the problem here, and share some Python code for generating instances of it. Then, you, me, and everyone, can have a handy instance to try optimizing. I think that this problem is pretty hard, on average, but there is a lot more chance of making progress on an algorithm for it than for cracking the P versus NP nut. Continue reading

4 Comments

Filed under combinatorial optimization, cryptography, TCS

August is Too-Many-Projects Month

(Tap… tap… tap… is this thing on? Good.)

July was vacation month, where I went on a glorious bike tour of the Oregon/California coast, and learned definitively that I don’t like biking on the side of a highway all day. Don’t worry, I escaped in Coos Bay and took trains and buses between Eugene, Santa Cruz, Berkeley, and SF for a vacation more my speed.

But now that I’m back, August is turning out to be project month. I have 3 great TCS applications to global health in the pipeline, and I have big plans to tell you about them soon. But one mixed blessing about these applications is that people actually want to see the results, like, yesterday! So first I have to deal with the results, and then I can write papers and blogs about the techniques.

Since Project Month is a little over-booked with projects, I’m going to have to triage one today. You’ve heard of the NetFlix Challenge, right? Well, github.com is running a smaller scale recommendation contest, and I was messing around with personal page rank, which seems like a fine approach for recommending code repositories to hackers. I haven’t got it working very well (best results, 15% of holdout set recovered), but I was having fun with it. Maybe someone else will take it up, let me know if you get it to work; networkx + data = good times.

    f = open('download/data.txt')
    for l in f:
        u_id, r_id = l.strip().split(':')
        G.add_edge(user(u_id), repo(r_id))

[get the code]

2 Comments

Filed under combinatorial optimization, software engineering, TCS

ACO in Python: Minimum Weight Perfect Matchings (a.k.a. Matching Algorithms and Reproductive Health: Part 4)

This is the final item in my series on Matching Algorithms and Reproductive Health, and it brings the story full circle, returning to the algorithms side of the show. Today I’ll demonstrate how to actually find minimum-weight perfect matchings in Python, and toss in a little story about \pi^2/6. Continue reading

4 Comments

Filed under combinatorial optimization

Matching Algorithms and Reproductive Health: Part 3, A Stylized Virginity Pledge

It’s been three weeks and one IHME retreat since I wrote about matching algorithms and virginity pledges, and I think I now understand what’s going on in Patient Teenagers well enough to describe it. I’ll try to give a stylized example of how the minimum-weight perfect matching algorithm makes itself useful in reproductive health research.

I think it’s helpful to focus on a concrete research question about the virginity pledge and its effects on reproductive health. Here’s one: “does taking the pledge reduce the chances that an individual contracts trichomoniasis?” If the answer is yes, or if the answer is no, people can still argue about the value of the virginity pledge programs, but this seems like relevant information for decision making. Continue reading

2 Comments

Filed under combinatorial optimization, global health