Linear program solvers: Lpsolve

In the following articles we will solve the instance of a Minimum cost flow problem described in (1). Node 1 is the source node, nodes 2 and 3 are the transshipment nodes and node 4 is the sink node.

mcf_dimacs_1

As lpsolve can read the DIMACS file format we don’t have to transform a graph structure into a plain linear program. The XLI (eXtensible language interface) does this for us.
A good description of the DIMACS Minimum cost flow problem file format can be found here.
So for solving our MCFP we just have to write down the MCFP in DIMACS file format with a text editor of our choice (I called the file ’simple_MCFP.net‘) and let lpsolve do the dirty work:


c Problem line (nodes, links)
p min 4 5
c
c Node descriptor lines (supply+ or demand-)
n 1 4
n 4 -4
c
c Arc descriptor lines (from, to, minflow, maxflow, cost)
a 1 2 0 4 2
a 1 3 0 2 2
a 2 3 0 2 1
a 2 4 0 3 3
a 3 4 0 5 1

Here is the python code for solving a minimum cost flow problem in DIMACS file format with the python API of lpsolve:

from lpsolve55 import *

# full file path to DIMACS file
path = 'simple_MCFP.net'

# read DIMACS file and create linear program
lp = lpsolve('read_XLI', 'xli_DIMACS', path)

# solve linear program
lpsolve('solve', lp)

# get total optimum
optimum = lpsolve('get_objective', lp)

print optimum #should be 14

When you are working with the python API of lpsolve you’ll always have to call the function lpsolve() and pass the C method you want to access as first argument as string, e.g. lpsolve(’solve‘, lp). So obviously this API is a very thin layer upon the C library underneath.

The usage of the python API of lpsolve is not really pythonic because lpsolve is written in C – but hey: it works!  The complete list of functions can be found here.

2 thoughts on “Solving the Minimum Cost Flow problem (3) – lpsolve”

  1. Hi,

    it’s easy to implement and is truly very very fast. I’ve one question, because our need for speed in solving th mcf-problem is extreme. Is it possible to set an initial solution to the mcf-problem in the dimacs file, so that the solver is perhaps a little bit faster?

    In our mcf-problem we have a non-optimum solution at the time we start lpsolve and hope that lpsolve is faster if it does not have to start from scratch.

    Thanks, sebastian

  2. Hi Sebastian,

    If you need more speed than you should try the python wrapper of MCFSimplex: pyMCFSimplex. I have announced the release in one of my blog posts. This package is much faster than the linear problem solver of lpsolve.
    But in both cases I’m Not aware of giving an Initial solution to the solver (I don’t think you need this if you are using MCFSimplex).

    Johannes

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.