The 12-pack problem: combination of integers

A fun problem came my way today. Imagine that you are the owner of a renowned brewery in Bizzarostan, a country where beer is sold only in 7-packs and 13-packs, sometimes described as the ++ packs. Beer is a serious matter in Bizzarostan, and buying single bottles is not tolerated by the law.

You take great pride in doing what’s best for your customers, so when a customers asks you for, say, 20 beers, you always try your best to find the combination of 7-packs and 13-packs that will meet your customer’s thirst, for the least amount of hard-earned money – in that case, a 7-pack and a 13-pack.

To be extra clear, the goal is to find a combination of 7- and 13-packs containing at least as many bottles as requested, with a total number of bottles as close as possible to the amount requested.

But the unquenchable thirst of the population of Bizzarostan has been increasing lately, which is making your job harder. How would you know on top of your head what’s the best combination for a hundred bottles of Beer? Having great faith in the wonders of modern technology, you decide it’s time to write an application to find that ideal combination of beer packs.

I got a rather brute-force working solution already, which I will share in the next few days. This may be massive overkill, but that’s also a problem the Microsoft Solver Foundation can handle fairly easily, so we’ll look into that as well. I have this nagging feeling that there is an elegant recursive solution to the problem, but couldn’t write anything clever so far; if you have thoughts, please share them in the comments!

PS: no, I haven’t started working for a company that manufacture 7-packs of beers, it’s a transposition of a real-world, analogous problem.

PPS: I think this is also the closest I ever got to seeing a real application of the FizzBuzz problem in the real world.

Wrapping long-running Excel operations with IDisposable

When working with Excel, it is common to use small optimization tricks, like setting Excel.ScreenUpdating to false to avoid un-necessary screen refreshes, during lengthy operations – something along these lines:

public void DoJob(Worksheet  worksheet)
{
   var excel = worksheet.Application;

   var initialScreenUpdating = excel.ScreenUpdating;
   var initialCursor = excel.Cursor;

   excel.ScreenUpdating = false;
   excel.Cursor = XlMousePointer.xlWait;

   // do stuff

   excel.ScreenUpdating = initialScreenUpdating;
   excel.Cursor = initialCursor;
}

This is a good outline of what we would like to happen, but as is, this code has limitations. We would like to be certain that whenever we capture the state, the final two lines, which reset the state to what it was originally, are executed.

Create optimization programs dynamically with C# and the Microsoft Solver Foundation

In our last post, we explored how the Microsoft Solver Foundation can be used to solve simple maximization/minimization problems from C#. The problem we looked at is the following: given a set of products, each with a unit cost, a reselling price, and a weight, how can we maximize profit if we have only a limited budget and a limited weight capacity available.

Expressing and resolving the problem for a particular set of inputs was rather easy. However, the example we presented was very static: the decisions, the goal and the constraints were completely hard-coded.

The real value I found in the Microsoft Solver Foundation is that it can be completely integrated in your .NET code, working with strongly-typed objects. Today, we will revisit the same example we presented previously, but our goal will be to make the optimization program “generic”, so that we can resolve the same prototypical problem, given any set of inputs.

At a high level, what we are looking for is a class which, given a collection of Products, a Budget and a Capacity, returns a “recommended” purchase quantity for each product, maximizing our profit:

public class Profit
{
   public static IDictionary<Product, int> Maximize(
      IEnumerable<Product> products, 
      double budget, 
      double capacity)
   {
      // do stuff here
   }
}

Let’s first define what a Product is:

public class Product
{
   public Product(string name, double cost, double price, double weight)
   {
      this.Name = name;
      this.Cost = cost;
      this.Price = price;
      this.Weight = weight;
   }

   public string Name { get; private set; }
   public double Cost { get; private set; }
   public double Price { get; private set; }
   public double Weight { get; private set; }
   public double Margin
   {
      get { return this.Price - this.Cost; }
   }
}

First steps with the Microsoft Solver Foundation

