Artikel getaggt mit ‘Solver’

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.

Juli 5th, 2012

Solving the Transportation Problem (1) – Theory

Introduction

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.