Artikel getaggt mit ‘Linear programming’

Oktober 24th, 2012

Solving the Transportation Problem (3) – MSF API in .NET

Solver Foundation in C#. Net

In order to solve the above described instance of a Transporation problem we only need a C# Console Application with a few lines of code. So start your IDE (SharpDevelop or Visual Studio [Express Edition will work either]) and create a new console application project. Then add a reference to the Microsoft.Solver.Foundation.dll under „References“. This DLL should be found after the successful installation of MSF in „C:\Program Files\Reference Assemblies\Microsoft\Framework\.NETFramework\v4.0\“. As we are using Data (DataTables, DataSets) you also need to reference „System.Data“.

The agenda for the current article is the following:

  • load the OML model into Solver Foundation Context
  • retrieve data from our sample Access Database
  • bind data to the model
  • solve the problem
  • print out minimized total result and the amount of flow of each arc

So here we go with the first section of our class.

using System;
using System.IO;
using System.Data;
using System.Data.OleDb;
using Microsoft.SolverFoundation.Services;

namespace GSharpBlog.Optimization.TP_Example 
	class Program
        /// Gets results of a SQL query through a OLE-DB connection.
        private static DataSet getDataFromDB(string connectionStr, string query)
            DataSet ds = new DataSet();
            OleDbDataAdapter adapter = new OleDbDataAdapter();
            OleDbConnection conn = new OleDbConnection(connectionStr);
            try {
                adapter.SelectCommand = new OleDbCommand(query, conn);
                return ds;
            catch (Exception ex){ throw ex; }
            finally{ conn.Close(); }

First we state a helper method for retrieving data from our Access Database, that simply takes the Connection String and the SQL query and returns a DataSet. After that we can go on with the automatically generated Main() method in which all code is written for the sake of simplicity.
In the following lines of code we define the above stated OML model as string and read it into the Solver Foundation Context. Then the structure of the supply, demand and arcs table (or OD-Matrix) are defined as DataTables.

            // Access (2007) DB ConnectionString
            string connectionStr = @"Provider=Microsoft.ACE.OLEDB.12.0;Data Source=D:\tp.accdb";

			// Transportation Problem as OML model
			string strModel = @"Model[
					TotalCost == Sum[{i,Source},{j,Sink},Cost[i,j]*flow[i,j]],
                    Foreach[{i,Source}, Sum[{j,Sink},flow[i,j]]<=Supply[i]],
					Foreach[{i,Source}, Sum[{j,Sink},flow[i,j]]>=Demand[j]]],
				Goals[Minimize[TotalCost]] ]";

			// Load OML-Model
			SolverContext context = SolverContext.GetContext();
			context.LoadModel(FileFormat.OML, new StringReader(strModel));
			context.CurrentModel.Name = "Transportation Problem";

			// Create Tables
			// Supply table
			DataTable pSupply = new DataTable();

			// Demand table
			DataTable pDemand = new DataTable();

			// OD-Matrix
			DataTable pCost = new DataTable();

