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?
Feedback:
Feedback was imported from my only blog engine, it's no longer possible to post feedback here.
re: Solvers, Optimization, and more on DSLs - Al
Finally after a month somebody actually writes about how to use this stuff. You have to wonder with the state of the documentation and examples if they really want anybody to use the solver...
Thanks Robert!
re: Solvers, Optimization, and more on DSLs - Alexander Stojanovic
The CTP of Microsoft Solver Foundation that just shipped on Monday and which is available at http://code.msdn.microsoft.com/solverfoundation comes with full documentation, models and sample projects in several CLR languages (C#, F#, IronPython) as well as a full Excel2007 Designer Add-in so that you can model and solve from within Excel (with nice declarative data binding to cells/ranges/worksheets). It incudes programming against what we term the "Solver Foundation Services" layer or against the low-level solver APIs. The SFS gives you nice features liek LINQ data binding and automatic parallelism of your model solving using declarative mechanisms (called directives). Try it out. The installer puts all of the docs, models, and samples in your My Documents folder under "Microsoft Solver Foundation" including a step by step guide to using the Excel Add-in.
Alexander Stojanovic (GM/MSF)
re: Solvers, Optimization, and more on DSLs - Robert Pickering
Yes, I've already downloaded the new version and agree the documentation is much better! It looks like the start of a nice product.
Cheers,
Rob
re: Solvers, Optimization, and more on DSLs - Alexander Stojanovic
Thank you for the kind words Rob. The team appreciates all feedback. Your article was very well done. We'll be interested in your experiences using OML (Optimization Modeling Language) which is a super-set of the F# DSL (that our colleague Ralf Herbrich did a superb job on btw). You can try it out in the Excel Add-in Designer and lay with OML directly or via the Object Model in C# and other languages. The object model is a type safe way of programming with Solver Foundation but essentially exposes a (nearly) isomorphic version of OML. The only difference being the way we perform data binding in Excel (using cell/range/worksheet binding) versus in a NETfx solution (LINQ).
Regards,
Alexander Stojanovic (GM/MSF)