Category Archives: combinatorial optimization

Python throw-back: making mazes again

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

Old Maze Making Code

Playing around with that GIS optimization stuff was a chance for me to revisit some maze-making code I wrote a few years ago: I wonder what age kids it will be good for.

Comments Off on Old Maze Making Code

Filed under combinatorial optimization

Movie about a healthy algorithm for matching kidney transplants

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.


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.


Comments Off on Movie about a healthy algorithm for matching kidney transplants

Filed under combinatorial optimization

Power of SPARQL?

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.

1 Comment

Filed under combinatorial optimization

A simple optimization problem I don’t know how to solve (from DCP)

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:
\max \bigg\{ \sum_{i=1}^n v_ix_i \qquad s.t. \quad \sum_{i=1}^n w_ix_i \leq W, \quad x_i \in \{0,1\} \bigg\}
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.

  • Gurobi – 1 2 3
  • ILOG/CPLEX – 1 2
  • GAMS – 1
  • AMPL – 1
  • NEOS – 1


Filed under combinatorial optimization, global health

haiti.ushihidi by category

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