#### Solvers, Optimization, and more on DSLs

To coincide with the release the CTP release of F# Microsoft also released and early version “Solver Foundation”. Don Box described himself as being elated by its release. You can tell it’s an early version as it’s currently the only way to get it is part of “F# Optimization Modelling Language” sample on the MSDN code gallery.

So what does optimization mean in this context? Simply put an optimization problem is the problem of finding the best solution from all feasible solutions. Or (slightly) more formally:

Given a function “f” which takes a value from set “A” and transforms it to a real number, find the element “x0” in set “A” which “f(x0)” is smaller (or greater) than “f(x)” where “x” is all other values in A.

Many problems from physics and mathematics can be modelled using this simple framework and much mathematical research has gone into finding the solution efficiently. For example the travelling salesman can be considered an optimization problem, our function “f” (often referred to as the cost function) is the cost of travelling between the nodes in the chosen order. Our set “A” is the set of all possible routes between the nodes. So it is an optimization problem because we are looking for the element in the set of all possible routes which makes our function “f” – the cost function – return the best (smallest/cheapest) value. Wikipedia currently has two articles on optimization that maybe merged in the future:

http://en.wikipedia.org/wiki/Optimization_(mathematics)

http://en.wikipedia.org/wiki/Optimization_problem

Solvers are pieces of software that aim to solve an optimization problem. To use a solver we generally have to describe the problem to the solver. So if we were trying to solve the travelling salesman problem to the solver we would have to input a description of all possible routes between the nodes in our graph and tell it how to compute the cost function for each element in the set of all possible routes. Depending on the API that the solver offers this might be ease or quite difficult. The Solver Foundation is a set of solvers implemented as a .NET library with a classical object model interface, the F# Optimization Modelling Language is a DSL that offers an alternative way to describe the your problem optimization.

The F# Optimization Modelling Language allows you to solve linear equations. Solving linear equations may sound quite easy, image we have the equation:

20.0 * sa + 15.0 * vz

You can pretty much straight away tell me the maximum value is infinity and the minimum value is negative infinity. If I add a simple constrain the variables “sa” and “vz”:

0 < sa < 500

0 < vz < 200

you can probably still easily tell me that the minimum value is 0 and the maximum is 13000 (20 * 500 + 15 * 200). However if we were to add more constrains and variables the problem would quickly become two difficult to solve with a pen and paper. The DSL uses a using a simplex solver “under the hood” and if you check out the Wikipedia article you can see the maths of this are quite challenging.

So how does the DSL work? The DSL re-interprets an F# quoted expression and inputs this into the SimplexSolver class which is available in the Microsoft.Solver.Foundation.dll. The quoted expression must have the form:

variable declarations

cost/goal function

constraints

More concretely an example of the syntax looks like this:

<@

let sa = var "SA"

let vz = var "VZ"

minimise (20.0 * sa + 15.0 * vz)

where

[

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.

]

@>

Here we can see we have two variables sa and vz and an we’re trying to find the minimum value of the equation 20.0 * sa + 15.0 * vz, at the end we have a set of constrains that the solution must conform to. As this is a quotation, it is a data structure rather than code, so it can be interpreted rather like a C# expression tree can. So the whole quoted expression is then passed to a function to be interpreted by making calls to the underlying object model exposed by the Microsoft.Planning.Solvers.dll and then hopefully solved. So to put you out of your misery the minimum value of this equation, give the constraints, is 92500.0 where SA = 2000.0 and VZ = 3500.0.

So why would be use a DSL to input this problem rather than using the classical object model? Well in short it’s simpler and easier to use. To illustrate this point I’ve rewritten the previous example as a C# program, which is clearly a lot longer, but worse than that it feels a lot more like programming, the meaning of our expressions is hidden in amongst lots of variable declarations and method calls:

static void Main(string[] args) {

SimplexSolver simplexSolver = new SimplexSolver();

int saId;

int vzId;

simplexSolver.AddVariable("SA", out saId);

simplexSolver.AddVariable("VZ", out vzId);

//0.3 * sa + 0.4 * vz >= 2000.;

int constraint1;

simplexSolver.AddRow("constraint1", out constraint1);

simplexSolver.SetCoefficient(constraint1, saId, 0.3);

simplexSolver.SetCoefficient(constraint1, vzId, 0.4);

simplexSolver.SetLowerBound(constraint1, 2000.0);

//0.4 * sa + 0.2 * vz >= 1500.;

int constraint2;

simplexSolver.AddRow("constraint2", out constraint2);

simplexSolver.SetCoefficient(constraint2, saId, 0.4);

simplexSolver.SetCoefficient(constraint2, vzId, 0.2);

simplexSolver.SetLowerBound(constraint2, 1500.0);

//0.2 * sa + 0.3 * vz >= 500.;

int constraint3;

simplexSolver.AddRow("constraint3", out constraint3);

simplexSolver.SetCoefficient(constraint3, saId, 0.2);

simplexSolver.SetCoefficient(constraint3, vzId, 0.3);

simplexSolver.SetLowerBound(constraint3, 500.0);

//sa <= 9000.;

simplexSolver.SetUpperBound(saId, 9000.0);

//vz <= 6000.;

simplexSolver.SetUpperBound(vzId, 6000.0);

//sa >= 0.;

simplexSolver.SetLowerBound(saId, 0.0);

//vz >= 0.

simplexSolver.SetLowerBound(vzId, 0.0);

//minimise (20.0 * sa + 15.0 * vz)

int goalId;

simplexSolver.AddRow("goal1", out goalId);

simplexSolver.SetCoefficient(goalId, saId, 20.0);

simplexSolver.SetCoefficient(goalId, vzId, 15.0);

simplexSolver.AddGoal(goalId, 1, true);

simplexSolver.Solve(new SimplexSolverParams());

double sa = (double)simplexSolver.GetValue(saId);

Console.WriteLine("SA: {0}", sa);

double vz = (double)simplexSolver.GetValue(vzId);

Console.WriteLine("VZ: {0}", vz);

double goal = (double)simplexSolver.GetValue(goalId);

Console.WriteLine("Goal: {0}", goal);

Console.ReadLine();

}

But at the end of the day I think it’s nice to of the choice of interface to have the choice of interface, especially as currently the F# Optimization Modelling Language only exposes a small sub-set of the Solver Foundation. Sometimes you’ll want to work with the lower level object model; often you’ll want to abstract this away to a DSL which allows you to describe the problem you’re solving rather than having to program it. Probably the most interesting job will be coming up with new DSL to describe specific optimization problems. Any one fancy writing a travelling salesman DSL?

Bookmark

dotnetkicks+,
digg+,
reddit+,
del.icio.us+,
dzone+,
facebook+

Print | posted @ Sunday, September 21, 2008 2:13 PM

## Comments on this entry:

# re: Solvers, Optimization, and more on DSLsThanks Robert!

# re: Solvers, Optimization, and more on DSLsAlexander Stojanovic (GM/MSF)

# re: Solvers, Optimization, and more on DSLsCheers,

Rob

# re: Solvers, Optimization, and more on DSLsRegards,

Alexander Stojanovic (GM/MSF)

## Your comment:

(Note: all comments are moderated so it may take sometime to appear)