While most of my posts tend to focus on software development, my background is in optimization. Unfortunately, I don’t get to use these two skillsets together too often, because most projects require fairly basic modeling, and because the tools they require do not always integrate well together.

Luckily, the project I am currently working on involved performing some optimization, from within a .NET application, which gave me an opportunity to investigate the Microsoft Solver Foundation, which comes with a free solver and provides a framework for leveraging existing commercial solvers.

What is a solver? In a nutshell, it is an algorithm designed to identify optimal input values to maximize a function, while satisfying constraints. Certain classes of problems can be solved very efficiently using known algorithms, while others require the use of heuristics – but in general, if you find yourself asking “what is the best combination of values for this situation”, chances are, a solver is the tool you should be using.

Rather than go into theory, let’s look at an illustration, which will hopefully give you a sense for what the Microsoft Solver Foundation can do for you, and how you can leverage it in your .NET applications.

The problem: cheap imports from Gadgetistan

Imagine the following situation. You are an enterprising individual, and realize that there is good money to be made by importing goods from the Republic of Gadgetistan, the neighboring country. You break the piggybank, invest in an old truck, drive over there and get ready to buy a truckload of the local specialties, Widgets, Sprockets and Gizmos.

The truck didn’t come cheap, so you have only 200 Rublars (the official currenty of Gadgetistan) left in your wallet – this is your Budget Constraint.

The truck user manual is very clear – the Capacity of your truck is 500 Kilograms. One pound more, and your wonderful truck could collapse in a sad heap of scrap metal. This is your Capacity Constraint.

A bit of market research yielded the following information about the main product: the buying Cost, the reselling Price, and the Weight for a unit of each of the main goods from Gadgetistan.

| **Cost (Rublars)** | **Price (Rublars)** | **Weight (Kgs) --- | --- | --- | --- **Widget** | 10 | 30 | 50       **Sprocket** | 15 | 30 | 20       **Gizmo** | 25 | 60 | 80  

Your problem at that point is simple: how many units of each product should you carry in your truck, to make the most of your trip?

FizzBuzz, the hard way

I have been digging into the Task Parallel library lately, and enjoying it a lot. As an exercise, I wondered if I could implement the classic FizzBuzz problem, using only Tasks, no loop-related keyword, and no method or property. To enforce this is, we’ll get FizzBuzz to run in the Main() method of a simple console, using only variables created locally.

Note: this is clearly a totally preposterous way to use the Task Parallel library. There is absolutely no benefit in using it in this context, I am doing this only for the sake of exploring how tasks work.

So how would we go about that? A Task represents an asynchronous operation; it wraps a block of code, waiting to be executed. For instance, the following code queues up work to print out “Starting” to the console, and begins execution when we request the Task to start:

private static void Main(string[] args)
{
   var rootTask = new Task(
      () =>
         {
            Console.WriteLine("Starting");
         });
   rootTask.Start();
   Console.ReadLine();
}

We clearly need something more for FizzBuzz. If we want to avoid looping constructs, we need to have a form of recursion going on, so that we can work on increasing integers, until we reach the limit we set to our FizzBuzz.

Fortunately, Tasks are about more than simply executing a block of code; they can be composed, defining what tasks can be started when some precursor tasks are finished. In particular, Tasks allow Continuations: what to do once a specific task terminates can be defined, by using Task.ContinueWith(), as in this example:

private static void Main(string[] args)
{
   var rootTask = new Task(
      () =>
      {
         Console.WriteLine("Starting");
      });

   var nextTask = new Task(
      () =>
      {
         Console.WriteLine("Next task!");
      });

   rootTask.ContinueWith(it => nextTask.Start());

   rootTask.Start();
   Console.ReadLine();
}

Here we define our root task, still printing “Starting”, and another task, which will print “Next task!”, and we pass that nextTask as a follow-up task to the rootTask via ContinueWith. Running this code will execute first the rootTask, and upon completion, kickstart the second one, and print both expected lines to the Console.