Solver Foundation

Microsoft’s Solver Foundation (http://code.msdn.microsoft.com/solverfoundation), not to be confused with the Solver Add-In for Excel, is a runtime for various types of mathematical problem solving. The download includes solvers for a number of specific types of problem (Linear Programming, Mixed Integer Programming, Quadratic Programming and Constraint Programming) and enables other 3rd party solvers to be plugged in to the runtime.

The provided solvers cover a more general area known as Operational Research, that roughly speaking is a set of mathematical approaches to find the best (or sometimes nearly the best) solutions to complex problems.

A typical example of a linear programming type problem might go something like this. A global manufacturing company has the capability to manufacture its products at a number of different factories in different countries, and these factories have different costs associated with the manufacturing process and different maximum production capacities. The goods produced need to be transported to their target markets (again there will be different shipping costs for each factory/market combination) and there are forecasts for the amount of each product that will be sold in each market. The problem is to try and minimise the costs involved and therefore maximise profits.

An example of a constraint problem might look like this. You have a set of servers with a range of specifications covering things like; memory, number of processors, disk space, installed web server, installed database server. You also have a set of applications that need to be deployed, and each application has a set of requirements in terms of memory usage, processor usage, disk space, web server and database server. You need to work out which applications should be installed on which machine, possibly taking into account other constraints such as application A cannot be on the same machine as application B, and applications C and D must be installed together.

One of the interesting samples included in the download applies this type of problem solving to search by implementing a guided search mechanism. For example an online retailer sells laptops which can be categorised in different ways; by price, brand, weight, operating system, memory, disk space, processor, extended warranty, rating, etc. The problem in providing a search facility to customers where they can select values for any of these criteria is that many combinations won’t return anything at all, making people think (wrongly) that the choice offered by the site is limited. Guided search solves this problem by limiting the available options based upon previous selections, so for example if I selected price under £1,000 and weight under 2kg I would find that my choice of brands and disk capacity had been limited. Notice that you can’t use a hierarchy to structure your data as you’ve no idea which criteria the user is going to start with as the basis of their search.

So how does this all work with Solver Foundation? The first step is to express the problem as a model, using a modelling language called OML which looks like this:

Model[
  Decisions[
    Reals,
    SA, VZ
  ],
  Goals[
    Minimize[ 20 * SA + 15 * VZ ]
  ],
  Constraints[
    0.3 * SA + 0.4 * VZ >= 2000,
    0.4 * SA + 0.2 * VZ >= 1500,
    0.2 * SA + 0.3 * VZ >= 500,
    SA <= 9000,
    VZ <= 6000,
    SA >= 0,
    VZ >= 0
  ]
];

 

The decisions are the data we’re working with, the goals are our targets and the constraints are the limitations we have to work with. Translating your real world scenario to this kind of model can take a bit of thought!

The model can then be solved using one of three techniques:

1. It can be passed to a command line utility.
2. It can be processed by an Excel add-in (not the Solver Add-in that comes with Excel) that enables you to bind cells to the model for both input and output.
3. It can rewritten to a .NET managed API that enables finer control over the solver and binding input and output data via LINQ.

The important point to take away from this is that you don’t have to solve the problem, you do need to express the problem using the modelling language and possibly bind the model to external data.