relax4

relax4.rubyforge.org

github.com/jdleesmiller/relax4_ruby

DESCRIPTION

Ruby interface for the RELAX IV code for minimum cost network flow problems, which include transportation problems and assignment problems. In the words of the code's authors:

PURPOSE - THIS ROUTINE IMPLEMENTS THE RELAXATION METHOD
          OF BERTSEKAS AND TSENG (SEE [1], [2]) FOR LINEAR 
          COST ORDINARY NETWORK FLOW PROBLEMS.

[1] BERTSEKAS, D. P., "A UNIFIED FRAMEWORK FOR PRIMAL-DUAL METHODS ..."
    MATHEMATICAL PROGRAMMING, VOL. 32, 1985, PP. 125-145.
[2] BERTSEKAS, D. P., AND TSENG, P., "RELAXATION METHODS FOR 
    MINIMUM COST ..." OPERATIONS RESEARCH, VOL. 26, 1988, PP. 93-114.

   THE RELAXATION METHOD IS ALSO DESCRIBED IN THE BOOKS:

[3] BERTSEKAS, D. P., "LINEAR NETWORK OPTIMIZATION: ALGORITHMS AND CODES"
    MIT PRESS, 1991.
[4] BERTSEKAS, D. P. AND TSITSIKLIS, J. N., "PARALLEL AND DISTRIBUTED 
    COMPUTATION: NUMERICAL METHODS", PRENTICE-HALL, 1989.

THIS CODE WAS WRITTEN BY DIMITRI P. BERTSEKAS AND PAUL TSENG,
WITH A CONTRIBUTION BY JONATHAN ECKSTEIN IN THE PHASE II INITIALIZATION.
THE ROUTINE AUCTION WAS WRITTEN BY DIMITRI P. BERTSEKAS AND IS BASED ON
THE METHOD DESCRIBED IN THE PAPER:

[5] BERTSEKAS, D. P., "AN AUCTION/SEQUENTIAL SHORTEST PATH ALGORITHM 
    FOR THE MINIMUM COST FLOW PROBLEM", LIDS REPORT P-2146, MIT, NOV. 1992.

The original source can be downloaded from:

See also:

SYNOPSIS

require 'rubygems'
require 'relax4'

A general network flow problem:

#
# From Figure 29.3 of Cormen, Leiserson, Rivest and Stein (2001).
# Introduction to Algorithms, 2nd Edition.
#
#      (2)          edges are directed ((1,2), (1,3), ...)
#     / | \         each edge has a cost and a capacity
#    /  |  \        
#  (1)  |  (4)      the aim is to find the flow on each edge such that we 
#    \  |  /        move four units of flow from (1) to (4) at minimum cost
#     \ | /
#      (3)
#
Relax4.solve(
    :demands     => [-4, 0, 0, 4],
    :start_nodes => [ 1, 1, 2, 2, 3],
    :end_nodes   => [ 2, 3, 3, 4, 4],
    :costs       => [ 2, 5, 3, 7, 1],
    :capacities  => [ 5, 2, 1, 2, 4]) #=> [2, 2, 1, 1, 3]

A lower-level interface is also available; see the docs for the Relax4 module.

A transportation problem:

#
# From http://www.me.utexas.edu/~jensen/models/network/net8.html
# A nil cost means that the flow is not allowed.
#
Relax4.solve_transportation_problem(
  :costs =>   [[   3,   1, nil],
               [   4,   2,   4],
               [ nil,   3,   3]],
  :demands =>  [   7,   3,   5],
  :supplies => [   5,   7,   3]) #=> [[2, 3, 0], [5, 0, 2], [0, 0, 3]]

An assignment problem:

#
# From http://www.me.utexas.edu/~jensen/models/network/net9.html
# A nil cost means that the assignment is not allowed.
#
Relax4.solve_assignment_problem(:costs =>
  [[ nil,   8,   6,  12,   1],
   [  15,  12,   7, nil,  10],
   [  10, nil,   5,  14, nil],
   [  12, nil,  12,  16,  15],
   [  18,  17,  14, nil,  13]]) #=> [4, 2, 3, 0, 1]

REQUIREMENTS

Has been tested on:

  • ruby 1.8.7 (2011-06-30 patchlevel 352) [i686-linux] and [x86_64-linux]

  • ruby 1.9.2p290 (2011-07-09 revision 32553) [i686-linux] and [x86_64-linux]

The following packages were required to install with the system ruby on Ubuntu 10.04:

  • ruby, ruby-dev, rubygems

The bindings were generated with f2c (FORTRAN to C converter) and SWIG (www.swig.org), but you don't need either to build the gem.

INSTALL

gem install relax4

DEVELOPMENT

Get the source from github (github.com/jdleesmiller/relax4_ruby) and use bundler to get the development dependencies:

gem install bundler
bundle
rake -T # list development tasks

TODO

  • there are some hard-coded parameters that could be exposed

  • problem state is global (cf. FORTRAN), so can have only one instance at a time

HISTORY

1.2.0 20110905

  • reorganized gem to be consistent with guides.rubygems.org/c-extensions

  • now using gemma 2 for development tasks

  • added major, minor and patch version constants (no other API changes)

  • wrapper regenerated with swig 2.0.4 (was 1.3.38)

1.1.0

  • added wrappers for transportation and assignment problems

  • updated docs

1.0.5

  • fix in previous version didn't quite solve the problem; new fix applied

1.0.4

  • fixed apparent bug in ascnt2_ that caused memory corruption or infinite loop

  • switched to gemma for basic rake tasks

1.0.3

  • now uses RELAX4_UNCAPACITATED by default for uncapacitated problems

  • updated docs

1.0.2

  • added RELAX4_UNCAPACITATED; setting capacities to RELAX4_DEFAULT_LARGE to represent uncapacitated arcs was found to cause overflow for some problems

  • now have only the necessary parts of the standard f2c headers

  • more tests

1.0.1

  • set platform in gemspec to Ruby (not a binary gem)

1.0.0

  • first release

LICENSE

The authors of RELAX IV (D.P. Bertsekas and P. Tseng) released the code with the following user guidelines:

THIS ROUTINE IS IN THE PUBLIC DOMAIN TO BE USED ONLY FOR RESEARCH
PURPOSES.  IT CANNOT BE USED AS PART OF A COMMERCIAL PRODUCT, OR
TO SATISFY IN ANY PART COMMERCIAL DELIVERY REQUIREMENTS TO
GOVERNMENT OR INDUSTRY, WITHOUT PRIOR AGREEMENT WITH THE AUTHORS.
USERS ARE REQUESTED TO ACKNOWLEDGE THE AUTHORSHIP OF THE CODE,
AND THE RELAXATION METHOD.  THEY SHOULD ALSO REGISTER WITH THE
AUTHORS TO RECEIVE UPDATES AND SUBSEQUENT RELEASES.

The main author of the RELAX IV code is:

DIMITRI P. BERTSEKAS
LABORATORY FOR INFORMATION AND DECISION SYSTEMS
MASSACHUSETTS INSTITUTE OF TECHNOLOGY
CAMBRIDGE, MA 02139
(617) 253-7267, DIMITRIB@MIT.EDU

The code for these Ruby bindings is released under the MIT license.

Copyright © 2010 John Lees-Miller

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the 'Software'), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.