Just saw that version 3.1 of Microsoft Solver Foundation has been released. I haven’t had time to try it out yet, but the list of improvements looks promising. A better non linear solver, better MIP and MIQP – sounds like Santa has come early! And I am curious about the faster bindings with LINQ…

In our last post, we looked at a Sieve-like algorithm to help a Brewery find how closely they can match the number of beer bottles their thirsty customers desire, using only 7-packs and 13-packs of delicious beer; in less appetizing but more precise terms, we are trying to solve the following problem:

Suppose that you are given a list of integers, and a target integer. Your goal is to find the closest value that is greater or equal to the target, by combining integers (“packs”) from the list (only positive combinations are allowed). For instance, given 3 and 5, the closest you can get to 16 would be 5 x 2 + 3 x 2 = 16, and the closest to 17 would be 3 x 6 = 18.

The Sieve solution is pretty effective, but has some limitations. Today, we’ll take another approach: leveraging the Microsoft Solver Foundation.

The beauty of the Solver is that it allows you to focus on what you want to achieve, rather than on how to achieve it. As long as you can define clearly what your **goal**, your **decision** variables and your **constraints** are, you can leave it to the Solver engine to figure out what the best way to achieve that goal is, by searching the best values for the Decision variables you defined.

So what are we trying to achieve here? Our goal, in Solver terms, is to minimize the extra number of bottles shipped, under the constraint that the number of bottles shipped is greater than the requested target number. Our Decision variables are the number of units of each Beer Pack we will ship, with a constraint that Decisions must be integer (we cannot ship half-packs), and positive.

Let’s add a reference to the Solver in our project (details here), and see how this looks like in code:

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

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?

## Comments

- How dense is the product of Sparse Matrices? (5)
- Testing and mocking your C# code with F# (5)
- Field notes from the F# tour (2)
- Throttling F# Events using the Reactive Extensions (3)

Comment RSSHow To Reverse Aging wrote: Hello, I enjoy reading all of your article. I want... [More]

thetaoofbadassus.tumblr.com wrote: I have read so many articles about the blogger lov... [More]

reverseagingprocess.newsvine.com wrote: Normally I do not read post on blogs, however I wo... [More]

How To Cure Herpes wrote: Thanks for finally writing about > Throttling F... [More]