### Archive

Archive for May, 2010

## Stochastic optimization, kidneys, and ethics

I have been reading about online stochastic optimization problems in response to some internal interest in applying Solver Foundation to solve them. Pascal Van Hentenryck’s book is a great introduction. Anyway, I came across a very interesting article by two researchers at Carnegie Mellon: here’s the link. The authors have applied online stochastic optimization techniques to facilitate kidney transplants. When a patient needs a kidney transplant, often a family member or loved one will step up to offer to donate. Unfortunately in many cases the prospective donor and patient are not compatible.  By sharing information about donors and patients, it is possible to set up a “kidney exchange network” whereby willing donors are matched up to patients. By making good matches and performing swaps, more patients get kidneys and lives are saved.

More formally, we have a directed graph and we are seeking the largest collection of vertex-disjoint cycles where the cycle length is under some limit.  A cycle represents a swap between patients and donors.  We want a limit because big cycles (swaps involving lots of parties) are not very practical. We want to apply a so-called “online” algorithm because the problem is continually changing.  New donors appear, and sadly some patients pass away due to the inability to find a match. These events are unpredictable, so we need to come up with a strategy for when and how to perform swaps in the face of an uncertain future.

The technical side of this is very interesting, and it is an inspiring example of the power of mathematical programming to effect positive change in the world. It’s clear that the authors, while remaining completely professional and scientific in their approach, are aware of this aspect to their work. I am sure that it occurred to the authors – as it did to me – that ethical questions quickly arise when we consider how to model and solve such problems.  This leads us to Section 5.3.

Section 5.3 considers the impact of so-called “dummy actions”. In this context, a dummy action means choosing NOT to make any swaps at a time where there are swaps that could be made. In Section 5.3 the authors show that by allowing dummy actions the expected solution quality is around 2% better. And to be really blunt – 2% in this case means 2% more transplants. But consider the implications: this means that somewhere in the country there may be a patient who needs a kidney; somewhere else there is a compatible donor; we are aware of this information; and the model is telling us that we should NOT do an exchange. The logic is that by delaying a swap now, we will have more options later, and we’ll be in a position to help more people. But imagine that you run the kidney exchange: how much confidence must you have in your model to justify such a decision? Perhaps you know that a match exists but the donor and patient do not. Do you feel good about saying nothing? Should we consider disallowing “dummy actions” in certain cases even though we know on average it leads to a better overall outcome?

The beauty of mathematical programming is that we put our cards on the table. We build models and list our assumptions explicitly. It also affords us the ability to make different assumptions and understand (however imperfectly) their impact. Our models seldom capture all the complexities of nature and ethics, but they are often so much better than simply guessing. Awasthi and Sandholm are doing us all a favor when they raise these tough questions because they cause us to think more deeply about what the hell is going on. It is my hope that when we apply deep math to solve real problems we are just as transparent about policies and tradeoffs.

Categories: Optimization Tags:

## Solving a Knapsack problem with Solver Foundation and LINQ

On an internal message board, somebody asked how to solve the following problem:

Let’s say I have this list of days and prices:

```List<ReservationPrice> prices = new List<ReservationPrice>();
prices.Add(new ReservationPrice { NumberOfDays = 1, Price = 1000 });
prices.Add(new ReservationPrice { NumberOfDays = 2, Price = 1200 });
prices.Add(new ReservationPrice { NumberOfDays = 3, Price = 2500 });
prices.Add(new ReservationPrice { NumberOfDays = 4, Price = 3100 });
prices.Add(new ReservationPrice { NumberOfDays = 7, Price = 4000 }); ```

What I would like to able to do now is: give me the best price from the list based on a number of days.

So if ask for 3 days the best price from the list is from child one (1000) and two (1200), but there are of course different combinations. How would an algorithm that found the best price from this list look like ?

Here’s how you could do it in Solver Foundation. You’ll note that the way we bind the solution (which items to choose) back to the ReservationPrice data structure kind of stinks. Other than that the code is pretty straightforward.

```using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.SolverFoundation.Services;

namespace SolverFoundationSample {

public class ReservationPrice {
private double _selectedValue;

public int Id { get; set; }
public int NumberOfDays { get; set; }
public int Price { get; set; }

public bool Selected {
get { return _selectedValue > 0.0; }
set { _selectedValue = value ? 1.0 : 0.0; }
}

// It's too bad that we need this field. It would be nicer to bind
// the Decision to the Selected property - but we need a double-valued
// property.
public double SelectedValue {
get { return _selectedValue; }
set { _selectedValue = value; }
}

public override string ToString() {
return "Number of days = " + NumberOfDays + ", price = " + Price;
}
}

public class Knapsack {

public static void Main(string[] args) {
SolveKnapsack();
}

private static IEnumerable<ReservationPrice> GetData() {
List<ReservationPrice> prices = new List<ReservationPrice>();
prices.Add(new ReservationPrice { NumberOfDays = 1, Price = 1000, Id = 0 });
prices.Add(new ReservationPrice { NumberOfDays = 2, Price = 1200, Id = 1 });
prices.Add(new ReservationPrice { NumberOfDays = 3, Price = 2500, Id = 2 });
prices.Add(new ReservationPrice { NumberOfDays = 4, Price = 3100, Id = 3 });
prices.Add(new ReservationPrice { NumberOfDays = 7, Price = 4000, Id = 4 });
return prices;
}

private static void SolveKnapsack() {
SolverContext context = SolverContext.GetContext();
Model model = context.CreateModel();
var items = new Set(Domain.Any, "items");

var theData = GetData();

// Duration of each reservation
var length = new Parameter(Domain.IntegerNonnegative, "length", items);
length.SetBinding(theData, "NumberOfDays", "Id");

// Price for each reservation.
var price = new Parameter(Domain.IntegerNonnegative, "price", items);
price.SetBinding(theData, "Price", "Id");

// The duration requirement.
int duration = 3;

var choose = new Decision(Domain.IntegerRange(0, 1), "choose", items);
choose.SetBinding(theData, "SelectedValue", "Id");

// Reserve the right number of days.
model.AddConstraint("c", (Model.Sum(Model.ForEach(items, i => (choose[i] * length[i]))) == duration));

// Spend as little as possible.
model.AddGoal("g", GoalKind.Minimize, Model.Sum(Model.ForEach(items, i => (price[i] * choose[i]))));

var solution = context.Solve();
context.PropagateDecisions();

var selected = from d in theData
where d.Selected
select d.ToString();

foreach (var s in selected) {
Console.WriteLine(s);
}
}
}
}```