Multicommodity network flow in Java

Leave a Comment
0 Flares Twitter 0 Facebook 0 LinkedIn 0 Filament.io Made with Flare More Info'> 0 Flares ×

Problem Statement

In a previous post I presented an approach to solve the shortest path problem using different implementations of algorithms. The shortest path problem is a classic and important combinatorial optimisation problem. It often appears as a subproblem when solving difficult combinatorial problems like the multicommodity network flow (MCNF) problems.

The problem is to route a set of demands (commodities) through a network1 with limited arc capacities. The inherent assumption with the following implementation is that the commodities can be shipped in fractions, hence are divisible.

The technique that is implemented in the Java code is the Column Generation a.k.a. the Dantzig-Wolfe Decomposition. This technique has many applications to practical problems. For instance routing data packets through telephone networks, routing electricity demand in power grids, routing vehicles on the road network, allocating airline crews to flights, production scheduling and planning, etc.

The column generation algorithm can be interpreted as applying the Simplex Method to a Linear Problem with a huge number of columns. Only a few columns are present at the start, other columns are generated when needed.

Problem Example

Taking the small network shown below as an example, we can state that all edges are bidirectional with a cost of 1 and a total capacity of 2.5 (D-F has 2.6)

If the commodities:

  • A-F: 3 units
  • e-D: 2 units
need to be shipped, then arc C-D is overloaded. This problem could be solved as a standard Linear Programming (LP) constraint problem, using an LP solver, but it becomes intractable and inefficient when dealing with huge networks.
This is why column generation, by creating paths on a need to have basis and decomposing the problem into smaller sub-problems, provides a much better and more efficient solution.

Implementation

The Java code will solve both the small network problem shown above as well as the UK transport network shown below.
with commodities: INV-DOV: 1.5 units, EDI-PLY: 2 units.
The requirements of the assignment were to read a data file of specific format, construct the graph, perform the D-W algorithm to find the solution to the MCNF problem and report for each commodity the routing by which it is shipped and the cost of shipping via that route, and also in the case of fractional shippings report the paths along with the percentage of commodity using them.
For this work the Graph.java was provided (although there is an implementation of it with the PERT article) and also a wrapper for the LP solver library was provided.
In order to be able to succesfully run this code you’ll need to install the lp_solve library and access it via the LP class wrapper, in order to pass the LP problem to the solver and get the optimal value for the solution. The library used is lp_solve 5.5, which is implemented in C and offered under a GNU LGPL licence2.
As usual you can find the complete code on Github.


References

1. The network in the present example is defined as a graph V, which is a set of vertices V= {1,…n}.

It also includes a set j in E of (directed) edges specified by a start and end verted and also the cost and cpacity of each vertex: Cj, CAPj.

Finally a set i in C of commodities which is given by the source and target of each commodity: Si, Ti, and the demand Di.

2. You can find the library at http://lpsolve.sourceforge.net. To use it on Windows you need to copy the shared libraries lpsolve55.dll, lpsolve55j.dll as well as the interface lpsolve55ja.jar into the project workspace.

To compile use:

javac -cp lpsolve55ja.jar;. Mcnf.java

To run the program use:

java -cp lpsolve55ja.jar;. Mcnf

Remark

For OSX you’ll needto compile from source. Change to the lib/mac directory and edit the file build_osx. Change the directory paths as indicated in the comments. Follow the compilation instructions to get the binaries of the solver

0 Flares Twitter 0 Facebook 0 LinkedIn 0 Filament.io Made with Flare More Info'> 0 Flares ×