Archiv für Oktober, 2012

Oktober 24th, 2012

GRASS GIS v.out.ogr vs ogr2ogr

In der aktuellen stabilen Version von GRASS GIS 64bit (6.4.2) ist der Export von Geodaten per v.out.ogr extrem langsam. Zum Glück gibts dafür eine schnelle Lösung: die OGR Tools.

Mit der Installation von OGR wird auch das Werkzeug ogr2ogr mitgeliefert. Und das kann sehr schnell auch Daten im GRASS GIS Format lesen und ein anderes Geodatenformat schreiben. Leider ist der Zugriff mit diesem Werkzeug auf die GRASS GISBASE nicht sehr umfangreich dokumentiert.

Dabei gilt folgendes Format des Exportbefehls:

ogr2ogr <OUTPUTSHAPEFILENAME>.shp <$GISBASE/<LOCATION>/<MAPSET>/vector/<LAYERNAME>/head <LAYERNUMMER> [-nlt <OGRGEOMETRYTYPE>]

Hier ein Beispiel, wie ein GRASS Layer in ein ESRI Shapefile vom Typ Multipolygon geschrieben wird.

ogr2ogr /home/GISDATA/shp/lakes.shp /home/GISDATA/GRASS/Bayern/testdata/vector/lakes/head 1 -nlt MULTIPOLYGON

 

Be the first to like.

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 {
                conn.Open();
                adapter.SelectCommand = new OleDbCommand(query, conn);
                adapter.Fill(ds);
                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[
				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[{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();
			pSupply.Columns.Add("SupplyNode",Type.GetType("System.String"));
			pSupply.Columns.Add("Supply",Type.GetType("System.Int32"));

			// Demand table
			DataTable pDemand = new DataTable();
			pDemand.Columns.Add("DemandNode",Type.GetType("System.String"));
			pDemand.Columns.Add("Demand",Type.GetType("System.Int32"));

			// OD-Matrix
			DataTable pCost = new DataTable();
			pCost.Columns.Add("SupplyNode",Type.GetType("System.String"));
			pCost.Columns.Add("DemandNode",Type.GetType("System.String"));
			pCost.Columns.Add("Cost",Type.GetType("System.Double"));

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;
            accessDS.Clear();

            // 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;
            accessDS.Clear();

            // 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");
							break;
						case "Demand":
							p.SetBinding(pDemand.AsEnumerable(), "Demand", "DemandNode");
							break;
						case "Cost":
                            p.SetBinding(pCost.AsEnumerable(), "Cost", "SupplyNode", "DemandNode");
							break;
					}
			}

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);
			}
		}
		Console.WriteLine(result);
	}
}

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

Total result: 46
**********************

„S1_D1″;“S1″;“D1“;5;3
„S2_D1″;“S2″;“D1“;2;4
„S2_D2″;“S2″;“D2“;3;2
„S2_D3″;“S2″;“D3“;2;4
„S3_D3″;“S3″;“D3“;3;3

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:

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.

3 Leute mögen diesen Artikel.