{ inercia }

Maximum flow problems

The last project where I’m was involved, NetStitcher, went around an old optimization problem, the Maximum Flow problem. In this kind of problems, you try to make the most of a “transport” network by optimizing the amount of resources that can traverse it. Imagine a regular rail network where you want to know the maximum number of trains that can cross it at the same time. We can add additional constraints to the problem, the most common is that not all trains have the same priority, as some of them carry very valuable goods (ie, people, oil …) while some other trains are not so important…

In fact, this family of linear programming problems was first introduced by russian mathematicians who were looking for the optimal routes for moving goods by train from different parts of Russia, specially from the West to the East coast. Optimizing these movements was an important economic problem: which train should move first, which one should wait, where and for how long, etc, taking into account time constraints, priorities and so. A good solution could result in huge gains, while the wrong movements could lead to big losses.

You can read on this on the history of the transportation and maximum flow problems, but you can obtain a more formal description of this problem on these two chapters of Practical Optimization: A Gentle Introduction book. A specialization of this problem, the Max-flow min-cut, tries to reach the same goal but using the smallest group of nodes.

There are several libraries in Python for solving this type of linear programming problems in an efficient way. CVXOPT is a well known library, internally optimized by using BLAS and LAPACK, and with a more user-friendly abstraction called CVXMOD.

There is also pplp, a high-level interface on top of the glpk linear programming library, where you can build optimization problems symbolically, like this:

lp = LinearProgram()
x, y, z = lp.IntVar(), lp.IntVar(), lp.IntVar()
lp.objective = 10*x + 6*y + 4*z
lp.add_constraint( x + y + z <= 100 )
lp.add_constraint( 10*x + 4*y + 5*z <= 600 )
lp.add_constraint( 2*x + 2*y + 6*z <= 300 )
lp.add_constraint( x >= 0 )
lp.add_constraint( y >= 0 )
lp.add_constraint( z >= 0 )

maxval = lp.maximize()
print maxval
print x.value, y.value, z.value

Other linear programming libraries include lp_solve, puld-or