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");
      model.AddParameter(length);

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

      // The duration requirement.
      int duration = 3;

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

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

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

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