Microsoft Solver Foundation
Solver packages either offer APIs for various programming languages or a mathematical modeling language. And there are also some industry standard file formats of linear programs like *.MPS or *.LP which carry both the mathematical model and the data while modeling languages such as AMPL or OML allow the formulation of the model only without data. Additionally solver packages supporting a modeling language provide a binding mechanism for model and data.
Microsoft offers a Optimization programming library which is called Microsoft Solver Foundation (MSF). This product fits perfectly into the .NET programming environment and offers various solvers (e.g. linear, non-linear and goal programming), a .NET API and its own modeling language: OML.
You are allowed to download a limited copy of MSF (Express Edition). The important limitations of this copy are:
- restricted to 50’000 variables when you’re using the MIP-Solver
- you are allowed to install MSF on one single client only for commercial and productive use
So for prototyping you can go with the Express Edition of MSF. For professional use you would have to license the Standard or Professional Version.
Furthermore Microsoft Solver Foundation offers an interface to third-party solvers. This means you can stay in this optimization framework with the advantage of its tight integration in the .NET environment using your preferred solver – prodividing it conforms to the interface of MSF. With Solver Foundation 3.1 the following third-party-solvers are supported: CPLEX (IBM), Xpress (FICO), Gurobi, LINDO, lp_solve (Open Source), MOSEK, Ziena and Frontline Systems.
And there is a Excel-Plugin for Solver Foundation which allows you to write your models in OML, feed them with data and solve them. This is useful for fast prototyping and for testing your models – although it lacks debugging features of models – because your can focus on data and the mathematical model and you don’t have to worry about programming in .NET. Take a look at the paper of Erwin at Amsterdam Optimization for more info about MSF, OML and the Excel-Plugin of Solver Foundation.
Hands on!
Now we’ve had the theory of the Transportation problem (1) and we have got a software package that should solve such problems.
First we need data. The simple instance of the Transportation problem in the previous article can be represented in a simple Microsoft Access Database like the this:
With the following content of its tables:
Note, that in the values in the demand table are signed positive in contrast to the common modeling convention stated in the previous article.
Now we have to build the model in our solver environment. I’m not able to give you a comprehensive introduction into the syntax of OML. Have a look at the paper of Erwin at Amsterdam Optimization for further study here.
So the ingredients for the transportation solver are: data, a model and the solver. As we’ve got data in our Access Database, we’ll have a look at the model. Erwin has transformed the mathematical formulation of the transportation problem into a OML-model which looks like this:
Model[
Parameters[Sets,Source,Sink],
Parameters[Reals,Supply[Source],Demand[Sink],Cost[Source,Sink]],
Decisions[Reals[0,Infinity],flow[Source,Sink],TotalCost],
Constraints[
TotalCost == Sum[{i,Source},{j,Sink},Cost[i,j]*flow[i,j]],
Foreach[{i,Source}, Sum[{j,Sink},flow[i,j]]<=Supply[i]],
Foreach[{j,Sink}, Sum[{i,Source},flow[i,j]]>=Demand[j]]],,
Goals[Minimize[TotalCost]] ]
In this case OML is relatively close to the mathematical formulation of the problem. Just a few explanations:
- first you define the fixed data of the model (called „parameters“ in OML) and their value domains (e.g. Reals)
- then you define the variables (i.e. their values can be changed in the optimizatin process, called „decisions“)
in this case the flow between source and sink nodes shall be changed until the total cost is minimized - our constraints of the model are
- the supply that is being shipped from each supply node must be less or equal the given supply at each suppl node
- the demand that shall be fulfilled at each demand node must be greater or equal the given demand at each demand node
- our goal is the shipping of all goods from supply to demand nodes while minimizing the total shipping costs
Now there is a speciality about OML. OML in MSF 3.1 cannot handle sparse data. But in real networks sparse data is very common. In the OML model above MSF will expect all possible combinations of source and sink nodes and will throw an error if not all combinations exist in the data. There are two possibilities to get around this problem:
- change the data with pseudo entries so it is not sparse anymore
- change the model
The simple way to get things work is to change the data. We have to add the missing combinations (S1;D3 and S3;D1) in the arcs table and put an arbitary high amount of cost in comparison to the rest of the data (e.g. 99999) so that the solver would never take these pseudo arcs into account.
Of course under real time conditions this would not always be the way to solve the problem of sparseness. A better but more complex solution would be to change the model.
Now as we have data and the model we’re talking to the solver in the next article.