Archiv für März, 2013

März 31st, 2013

Solving the Minimum Cost Flow Problem (2) – Software

I don’t want to give you a complete overview of MCFP solvers because I just dipped into the world of linear and network flow programming. Instead of this I just want to mention a few MCFP solvers that I have tested. Python will be the programming language for the test – so I checked solvers with the corresponding language bindings.

Linear program solvers

As mentioned in the previous article one can solve MCFP also as ordinary linear programs. So here are the two packages I tested.

 

lpsolve is a Mixed Integer Linear Programming (MILP) solver written in C released under the LGPL. You can use lpsolve on Windows and Linux systems. For windows there is a nice GUI which is called LPSolveIDE. It reads several LP file formats such as *.mpl, *.lp and also the DIMACS file format which is used for network flow problems. Furthermore it has a rich API: you can use lpsolve with .NET (there is even a lpsolve plugin for Microsofts Solver Foundation MSF!), Java, PHP and Python.

 

PuLP is kind of a python wrapper for various (LP) solver packages released under the MIT license:

 PuLP is an LP modeler written in python. PuLP can generate MPS or LP files and call GLPK (http://www.gnu.org/software/glpk/glpk.html), COIN (http://www.coin-or.org/), CPLEX (http://www.cplex.com/), and GUROBI (http://www.gurobi.com/) to solve linear problems.

 

Specialized MCFP solvers

As the MCFP is a special linear program that can be solved more efficiently with algorithms that exploit the network structure you should also have a look at specialized solvers around.

 

NetworkX is a pure Python library that deals with graphs:

NetworkX is a Python language software package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks (http://networkx.github.com/).

The API is not very hard to learn, it’s well documented and obviously there is a active user community. NetworkX is released under the BSD license. It offers algorithms for many graph related issues (complete list here):

  • Clustering
  • Shortest Paths (Dijkstra, A*, Bellman-Ford, Floyd-Warshall)
  • Network flows (Minimum cost flow, maximum cost flow, minimum cut, Maximum flow minimum cost)
  • Minimum spanning tree

 

Google or-tools are a set of tools that deal not only with graph structures and algorithms but also with various other issues related to Operations Research (OR). This package is released under the Apache 2.0 license:

This project hosts operations research tools developed at Google and made available as open source. The project contains several tools:

  • A Constraint Programming solver.
  • A wrapper around third-party linear solvers (GLPK, CLP, CBC, SCIP, Sulum).
  • Knapsack algorithms.
  • Graph algorithms (shortest paths, min-cost flow, max flow, linear sum assignment).

Everything is coded in C++ and is available through SWIG in Python, Java, and .NET (using Mono on non-Windows platforms) (http://code.google.com/p/or-tools/).

Ok that’s it for now – let’s dive into the API of the packages in the next articles..

1 andere Person mag diesen Artikel.

März 24th, 2013

Solving the Minimum Cost Flow Problem (1) – Intro

Minimum cost flow problem: a short description

The Minimum cost flow problem (MCFP) is a generalized network flow problem that describes the goal of minimizing the total cost of flow through a network made of arcs and nodes which contains source, sink and transshipment nodes.

The minimum-cost flow problem is to find the cheapest possible way of sending a certain amount of flow through a flow network. Solving this problem is useful for real-life situations involving networks with costs associated (e.g. telecommunications networks), as well as in other situations where the analogy is not so obvious, such as where to locate warehouses (http://en.wikipedia.org/wiki/Minimum-cost_flow_problem).

Source nodes emit flow while sink nodes absorb flow. The flow through transshipment nodes is only intermediate: inflow must be equal to outflow at these nodes: so the net flow at these nodes is zero. Additionally there are maximum flow capacities on each arc of the network, i.e. it is not allowed that the amount of flow through a certain arc exceeds the maximum capacity specified on this arc.

In the following picture node 1 has 4 units of supply (= source node with positive value), node 4 has 4 units of demand (sink node with negative value) while nodes 2 and 3 are only transshipment nodes with a supply of zero. On the arcs you find lower flow bounds, upper flow bounds (or capacities) and costs. The goal is to ship 4 units from node 1 to node 4 with the lowest costs and without violation of the flow constraints (lower and upper bounds on the arcs).

Instance of a Minimum Cost Flow Problem

Instance of a Minimum Cost Flow Problem (http://lpsolve.sourceforge.net/5.5/DIMACS_mcf.htm)

The Minimum cost flow problem can be seen as a general problem from which various other network flow problems can be derived:

  • Transportation problem
  • Transshipment problem
  • Assignment problem
  • Shortest path (tree) problem

A special case of the Minimum Cost Flow Problem is the famous transportation problem (TP). In a regular TP the network lacks transshipment nodes and capacities on the arcs. So it’s a simpler version of the MCFP. The transshipment problem comes with transshipment nodes but lacks capacities on the arcs of the network. The assignment problem is a special version of the transportation problem and you can even solve a shortest path (tree) problem as a MCFP. Read more on the theoretical background here.

So in short: if you have a MCFP-Solver at hand you are able to solve various problems with this package.

The assignment problem is a special case of the transportation problem, which is a special case of the minimum cost flow problem, which in turn is a special case of a linear program. While it is possible to solve any of these problems using the simplex algorithm, each specialization has more efficient algorithms designed to take advantage of its special structure (http://en.wikipedia.org/wiki/Assignment_problem).

As stated in this quote and in previous articles, you can describe and solve a MCFP as a Linear program with an ordinary LP solver package. The simplex algorithm will likely be applied in this case. Or you can speed up things (magnitudes faster!) with a solver that is specialized on network flow problems and exploits the network structure of the MCFP: a network simplex solver or the push-relabel algorithm.

More on this in the next articles..

2 Leute mögen diesen Artikel.

März 6th, 2013

Linux 64Bit auf Samsung P560

Seit geraumer Zeit nutze ich Ubuntu und OpenSUSE 64Bit auf meinem Samsung Notebook P560. Die Installation funktionierte jedoch – egal welche Distribution – immer nur, wenn beim Starten des Kernels die Option ‚acpi=off‘ gesetzt wurde.

Damit ließ sich Linux auch auf dem Notebook installieren. Allerdings störte mich folgendes immer mehr:

  • beim Anschluss des Stromkabels im laufenden Betrieb stürzte das System ab
  • auch beim Entfernen des Stromkabels gab es jedes Mal einen Reboot (beide Fälle wohlgemerkt mit vollem Akku..)
  • das Betätigen der Funktionstasten zur Helligkeitseinstellung des Bildschirms (Fn) führten zum Absturz
  • das Samsung Galaxy Tab wurde nicht per mtpfs erkannt
  • der SD-Slot wurde von Linux nicht erkannt

Nach einigem Suchen fand ich immer wieder den Hinweis auf ein möglicherweise veraltetes BIOS. Meine Version war 10LU. Samsung bietet für den P560 auch ein BIOS Update an: das 11LU. Leider gibt es die Software zum Flashen des BIOS nur für Windows.

Also Windows starten, das Update von Samsung runterladen, BIOS flashen mit der Software und neustarten. So einfach sollte es eigentlich sein. Leider stellte sich dann nach etlichen Versuchen, die alle mit der Medung „Fehler: Treiber konnte nicht geladen werden“ abgebrochen haben heraus, dass man die Software unter Windows 7 mit dem Kompabilitätsmodus für Windows XP ausführen muss. Und siehe da: es funktionierte.

Seit ich das BIOS in der Version 11LU drauf habe, funktioniert auch Linux 64Bit mit ACPI wunderbar. Keine Abstürze mehr. Und es ist nun ein vollwertiges Notebook. Auch das Samsung Galaxy Tab wurde nun von den mtpfs-Tools erkannt.

Ab jetzt wird bei mir Windows  sein Dasein endgültig in einer virtuellen Gast-Maschine fristen..

3 Leute mögen diesen Artikel.