Then data is pulled out of our Access Database and loaded into the DataTables. Now we can use the helper method getDataFromDB().

            //// Fill tables
            // 1. Fill Supply
            string query = String.Empty;
            DataSet accessDS = new DataSet();
            query = "SELECT SupplyNode, Supply FROM Supply ORDER BY SupplyNode";
            accessDS = getDataFromDB(connectionStr, query);

            foreach (DataRow row in accessDS.Tables[0].Rows) {
                pSupply.Rows.Add(row[0].ToString(), row[1]);

            // Clear
            query = String.Empty;

            // 2.Fill Demand
            query = "SELECT DemandNode, Demand FROM Demand ORDER BY DemandNode";
            accessDS = getDataFromDB(connectionStr, query);

            foreach (DataRow row in accessDS.Tables[0].Rows) {
                pDemand.Rows.Add(row[0].ToString(), row[1]);

            // Clear
            query = String.Empty;

            // 3. Fill Arcs (or OD-Matrix)
            query = "SELECT SupplyNode, DemandNode, Cost FROM Arcs ORDER BY SupplyNode";
            accessDS = getDataFromDB(connectionStr, query);

            foreach (DataRow row in accessDS.Tables[0].Rows) {
                pCost.Rows.Add(row[0].ToString(), row[1].ToString(), row[2]);

Now we bind the data to the OML model that we have defined earlier. Microsoft Solver Foundation has an advanced binding mechanism that is pretty straight forward. With the following lines, we bind the data from our tables to the OML model: loop through the parameters in the model and simply call the method SetBinding([DataTable].AsEnumerable(), [ValueColumnName], [IDColumnName]) for each parameter.

			// Bind values from tables to parameter of the OML model
			foreach (Parameter p in context.CurrentModel.Parameters)
				switch (p.Name)
						case "Supply":
							p.SetBinding(pSupply.AsEnumerable(), "Supply", "SupplyNode");
						case "Demand":
							p.SetBinding(pDemand.AsEnumerable(), "Demand", "DemandNode");
						case "Cost":
                            p.SetBinding(pCost.AsEnumerable(), "Cost", "SupplyNode", "DemandNode");

Then we just have to call the Solve() method and fetch the result. Now we loop through the decisions of the model, look for the decision „TotalCost“ and fetch the value of the optimized result.

			// Call solver
			solution = context.Solve();

			// Fetch results: minimized total costs
			Report report = solution.GetReport();	
			double cost = 0;
			foreach (Decision desc in solution.Decisions) {
				if (desc.Name == "TotalCost")
						foreach (object[] value in desc.GetValues()) {
							cost = Convert.ToDouble(value[0]);

Because we want to know not only the optimized total costs but also the amount of flow between each supply node and demand node we have to query the solution more detailed. We get information about the source/sink-pairs about the amount of flow from MSF – but we lack the distance (or cost) between each pair. So we need to lookup the distances in the original arcs table.

// Print out optimized results
string result = String.Empty;
double totalFlow = 0.0;
foreach (Decision desc in solution.Decisions) {
	// flow as variable
	if (desc.Name == "flow")
		foreach (object[] value in desc.GetValues()) {
			string source = value[1].ToString();
			string sink =  value[2].ToString();
			double flow = Convert.ToDouble(value[0]);

			// lookup km from arcs table
			DataRow[] rows = new DataRow[1];
			rows = pCost.Select("SupplyNode ='"+source+"' AND DemandNode ='"+sink+"'");
			double km = Convert.ToDouble(rows[0]["Cost"]);
			string sourceSink = String.Format("{0}_{1}", source, sink);
			if(flow != 0)
				totalFlow += flow;
				result = result + "\n" + String.Format("\"{0}\";\"{1}\";\"{2}\";{3};{4}",
													   sourceSink, source, sink, flow, km);

The optimized result is 46. Our solver application prints out the following results.

Total result: 46


Download as IDE-Project (SharpDevelop/Visual Studio 2010)

4 Leute mögen diesen Artikel.

Oktober 24th, 2012

Solving the Transportation Problem (2) – Microsoft Solver Foundation

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:

  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.

3 Leute mögen diesen Artikel.

Juli 5th, 2012

Solving the Transportation Problem (1) – Theory


Every GIS-professional has probably heard of networks (e.g. streets or rivers) and the widely applied shortest path algorithm which finds the cheapest (time, length or whatever you specify as „cost“) route from point A to B. Converting line features into some network data structure and performing shortest path calculations is a common task in the geospatial world. But in the past few months I found out that there is a lot more than this to discover!

If you want to do a little more than finding shortest routes, e.g. minimizing the overall shipping costs from several factories to several stores and satisfying both supply and demand you would not find any tool in your everyday GIS toolbox that allows you to set up such a model. Need it though? Or just interested how to solve this problem? Well read on…

Theory: Network Flows

First you’ll need a little bit of background information about network flows. We’ll leave the regular world of GIS now for a while and dive into the world of graphs and – beware! – mathemathics. Afraid? Common, it’s not too tricky..

TP Example

A simple instance of a TP

The example mentioned in the introduction is called „Transportation Problem“ (TP). This simple form of a network flow model was first described by HITCHCOCK (1941).

There are supply nodes (or sources, e.g. factories) and demand nodes (or sinks, e.g. stores) which are connected through arcs. All nodes carry data about how much flow (e.g. goods) shall be shipped resp. received. Supply is usually noted with positive numbers, demand with negatives.

Each arc is defined through its connecting nodes (e.g. Arc1: {S1,D1}, Arc2: {S1,D2} etc.). Additionally each arc has a cost attribute (e.g. km). In the simple instance on the right the cost for traversing each arc is noted in brackets (e.g Arc1: {S1,D1} : Cost 3 ). Note that the cost information is per flow, i.e. shipping one unit of goods from S1 over Arc1 to D1 costs 3 units. More important is the concept of flow at the nodes level. In Reality you ship packets of goods and not single goods. Theses packets are transfered as one flow and the shipping of one packet will cost the given cost on the certain arc.

An example from forestry will clarify the concept of flow. There is 150 cubic meters of wood at Node S1 that must be shipped. But you wouldn’t call a transportation company to ship each single cubic meter out of supply node S1. You would pack them together in packets of 30m³, because this is the maximum load for one truck. As a result the amount of flow is not 150m³ but 5 (150/30). Of course the same procedure must be considered on the demand side. Node D1 has a demand of 7 flow units, which corresponds to 7*30m³ = 210m³.

„Well“ you could say, „I know all that. Except for this flow concept – I’m familiar with arcs ’n‘ nodes and cost attributes. I’m a GIS professional! So what?“

Transportation Problem as LP

OK, now it’s time for some maths. A network flow model can be expressed as a set of mathematical equations. Often you can formulate a network flow model as a Linear program (LP). The Transportation Problem can be stated as seen on the left, which can be read as:


„Minimize the total cost of flow (x) over the arcs (ij) holding the costs (c) and respect the following:

-> flow (x) is always lower or equal the supply (s) of each supply point
-> flow (x) is always greater or equal the demand (d) of each demand point
-> flow (x) must be greater or equal zero“




The network graph of the simple instance of the TP can also be written as a matrix. Using that matrix you‘ ll understand the formulations of the sum equations better. If you write down the first sum equation for our TP instance you’ll get the following:

min = 3x11 + 1x12 + 4x21 + 2x22 + 4x23 + 3x32 + 3x33

TP as Matrix

x11 + x12 = 5
x21 + x22 = 5
x23 + x32 + x33 = 3

x11 + x21 = 7
x12 + x22 + x32 = 3
x23 + x33 = 5

xij >= 0

Now go and find the best value for x and the minimum equation and respect all other equations. This is the task of a linear program solver. In this peticular case the optimum value for the Transportation Problem is 46 (min = 46). This is the minimized overall shipping cost satisfying all demands with the supply. The value of x (flow) will vary on each arc. Of course a solver package is able to return both the minimized optimum and the amount of flow through each arc.

So this is a Linear Program which cannot be solved in a regular GIS package. There are specialized Solvers in GIS packages (e.g. the TSP-Solver in GRASS GIS or various solvers of Network Analyst in ESRI ArcGIS) but they are not able to solve a plain Linear Program such as the Transportation Problem. So you need another software package. But you’re lucky – there are many solvers available for linear programs – both commercial or free ones (list).

Now you might have an idea of what linear programming in context of networks basically is. The next challenge is to get the mathematical equations of a model into some linear solver package.



2 Leute mögen diesen Artikel.