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):
- 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..